RSA Cracked - Not 128
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
RSA problem is NP, but not known to be NP-hard (Score:1)
You may know more about RSA than I do, but isn't the RSA algorithm NP? Or, is just O(x^)?
Yes, they are NP, that is, given two integers P, Q that are claimed to be a factorization of a given number N, you can compute their product P*Q and compare it to N in polynomial time. Remember, NP means ``an answer can be verified in polynomial time''; it does NOT mean `not P' (where P means: a solution can be found in polynomial time). NP is a superset of P.
That said, neither the RSA problem (factor large integers) nor the Diffie-Helman problem (compute discrete log) are proven to be NP-hard (that is, if you can solve them, you can solve any NP problem). Some attempts have been made to make crypto algorithms that are based on NP-hard problems (back pack packing, traveling salesman), but no satisfactory implementation of these is currently known.
RSA is not one of the best (Score:2)
RSA encryption will be one of the best types around, at least mathematically speaking.
This is incorrect. RSA is strictly worse than Diffie-Helman. To elaborate, there are four problems we need to distinguish:
To elaborate: a solution for the DHP would give a solution to the RSAP; thus RSA is on shakier ground than DH. Note that if cracking DH or RSA does not require solving DHP (resp. RSAP), then this is academic. We thus get the diagram:
that is, if you can solve DHP, you can solve all of these, but if you can solve RSAP, you only get RSA cracked. Thus the security of DH (resp. RSA) is based on two assumptions:
Unless you think there is something wrong with DH that allows cracking it without solving DHP, then DH is better than RSA. That said, the reason RSA is so prevalent is b/c it was patented after DH, and thus RSA inc. could make $$$ off it longer than if they used the technically superior DH; however, RSA has been ``good enough''; regardless of whether governments can crack it, $|<r1p+ <1dd1e$ sure can't. But that's all RSA is: good enough.
Re:Ron Rivest Rules (Score:1)
I, for one, am very impressed.
Re:Ron Rivest Rules (Score:1)
Re:Thanks for the laugh... (Score:2)
Re:RSA's status (Score:2)
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
#1 is incorrect, there are a few ways to break RSA, only one of which is to factor large composite numbers (another is this Leo person's method). Assuming effective key management, no method has been found which is significantly easier than the factorization problem (although some are no harder). For more detail, see http://www.rsasecurity.com/rsalabs/faq/3-1-3.html [rsasecurity.com]
#2 is also incorrect. Factorization is probably not NP-Complete, but RSA never depends on it being NP-Complete, merely on it being really hard to solve. Factorization is provably NP, but has not been shown to be NP-Complete. This is potentially a good thing, if #3 ever falls through for the NP-Complete set, the fact that it isn't NP-Complete means that Factorization will probably still be hard.
#3, of course, has not been proven. It also has not been disproven, despite hundreds of mathematicians trying for decades. A good analysis of the issue is at http://ic-www.arc.nasa.gov/ic/projects/bayes-grou
Just because #3 hasn't been proven doesn't mean it's not a useful assumption. People routinely bet their lives on much flimsier ones.
----
Re:We shouldn't use RSA too much. (Score:1)
Re:This is exactly what the NSA wants you to think (Score:1)
That sounds about right - and since single-DES uses a 56-bit key (which provides, I believe, a 55 bit keyspace,) you've really only added one bit onto the key. There's a fairly clever meet-in-the-middle attack on double-encrypted ciphers; I can't remember most of it right now, though -- I believe that while it ends up only taking twice as long as a brute-force attack on single encryption, it consumes an awful lot of memory.
Triple-DES does give you the full 112 bits of your key, since triple-encryption manages to avoid that problem.
- cicadia
Re:breaking RSA (Score:3)
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.
Re:We shouldn't use RSA too much. (Score:1)
Andrew
Re:Sarah Flannery (Score:1)
Re:The best part of the article (Score:1)
[Translation: shouldn't you stick to making sneakers for Nike, instead of worrying about this newfangled math stuff?]
RSA Crack (Score:4)
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 (Score:4)
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 (Score:4)
cryptome.org/flannery-cp.htm [cryptome.org]
Shaun
Multiple Crypto (Score:1)
Re:NSA has already done it (Score:2)
On average, its 10 years ahead of the curve on everything...
Where did that figure come from? Do you know of any concrete examples? (Not sarcasm, I'm really interested)
I know that when DES was being designed, in the early 70's, they were roughly 20 years ahead of the civilian mathematics field. The differential attacks that it had been designed to withstand weren't discovered until 1990.
Makes you wonder what they've been up to since then... :|
- cicadia
Re:RSA's status (Score:2)
By the way--how the hell do you define `really hard' without NP-completeness?
Re:Ramanjun (Score:1)
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.
I certainly hope that, if RSA is ever broken, that that's exactly how it happens. It would be so much more satisfying to see some brilliant stroke of human insight cut through a problem which has been declared "really really hard; maybe impossible" by leading cryptographers than to see it broken by a computer through mechanical processes. I remember being thrilled when hearing that Fermat's Last Theorem had been proven, and then quite disappointed when I then heard that it had taken so much computer assistance that it would likely take years of hand checking to be sure that it really had worked, and that even then, it was so complex that a lay mathematician wouldn't have a hope of understanding it.
That being said, I don't think that Leo de Velez is RSA's Ramanujan (yet) - His description of his method shows that he understands some of the mechanics behind the algorithm, but lacks a feel for the behaviour of numbers at the sizes used in practical public-key crypto.
- cicadia
Re:RSA's status (Score:1)
Not really. It would be catastrophic if factorisation had a low-exponent polynomial solution. If someone could find a n^10 algorithm, and prove that this was a lower bound on the complexity, RSA would be strengthend, not weakened.
Congratulations (Score:5)
CK
---
Re:There is a path to cracking RSA (Score:2)
The reason quantum computers are exciting is not that they do anything which classical ones can't or that they have a really high clock speed or something. It is that in certain cases, they can solve in polynomial time problems which classical machines take exponential time to complete. With classical computers, if someone came up with a machine which could factorise a 400 digit number in 1 hour, it would still take perhaps 2 hours to factorise a 401 digit number, 4 hourse to factorise a 402 digit numbers, 8 hours...etc. So if you used an 800 digit number it would still take a crazy amount of time to factorise it. With quantum computers (if you found a linear time algorithm) if a 400 digit number required 1 hour, an 800 digit number would require 2 hours, making any encryption based on factorising a large number crackable in minutes, hours or days rather than a billion billion billion years or something.
It is hoped that quantum computers will complement classical ones and be useful for specific problems, not that they will run word processors - classical computers do that well enough and are many orders of magnitude easier to program.
And in related news... (Score:2)
I will retract the following statement later today, after it has been forwarded to the scientific community ten times over
Not quite... (Score:2)
For some reason optimisation problems are the most popular examples of NP-complete problems, but they're harder to think about than simple decision problems, because you have to look at them through this layer of abstraction. NP problems don't ask "what's the best you can do", they ask "can this be done?", so for an optimisation problem you have a family of questions "can this be done in 100 miles of travel?", "can this be done in 50 miles?" and so on.
--
So in response to this... (Score:1)
----
Re:There is a path to cracking RSA (Score:1)
And now, in the interest of giving something back, here's some tips for you:
I think these things called "computers" might be big, they seem like more than a fad.
The internet... I think it really might catch on!
Now, use this information wisely.
The best part of the article (Score:5)
The moral of the story is to always obtain peer review (by qualified peers) before publishing your results!
Sorry for calling you a troll... (Score:2)
--
Thanks for the laugh... (Score:4)
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
Re:This is exactly what the NSA wants you to think (Score:2)
How can you prove that the product of the chain is not encoded with fewer bits than any of the steps? (Trivial example: double ROT-13)
Re:factoring large primes. (Score:1)
What billg meant to say was "... factor into prime numbers".
Paul
Ron Rivest Rules (Score:4)
Re:The lesson to learn... (Score:1)
That's been known for a long, long time. We already know how to find prime factors faster than checking them individually. What's hard is finding them fast enough.
Paul
Are you out of your mind? (Score:2)
The whole basis of your argument is that if we use the algorythm too often, we're giving too much incentive to hackers to break it. That's stupid. If the algorythm is sufficiently breakable that we can realistically believe it may be broken anytime soon, we shouldn't use it at all because it's obviously not safe enough.
Also, by only encrypting "a small proportion of our data", you effectively take everything important and hang a neon sign on it saying "This is the valuable stuff that we are afraid you might want to steal!" It's a big pointer to potential hackers to tell them what to look for. Why else do you think sites using SecureID get so many hack attempts? Applying abnormally high security to something (such as encrypting it when nothing else is encrypted) makes it just scream that it's a target.
Re:The lesson to learn... (Score:2)
Given that, it seems a whole lot less "obvious" that it is not possible to find large prime factors in polynomial time--though based on the amount of research that has gone into it, I am inclined to believe it.
Likewise, Quantum Computing algorithms for factoring prime numbers are not perfect. Since QM is inherently statistical, it only has a statistical chance of getting the right answer -- of course, you can check it on a regular computer and try again if it doesn't work, but the point is, Quantum Computing algorithms may have very good runtime for various algorithms, but in general have completely unbounded worst case runtimes.
Re:The lesson to learn... (Score:1)
Re:Cliff Notes (Score:1)
Re:We shouldn't use RSA too much. (Score:1)
I'm not reffering to Urban Existentialist, or Kiss the Blade, or New Lover's Arrival. I'm referring to the social misfits that keep moderating up the posts of these people.
I'd love to shake the hand of the guy who posted the above as +1 insightful. He's the reason I read slashdot.
Re:We shouldn't use RSA too much. (Score:2)
you assume tha RSA is breakable. It probably isnt unless quantum computers become a reality. Before you say something like "everything is breakable" learn some number theory. Understand what people mean when they say that a problem is hard. Given that most encryption schemes rely on factoring large numbers, for the most part, you break RSA, you pretty much have broken encryption. The only serious encryption that I know of that doesnt rely on factoring numbers being hard is a one time pad.
Re:This is exactly what the NSA wants you to think (Score:1)
No, triple encryption has the same problem, which is why it only gives you 112 bits from a 168 bit key. (Though you can use a 168 bit key with 112 bits of entropy - http://khan.postech.ac.kr/crypto/joc/11n3p209.pdf
--
Re:RSA's status (Score:2)
By the way--how the hell do you define `really hard' without NP-completeness?
Personally, I define it as impossible to solve given current mathematical and computational technology in less than a year for less than a hundred thousand dollars. If I was in a field with stricter security requirements, I'd probably up the dollar figure. If I was in a less time-critical field I'd probably up the time. Factorization of a typical RSA key easily falls into my definition of "really hard".
Yes, people put a lot of faith in flimsier assumptions--but that doesn't mean we ought to put blind faith in an assumption.
The Brooklyn Bridge (finished 1883) was built with many assumptions, one of which was "Gravity acts in the way that Isaac Newton described". Not only had this assumption never been proven (just as current gravitational theory has never been proven), a few decades later that assumption was actually disproven. Does that make the bridge any less stable? No.
Most things in life are unprovable. If you only allow yourself provable things, you never leave abstract mathematics.
The heart of security is the management of risk; and without a fair and frank assessment of risk, there is no security.
Which is why RSA is so much more popular than elliptical cryptosystems. Because the risks involved in RSA are better understood, explored and documented. If you implement a security system that involves RSA, you have an easy-to-calculate risk involved in that link of the chain depending on key length. You can be confident that, absent an advance in technology, you fully understand the risks involved in your security system.
Note that "absent an advance in technology" phrase. That is not unique to RSA, but is true with any security system: be it cryptography, digital or even a physical security system. The risk of technological advances obsoleting your security system is always present. If you cannot stomach that, I'd suggest that you keep away from fields that require significant security.
----
Re:RSA's status (Score:2)
2. I define "really hard" as "intractable": ie "yielding to no polynomial-time algorithm" or "outside P" in short. Assuming P != NP, I see no reason to believe that all problems in NP but outside P will be NP-complete.
3. We currently have no means to prove any cryptographic problem intractable. Thus the best we can do is base our cryptosystems on the best-tested assumptions. The RSA problem is certainly one of the best studied problems in cryptography.
--
About Point 2 (Score:2)
--
Looking closely... a patent trap for the future? (Score:1)
The guy who came up with the attack seems to have failed- but Ron R. came up with the interesting observation that the attack converts an RSA problem into finding a discrete log in a finite field (Diffie's public key algorithm, first implemented in GPG before RSA became public domain.)
Now, if a math problem can be converted from a patented algorithm into one in the public domain, which wins? Does the PD algorithm fall under the patent, or does the patent go away?
This wouldn't have been trivial a year ago when RSA was still under patent protection. Even two years ago RSA, Inc. was peddling FUD on Diffie's finite field problem, saying it needed more analysis before being trusted.
Mathematics behind both processes look a lot alike to the untrained (only 18 semester hrs of undergrad math) armchair math/crypto geek.
Er, no. (Score:2)
--
Re:We shouldn't use RSA too much. (Score:1)
I would therefore suggest that we use RSA to encrypt my dog, as evidenced by the influx of fleas onto his own corporeal being. Or better yet, to tie bananas around our necks as to attract more monkeys. Because monkeys are fun.
Re:like kicking a hornet's nest (Score:1)
Re:like kicking a hornet's nest (Score:5)
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.
RSA is cracked, but slashdot refuses to report it. (Score:1)
As it stands, the software requires some small changes but is very close to a working copy. Email me if you want a copy, or talk to this guy [prodigy.net].
please point to the source (Score:1)
Re:like kicking a hornet's nest (Score:1)
Furthermore, "Plan B", as you call it, has been under development for some time. Theoretically, a quantum computer would be able to test many possible factors simultaneously, thus reducing the problem of factoring large numbers to a constant-time (O(1), for you math geeks) problem. However, algorithms for quantum cryptography using phase-shifting of the wavepacket are being perfected by several groups.
Which is all well and good, except that the best quantum computer to date is one bit. That's actually okay, since the current maximum bitsize for a quantum compiler is also one bit. Pretty soon, a quantum computer will be able to show that 4 = 2 * 2.
Re:No, that was NOT harmless gas (Score:1)
Re:We shouldn't use RSA too much. (Score:2)
This is an obvious troll, and repeats the tired old myth that only people with something to hide need to use encryption.
The security of the RSA algorithm is based around factoring of large prime numbers. Unless a faster method of factoring is developed (e.g. quantum computers) RSA (the algorithm) is safe.
The main vulnerabilities with RSA are implementation-specific: short passwords, keystroke recording, etc. That's why an open-source implementation is desirable. I'll give a meatspace analogy. Which would you choose - a lock that you have the blueprints for and hackers worldwide can't crack or a lock a martektroid assures you is secure.
Would you like a challenge text? (Score:2)
Ron Rivest indicated he was happy to generate an RSA challenge for anyone who thought they had a break. Why don't you ask him for a challenge, break it, and then the world will believe you?
Alternatively, piss off and stop spreading FUD.
--
Re:Good lord. (Score:1)
Man I loved that gag. Douglas adams excells at setting things up in one half of the book and then waiting until you're off guard to pull them out for maximum effect.
Re:RSA's status (Score:2)
2) Factors doesn't have to be NP complete. If I have a P time way of solving Factors, that doesn't help me solve 3-SAT without a bidirectional reduction between them (from 3-SAT to Factors should be straight forward, the reverse is thought unlikely to exist). Factors only has not to be in P, which would require NP != P. which brings us to #3
3) ALL key-based encryption is based on the assumption that P!=NP, as ALL such schemes are in NP. Thus, if a solution demonstrating how to solve any one NP-complete problem (any one NP problem will not suffice) in P time is found, all key based encryption has been broken.
However, your first point is well taken.
Ok, now that I've nitpicked on your points, feel free to return the favor.
Re:RSA's status (Score:2)
Factors is one such problem, as are most other encryption schemes, including blowfish and rijndael (sp?).
For all these problems, if NP = P is proven, we're hosed. But it is fine if Factors is proven not to be NP-Complete.
Re:key question (tangent) (Score:1)
Re:We shouldn't use RSA too much. (Score:1)
Re:RSA's status (Score:1)
And since computer speeds are still improving at an exponential rate, you can't guarantee anything will be insoluble in the future unless you can demonstrate supra-exponential running time (which I don't think factorization has).
Granted, having a worse-than-polynomial running time to crack your cipher is nice, but I'll take a cipher which takes N^3,000,000 days to crack (where N is my keysize) over one that takes (1 + 1e-302)^N femptoseconds to crack, even though the former has a polynomial running time.
Re:This is exactly what the NSA wants you to think (Score:1)
No, triple encryption has the same problem, which is why it only gives you 112 bits from a 168 bit key. (Though you can use a 168 bit key with 112 bits of entropy
The general method for triple-encryption of any block cipher is to use two keys, A and B, and to compute the ciphertext as Enc(A,Dec(B,Enc(A,Plaintext))).
With 56-bit DES, this method uses 112 bits of key, and is resistant to the meet-in-the-middle attack used against double-DES
Now, the issue of whether to call this a single 112-bit key (AB) or a 168-bit key (ABA) with only 112 bits of entropy is really a matter of semantics. I prefer the to use the first, and to consider the number of times that a particular bit is reused in an algorithm irrelevant.
Re:The best part of the article (Score:1)
Re:Look for cracks in the implementations (Score:2)
Re:Cliff Notes (Score:1)
There is a path to cracking RSA (Score:2)
However, Quantum Computing is a line of investigation these days that has the potential to break RSA. It's known that factoring can be performed in polynomial time on a quantum machine. Practical implementations are far away, but the problems inherent in this method of computation are being tackled bit by bit. It's conceivable that in a few decades a whole new class of computational devices may exist that make cracking RSA and many other problems trivial. You have been forewarned!
Re:RSA Crack (Score:1)
Re:This is exactly what the NSA wants you to think (Score:1)
Two algorithms can look completely different, and then be almost exactly the same when reduced. The reduction may just not have been discovered yet. And even if the algorithms are completely different, how do you know that the strengths of one are partially(or even completely) eliminated by the weakness in another?
The example I've seen mentioned here (I don't know if it's true or not) is that double DES has exactly the same strength as single DES, but triple DES is stronger. Not an intuitive result.
Re:Congratulations (Score:1)
This has to be a first... doesnt it?
Well you should have checked with slashdot first before posting such speculation, Jeez!
Re:crack RSA = factoring in P (Score:1)
NP-Complete refers to problems for which verifying the solution is in NP.
Travelling Salesman is NP-Complete because given a potential solution it is believed that you still have to check all the others to prove it's optimal.
Factoring is provably not in NP-Complete, because given a potential solution all you have to do is multiply the factors together to check it's correct.
Re:RSA Crack (Score:3)
Re:like kicking a hornet's nest (Score:2)
As for quantum encryption, there are still problems. The MitM factor becomes very serious in quantum key exchange. But if you can get around that, it's possibly provable.
breaking RSA (Score:2)
Re:Hasn't everyone? (Score:1)
Of course, my favorite method of encryption is the ultra-secure, one-way method that gives you optimal compression to boot: piping to
Bingo Foo
---
Re:There is a path to cracking RSA (Score:1)
If it happens, I suspect a crack to RSA will be simple and elegant.
------------------------
Re:Good lord. (Score:1)
Not since I lost all the pages between giraffe and tuberculosis.
Cue trombone and cymbal sting.
Re:RSA Crack (Score:1)
Re:This is exactly what the NSA wants you to think (Score:1)
No. The general method is to use three keys. Using ABA is a (commonly used) special case of that.
Someone's borrowed my copy of Schneier, so I can't give a page reference in that right now, but yhe bottom of page 272 of HAC mentions both two and three key triple encryption (and EEE as well as EDE). See also RSA Labs Crypto FAQ
Now, the issue of whether to call this a single 112-bit key (AB) or a 168-bit key (ABA) with only 112 bits of entropy.
Read the reference I posted. There's more to it than repeating one of the keys.
--
Granted, but... (Score:2)
Factorisation is super-polynomial but sub-exponential. I don't think Moore's Law will be threatening 4096-bit keys for some time to come...
--
Re:Thanks for the laugh... (Score:2)
I think this is a slightly risky viewpoint. We do not yet have a mathematical proof that prime-factorising is hard (and even if it is hard in the asymptotical sense, as N -> infinity, that doesn't mean RSA isn't easily crackable for any particular values of N we might use). Most mathematicians believe that is hard, but nobody can prove it.
Although it would be remarkable for someone to find a counterexample to this viewpoint, it is not unprecedented. People used to believe that "strange attractors", like the Lorenz fractal, could not exist. Frege spent years developing his set theory, only for Russell to show that it was inconsistent.
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. Save the laughter for the many people who still believe they can trisect the angle, square the circle, double the cube etc., in the face of proofs of their impossibility.
crack RSA = factoring in P (Score:2)
Factoring is not believed to be NP-Complete, but it isn't thought to be in P either. It's in the "can't do it in P, but it's easier than other stuff you can't do in P". Breaking RSA isn't the same as breaking something like DES. DES is a strange bundle of a bunch of stuff with little theoretical backing (it just works). RSA is based on really simple number theory. Breaking it would probably be the biggest math story of the decade (this one, that is. last decade had a better one).
Good lord. (Score:2)
Re:like kicking a hornet's nest (Score:2)
Ramanjun (Score:3)
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.
Re:crack RSA = factoring in P (Score:2)
Problems in NP have yes/no answers, and the question can always be cast as "is there a string with this property?" where you can check a candidate string in P time (on the size of the problem). In this sense, the TSP doesn't ask "what's the shortest route?". It asks "is there a route shorter than this?"
NP-complete problems are as hard as any in NP: given any problem in NP, you can re-cast it as an instance of the Travelling Salesman problem (in polynomial time), so if you solve TSP, you effectively solve all of NP, and thus proven that P = NP.
Factoring is neither proven in P nor proven NP-complete.
--
The lesson to learn... (Score:2)
Check your sources people! Unless you can link to it on a reputable site or find it in a reputable (whatever), don't trust it. And for the reputable sites - CHECK IT FIRST!
Ok, end-of-rant. RSA is safe to use and since it is the simplest public-key algorithm I know of, I don't it believe it will be broken (simpler is easier in security). In fact, in order to break RSA, you'd have to find a way to discover prime numbers without having to check them individually - that'd be quite an achievement and a mathematical triumph.
The problem with capped Karma is it only goes down...
Dammit, Jamie! (Score:5)
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 (Score:4)
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.
In Related News... (Score:2)
Stories by credulous journalists everywhere.
Good! (Score:2)
Re:RSA Crack (Score:2)
Re:crack RSA = factoring in P (Score:2)
"Less than exponential time" != "polynomial time". Factoring is slower than polynomial time but faster than exponential time.
"breaking RSA" != "recovering the private key". You're right that recovering the private key allows you to factor N. But it hasn't been proven that being able to recover the plaintext to arbitrary ciphertext given only the public key gives you a way to find the private key, and so in that sense RSA is not provably as hard as factoring. Some other cryptosystems, like Rabin and Blum-Blum-Shub, have this property.
--
RSA's status (Score:3)
- The only way to make a general break of RSA is to factor large composite numbers,
- Factorization of large numbers is an NP-complete problem,
- 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.
Re:This is exactly what the NSA wants you to think (Score:2)
factoring large primes. (Score:4)
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 (Score:4)
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!
Re:RSA's status (Score:2)
"Look at the Brand X security system! It's based on unproven conjectures! But our ACME security system recently had one of our conjectures proven!
(Guy talking really fast) Not all ACME conjectures have been proven. Proven ACME conjecture has not yet been proven. Unproven ACME conjectures are unstated and may be 1+1=3 (which has not been proven)."
Early PGP development (Score:2)
Insofar as the likelihood of breaking RSA, history shows that you're exactly right. While RSA is built on a lot of conjecture, it's survived a lot of mathematical attack. Protocol attacks against RSA have historically been far more effective. Check out the Crypto-Gram of a couple of months back for a quick look at RSA protocol attacks over the years.
(I know Schneier covered at least one RSA protocol attack recently; I think he covered more than just the one. But my memory could be mistaken.)
No, that was NOT harmless gas (Score:5)
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? (Score:3)
Pete Davis
Breaking RSA a DMCA violation? (Score:4)