```Newsgroups: sci.crypt.research
Path: illuminati.io.com!uunet!news.mathworks.com!news.alpha.net!uwm.edu!news.
+     moneng.mei.com!howland.reston.ans.net!ix.netcom.com!netcom.com!mpj
From: suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk)

Subject: Re: A cryptographic pseudorandom number generator
Message-ID:
Sender: mpj@netcom17.netcom.com
Organization: University of South Carolina - Columbia - Computer Science
Date: Mon, 13 Mar 1995 15:24:51 GMT
Approved: crypt-request@cs.aukuni.ac.nz
Lines: 67

beaver@castor.cse.psu.edu (Don Beaver) writes:

>suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk) writes:
>
>>with a 512 bit modulus?  We could run a fast 64-bit block cipher in
>>OFB mode, and occasionally flush the shift register and insert 63 bits
>>from seven iterations of the BBS generator.  (We have lg(512) = 9 bits
>>available from an iteration.)

>Not to quibble, but why are you assuming lg(512) bits are secure?
>
>It would be misleading to use theoretical results to assume this.

If the _Applied Cryptography_ blurb is not in error, then two things:

1) I am wrong.  The BBS generator is:

X_(i+1) = X_(i)**2 MOD N  [where N = pq - two primes
where (p mod 4) = (q mod 4) = 3]

We can use about lg lg(X_(j)) bits of X_(j), not lg lg(N)
of X_(j).  (The LSB's, that is.)

>A proof that O(lg n) bits are secure doesn't help.  It merely says
>that if you design a method to predict bits, it won't work in the
>limit if it's given O(lg n) bits.  This says nothing about what happens
>in initial cases.
>
>For example, I can request that you use  1000 lg n  bits
>(which is O(lg n)) and I'll then predict the sequence trivially
>for n = 512.  Surely, my prediction method will fail when n gets larger,
>but not yet.

2) Where the heck did "Big-Oh" get into this?  I think there's
some confusion here between N = pq and n = ceil(lg(N)).

>And even if a theoretical result stated  lg n  (rather than O(lg n)),
>it still would not apply.  For "small" n, where "small" depends
>on the attack, the BBS generator could fail utterly.  There are
>simple polynomial-time attacks that probably predict BBS very well
>for  n  up to 10000 bits, even when you use only lg n bits for the RNG.
>(They just are fairly long to specify.  But theoretical proof says
>nothing about their size and whether there are "shorter" ones.)
>
>Don

>From what I've read, BBS is secure, both to the left and to the right,
so long as you only use a few (~lg n) bits of each X_(j).  To correct
my mistake, all we need to do is add a few more iterations/hardware
generators to insure that we almost always get 64 usable bits.

Do you know of any actual polynomial-time attacks on BBS?  As I
understand it, these would imply polynomial-time factoring.  Please
post some references, I would be very interested in these.

--PKS

There's neither heaven nor hell -- Save that we grant ourselves.
There's neither fairness nor justice -- Save what we grant each other.
Peter Kwangjun Suk -- suk@cs.scarolina.edu -- Musician, CSCI Graduate Student

```