From: (Don Beaver)
Newsgroups: sci.crypt.research

Subject: Re: A cryptographic pseudorandom number generator
Followup-To: sci.crypt.research
Date: 22 Mar 1995 09:46:13 +1000
Organization: Penn State Comp Sci & Eng
Lines: 109
Approved: (sci.crypt.research co-mod)
Distribution: world
Message-ID: <3knog5$>
NNTP-Posting-Host: (Robert I. Eachus) writes:
> (Don Beaver) writes:
>  > Not to quibble, but why are you assuming lg(512) bits are secure?
>  > It would be misleading to use theoretical results to assume this.
>   The "problem" with Blum, Blum, and Shub is that it is inherently a
>public key system where the sequence can be forced forward.  In an
>application like this factoring N is not necessary to break security,
>all you have to do is find N.
This isn't quite right.  The system can't be forced forward in an
obvious way unless you know the entire residue generated at each
squaring -- as opposed to just a small window onto it.
>  (This is why, just as RSA is used in
>PGP, you only want to use BBS to conceal randomly generated private
>keys.  That way no one can guess a partial text, and read the
>remainder of the message.)
This isn't quite right, either.  It _would_ be true if:
(1) the residues were not output in reverse order; and
(2) the entire residues were used, rather than just a 1-bit or lg2(N)-bit
If you want to use the entire residues (not just lg2(N)-bit windows),
then you certainly don't use
     x, x^2, x^4, x^8, x^16, ...
but rather
     ..., x^16, x^8, x^4, x^2, x.
This provides an *unpredictable* sequence, but not a *pseudorandom* one.
(It is unpredictable because taking square roots is hard without knowing
the factors of N.  It is not pseudorandom because it is easy to tell
that this is not a random sequence, knowing just N itself.)  Anything
hidden by it would later become revealed, once the later portions of
the output are discovered.
You probably don't even want to use it for the purpose you mentioned,
unless you are very sure that N is used solely for a specific pair of
If you use only a small window (1 bit or lg(N) bit) of each residue,
of course, then you don't need to reverse the order.
(All these statements are *asymptotic* statements, i.e. it is invalid
to use them for N of a fixed size, such as, e.g., 512.)