Re: [Fwd: Supposedly RSA has been cracked]

[Ron DuFresne <dufresne () WINTERNET COM>]

Interesting, as a related article gave a tad more info, though, only a
tad, and your reply cut off and real info.  From the related article:

Ron Rivest of RSA has informed De Velez: "In response to my inquiry, which
was: Maybe you could explain how it works on the following example?

n = 55
e = 3
ciphertext = 2


"You (De Velez) said: Using the extended Euclidian algorithm twice with
some empirical formula, you can get a private key of 7 which can decipher
about 80 percent of the codes. Using again the extended Euclidian
algorithm, you can calculate 27, 47 as some of the other private keys that
can decipher the code."

"You may or not be aware that any decryption exponent d that satisfies e *
d = 1 (mod lambda(n)) where lambda(n) = lcm(p-1,q-1) will work perfectly
as an RSA decryption exponent, since every element of the multiplicative
group modulo n (where n = pq) will have order dividing lambda(n).

Note that lambda(n) divides phi(n) always. In the example with n = 55, we
have phi(n) = (p-1)(q-1) = 40 and lambda(n) = 20.

Since 7 is a multiplicative inverse of 3, modulo 20, then 7 is a perfectly
good decoding exponent for 3. It doesn't just decrypt 80% of the values;
it decrypts them all. Since 3*27=81=1 (mod 20) and 3*47=141=1 (mod 20),
the decoding exponents 27 and 47 are also perfect decoders corresponding
to the exponent 3.

Rivest noted that any technique that can find a multiplicative inverse of
e modulo lambda(n) can be used to factor n. "So if your approach finds
such exponents somehow, then you also have a factoring algorithm, not just
an algorithm to break RSA," Rivest said. (Edu H. Lopez)



Now, how much meat is in there is a question.  How much it will stand the
test of time is another.  But, there was nothiong I noted in the reply
from rivest that had any real meat in it, you cut off that part.

Thanks,

Ron DuFresne


On Sun, 4 Feb 2001, David Kennedy CISSP wrote:

> At 09:09 PM 2/2/01 -0500, Jason Brvenik wrote:
>
> > Oops,
>
> >
>
> > http://www.zdnetasia.com/news/dailynews/story/0,2000010021,20178050-1,00.htm
>
> > I'm very skeptical about the claim put forward by this article but I
>
> > wanted to see if anyone on the list might have more information or
>
> > contacts that can confirm or deny.
>
> >
>
>
> <<set recursive netiquette violation = on>
>
>
> On Perry Metzger's crypto list, a lengthy private e-mail was X-posted.
> Here is an excerpt:
>
>
> > > > >
>
> <excerpt>Ron Rivest wrote:
>
>
>
> > Dear Leo --
>
> >
>
> > Thanks for the more detailed explanation of your approach to
> attacking
>
> > RSA given in your emails (copied below).  For the reasons I will
>
> > explain, and as you are perhaps aware, I think your approach is
>
> > unlikely to work in practice against large RSA numbers.  It would be
>
> > very premature or misleading to characterize RSA as "broken" based on
>
> > your work to date.
>
> >
>
>
> </excerpt><<<<<<<<
>
>
>
>
> --
>
> Regards,
>
>
> David Kennedy CISSP
>
> Director of Research Services, TruSecure Corp. http://www.trusecure.com
>
> Protect what you connect.
>
> Look both ways before crossing the Net.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
"Cutting the space budget really restores my faith in humanity.  It
eliminates dreams, goals, and ideals and lets us get straight to the
business of hate, debauchery, and self-annihilation." -- Johnny Hart
        ***testing, only testing, and damn good at it too!***

OK, so you're a Ph.D.  Just don't touch anything.