10
$\begingroup$

If you have a random uniform sequence of bits $A$ generated by a TRNG with good performance of randomness tests (eg Dieharder, NIST, Kolmogorov complexity, chi-square, etc) and perform an encryption (eg AES) with a known deterministic key $B$ so that it results in a new encrypted sequence $C$.

Is the encrypted sequence $C$ generated by a TRNG? Should it have the same good performance in the randomness tests as the unencrypted sequence $A$?

$\endgroup$
  • 7
    $\begingroup$ Note that "good performance of randomness tests" certainly does not imply your generator is cryptographically pseudorandom, let alone "truly" random. $\endgroup$ – fkraiem Oct 16 '15 at 2:33
  • 1
    $\begingroup$ @fkraiem, I suggest the OP could drop "with good performance of randomness tests (... etc)" and the meaning would be unchanged but clearer -- essentially assume an ideal random uniform sequence. $\endgroup$ – Chris H Oct 16 '15 at 9:32
  • $\begingroup$ Does not steganography disprove this assertion? $\endgroup$ – emory Oct 16 '15 at 12:42
  • 1
    $\begingroup$ @emory please can you elaborate? $\endgroup$ – Victor Oct 17 '15 at 3:56
  • $\begingroup$ @VictorP It is a question, not a statement. If a steganography program hides a random sequence of data in a picture of a cat, wouldn't the randomness tests show the output data has less randomness than the input data. My feeling is that steganography is removing entropy, but I am not able to defend that statement mathematically. $\endgroup$ – emory Oct 19 '15 at 0:24
10
$\begingroup$

Yes. If $r\colon\;\Omega\to X$ is a uniformly distributed random variable, and $f\colon\;X\to Y$ is a bijective function (such as, for instance, a symmetric cipher instantiated with some key), then $f(r)\colon\;\Omega\to Y$ is uniformly distributed as well.

The proof is simple: For all $y\in Y$, we have $$\Pr[f(r)=y] = \Pr[r=f^{-1}(y)] \text,$$ and the latter probability is independent of the choice of $y$ since $f$ is a bijection and $r$ is uniformly distributed. Hence $f(r)$ is.

$\endgroup$
  • 2
    $\begingroup$ The randomness after AES encryption may even be better. If your TRNG is not optimal (e.g. due to physical environment effects) its a good idea to post-process it with a hash or symmetric encryption algorithm. $\endgroup$ – user27950 Oct 16 '15 at 3:56
  • 7
    $\begingroup$ In practice AES encryption is not necessarily a bijection, if you have a mode of operation with IV and padding, but this applies e.g. when you just use the block cipher on a block. $\endgroup$ – otus Oct 16 '15 at 5:18
8
$\begingroup$

If your encryption algorithm is possible to decrypt and if the algorithm always produces the same number of bits of output as it has bits of input then clearly by the pigeon-hole principle every input sequence must map to exactly one output sequence. Therefore if the input is perfectly random the output will also be perfectly random.

This isn't always the case with practical implementations of encryption algorithms. Many produce outputs larger than their inputs due to padding, parameter specifications etc.

Also most "true random number generators" are not perfectly random. Encrypting the output will hide flaws in the underlying random number generator from statistical tests but that doesn't mean those flaws no longer exist, only that they can't be found without decrypting the output.

Always remember that statistical tests can only look for particular types of pattern, they cannot prove that a sequence is truely random.

$\endgroup$
  • 2
    $\begingroup$ Minor nitpick: I don't think it's the pigeon-hole principle you mean to quote here. $\endgroup$ – D.W. Oct 16 '15 at 6:11
  • 1
    $\begingroup$ @D.W., it follows from the pigeon-hole principle (no function from a set to a set of smaller cardinality is injective) that in injective function between sets of the same cardinality is surjective and hence a bijection. $\endgroup$ – Carsten S Oct 16 '15 at 9:59

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.