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 Cox writes:
>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