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: e6e585962a49d26f69fecf0a1f0554422929a272901d7a484b79f6867b359508
Message ID: <9406171906.AA02710@snark.imsi.com>
Reply To: <199406171835.NAA09573@zoom.bga.com>
UTC Datetime: 1994-06-17 19:06:24 UTC
Raw Date: Fri, 17 Jun 94 12:06:24 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Fri, 17 Jun 94 12:06:24 PDT
To: Jim choate <ravage@bga.com>
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406171835.NAA09573@zoom.bga.com>
Message-ID: <9406171906.AA02710@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain

Jim choate says:
> I am *NOT* talking about factoring anything.

Who cares what you think you are talking about? You haven't shown much
common sense thus far.

If I have an algorithm that will take any arbitrary RSA key and
produce the private key by a mechanism such as the one you propose,
you are (almost certainly) proposing an algorithm that will factor
arbitrary numbers that are a product of two primes. I can't prove that
right now -- not even sure that I can prove it right now. However,
there are lots of people who's intuitions likely agree with mine. Most
people believe RSA is probably equivalent to factoring.

> I don't care what the original key is, simply am I above it
> or below it.

I'm afraid that given such a function, I can derive the original key
within log[base2](n) operations.