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

Re:breaking RSA

the key to breaking RSA encryption, as most people know, is factoring large numbers quickly. According to the current state of mathematics this is not possible except by trial and error, brute force.

Actually, factoring is a problem which is believed to be hard, but there is no proof that it is. There's no formal lower bound on the amount of computation required to break RSA. But it's a problem that many mathematicians have worked on without cracking it. That's the main reason for confidence in RSA. Nevertheless, the possibility of a new discovery cannot be excluded. (Nor can you exclude the possibility that it has been made already. You have to assume that the world's major cryptographic agencies have smart people working hard, but quietly, on the problem).

It's also worth remembering that there are lots of problems for which the worst case is exponentially hard, but the average case is far easier. Linear programming and the travelling salesman problem are examples. If you could break a high percentage of keys, that would be of practical use, even if some were harder than others. Note that there have been weak RSA implementations where the keys were ill-chosen from some subset of primes.

The first attempt at a public-key cryptosystem was based on the knapsack algorithm, a problem that hadn't received much attention. Once people starting looking hard at that problem, a way was found to solve it rapidly. Since then, cryptographers have been very cautious about new asymmetric-key algorithms.

RSA Crack

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

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

Here you go.

cryptome.org/flannery-cp.htm [cryptome.org]

Shaun

Congratulations

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

The best part of the 'cleaned-up edit [seedmuse.com] 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...

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

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

>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.

Re:RSA Crack

I think we are doomed to see one of these remarks every time there is a story that has something to do with some kind of math problem/puzzle. Oh well.

Ramanjun

Though seems unlikely that an unknown person might find the counterexample, it's a bad idea to dismiss it as "impossible" or "funny", because one day, in some mathematical field or another, it'll happen.

It has happened before, and could happen again. Higher mathematics is a fascinating field - every now and then you end up with interesting character. Erdos was a crazy vagabond but he is one the most prolific and insightful mathematicians of modern times. Ramajun (sp?) was an Indian college dropout who made made significant contributions in analysis with little formal training in math. He wasn't big on proof, and some of his 'thereoms' were just stated as truths, and not rigorously justified (or dejustified) until after his death.

RSA's biggest fear just might be some modern day Ramajun. The big 'R' should be understandably apprehensive whenever some guy off the street emails and says he's broken RSA - because it just could be true.

Dammit, Jamie!

"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 [openone.com]

like kicking a hornet's nest

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.

RSA's status

I'm very hesitant to declare RSA to be "one of the best types around". RSA is built on several conjectures, none of which have been proven, namely:

1. The only way to make a general break of RSA is to factor large composite numbers,
2. Factorization of large numbers is an NP-complete problem,
3. P != NP

Remember: none of these have been proven. At all. There is absolutely no evidence of the correctness of any of the three conjectures, except that historically we haven't been able to do it--and that's exceptionally weak evidence.

Compare this against something like elliptical-curve cryptography. ECC is also built on many conjectures, but one of them (the Taniyama-Shimura Conjecture) has recently been formally proven (by Wiles, et al). Mathematicians are still reviewing the multiple Taniyama-Shimura proofs to make sure that (a) they are correct singly, and (b) taken together they prove the entirety of Taniyama-Shimura--but last I heard, things were looking promising.

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.

Absolutely not. We've got some extremely good ways of generating large random primes. The odds of a collision in the keyspace is probably somewhere on the order of 10^(-150), a really really small chance.

If you want to see this principle in action, connect to a PGP keyserver and type in your key ID (a cryptographic hash of your key). If you get any other keys coming up with your same key ID, then I'll agree that we've got a problem. Otherwise, don't worry about it. :)

factoring large primes.

According to Bill Gates, "the obvious mathematical breakthrough would be to factor large prime numbers" [google.com]

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

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

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.

Hasn't everyone?

Hasn't everyone cracked RSA? I did a long time ago. Read about it in my out-of-print book Undocumented Cryptographic Algorithm Cracks.

Pete Davis

Breaking RSA a DMCA violation?

Just asking. :)