Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Suppose I have a list of randomly generated uint_8's, uniform over the whole range of uint_8. I write them into a file as raw bytes, no encoding.

Then I reopen the file and interpret the file as packed uint_16's (by pairing up adjacent bytes).

  1. Is my reinterpreted stream of uint_16's a uniformly random distribution in the whole range of uint_16?

  2. Now I reinterpret the bytes as packed int_32's. Is my reinterpreted stream a uniformly random distribution of int_32's, in the whole range of int_32?

Note: uintN_t is the type of N-bit unsigned integers, i.e. integers in the range $[0,2^N-1]$. intN_t is the corresponding signed type, i.e. integers in the range $[-2^{N-1},2^{N-1}-1]$.

share|improve this question
2  
A small complement: if int32_t isn't the usual 2's complement with no trap value, then the signed values may not be uniformly distributed. For example, with sign-magnitude and no trap value, +0 == -0 is overrepresented. –  Gilles Sep 11 '13 at 15:58
3  
You need not only "uniformly distributed", but also "independent". –  Paŭlo Ebermann Sep 11 '13 at 17:46

1 Answer 1

up vote 5 down vote accepted

Well, it rather depends on what you mean by "uniformly distributed". If you mean that, over all possible lists, each byte position was from a uniform distribution, that doesn't actually tell you that.

Here's the problem: all "uniformly distributed" in this case means is that, in a sufficiently large sample, each value occurs approximately equally often (in the uint_8 case, about 1/256 of the time).

However, it says nothing about correlations, that is, which values tend to immediately follow other values. It is easy to design a 'random string' that is perfectly uniform, however the adjacent bytes are strongly biased; this means that, when you combine adjacent bytes, each uint_16 will not be equally represented. For example, consider a string where, after a byte value $X$, the next position is also the value $X$ with probability 1/2+1/512, and a value $Y \neq X$ with probability 1/512. This sequence is equidistributed; however if you combine uint_8 values, the resulting sequence is strongly biased.

However, if by "uniformly distributed", you mean that the $N$-byte sequence as a whole was selected uniformly from all possible $256^N$ possible sequences, then yes, uniformness is preserved by combining adjacent elements.

Now, getting down to practice: if the list was generated by a cryptographically secure random number generator (CSRNG), then we can assume that combining adjacent elements is harmless. That's because we assume that the output of a CSRNG cannot be efficiently distinguished from random by any method; if the attacker could distinguish it by combining adjacent bytes, that would mean that we really didn't have a CSRNG in the first place.

On the other hand, if the list was generated by a statistical random number generator (that is, a generator that was designed to generate output that "looks" random, that is, passes some standard statistical tests), then it's a tad trickier. Real life generators can have problems when you combine outputs at the "wrong" size; however it is unlikely that one used in practice would have a problem with combining only 2 or 4 elements. So, in this case, you're probably safe (although you might want to check with the generator to be sure)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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