Newsgroups: sci.crypt.research Path: illuminati.io.com!uunet!netnews.jhuapl.edu!aplcenmp!darwin.sura.net! + convex!cs.utexas.edu!howland.reston.ans.net!newsserver.jvnc.net! + nntpserver.pppl.gov!princeton!phoenix.princeton.edu!dawagner From: beaver@castor.cse.psu.edu (Don Beaver) Subject: Re: A cryptographic pseudorandom number generator Message-ID: <1995Mar26.174936.26230@Princeton.EDU> Originator: news@hedgehog.Princeton.EDU Sender: dawagner@princeton.edu (sci.crypt.research co-moderator) Nntp-Posting-Host: phoenix.princeton.edu Organization: Penn State Computer Science Date: Sun, 26 Mar 1995 17:49:36 GMT Approved: crypt-request@cs.aukuni.ac.nz Lines: 58 Benjamin Coxwrites: >beaver@castor.cse.psu.edu (Don Beaver) writes: >> In fact, it is theoretically trivial to factor N when N is no bigger >> than 2^1000000000000000. > >Would you care to explain this assertion? Here's a polynomial-time algorithm that manages to factor N when N is no bigger than 2^1000000000000000: 1. If N>2^1000000000000000, then output 0. // Yes, this is wrong! 2. Otherwise, for i = 1..2^1000000000000000, check whether i divides N. If so, append i to the output, set N = N/i, and continue. Theoretical Analysis -------------------- Correctness: Always correct for N <= 2^1000000000000000. Always wrong for larger N. (But we don't care.) Running Time: Size of input, n Running Time, t(n) ---------------- ------------------ 1 t(1) <= 2^1000000000000000 * 10^45 2 t(2) <= 2^1000000000000000 * 10^45 ... 1000000000000000 t(1000000000000000) <= 2^1000000000000000 * 10^45 1000000000000001 t(1000000000000001) = 1 1000000000000002 t(1000000000000002) = 1 1000000000000003 t(1000000000000003) = 1 ... any n>1000000000000000 t(n) = 1. Since t(n) = O(1), the algorithm is polynomial-time. Is complexity theory helpful in this case? You bet it isn't! That was the point that I was trying to make earlier: the complexity-theoretic results can't be used to say that lg(512)-bit windows of a BBS generator are secure. Sure, the theoretical proofs might lend some support to a *superstitious* belief. And we might *hope* that it's safe to form such beliefs, even when they are logically unfounded. But we might just be unlucky. We might have overlooked that the theoretical proof said, "For N larger than 2^2^2^2^1000...", or that it is difficult to find out precisely how big N must be for an *eventually-true* property to start holding. And cryptography is exactly the place that such unluck and oversight can lead to holes... Don