4
$\begingroup$

I've got the following theoretical problem which puzzles me a bit:

I can obtain a string of n bytes (as octets, one byte = one octet = eight bits) of random data. I need to preserve the randomness while reducing the base from 256 to x where x is below 256 (and not 0, 1, 2, 4, 8, 16, 32, 64 or 128).

As I want to preserve the randomness, I don't want to cut-off (waste) any information from this string until I've obtained the number of chunks I need. This is for reason of randomness which can be a limited resource on the computer.

I had the idea to do this for base64 which is simple because I can just create 4 numbers out of a single byte (by shifting bits for example: encode64()). But how to do with a base like 254 for example? I can not cut off at bit-boundaries here, can I?

Do I probably need to create a number large enough out of base 2 based bits that can contain both bases? (This is one of the ideas I have so far).

Would be great to get some feedback, I normally paint pictures with such problems, however, just discovered this website here yesterday and I normally use Stackoverflow so I thought I give it a try :D

If you're interested in some non-theoretical background to my question, see "What is the meaning of the term “simple string” for the SALT string in Unix crypt using SHA-256 and SHA-512?", you might get an idea why I don't want to loose any information bits from the random source.

$\endgroup$
  • $\begingroup$ I'm not sure I understood the question but why don't you normalize your string? Something like you receive $m$ then you return $\lfloor m\cdot \frac{x}{256}\rfloor$. Anyway you will loose some informations when you convert to a smaller basis. $\endgroup$ – wece Jul 24 '13 at 13:59
  • $\begingroup$ I don't want to loose information otherwise this is a simple floating-point/floor operation which is not what I'm looking for. $\endgroup$ – hakre Jul 24 '13 at 14:25
  • $\begingroup$ If your random variable can take 256 values and you want to encode it with less than 8 bits then you will loose informations no matter what you do. $\endgroup$ – wece Jul 24 '13 at 14:48
  • $\begingroup$ @wece: I know about base64 implementation using 256 value sources, just making four out of one. No information is lost. And that's with less thatn 8 bits as well, so what you write sounds pretty short. $\endgroup$ – hakre Jul 24 '13 at 15:32
  • 1
    $\begingroup$ Do you? I was pretty sure that information theory stated that you can't. But may be I'm wrong and may be I didn't get what you mean by loss of information (or by bits may be). $\endgroup$ – wece Jul 24 '13 at 16:25
6
$\begingroup$

You can use "arithmetic decoding". Interpret your random data as a random bit stream which encodes a random number between $0$ and $1$. Then write this number in base $B$.

A much simpler method is "rejection sampling". Suppose for example that $128 < B < 256$. Given a random byte $x$, if $0 \leq x < B$ then output $x$, otherwise reject. If $x$ is close to $256$ then this is pretty efficient. (To get higher efficiency, try the same trick with some power of $B$, i.e. output several digits at once.)

$\endgroup$
  • $\begingroup$ In my understanding / mental model, this rejecting and then sampling the final data destroys the randomness. Technically this works for the number (and I would have considered this the most straight forward and simplest way to do the job) but I think as well it destroys/weakens/taints the randomness. Or am I just wrong about that point? $\endgroup$ – hakre Jul 24 '13 at 18:59
  • $\begingroup$ If the input bits are perfectly random then rejection sampling produces perfectly random outputs. The only loss is that some randomness is "wasted". $\endgroup$ – Yuval Filmus Jul 24 '13 at 23:05
  • $\begingroup$ Okay, I just had the same thought after waking up in the morning today. Otherwise it would not have been random anyhow. The only question left is: is a random source that is deemed cryptographically secure such a perfectly random source? $\endgroup$ – hakre Jul 25 '13 at 7:32
  • $\begingroup$ As my last question is most certainly not answerable, just accepting this as it does at this point answer the question - And that is in both parts. I also had the idea of taking the bit-lane however it does not work for 254 because I need 8 bits for 254 as well, so the second part does it here. Thanks for the nice answer. With the efficiency, you mean this because of data-handling (like doing buffered reads), right? $\endgroup$ – hakre Jul 25 '13 at 7:46
  • 1
    $\begingroup$ No, you can always do arithmetic decoding. Check out the Wikipedia article on arithmetic encoding. The basic idea is that your stream of bits encodes a number in $[0,1)$. If the number $Z$ falls in $[x/254,(x+1)/254)$, then you decode $x$ and continue with $254(Z-x/254)$. $\endgroup$ – Yuval Filmus Jul 26 '13 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.