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

Subject: Re: A cryptographic pseudorandom number generator
Message-ID: <1995Mar20.055735.1953@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: (sci.crypt.research co-moderator)
Organization: University of South Carolina - Columbia - Computer Science
Date: Mon, 20 Mar 1995 05:57:35 GMT
Lines: 70 (Don Beaver) writes:

> (Peter Kwangjun Suk) writes:
>> (Don Beaver) writes:

>[much deleted]

>        ============ Polytime Attacks on BBS ==============
>>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.
>Here is a polynomial-time attack on BBS [using  lg n  windows]
>that works fine for n up to 1000000 bits.
>0. If n>1000000, then flip a random bit and return it as the prediction
>   for the next bit.  Else do 1-6:
>1. Factor n.

This is polynomial?

>2. List all cycles  x,x^2,x^4,...  modulo n.

This is polynomial?  You're going to have to provide a proof for this one.
For general graphs, listing cycles is exponential worst-case.  Of course,
you're only going to get one cycle here, unless you are dropping all but
the lg lg n LSB's.

>3. Request a sequence of n^1000000 BBS bits.
>4. Divide that sequence into  lg n  sized chunks.
>5. Match those chunks up to one of the cycles we found in step 2.
>6. Predict the n^1000000+1'st  bit by using the next number in the cycle.

Please re-read the revious posts.  You are indeed getting N = pq and n
= ceil(lg(N)) mixed up.

>(Okay, I overstepped human knowledge in one place, but it's not where
>you might think.  This is *indeed* a polynomial-time algorithm.

Oh, sure.  How about the following 'algorithms' for n<1000000:

1. Factor all numbers up to 2**1000001 - 1.  Place your results in a
   convenient lookup table somewhere...

2. Generate all BBS generator sequences for N up to 2**1000001 - 1.
   Place your results in a handy dandy lookup table...

>using only a 1-bit window.  This is an easy algorithm to state, but for
>all I know it could be as hard as FLT to prove or disprove the existence
>of multiple subsequences matching a given pattern.

So, in other words, your 'algorithm' has no proof of correctness.

>None of the cited references are talking about this, however.  I've tried
>to pose a simple candidate solution for the sake of illustration.)

I would guess that you've succeeded to an extent you didn't originally

Moderation on this group seems to have produced a false positive in
this case.  For my part, I'll admit that I'm just a precocious student
who chimed in with a suggestion.  (In retrospect, it wasn't such a
great suggestion in any case.)

Clearly, further discussion on this subject would just be a waste
of bandwidth.