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: > >>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.) > >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