Math Advance Suggest RSA Encryption Could Fall Within 5 Years 282
holy_calamity writes "The two encryption systems used to secure the most important connections and digital files could become useless within years, reports MIT Technology Review, due to progress towards solving the discrete logarithm problem. Both RSA and Diffie-Hellman encryption rely on there being no efficient algorithm for that problem, but French math professor Antoine Joux has published two papers in the last six months that suggest one could soon be found. Security researchers that noticed Joux's work recommend companies large and small begin planning to move to elliptic curve cryptography, something the NSA has said is best practice for years. Unfortunately, key patents for implementing elliptic curve cryptography are controlled by BlackBerry."
Elliptical Curve (Score:2, Informative)
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
Re:RSA = out of date (Score:5, Informative)
You need upvotes, but I'm out of modpoints.
You are very correct. Take for instance OpenVPN. It uses RSA to exchange an random AES session key. RSA and AES/DES/3DES have different uses, and replacing RSA with AES is simply not possible.
Re: Elliptical curves (Score:4, Informative)
Without a statement as to whether the NSA has been involved in elliptic curve stuff (though I will point out that they have nearly as much motivation to make things hard for, say, the USSR/China [depending on era] to crack as they do to make things easy for them to crack), did you read your link? It isn't really talking about elliptic curve crypto at all.
It's describing a potential flaw in a random-number generator whose algorithm is based around elliptic curve crypto. Even if every worry presented by the article is true, that means absolutely nothing about whether elliptic curve is secure against the NSA.
(Actually it almost suggests that it is, because if EC was breakable then the NSA wouldn't have as much motivation to get a known key into the RNG standard.)
Re:RSA = out of date (Score:5, Informative)
Wow, that is so wrong.
RSA is an asymmetric (aka publick key) cipher - because it requires two keys - one to encrypt, one to decrypt. AES, DES, 3DES are symmetric ciphers because you use the same key to encrypt and decrypt.
RSA and EC (elliptic curve) encryption is useful if you want to send data to someone without the hassles of secretly sharing the key ahead of time - e.g., I can encrypt a message using the public key and only the private key can decrypt it. Or I can use my private key to encrypt a message, and the public key can be used to decrypt it (the latter is often used to sign stuff, except the message is typically a hash instead of the original message).
The reason you use AES, DES, 3DES is because public key encryption is hideously slow. In the case of RSA, you're exponentiating one horrendously large number with other horrendously large numbers. (If your message is long, that horrendously large number Is big).
That's why what every public key encryption thing does is it encrypts the message with a fast symmetric cipher like AES, then encrypts the key (much shorter) with RSA or EC. If I want to send you a document, I encrypt it with AES, then use your public key to encrypt the AES key I used.
It's also why signing uses a hash - it's easier to encrypt the hash than the message. And verification just means recomputing the hash, and then decrypting the encrypted hash with the public key, producing the original hash to which can be compared to the just computed one.
The breakthrough in math would be a way to factor a large number quickly - which is what RSA relies on for security - it's easy to multiply two big numbers, but it's very time consuming to factor it.
read the paper (Score:2, Informative)
http://arxiv.org/abs/1306.4244
Re:What patents? (Score:5, Informative)
You can't patent math.
As TFS states, it's the implementation that is patented. Not sure which ones belong to blackberry, but google patents has a number of related patents based on a quick cursory search. [google.com]
Re:OpenSSL? (Score:2, Informative)
They claim patents on various ECDSA/ECDH implementations. There really isn't more to say, we here at slashdot know how evil patents are. :)
To avoid the patent issues its best to implement as specified in: http://tools.ietf.org/html/rfc6090
Abstract
This note describes the fundamental algorithms of Elliptic Curve
Cryptography (ECC) as they were defined in some seminal references
from 1994 and earlier. These descriptions may be useful for
implementing the fundamental algorithms without using any of the
specialized methods that were developed in following years. Only
elliptic curves defined over fields of characteristic greater than
three are in scope; these curves are those used in Suite B.
Re:RSA = out of date (Score:1, Informative)
Your first sentence sounds weird to me, and it isn't supported by your second. AES can't be a suitable replacement for RSA because AES is a secret-key system and RSA is a public-key one.
Sigh. We're discussing an encryption algorithm that is aging and was designed to run under limited computational resources... and now that resources have increased many-fold since the original, it is no longer secure. I then compared it to other encryption schemes that are less resource-constrained which have been coming into wider use. I said nothing about key exchange systems or anything else... I was making a general comment about encryption schemes; Your confusion is because you are drawing your own conclusions, rather than staying on point: Which is that every encryption algorithm, regardless of type or usage-scenario, has a shelf life.
Re:RSA is outdated, but... (Score:3, Informative)
What exactly, does proving P = NP have to do with the price of tea in China? We knew when RSA was created that advances in computation power would eventually make it feasible for us to decrypt its contents. We even know what that boundary is.. and we're coming up on it now.
No encryption algorithm is immune to the fact that the faster you can run an algorithm, the sooner you'll get a result. That's all encryption is. I don't need to be a math major to figure out that if I have a car that can go 200 MPH it'll get there twice as fast as a car that can only do 100 MPH.
Re:RSA = out of date (Score:5, Informative)
You still can't replace an outdated public-key encryption key system with a symmetric system. Because, in real life, usage scenarios and key exchange systems actually matter - in fact, they are the most crucial aspect of the whole thing, otherwise we'd use true random one-time pads and be safe from any attack with any level of computing power forever.
Re:RSA = out of date (Score:5, Informative)
I didn't say that you said that AES could replace RSA: I said that your AES/DES analogy didn't support your statement that RSA is or should be deprecated. That may sound like I'm nitpicking here, but I'm really not: it's pretty fundamental to my point. And the reason is this:
This absolutely need not be true. RSA for instance is based in part around a hardness assumption: that given a very large number n which is the product of p and q, it is far harder to find p and q from n then it is to find n from p and q. Assume for the sake of argument that this is the only hardness assumption RSA depends on. (If the summary isn't misleading it apparently also depends on the hardness of discrete log, but I don't know how.)
If the hardness assumption holds, then RSA as such will never be insecure. Why? Suppose you say "here is a computer capable of factoring a number n with b bits." I'll say "OK, fine; I'll use 100*b bits (or something)"; because multiplying is so much easier than factoring, your computer will still be able to carry out that task but it won't be able to crack my key.
In other words, if the hardness assumption holds, RSA doesn't have a specific difficulty: it can scale with computational power. That's why you see people using 2048-bit keys now instead of 512-bit keys a couple of decades ago.
The only things that the age of the algorithm has to say about the security of it is (1) if the difficulty cannot scale with computational power (true of DES, not true of RSA) and (2) being out longer gives people more time to find flaws in its assumptions.
But here's the thing: #2 isn't necessarily bad or speak against the algorithm. It is conceivable that the assumptions just fundamentally hold. If they do, being out longer will not impact the security at all. If anything, being out longer with no one discovering anything should give a higher assurance that an algorithm is secure than a newer one would.
I don't think I've ever heard a blanket statement about RSA being insecure -- only things like certain key sizes or certain implementations or PRNGs being insecure. (Wikipedia also lists a couple of side-channel and plain-text attacks, but those are also arguably quality-of-implementation issues, and similar attacks exist for EC systems.) The intro to the Wikipedia article says nothing about RSA being insecure. "Deprecated" and "discouraged" both fail to appear on the page.
The strongest statement against RSA I've heard is just that EC is better.
Except that the DES vs AES case is not even close to being the same case, as Adam Van Ymeren said [slashdot.org] in response to you, and then I elaborated on elsewhere [slashdot.org] and above.
The reason it's not even close is that DES does not scale with computational power, because it has a fixed key size.
Re:RSA is outdated, but... (Score:3, Informative)
You don't know that for certain; it is conceivable (if seemingly unlikely) that the easiest proof and the first found could be non-constructive.
(Remember, to prove that a problem is in P you not only have to come up with a P algorithm for it but then you have to prove that the algorithm is actually in P. It could be that any algorithm for a (currently-considered) NP-complete problem is complex with a staggeringly complicated proof that it's in P at all.)
This is a bit of a nit, but factoring isn't known to be NP-complete; from what I can tell, it's actually widely believed to be in an intermediate class between P and NP. (No P algorithm is known, as you note, but there is a sub-exponential algorithm for it, which violates a widely-held belief that NP-complete problems are necessarily exponential.)
Re:We need to keep this secret (Score:5, Informative)
You mean like SSL is broken and nobody talks about it?
First there was BEAST in 2011, which was fixed. But the situation in 2013 is not better!
https://www.globalsign.com/blog/is-ssl-broken.html [globalsign.com] (and links therein, especially the last two)
https://www.imperialviolet.org/2013/02/04/luckythirteen.html [imperialviolet.org]
http://blog.cryptographyengineering.com/2013/02/attack-of-week-tls-timing-oracles.html [cryptograp...eering.com]
List of all attacks: http://armoredbarista.blogspot.de/2013/01/a-brief-chronology-of-ssltls-attacks.html [blogspot.de]
Re:Key patents controlled by Blackberry (Score:4, Informative)
I blame little-endian on a sort of backwards compatibility.
Little-endian simplifies CPU circuits that perform multi-word operations. Its really that simple. End of discussion.
Re:RSA = out of date (Score:5, Informative)
The RSA encryption is
c = m^e (mod n), where m is message, c is ciphertext, e is public exponent, and n is p*q
Decryption is
m = c^d (mod n) where d is the private exponent.
The process of computing d given m,n and c is exactly the discrete logarithm problem. Given n and e, which are public, you can pick an arbitrary m and generate a corresponding c.