94061701.HTM (original) (raw)
Path: illuminati.io.com!news.tamu.edu!cs.utexas.edu!howland.reston.ans.net!europ a.eng.gtefsd.com!MathWorks.Com!blanket.mitre.org!linus.mitre.org!linus!mbunix!ea chus From: eachus@spectre.mitre.org (Robert I. Eachus) Newsgroups: sci.crypt,alt.security,sci.math
Subject: Re: Random/Pseudo Random Number Generator Date: 17 Jun 94 10:29:35 Organization: The Mitre Corp., Bedford, MA. Lines: 42 Message-ID: eachus.94jun17102935@spectre.mitre.org References: 2tjgf9$6b3@ccu2.auckland.ac.nz vladimir.94jun15181548@prosper.prosper.eng.sun.com NNTP-Posting-Host: spectre.mitre.org In-reply-to: vladimir@prosper.Eng.Sun.COM's message of 16 Jun 1994 01:15:47 GMT Xref: illuminati.io.com sci.crypt:28111 alt.security:17162 sci.math:72356
In article vladimir.94jun15181548@prosper.prosper.eng.sun.com vladimir@prosper .Eng.Sun.COM (Vladimir G. Ivanovic) writes:
Both articles are ESSENTIAL reading for anyone interested in random number generation, and this includes naive users. The conclusion of both articles is that horrible random (sic) number generators are used by people who don't know better, while very good ones take less than 20 lines of Pascal! Amoung the horrid generators are some that come with certain systems or are presented in textbooks!
Very true, and I second the recommendation. But neither generator belongs anywhere near a cryptographic application. For cryptography, you want a cryptographically secure RNG that is at least as secure as the cryptographic application you are using it to key.
AFAIK the only algorithmic RNG that can be considered secure and has reasonable performance is Blum, Blum, and Shub. You could probably build a reasonable RNG out of RSA or Diffe-Helmann but I don't know of one. Various generators based on DES or digest algorithms are either too slow, known to be breakable, or on shaky theoretical ground.
Just so I don't start a flame war... The main property you want in a crypto RNG is that, if someone has a part of the output sequence, he can't generate the next bits (or the preceding bits) in the sequence from it. (You have to take it from a cryptographers point of view. Assume he knows the algorithm--but not the key--and has a known plaintext for part of the message. Can he read more? How much of a crib does he need?) So using a digest algorithm to digest the previous output doesn't work unless you digest ALL of the previous output. (Hmmmm... For some digest algorithms, digesting the previous output AND the hidden key might work. With others, that is asking for trouble.) With RSA, the problem is both speed, and the fact that both keys must be hidden for security, etc.
--
Robert I. Eachuswith Standard_Disclaimer; use Standard_Disclaimer; function Message (Text: in Clever_Ideas) return Better_Ideas is... /vladimir.94jun15181548@prosper.prosper.eng.sun.com/vladimir.94jun15181548@prosper.prosper.eng.sun.com/eachus.94jun17102935@spectre.mitre.org