Newsgroups: sci.crypt.research
From: (Peter Kwangjun Suk)

Subject: Re: A cryptographic pseudorandom number generator
Organization: University of South Carolina - Columbia - Computer Science
Date: Mon, 13 Mar 1995 15:24:51 GMT
Lines: 67 (Don Beaver) writes:
> (Peter Kwangjun Suk) writes:
>>How about using the secure Blum-Blum-Shub quadratic residue generator
>>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.)
>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.
       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 -- -- Musician, CSCI Graduate Student