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.

I understand the use of pseudo-random number generators. I am not getting mixed up between these and "real" random number generators.

However, I don't understand for what a real random number generator is used. If it is not deterministic, how can it be used in an algorithm?

share|improve this question
    
You need a real random number generators to seed the pseudo-random number generator. Additionally, most true random number generators require post-processing of the random output, which is often done using pseudo-random generators. –  j.p. Sep 20 '11 at 12:01
    
@jug Yup, entropy sources may even have a particular bias to bits valued 0 or 1. Normally you need at least a whitening technique to get something looking like a random number. Feeding that as a seed into a PRNG is certainly helping to get the right quality. Be careful not to confuse a source of entropy with a secure random number generator. –  Maarten Bodewes - owlstead Mar 20 '12 at 23:58

3 Answers 3

up vote 11 down vote accepted

For some types of algorithms (or protocols) we only need non-guessable (by the attacker) bits/numbers, not reproducible non-guessable ones (like from a deterministic PRNG).

In this cases, "real" random numbers are in theory (i.e. from an information-theoretic point of view, not a cryptographic one) better, since they can't be guessed (or even influenced) by an attacker, even if she could break our PRNG.

Some cases that I can now think of, where we don't need deterministic random numbers:

  • key generation (both symmetric and asymmetric)
  • initialization vectors for block cipher modes of operation (these are usually sent with the message, so the same plaintext will not result in recognizable ciphertext for the next message)
  • random padding in asymmetric encryption (for example OAEP)
  • salts for password storage (these are stored with the hash)
  • challenges in zero knowledge proofs (sent to the partner)
  • random values used in digital signatures (the k in DSA)
  • one time pads (OTP) (Here, for the security proof, we actually need "real" random numbers.)
  • chaffing and winnowing

In practice, pseudo-random bits are cheaper and just as secure for real-world attackers (e.g. with resources limited by our earth mass and universe lifetime), as long as the PRNG is not broken and has enough entropy input to start with.

(If the attacker can control the seemingly random input to the "true random" generator, this would be even worse than a good PRNG.)

Often for these uses we use a combination of a cryptographically secure (deterministic) PRNG and an entropy pool, which gets filled (and re-filled) by random bits gathered by the OS. This would be a non-deterministic PRNG.

share|improve this answer
    
So basically the use for a REAL random number generator is for creating random bits, to reduce entropy, because humans cannot think of data that is truly random –  liamzebedee Sep 20 '11 at 5:43

Many of the uses of a True RNG fall into the general category of generation, without persistent storage, of a value that is different with high probability from any value determined otherwise.

A value that is different with high probability from any value determined otherwise is very useful in cryptographic protocols. For example, under classic CBC encryption with multiple messages enciphered with the same key, an IV needs to be distinct from a previous IV (which is necessary to conceal a possible repeat of the plaintext), and distinct from the XOR of the first block of plaintext with any value that has or will ever enter the input of the block cipher (which is necessary to ensure confidentiality of that first block of plaintext under the assumption that all other plaintext is known).

"Without persistent storage" requirement rules out a Pseudo RNG, and greatly simplify things: in the case of PRNG, persistent storage needs to be made confidential and/or integrity-protected, which is plain impossible on a regular PC under the basic "maid boots USB stick" security threat. Sometime there is just no persistent storage (boot from CD-ROM), or it is a bit slow.

Another reason to use a True RNG is protection of the implementation of a cryptographic algorithm from side-channel attacks, a process often called "masking". For example, protection against DPA of the crypto-engines used in Smart Cards uses random data for that purpose. Using a Pseudo RNG here would create a chicken-and-egg problem (since secure PRNGs use cryptographic algorithms); while this might be solvable, it is simply easier and much faster to use a TRNG.

share|improve this answer

That's the whole point. With a pseudo-random number generator, one is able to (theoretically) repeat the same sequence of numbers that appear to have been chosen at random (one just needs to know the seed), while with a true random number generator they can not (one needs to know all bits of output).

This is useful for generating private keys of symmetric and asymmetric cryptosystems. By using a true random number generator, the cryptanalyst is not able to guess the private key as easily using a brute force attack. (Of course, if the seed and state of the PRNG is large enough, there is practically no way to do it, too.) This is why it pays to re-seed your (pseudo) random number generator every time you generate a private key.

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.