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: 
References: <2tjgf9$6b3@ccu2.auckland.ac.nz>
        
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@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. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...