RSA Cracked - Not

fintler was the first of many to tell us about the ZDNetAsia and Philippine newspaper stories that proclaim that RSA encryption has been "cracked." This might make an entertaining movie plot but it isn't true. I bet cryptographers get hot tips like this from well-meaning amateurs all the time, but most of them don't get this much press. Here's a cleaned-up edit of what's been bouncing around your inboxes all day (read parts [F] and [I]), and for a briefer commentary by the "R" in RSA, read on.

Hi Jamie --

Thanks for checking with me.

A fellow by the name of Leo de Velez from the Phillipines had thought he had broken RSA, and a reporter colleague wrote up this story and published it. This is probably what you have heard about.

Mr. Velez also wrote to me with his ideas. Unfortunately for him, his approach is actually much *slower* than the naive approach to factoring by trial division by 2, 3, 4, .... His approach doesn't improve on any known techniques, and doesn't constitute a "break" of RSA at all.

If you write to Mr. Velez (leo at teammail dot com) he will confirm...

Thanks again for checking...

Feel free to quote me...

Cheers,
Ron Rivest

Comments

Congratulations

[CyberKnet]

A slashdot staffer (actually) checked the story, and found it wasnt true.. Then posted the results! This has to be a first... doesnt it?

CK

---

The best part of the article

[Nonesuch]

The best part of the 'cleaned-up edit is the encouragement Ron Rivest (The 'R' in RSA) gives to the budding cryptographer.

The moral of the story is to always obtain peer review (by qualified peers) before publishing your results!

Re:like kicking a hornet's nest

[norton_I]

>Nothing is unbreakable.

This is just Not True. Though no encryption agorithm other than a one time pad has been proven unbreakable, the foundations of computer science are based on the ability to calculate (for some problems) with 100% certainty that "you have to do operation o at least f(n) times to solve a this problem", and that certain problems (ie, the halting problem) cannot be solved by computers. Even quantum computing doesn't get around this, it just allows many parallel computations to take place at once.

I don't think that any wide spread encryption algorithm falls into either the "unsolvable" or "known scale super-polynomically", and I don't expect to see any of the former (that would make it kind of hard to decrypt), but super-polynomic encryption algorithms are certainly possible. That kind of algorithm, while crackable, can be made arbitrairly hard to crack, at much lower cost to the encryptor (assuming the actual alg. runs as a polynomial of the key size).

Quantum Encryption (which really isn't an encryption algorithm, but a protocol for securely exchanging one time pads) looks like it is provably secure. It is based on the principle that it is impossible to duplicate a 2-state system exactly.

Dammit, Jamie!

[OlympicSponsor]

"Here's a cleaned-up edit of what's been bouncing around your inboxes all day..."

Turn off your javascript! I don't want you reading what's bouncing around MY inbox!
--
MailOne

No, that was NOT harmless gas

[Ratteau]

I achieved cold fusion in my bathtub this morning.

You better double-check your results and to make sure that gas emission was indeed helium.