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$
5
  • 7
    $\begingroup$ Note that "good performance of randomness tests" certainly does not imply your generator is cryptographically pseudorandom, let alone "truly" random. $\endgroup$
    – fkraiem
    Commented Oct 16, 2015 at 2:33
  • 2
    $\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
    Commented Oct 16, 2015 at 9:32
  • $\begingroup$ Does not steganography disprove this assertion? $\endgroup$
    – emory
    Commented Oct 16, 2015 at 12:42
  • 1
    $\begingroup$ @emory please can you elaborate? $\endgroup$
    – Victor
    Commented Oct 17, 2015 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
    Commented Oct 19, 2015 at 0:24

2 Answers 2

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
  • 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
    Commented Oct 16, 2015 at 3:56
  • 8
    $\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
    Commented Oct 16, 2015 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
  • 2
    $\begingroup$ Minor nitpick: I don't think it's the pigeon-hole principle you mean to quote here. $\endgroup$
    – D.W.
    Commented Oct 16, 2015 at 6:11
  • 2
    $\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
    Commented Oct 16, 2015 at 9:59

Your Answer

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

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