Slashdot Mirror
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
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 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.
I, for one, am very impressed.
strategerie.
he==Jamie
strategerie.
-- RTFM:Slackware::Beer:Saturday
rjh writes:
.
p /NP/ijcai91/paper/IJCAI91-paper.html.
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
#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.
----
----
Open mind, insert foot.
why bother cracking an ssl session when the tried-and-true method of hacking into poorly-protected sites is available?
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
Living better through chemicals
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.
I thought part of the power of encryption (and RSA in general) was that it's wide spread use would lead to stronger security. I.E. if everyone uses it for everything, then why the hell bother decrypting anything since it could be nothing more than a slashdot post. This was explained to me as the "Fax machine" principle. Encryption is only valuable if enough people use it.
Andrew
Check out http://www.cayley-purser.ie/ tries... Link Here
[Translation: shouldn't you stick to making sneakers for Nike, instead of worrying about this newfangled math stuff?]
Humpty Dumpty was pushed.
I've cracked RSA. Unfortunately, the details of my algorithm are slightly too large to fit into this here Comment box.
-P. Fermat
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!
If it ain't broke, it doesn't have enough features yet.
Here you go.
cryptome.org/flannery-cp.htm
Shaun
Thanks to the War on Drugs, it's easier to buy meth than it is to buy cold medicine!
Of course this isn't so good for real time comms. And the more layers you add, the less easily you're able to get at your data. (unless you're only using one passphrase for eveything which can then be cracked...)
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
Living better through chemicals
By the way--how the hell do you define `really hard' without NP-completeness?
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
Living better through chemicals
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.
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
---
Video meliora proboque deteriora sequor - Ovidius
Coming up with a quantum algorithm is a pretty weird process. The algorithm doesn't actually come up with a single solution, but a random one governed by a probability distribution. The clever thing is that different possible paths through the algorithm can interfere constructively and destructively with each other, so in effect the final probability distribution is a result of the combined effects of all possible computational paths. The tricky part is to come up with a system which takes advantage of this parallelism and interfere in order to make the correct outcome by far the most likely. This makes coming up with a successful quantum algorithm a completely different, and much harder, process than programming in, say, C.
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.
I achieved cold fusion in my bathtub this morning.
I will retract the following statement later today, after it has been forwarded to the scientific community ten times over
He who joyfully marches in rank and file has already earned my contempt. - "Big Al" Einstein
The TSP problem is "is there a path within this threshold?". it's in NP because there's an obvious poly-time algorithm for determining whether a particular path is no longer than the threshold.
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.
--
Xenu loves you!
----
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.
Upon seeing the box was too small, Schrodinger's Elephant breathed a sigh of relief.
The moral of the story is to always obtain peer review (by qualified peers) before publishing your results!
I do not deploy Linux. Ever.
I've become wary of people who deliberately post misapprehensions because they think that helpfulness is laughable; I got a bit paranoid there. Glad to know I was wrong.
--
Xenu loves you!
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
But doing that naively is dangerous.
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)
What billg meant to say was "... factor into prime numbers".
Paul
Lasciate ogne speranza, voi ch'intrate
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...
"My mother never saw the irony in calling me a son-of-a-bitch." - Jack Nicholson
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
Lasciate ogne speranza, voi ch'intrate
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.
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.
While it's difficult to justify blind faith in a newspaper in a foreign country, one does put at least a little bit of faith in ZDNet. From the movie Sneakers, "You won't know who to trust..."
How long till Katz starts writing a Greek Tragedy about this?
"My mother never saw the irony in calling me a son-of-a-bitch." - Jack Nicholson
The most horrible thing about slashdot is that there's no mechanism to discover who the real trolls are.
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.
Slashdot is jumping the shark. I'm just driving the boat.
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.
> Triple-DES does give you the full 112 bits of your key, since triple-encryption manages to avoid that problem.
)
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
--
rant
rjh asks:
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.
----
----
Open mind, insert foot.
1. Yes, factorisation is the most effective attack on RSA known by far. Well, there's other stuff like low exponent attacks or chosen-ciphertext attacks which you can avoid with good practice, but factoring is the best approach given only the public key and one ciphertext.
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.
--
Xenu loves you!
If the NP-complete problems are in P, all NP problems are in P, including factoring: that's what P=NP means.
--
Xenu loves you!
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.
-Ouija- poke 53280,11:poke 53281,12
RSA is built on the assumption that the RSA problem is hard. This would imply point 3, and it would imply that factoring is hard, but RSA might still be strong even if both of your points 1 and 2 were false. In fact I don't think factoring is believed to be NP-complete, but it is believed to be outside P.
--
Xenu loves you!
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.
News for turds, shit that splatters
Plan B...in case of strike use robots to replace teachers.(From the Simpsons.)
"pr0n": An anagram of "porn," possibly indicating the use of pornography. - www.microsoft.com
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.
I've submitted a story 3 times about RSA encryption being cracked. It has been cracked using a Feed Forward Neural Network, and any RSA encrypted message up to 1024 characters can be broken using the software within 2 weeks. There is no limit to the keysize the software will handle, but currently it is optimized for 1024 bits. I have a copy of the software which was at one time hosted on my webserver and available to the general public for analysis.
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.
Ace
can someone please point to his source ? while there are some I trust none as so far have reveiwed this can someone point to his source so I may review it and make my mind up myself ! kind regards john jones
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.
Touche. Actually, that would be warm fusion, and I have achieved that in my bathtub for years now. :)
He who joyfully marches in rank and file has already earned my contempt. - "Big Al" Einstein
In 2 words, you're wrong.
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.
Life is a psychology experiment gone awry.
If this is true, you can easily prove it.
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.
--
Xenu loves you!
Dirk Gently's Detective Agency.
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.
As far as I can tell, 2 is inaccurate and 3 is not specific to RSA.
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.
#146 bascially beat me to the punch, but I'd like to reiterate the fact that there is a whole slew of problems that are not in NP (and not in P) but are unlikely to be NP-complete.
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.
English phrases tend to have about 1.1 bits of entropy per letter; see, for instance, Refining the Estimated Entropy of Engligh by Shannon Game Simulation. So guessing an English phrase (for instance, someone's password) tends to be easy.
ssl can be easily circumvented by using dnsspoof and sslmitm in the dsniff utility collection.
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.
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.
Living better through chemicals
No no no no. That's a "GEEK" tragedy.
7 November 2006: The day Americans realized corruption and incompetence weren't addressing 11 September 2001
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!
Define "similar"
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.
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.
I didn't pay for my operating system either
Are you making the distinction between deterministic and non-deterministic functions? Just asking.
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.
Returned Peace Corps IT Volunteer
the key to breaking RSA encryption, as most people know, is factoring large numbers quickly. according to the current state of mathimatics this is not possible except by trial and error, brute force. However if there was a way to factor numbers without the need for mathimatics, this method of encryption could be rendered useless. I have an idea for using physical means to break down large numbers into their prime number componants (factoring). If anybody is interesting in reading about my machine (which will never be build because i lack the skill, drive, and malice towards society) feel free to write me and i'll post it somewhere.
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
---
taken! (by Davidleeroth) Thanks Bingo Foo!
Not since I lost all the pages between giraffe and tuberculosis.
Cue trombone and cymbal sting.
Special Relativity: The person in the other queue thinks yours is moving faster.
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.
--
rant
What you say is true, but it's mathematically much easier to explore the boundary between poly-time and super-poly-time than it is to work with the real-world constraints you describe. In practice, anything with a super-polynomial difficulty can be made too hard for your attacker with an appropriate keysize; people are less likely to be confident of that with poly-time problems.
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...
--
Xenu loves you!
Depends on if you ever want to be able to decrypt...
Bingo Foo
---
taken! (by Davidleeroth) Thanks Bingo Foo!
If someone were to crack RSA, that is, find a method to find one key from the other in less than exponential time, it would automatically follow that they had a method to factor numbers in polynomial time. It's not just that if you can factor numbers, you can solve RSA. If you have the public and the private key, you can recover the factors of N, which almost everyone thinks is hard.
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).
I take it that "subtle" and "innuendo" aren't in your dictionary?
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.
Its fast and instant.
Both? Get right out of town.
Cunning linguists
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...
SIG: HUP
It's the sound of a 1000 script kiddies emailing Leo de Velez asking him how to hack RSA...
Must be nice to have your email address slashdotted... NOT!
"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
Non-meta-modded "Overrated" mods are killing Slashdot
(Hey Ryan! Here's your proof!)
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.
Ben Schumin :-)
A simple method of trisecting any angle has been developed by an amateur mathematician working in Los Angeles, following quickly on his patent for a perpetual motion machine.
Stories by credulous journalists everywhere.
Floating face-down in a river of regret...and thoughts of you...
I for one am very pleased to hear that the Republic of South Africa hasn't actually been cracked. They really have enough problems down there as it is.
I love going down to the elementary school, watching all the kids jump and shout, but they dont know I'm using blanks.
Hahaha! That link to the guy's page looks like 90% of Geocities pages! Black background and big bright cyan lettering with MSpaint doodled images! Hahaha? This guy knows the secret to one of the most vexing questions in computer science, along with studying "Computer Virus Theory?"
LMAO! HAHAHA!
120 characters isn't enough to explain it.
Theoretically, a OTP isn't an encryption.
Try out fish, the friendly interactive shell.
- 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.
My understanding of "triple DES" is this: You encrypt a plaintext file with some key (say "A"), then you run the decrypt function with some other key (say "B") and then recrypt the results with the original key ("A") When you go to decrypt it, Do the opposite steps (Decrypt A -> encrypt B -> Decrypt A), and that gives you the strength of 112bit key (IIRC) Also, I think that encrypting DES with two different keys gives you the strength of a 57 bit key
Doh!
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;
}
No, Thursday's out. How about never - is never good for you?
What about SSL? A cracker with enough computing power to regularly break encrypted SSL transactions would be able to retrieve all sorts of financial information about individuals: passwords, credit cards, SSN, etc. The best solution is to encrypt EVERYTHING, and get joy from the satisfaction that some hacker just spend 20 weeks cracking an email to your mother.
Rivest mentions that the Sarah Flannery "new encryption discovered by Irish teenager" never panned out.
Can anybody provide a link to more details?
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!
... is kind of interesting. If you look at very early versions of PGP, an algorithm of Phil Z's own design called Bass-o-Matic was used. Turns out that Bass-o-Matic wasn't a particularly good algo, but they learned from the mistake and from there on only used peer-reviewed algos.
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.)
they've already done it...you think the NSA hasnt already beaten the rest of the world to it? On average, its 10 years ahead of the curve on everything...so, why couldn't they have already done it?
"I am never less alone than when alone" --Scipio Africanus
There are already KeyID collisions
x &s earch=faiad
See DEADBEEF:
http://wwwkeys.pgp.net:11371/pks/lookup?op=inde
Link.
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.
The ivory tower has never had to reach so h
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
Just asking. :)
"Dogs and cats, living together...it's mass hysteria!"
...in his very first message to Rivest, he says that he has tried it with some small success on "small values of N". Well... so? With small enough values of N, breaking it becomes easy anyway. The trick is to find something that works against *large* values of N.
I must say, though, it is really neat to read eloquent, well written explanations of things by people who are obviously *much* more intelligent than me. If I ever run into Ron near a bar, I think I'll buy him a beer, just to listen to him explain complex mathematical concepts.
-- I'll be more enthusiastic about thinking outside the box when there's evidence of thinking going on inside it.