cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-06-17 - Re: Prime magnitude and keys…a ?

Header Data

From: “Perry E. Metzger” <perry@imsi.com>
To: Jim choate <ravage@bga.com>
Message Hash: 66259da30cf500c285f9a59803ee34118bbfc2b96f3309ca6dd3912311c82c84
Message ID: <9406171808.AA02606@snark.imsi.com>
Reply To: <199406171531.KAA01459@zoom.bga.com>
UTC Datetime: 1994-06-17 18:08:21 UTC
Raw Date: Fri, 17 Jun 94 11:08:21 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Fri, 17 Jun 94 11:08:21 PDT
To: Jim choate <ravage@bga.com>
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406171531.KAA01459@zoom.bga.com>
Message-ID: <9406171808.AA02606@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



Jim choate says:
> > I hope not.  If such a thing existed (if I understand your description
> > correctly) RSA could be cracked by a binary search of keyspace.  The
> > search would be O(log(n)), meaning it would be directly linear with
> > the number of bits in the key.
> > 
> Exactly.
> 
> If you (or anyone else comes across anything that even looks remotely 
> interesting would appreciate knowing about it).

I could believe some sort of amazing mathematical breakthrough that
produced a factoring algorithm that was polynomial in N. The notion
that one will show up thats not merely polynomial but actually
logarithmic in N is, I would say, in the "beyond pipe dream" state. I
might believe something like that showing up someday -- stranger
things have happened -- but I have an incredible amount of trouble
believing that one exists now and has merely been overlooked by people
smart enough to find an amazing result and too stupid to know what
their result implied.

Perry

Thread