Path: illuminati.io.com!uunet!comp.vuw.ac.nz!waikato!auckland.ac.nz!news From: eachus@spectre.mitre.org (Robert I. Eachus) Newsgroups: sci.crypt.research Subject: Re: A cryptographic pseudorandom number generator Date: 19 Mar 1995 03:11:42 GMT Organization: The Mitre Corp., Bedford, MA. Lines: 35 Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator) Approved: crypt-submission@cs.aukuni.ac.nz Message-ID: <3kg7de$8st@net.auckland.ac.nz> References: <3jdkuc$k6h@lyra.csx.cam.ac.uk> <3jl8lu$pdv@net.auckland.ac.nz> + <3jpiuj$c7j@net.auckland.ac.nz> Reply-To: eachus@spectre.mitre.org (Robert I. Eachus) NNTP-Posting-Host: cs26.cs.auckland.ac.nz X-Newsreader: NN version 6.5.0 #3 (NOV) In article <3jpiuj$c7j@net.auckland.ac.nz> beaver@castor.cse.psu.edu (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. Huh? The original Blum, Blum and Shub paper proved that at least one secure bit could be generated each iteration. The lg2(N) lower bound on the amount of provably secure randomness came later. (Techically, on the number of bits you can use and still have predicting the previous bits take non-polynomial time.) Even so, it is a lower bound, and the proof can be easily extended if you are willing to accept a polynomial limit on the proven difficulty. 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 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.) -- Robert I. Eachus with Standard_Disclaimer; use Standard_Disclaimer; function Message (Text: in Clever_Ideas) return Better_Ideas is...