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

RSA Crack

[Alan Livingston]

I've cracked RSA. Unfortunately, the details of my algorithm are slightly too large to fit into this here Comment box.

-P. Fermat

Look for cracks in the implementations

[sid_vicious]

The place to look for cracks is less in the theory and more in the implementations.

I was reading "Crypto", and I remember them mentioning that an older version of PGP was using a pretty weak random number generator, making it easy to guess what the supposedly random keys were.

Maybe there'll be a shortcut somebody figures out for factoring large numbers quickly into their constituent primes.. -shrug-.. more likely, somebody will find some kind of buffer overflow or cruddy random number generator, or hashed passwords in one particular implemenation of RSA..

Disclaimer: I am not a mathematician! No need to mentally bully me if I screwed up a detail!

:)

Re:Sarah Flannery

[ShaunC]

Here you go.

cryptome.org/flannery-cp.htm

Shaun

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!

Thanks for the laugh...

[jellisky]

I really needed something as funny as this to brighten my day.

Seriously, though, I don't recall all the specifics, but I do believe that, unless some brilliant advances in number theory or computational power happen soon, RSA encryption will be one of the best types around, at least mathematically speaking.
The thing we have to worry about most currently with RSA is whether or not we're all using the same keys over and over again. That's more of a threat than someone "breaking" RSA.

-Jellisky

Ron Rivest Rules

[Lizard_King]

I'm pretty impressed by how Ron handled this situation. I could understand someone in his position getting a little perturbed when a 'story' like this is leaked to the media. Instead, he put in the time and the effort to teach Leo the falicies of his algorithm. I got the feeling when reading the email conversations that Ron *truly* wants to challenge people to get out there and try to crack RSA...

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

like kicking a hornet's nest

[Ben Schumin]

People really seemed to get quite upset about the possibility of someone cracking RSA. I can imagine people were probably quite scared. I think this highlights a problem in our security infrastructure.

Right now, there are so many systems that are 100% reliant on encryption to provide their security. What's going to happen to our security infrastructure once someone *does* find a way to break these systems?

Don't we need some kind of "Plan B?" Whether it comes from a mathematical breakthrough on factoring, or quantum computing, these methods will eventually be broken. Nothing is unbreakable.

We're just lucky that this time someone was just a bit confused.

factoring large primes.

[Pinball Wizard]

According to Bill Gates, "the obvious mathematical breakthrough would be to factor large prime numbers"

I would like to announce the solution to this difficult scientific problem as well as to establish prior art against any future patent holders. The following code is now in the public domain, feel free to add it to your security product.

Here is my algorithm for factoring prime numbers.

double FactorPrime(double PrimeNum)
{
cout << "The factors of prime number " << PrimeNum << " are 1 and << PrimeNum << ".";
return PrimeNum;
}

Cliff Notes

[funkman]

Leo: I cracked RSA!
Ron: How about some details.
Leo: Here are some. Blah, blah...
Ron: How about some details.
Leo: Here is an example. Blah, blah...
Ron: Silly rabbit, trix are for kids. You've proved to yourself that this is a "hard problem". Everyone else in this field already knows this. But good try and keep up the good work.
Leo: I think you are wrong and my method is faster.
Half of Slashdot Crowd: What an idiot!
Other Half of Slashdot Crowd: I think he's onto something!
Troll: Look at my goatse.cx link hidden as an informative link!

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.

Breaking RSA a DMCA violation?

[wynlyndd]

Just asking. :)