[RC5] RSA decryption

Peter Cordes peter at llama.nslug.ns.ca
Sat Mar 3 18:27:21 EST 2001

On Sat, Mar 03, 2001 at 11:47:55AM +0000, Arne 'Timwi' Heizmann wrote:
> If this person had really found a way of cracking RSA, and hence to factor
> large integers, and hence had solved the P=NP problem, then I think we
> don't need to rely on these proprietary newsflash websites to hear about
> it. The whole story is therefore made up.

 IIRC, factoring is not NP-Complete, so a fast factoring algorithm wouldn't
prove P == NP.

 Anyway, the story is not "made up".  The story is that a guy in the
Phillipines did some math hacking, and thought he had an algorithm to
decrypt RSA.  I'm pretty sure he honestly thought he had done it, and that
he wasn't trying to attract publicity or something.  (If that were the case,
he wouldn't have bothered to do as much math work as he did.  IIRC, he had
transformed the RSA decryption problem into a discrete-logarithm problem, as
well as some other work.  Also, he emailed Rivest about it before he went
public with his work.  I don't know why he didn't wait for Rivest to finish
explaining his mistake to him before he posted it, but I would be excited
too if I thought I had broken RSA :)

 The world needs people like that, who hack on widely used crypto systems
trying to find holes, and publish when they think they have something. These
are the white-hat cryptographers.  They are the reason that open algorithms
are a Good Thing.  If people didn't even try to break RSA, we wouldn't be
saying that it's pretty secure since nobody's managed to break it since it
was invented.  We'd be saying "let's assume it's secure", or "we'll let the
NSA worry about that, and have them tell us about it (if they feel like
it)!" If there are problems with a cryptosystem, it's a Good Thing if the
white hats find them before the black hats do, so people know to stop
trusting tools that use them.

 Don't try to make this guy look bad.  Unless you've never made a mistake
when doing math, I don't think you should throw stones.

> In addition, this has nothing to do with RC5.

 It's encryption; close enough :)  If the guy had actually broken RSA, it
would certainly be worth talking about, since we'd all be screwed until we
converted everything over to Diffie-Hellman based crypto.  As it stands now,
there's no point in moving away from RSA, since it entered the public domain
in September of last year when the patent expired (Yay!!).

#define X(x,y) x##y
Peter Cordes ;  e-mail: X(peter at llama.nslug. , ns.ca)

"The gods confound the man who first found out how to distinguish the hours!
 Confound him, too, who in this place set up a sundial, to cut and hack
 my day so wretchedly into small pieces!" -- Plautus, 200 BCE
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list