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.

Improve this question
$\endgroup$
6
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 16:25

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
8
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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