6
$\begingroup$

Cryptographically secure random number generators seem to have similar properties to symmetric encryption:

  • initial seed is permuted to produce a random numbers (key and ciphertext)
  • given the seed, they produce a random number that cannot be linked back to the initial seed (diffusion)
  • changing a single value in the seed results in multiple changes in the random number (confusion)

Is there a formal relationship between symmetric encryption and SRNGs? I.e. is one a sub-set of the other?

$\endgroup$
6
$\begingroup$

Yes (loosely) and no (depending on your definition of a CSRNG).

A random number generator (restricting ourselves to Cryptographically Secure Random Number Generators) is actually a class of algorithms that produce a sequence of random numbers/bits - i.e. any sequence of numbers that is generated where the next part of the sequence cannot be predicted even with knowledge of the entire sequence to that point (with any non-negligible probability after a feasible amount of computation) can be a CSRNG, but a CSRNG can be constructed from cryptographic primitives in many different ways.

Symmetric encryption algorithms are generally either:

  • Stream ciphers, which are formally modeled as a Pseudo Random Generator or PRG. Technically these are usually a keystream produced by a PRG combined, e.g. by XOR, with the plaintext.
  • Block ciphers, which are formally modeled as a Pseudo Random Permutation or PRP.

Also in the general area of symmetric cryptography are Pseudo Random Functions or PRFs, which are often used as message authentication codes.

CSRNGs can be (and are) constructed from:

  • PRGs - a PRG is already a PRNG by definition.
  • PRPs - e.g. CTR_DRBG from NIST SP 800-90A
  • PRFs - e.g. HMAC_DRBG from NIST SP 800-90A. This also includes PRPs since a PRP is a pair of PRFs and you can just use the forward direction of the PRP.
  • (and also) hash functions - e.g. HASH_DRBG from NIST SP 800-90A

In practice a deployed CSRNG also involves gathering of entropy from the environment (otherwise it would use a static or predictable seed value, which would break the CSRNG contract) and other defensive measures to prevent the reverse-engineering of the internal state of the RNG.

Ignoring the entropy/seeding/defensive measures, if you consider a PRG to be equivalent to a CSRNG, then you can show a formal relationship to other symmetric cryptographic primitives since a PRG can be trivially constructed from any PRF (simply by using the PRF to encrypt an incrementing counter value).

As an interesting aside, PRGs, PRFs and PRPs can all be converted into each other using formal (although not necessarily efficient) constructions.

$\endgroup$

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.