Pseudo-Randomness in Cryptographic Applications

Randomness is a key ingredient for cryptography. Random bits are necessary not only for generating cryptographic keys, but are also often an integral part of steps of cryptographic algorithms. In practice, the random bits will be generated by a pseudo random number generation process. When this is done, the security of the scheme of course depends in a crucial way on the quality of the random bits produced by the generator. Thus, an evaluation of the overall security of a cryptographic algorithm should consider and take into account the choice of the pseudorandom generator. We started a combined study of pseudo-random number generators and cryptographic applications. The intent is to illustrate the extreme care with which one should choose a pseudo random number generator to use within a particular cryptographic algorithm. Specifically, in [BGM97] a paper by Mihir Bellare from UCSD and CIS members Shafi Goldwasser and Daniele Micciancio, they consider a concrete algorithm, the Digital Signature Standard, and a concrete pseudo random number generator, the linear congruential generator (or truncated linear congruential pseudo random generators) and show that if a LCG or truncated LCG is used to produce the pseudo random choices called for in DSS, then DSS becomes completely breakable.