Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Math Advance Suggest RSA Encryption Could Fall Within 5 Years

Soulskill posted about a year ago | from the which-will-be-about-the-time-encryption-becomes-useless-anyway dept.

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

cancel ×

282 comments

We need to keep this secret (4, Funny)

BenSchuarmer (922752) | about a year ago | (#44491131)

otherwise hackers will use it to mess up the internets.

Re:We need to keep this secret (0)

Anonymous Coward | about a year ago | (#44491513)

https://www.youtube.com/watch?v=F5bAa6gFvLs

Ah what does it matter... (1, Insightful)

Anonymous Coward | about a year ago | (#44491135)

...the NSA will have a backdoor into that epileptic curve whatnot too.

Re:Ah what does it matter... (0, Troll)

Bill, Shooter of Bul (629286) | about a year ago | (#44491341)

I care more about Hackers gaining access to my bank account than the NSA. NSA does lots of messed up stuff, but it hasn't tried moving money out of my account yet.

Re:Ah what does it matter... (4, Insightful)

Anonymous Coward | about a year ago | (#44491421)

Yeah. They have taxes for that.

Re:Ah what does it matter... (3, Insightful)

dmbasso (1052166) | about a year ago | (#44491433)

They do. It is called taxes.
You pay to be spied on, good deal!

Re:Ah what does it matter... (5, Funny)

Quasimodem (719423) | about a year ago | (#44491987)

You pay a fraction of your income to have someone watching you all the time.

It's a great deal if you're an exhibitionist!

Re:Ah what does it matter... (1)

Anonymous Coward | about a year ago | (#44491457)

I wouldn't worry about that.

Unless you're a communist. Or a trade-unionist. Or a Jew. Or maybe Catholic.

I'm sure we're all good on /. for a long time to come.

No need to say anything, really...

Re:Ah what does it matter... (2)

multisync (218450) | about a year ago | (#44492389)

I care more about Hackers gaining access to my bank account than the NSA.

I care more about Thieves gaining access to my bank account than Hackers or the NSA.

RSA = out of date (0, Flamebait)

girlintraining (1395911) | about a year ago | (#44491157)

The RSA encryption has been depreciated for years now. Hell, back in 2000 we were saying that DES was insecure, and triple-DES was just a stop-gap. Everyone's been switching to AES for awhile now. This isn't news.

Every encryption scheme has to balance performance and security; And we balance it so that in the next 5, 10, 50, or however many years, advances in technology won't render the data vulnerable in the interim. It's basic engineering. It's like building a safe -- you can't stop it from being broken, but you can make it so that it takes time. Hopefully enough time to get additional resources to the site to stop the thieves. There is no such thing as an uncrackable safe... or an encryption scheme.

The goal is to make sure it takes long enough that by the time they get in, either the men with shotguns have arrived, or whatever it was protecting is now useless to them. If you don't understand this fundamental rule of security, then perhaps this article is newsworthy... but to anyone who works with information security... it's just confirmation of existing methodology.

Re:RSA = out of date (5, Insightful)

EvanED (569694) | about a year ago | (#44491253)

The RSA encryption has been depreciated for years now. Hell, back in 2000 we were saying that DES was insecure, and triple-DES was just a stop-gap. Everyone's been switching to AES for awhile now. This isn't news.

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.

I'm not a crypto person, but RSA and elliptic-curve systems are the only two public-key systems I can think of. (There are others that allow secure exchange of a secret key, but that's different.)

Re:RSA = out of date (4, Informative)

burne (686114) | about a year ago | (#44491317)

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.

read the paper (2, Informative)

Anonymous Coward | about a year ago | (#44491539)

http://arxiv.org/abs/1306.4244

Re:RSA = out of date (0)

Anonymous Coward | about a year ago | (#44491583)

He's not saying AES is a replacement for RSA, it was a replacement for DES. RSA has been deprecated for years, while people are still using it, just as people were using DES when it was known to be insecure.

The idea is that encryption standards can quickly become ineffective due to improvements in computing power and cryptanalysis.

Re: RSA = out of date (2)

ceoyoyo (59147) | about a year ago | (#44491903)

Deprecated - I don't think that word means what you think it means. RSA can't be deprecated when there isn't a replacement. Elliptic curve cryptography has only really become a realistic replacement fairly recently, and nobody outside of government rushed to give Blackberry lots of money to use it because there wasn't a compelling reason to do so. Governments DID, which suggests to the conspiracy theorist that they might know of such a reason.

It's been long recommended you don't use short keys with RSA (which were used in the past for speed) but the algorithm itself is secure (as far as we know), no matter how much hardware you throw at it. This story is about the possibility of a mathematical advance (note, the possibility, it hasn't happened yet) that could make the RSA algorithm itself insecure, for any key length.

A breakthrough in solving the discrete logarithm problem would be a big deal. It could also very well lead to breakthroughs in integer factorisation.

Re:RSA = out of date (1, Informative)

girlintraining (1395911) | about a year ago | (#44491621)

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 = out of date (1)

Anonymous Coward | about a year ago | (#44491821)

Sigh. AES requires less resources to implement than DES (in software, anyway). It also happens that it is more secure due to better design and longer keylength (possibly it is less secure than 3DES, that is open to debate).

The real reason we have replaced DES with AES (and RC4) is neither because resources are constrained or because DES is broken (it's not), it is because the key length is only 56-bit, so while it is secure from a cryptographic standpoint, it can be bruteforced (expensively) and is insecure from a practical standpoint (when dealing with a commited adversary).

That both AES and RC4 (which is kind of insecure in design, but most widely used in SSL) are much faster than DES is also a huge advantage when you are using them for bulk encyrption as they are used in SSL and OpenSSH.

Re:RSA = out of date (4, Informative)

ultranova (717540) | about a year ago | (#44491909)

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.

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 (5, Informative)

EvanED (569694) | about a year ago | (#44491913)

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:

Which is that every encryption algorithm, regardless of type or usage-scenario, has a shelf life.

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.

now that resources have increased many-fold since the original, it is no longer secure.

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.

I then compared it to other encryption schemes that are less resource-constrained which have been coming into wider use

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 = out of date (1)

K. S. Kyosuke (729550) | about a year ago | (#44491633)

AES can't be a suitable replacement for RSA

True, but he isn't making any such claim.

Re:RSA = out of date (2)

mlts (1038732) | about a year ago | (#44491279)

Maybe it might be time for an algorithm challenge, similar to how AES got decided, and the lastest hash algorithm got chosen.

Of course, asymmetric algorithms are a lot harder to make that are secure than symmetric ones.

I wonder about, instead of naming one, naming three. That way, if in the future one gets compromised, the broken one would just not be used, or for very sensitive stuff, all three can be cascaded (not for bit length, but to keep things signed or encrypted in case one gets severely weakened.)

Re:RSA = out of date (1)

Anonymous Coward | about a year ago | (#44491395)

The interesting thing is that I think TFA confuses DSA with RSA. DSA would be useless if the discrete logarithm was solved but is not really threatened by quantum computers. RSA is relatively fine with this development because their major weakness is integer factorization, but would be hosed by quantum computers.

Re:RSA = out of date (0)

Anonymous Coward | about a year ago | (#44491401)

'deprecated' - have to be careful, not all spell checkers have that word.

It may actually be possible to build an unbreakable encryption scheme - advances in mathematics are not guaranteed.

Re: RSA = out of date (0)

Anonymous Coward | about a year ago | (#44491993)

There already exist unbreakable mathematical ciphers. The problem, invariably, comes down to key exchange - and even this is resolved wi quantum cryptography.

Re:RSA = out of date (5, Informative)

tlhIngan (30335) | about a year ago | (#44491431)

The RSA encryption has been depreciated for years now. Hell, back in 2000 we were saying that DES was insecure, and triple-DES was just a stop-gap. Everyone's been switching to AES for awhile now. This isn't news.

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.

Re:RSA = out of date (1)

K. S. Kyosuke (729550) | about a year ago | (#44491495)

Wow, that is so wrong.

How is it wrong? He's not referring to the operating principles, only to the fact that RSA and DES are about equally dated. You've just wasted time and space providing him with information he's already had.

Re:RSA = out of date (2)

EvanED (569694) | about a year ago | (#44491561)

He's not referring to the operating principles, only to the fact that RSA and DES are about equally dated

Adam Van Ymeren said it well [slashdot.org] . An algorithm's age doesn't necessarily speak to how secure it is. DES is considered insecure because it has a fixed key size that can be brute-forced, not because it is a fundamentally weak crypto system.

By contrast, the same objection does not apply to RSA, at least AFAIK: the key size can be scaled arbitrarily, so as computing resources grow so can the difficulty of the problem. I'm not familiar enough with the area to know how the discrete log helps RSA (integer factoring is the usual weakness I associate with that algorithm), but at least what the summary suggests is a fairly fundamental breaking of the algorithm. I didn't read TFA, but possibly key sizes would have to be scaled up prohibitively to remain secure.

DES vs AES is not the same situation at all as RSA vs EC.

Re:RSA = out of date (0)

Anonymous Coward | about a year ago | (#44491963)

By contrast, the same objection does not apply to RSA, at least AFAIK: the key size can be scaled arbitrarily, so as computing resources grow so can the difficulty of the problem.

This is also true with respect to DES, as in the case of 3DES, and you could easily create 5DES or 10DES or whatever by chaining cipher units with different keys which are each a portion of the combined key. We don't do this for the same reason that we don't normally use RSA8192, it's incredibly slow.

AES has an advantage over DES in that it has a much faster software implementation (and possibly a simpler hardware implementation, but IANAHD). The primary reason it was developed was because 3DES is slow and people wanted cheap encryption that could deal with fast channels like the internet and hard disks.

Considering there are some theoretical partial breaks on AES, if I was truly paranoid I would use 3DES or 6DES over AES, but I am a practical man, and the real practical security of AES, especially AES256 is assured for now.

Re:RSA = out of date (2)

Adam Van Ymeren (2844567) | about a year ago | (#44491473)

There's a fundamental difference between breaking the algorithm mathematically and the key space being too small. People left DES and 3-DES because the key size was too small and a brute force became feasible. The same is becoming true for RSA, but this is completely different than solving the discrete logarithm problem that underpins RSA and Diffie-Hellman. Solving that would be an amazing feat of mathematics. So please stop trying to show off to /. how you're smarter than everyone else.

Re:RSA = out of date (1)

pwizard2 (920421) | about a year ago | (#44491763)

The thing I'm not sure about right now is whether the RSA method itself is becoming insecure or if standard-size keys can simply be brute-forced. If it's a question of key size, then why not use larger keys?

The last time I checked, it is possible to increase the size of RSA keys quite a bit. Most frontends for PGP/GPG only allow keys up to 4096-bit to be created but several years ago I was able to generate valid key pairs up to 11296-bit. I had to modify the GPG source code and recompile it before it would let me create oversize keys but my 11296-bit key is still compatible with stock GPG.

Re: RSA = out of date (5, Insightful)

ceoyoyo (59147) | about a year ago | (#44492009)

The story is talking about the possibility of a mathematical breakthrough that would make solving the discrete logarithm problem (and possibly the integer factorisation problem) much, much easier. RSA relies on it being much easier to raise something to an integer power than to find a discrete logarithm (inverse operations). If you figure out how to make the two operations of similar difficulty then any encryption scheme based on them is hopelessly broken for any key size.

Re:RSA = out of date (2)

compro01 (777531) | about a year ago | (#44492179)

If it's a question of key size, then why not use larger keys? The last time I checked, it is possible to increase the size of RSA keys quite a bit.

Because large RSA keys do unfortunate things to performance. You double the key length, and it takes 6-7 times longer to run the decryption [javamex.com] .

Re:RSA = out of date (0)

Anonymous Coward | about a year ago | (#44492025)

No, people left DES because the keysize was too small, and left 3DES because DES was too slow.

You can keep increasing the security of a block cipher by chaining it with additional keys indefinitely*, but DES is already slower than AES and 3DES is 3 times slower than DES.

* Because there is no way to identify which intermediate ciphertext between each module is correct, you have to solve over the combined keyspace to brute force it. Of course if your individual cipher is vulnerable to DCA, then your composite cipher will likewise be vulnerable to DCA.

Elliptical Curve (2, Informative)

Anonymous Coward | about a year ago | (#44491159)

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

RE: Elliptical curves (4, Interesting)

Anonymous Coward | about a year ago | (#44491181)

https://www.schneier.com/essay-198.html

Re: Elliptical curves (0)

Anonymous Coward | about a year ago | (#44491371)

Schneier's essay refers to Dual_EC_DRBG, a pseudorandom number generator that is based (in part) on elliptic curve cryptography.

A broken or malicious pseudorandom number generator is bad news to be sure, but even if Dual_EC_DRBG is broken or malicious that doesn't mean that elliptic curve cryptography as a whole is broken or malicious.

Re: Elliptical curves (4, Informative)

EvanED (569694) | about a year ago | (#44491423)

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

OpenSSL? (5, Interesting)

pope1 (40057) | about a year ago | (#44491203)

OpenSSL [openssl.org] has had a good working implementation of ECDSA/ECDH for years: http://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography [openssl.org]

What exactly does BlackBerry have chained down that we don't have an open solution for?

Re:OpenSSL? (2, Informative)

Anonymous Coward | about a year ago | (#44491611)

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:OpenSSL? (1)

TechyImmigrant (175943) | about a year ago | (#44492355)

I.E. If you implement these RFC 6090 "Pre-patent" methods, the first obvious thing you would think of to make it better is point compression. That is one of the obvious implementation things that were patented.

Re:OpenSSL? (1)

Anonymous Coward | about a year ago | (#44491661)

They've chained down the technique of 'being an asshole'. Patenting math is evil.

RSA is outdated, but... (1)

aeranvar (2589619) | about a year ago | (#44491205)

I recently took a survey put out there by a researcher studying those working in the security community. One of the questions was about what threats really keep me up at night. My answer? That someone proves P = NP.

Re:RSA is outdated, but... (1)

EvanED (569694) | about a year ago | (#44491339)

Almost no one thinks that P=NP, so I wouldn't worry so much about that keeping you up at night. (The main thing I took away from a Robert Cook talk (the guy who basically invented/discovered the problem) was when he said that one of the big reasons that theorists think that P!=NP is that people seem to be really good at finding algorithms but really bad at proving complexity class differences. As a "proof" of the latter, he put forth that L any of them. :-) Obviously this was probably more intended as a humorous take on the situation, but it is slightly revealing.)

Actually in some ways it would be really really exciting and almost certainly a really good thing in the long run, because there are a lot of important, currently-intractable problems that become tractable if P=NP.

Of course, that assumes two things: (1) current approximation algorithms aren't "good enough" (which I'm not sure about), and (2) the chaos brought about by cryptography no longer working is relatively short term and we make it through it. :-)

Re:RSA is outdated, but... (3, Insightful)

Anonymous Coward | about a year ago | (#44491487)

Actually in some ways it would be really really exciting and almost certainly a really good thing in the long run, because there are a lot of important, currently-intractable problems that become tractable if P=NP.

Proving that P=NP doesn't make anything tractable, unless you use the ridiculous definition where tractable is the same as polynomial time. What would have practical applications is if someone finds a very fast algorithm for solving all the NP problems. Whether P=NP is not really very much related to the question of whether such an algorithm exists. ML has exponential-time type checking, yet ML compiles don't take that long. Polynomial time is not the same as practical - it fails in both directions.

Re:RSA is outdated, but... (1)

Anonymous Coward | about a year ago | (#44491597)

Mod up! This is an important point always lost in non-technical P-NP discussions.
Even if P != NP, the distinction only matters in the limit.
People ignore this when they claim that the security of PKC depends on P != NP.
In the real world, we're talking about actual fixed (or bounded) key sizes, so the tractability of breaking the cipher is a completely different question.

Re:RSA is outdated, but... (1)

EvanED (569694) | about a year ago | (#44491657)

Proving that P=NP doesn't make anything tractable, unless you use the ridiculous definition where tractable is the same as polynomial time.

Yes, you make some excellent points, and I should have addressed them before. I did a little bit (e.g. a close approximation to a solution may be "practical"), but you're right that I didn't go far enough.

More specifically, what I meant is a lot closer to the following. The OP was (while making the same mistake) considering crypto to be broken if P=NP. My hypothesis is that if crypto is broken because P=NP and then someone finds a good alogrithm, then many of the other very difficult problems will be solvable via whatever inspirational spark led to a good algorithm for factoring or whatever.

(One way this could fail is the following: factoring I think is in a no-mans land between P and NP, not known to be in P nor known to be NP-complete. If NP collapses into P then so must factoring, but it could be that factoring is some weird-ass O(n^23) algorithm or something while every NP-complete problem can't be done in less than, say, O(n^6000).)

Re:RSA is outdated, but... (4, Interesting)

gnasher719 (869701) | about a year ago | (#44492131)

(One way this could fail is the following: factoring I think is in a no-mans land between P and NP, not known to be in P nor known to be NP-complete. If NP collapses into P then so must factoring, but it could be that factoring is some weird-ass O(n^23) algorithm or something while every NP-complete problem can't be done in less than, say, O(n^6000).)

Consider this: Performing 2^256 operations is physically impossible (based on the quantum mechanical minimum energy to do anything, and the total amount of energy in the universe). 100 digit numbers are about 330 bits in size. If factoring n bit numbers required n^30 operations, then factoring just one 330 bit number would be physically impossible.

Re:RSA is outdated, but... (1)

steveb3210 (962811) | about a year ago | (#44492043)

Actually in some ways it would be really really exciting and almost certainly a really good thing in the long run, because there are a lot of important, currently-intractable problems that become tractable if P=NP.

Proving that P=NP doesn't make anything tractable, unless you use the ridiculous definition where tractable is the same as polynomial time. What would have practical applications is if someone finds a very fast algorithm for solving all the NP problems. Whether P=NP is not really very much related to the question of whether such an algorithm exists. ML has exponential-time type checking, yet ML compiles don't take that long. Polynomial time is not the same as practical - it fails in both directions.

Factoring is in NP... If P=NP, factoring is in P...

Factoring could be in P anyways as well...

Re:RSA is outdated, but... (1)

EvanED (569694) | about a year ago | (#44492181)

Yes, but the AC's (excellent) point is that P != "tractable". So factorization can be in P, but still not be tractable in a meaningful sense.

Re:RSA is outdated, but... (0)

Anonymous Coward | about a year ago | (#44491587)

Wasn't that Steve Cook, not Robert Cook?

Re:RSA is outdated, but... (0)

Anonymous Coward | about a year ago | (#44491749)

Arrr, it be Cap'n Cook ye Scallywag

Re:RSA is outdated, but... (1)

EvanED (569694) | about a year ago | (#44491971)

Yes, it was. My bad. :-)

Re:RSA is outdated, but... (5, Insightful)

qubex (206736) | about a year ago | (#44491411)

Based on my limited understanding, proving P = NP would not necessarily and automatically provide a manner of constructing reductions. It might. But there are proofs in computation theory that demonstrate limit complexities but do not provide the algorithms that might implement them, nor do they (currently, visibly) provide any indication of how that algorithm may be arrived at.

Besides, proving P = NP would have a vast number of consequences that would echo across mathematics and the more fundamental sciences. To harp upon the security implications is as short-sighted as fretting that all-out thermonuclear war would negatively affect the postal delivery service.

Re:RSA is outdated, but... (2, Informative)

girlintraining (1395911) | about a year ago | (#44491793)

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 is outdated, but... (1)

Nemyst (1383049) | about a year ago | (#44491911)

Proving P=NP implies that a host of processes taking non-polynomial time could take polynomial time instead. This has important implications in computer science, physics, chemistry and more, as you go from a problem considered to be effectively "impossible" (as in, impossible in a reasonable amount of time due to exponential growth) to one that is "possible". It's a very different change from incremental speedups we usually get from algorithms, because we're talking about something which has an entirely different growth function.

Also, please keep in mind that factorization of large numbers is not NP-complete. It is very possible (and very likely) that we will find an algorithm in P to solve this without proving or disproving that P=NP.

Re:RSA is outdated, but... (1)

EvanED (569694) | about a year ago | (#44491999)

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.

No, but as I pointed out in my other reply to you, you having a car that can go 200 MPH just means that I have to put your destination twice as far away.

And without fundamental math advances that haven't yet happened (at least outside of NSA-style organizations), for quite a long time it will be completely feasible to keep moving the destination further and further away as you get a faster and faster car -- without fundamentally changing the road network (which I guess is the crypto system :-)).

Re:RSA is outdated, but... (2)

amorsen (7485) | about a year ago | (#44492023)

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, we did not know any such thing. Advances in computation power can be defeated by increasing the key length of RSA, indefinitely. RSA cannot be made useless just by making regular computers run faster.

Re: RSA is outdated, but... (5, Insightful)

ceoyoyo (59147) | about a year ago | (#44492209)

You misunderstand the difference between throwing hardware at a problem and coming up with a more efficient algorithm.

RSA doesn't specify a key length. I can use a key that's 64 bits long (used originally but insecure today) or 1 megabit long (secure against known classical algorithms for the age of the universe no matter how much hardware you throw at it). As hardware gets better I can encrypt things using longer keys, in the same amount of time. It takes you MUCH MORE time to decrypt that, even with the better hardware. So long as you keep increasing key length as hardware gets faster, the encryption actually gets BETTER with better hardware.

The article is talking about a breakthrough in mathematics that could make solving discrete algorithms much faster. If it made it anywhere near as fast as exponentiation then it wouldn't take me much longer to decrypt your message than it took you to encrypt it, regardless of key length.

DES is insecure because it uses fixed length keys, that became practical to brute force. RSA doesn't have that problem. The situations are entirely different, and the potential breaking of RSA is much more interesting, and much more of an accomplishment.

Re:RSA is outdated, but... (2)

ImprovOmega (744717) | about a year ago | (#44492207)

Based on my limited understanding, proving P = NP would not necessarily and automatically provide a manner of constructing reductions. It might. But there are proofs in computation theory that demonstrate limit complexities but do not provide the algorithms that might implement them, nor do they (currently, visibly) provide any indication of how that algorithm may be arrived at.

You are technically correct, but certainly the quickest and most direct proof is to show a general solution for an NP-complete problem that runs in P time. And while proving P=NP would not necessarily provide the manner of constructing reductions in the general case, solving any NP-complete problem in P time does absolutely provide automatic solutions for *all* NP-complete problems in P time since, by definition, all NP-complete problems are reducible to each other. And factoring is an NP-complete problem.

Key patents controlled by Blackberry (4, Insightful)

Anonymous Coward | about a year ago | (#44491207)

Hmm ... considering Blackberry/RIM's precarious hold on existence, I have a hunch those patents will be in other hands very soon.

Re:Key patents controlled by Blackberry (0)

Anonymous Coward | about a year ago | (#44491527)

The question then becomes who's hands will they be in? Or better yet can we ensure they don't fall into the hands of someone who will abuse it?

Re:Key patents controlled by Blackberry (1)

Miamicanes (730264) | about a year ago | (#44491721)

Elliptic key cryptography per se isn't patented, just the most efficient ways of using it. So, worst-case, we might end up with some horrific eternal kludge whose only reason for existing was to provide a commercially-safe route around patents not set to expire for another 2-3 years.

Likely example: the horrific clusterfuck of an abomination known as "little-endian binary". I don't know for sure it came about due to patent reasons, but I can't think of any sane reason why it would have ever come into existence otherwise.

Re:Key patents controlled by Blackberry (1)

lgw (121541) | about a year ago | (#44491887)

I blame little-endian on a sort of backwards compatibility. Whether it's a pointer (index register) to an 8-bit or 16-bit value, you're pointing at the low-order byte. I've always suspected that made the first 16-bit Intel processors easier to build, in some way.

But if little-endian is a "horrific clusterfuck of an abomination" (and I'm not saying it isn't), what do you call PDP "middle-endian" - the Antichrist? I mean seriously, sometimes there is just no excuse.

Re:Key patents controlled by Blackberry (3, Insightful)

pipedwho (1174327) | about a year ago | (#44492097)

Likely example: the horrific clusterfuck of an abomination known as "little-endian binary". I don't know for sure it came about due to patent reasons, but I can't think of any sane reason why it would have ever come into existence otherwise.

From a purely machine theoretical standpoint, having the low order byte in the lowest memory location makes as much or more sense than the other way around.

Streaming transmission is a different matter, and in some instances can benefit from being able to receive the MSB first. This is especially true if the data gets acted upon in real time and the MSB is required earlier during the calculation. However, in may other cases, LSB first network byte order can be more advantageous (or at most at least not a disadvantage). So the decision to use either is really based on the algorithms chosen for the network traffic itself.

In creating interface code to opposite-endian systems, it's easier to think about avoiding translation and keeping both in the same format. But, I've personally never had trouble with this since I've always used reversed buffers where direct use of reversed multi-byte arithmetic was useful.

However, it stands to reason that the designers of the first little-endian processors didn't consider this a problem, as most byte traffic needs to be buffered and checked before it can be used in calculations, and that obviates the need for having network byte order being same-endian. Since these were all designed in the early days, I see no reason to assume that the choice to go with little-endian would have been any sort of compromise to the state of the art.

Re:Key patents controlled by Blackberry (1)

pipedwho (1174327) | about a year ago | (#44492147)

PS. I'm not defending patents here, just pointing out that patents were unlikely to be a motivation in the choice of Intel and others to go with little-endian byte order.

Re:Key patents controlled by Blackberry (4, Interesting)

amorsen (7485) | about a year ago | (#44492161)

There are plenty of sane reasons to use little endian. It means the same pointer can point to a value as 8-bits, 16-bits, 32-bits and so on, and it will get the right value as long as the value does not overflow.

Big-endian only exists because Latin languages write their numbers wrong -- text is written left-to-right but numbers are written right-to-left. This mess has also caused the middle-endian date and time formats currently in use. ISO tries to fix the date format, but unfortunately does it by standardizing exactly the big-endian way that feels so alien to humans.

If computers had been invented by someone writing either left-to-right or right-to-left consistently, big-endian would not have occurred to them. They would naturally write the smallest value first, just like the Arabic inventors of the numbers. Alas...

(Yes I am a convert. I used to think little endian was a sick joke.)

Re:Key patents controlled by Blackberry (0)

Anonymous Coward | about a year ago | (#44491875)

Let's hope they're not in the hands of http://en.wikipedia.org/wiki/Intellectual_Ventures

Re:Key patents controlled by Blackberry (0)

Anonymous Coward | about a year ago | (#44492375)

$6 billion in cash on the books. No debt. Free Cash flow positive (by $200 million or so) last quarter. An expected return to profitability in Q4.

And you think Blackberry has a precarious hold onto existance? That is far from the truth.

Explains BBRY 7% stock jump yesterday? (2)

JoeyRox (2711699) | about a year ago | (#44491225)

Article is dated 8/2 (Friday), yesterday would be the first tradable day on the information.

Re:Explains BBRY 7% stock jump yesterday? (1)

Threni (635302) | about a year ago | (#44491571)

Does BBRY sell elliptic curve technologies then?

Cue the conspiricy theories (0)

dunkindave (1801608) | about a year ago | (#44491229)

And cue the conspiracy theories that will say the NSA can break elliptic curve cryptography, so they cause fear that the discrete logarithm problem will soon be solved to get people to migrate to that which they can break. Hell, in today's world it might even be true, though I would bet on it.

I wouldn't be surprised if (1)

StripedCow (776465) | about a year ago | (#44491241)

the NSA had already solved the discrete logarithm problem...

[...] elliptic curve cryptography, something the NSA has said is best practice for years.

...or cracked elliptic curve cryptography.

Re:I wouldn't be surprised if (0)

Anonymous Coward | about a year ago | (#44491525)

I would be surprised if they hadn't.

Why not go back to original RSA? (1)

Excelcia (906188) | about a year ago | (#44491277)

Why elliptic curves when we can go back to good old fashioned original RSA that uses prime number factoring as the problem? No patent nonsense to worry about there.

Re:Why not go back to original RSA? (2, Funny)

Anonymous Coward | about a year ago | (#44491383)

Why elliptic curves when we can go back to good old fashioned original RSA that uses prime number factoring as the problem? No patent nonsense to worry about there.

We used up all the good prime numbers during the Internet boom years under Clinton.

Re:Why not go back to original RSA? (5, Interesting)

slew (2918) | about a year ago | (#44491689)

Why elliptic curves when we can go back to good old fashioned original RSA that uses prime number factoring as the problem? No patent nonsense to worry about there.

Sometimes the past needs to remain in the past...

Although prime factoring is considered a hard problem, the sparse distribution of prime numbers (~x/ln(x)) makes RSA increasingly inefficient in that superlinearly large moduli (to match large primes) need to be used to increase security linearly.

Lest nostalgia continue to be your guide, the original RSA was also found to be broken and needed to be patched to avoid the insecurity

1. Messages corresponding to small input values could be simply inverted ignoring the modulus operation (just doing numerical root estimation to invert the exponentiation). The larger the modulus, the more "insecure" messages there are.

2. Encryption is deterministic so is subject to dictionary attacks.

When people say they are using RSA today, they are usually using RSA-OAEP (optimal asymmetric encryption padding) which patches these two specific vunerablities of RSA.

FYI, the original RSA was patented (although later RSA labs decided to not enforce the patent and let it expire). This patent nonsense around RSA was a big issue in its day...

Re:Why not go back to original RSA? (0)

Anonymous Coward | about a year ago | (#44491727)

They're the same problem. x = a^n mod p.

Re: Why not go back to original RSA? (1)

ceoyoyo (59147) | about a year ago | (#44492235)

The discrete logarithm problem isn't technically the same as prime number factoring, but approaches that work on one tend to inspire approaches that work on the other. A breakthrough algorithm for one is likely to lead to a breakthrough algorithm for the other.

EC Patents (1)

Anonymous Coward | about a year ago | (#44491291)

Ed25519 by Dan Bernstein solves the patent issue and offers efficient and simple implementations.

Re:EC Patents (1)

Wickedpygmy (907341) | about a year ago | (#44491507)

more commonly used is ECDSA, which is not patented.

The NSA??? (0)

Anonymous Coward | about a year ago | (#44491353)

Really, we want to take the NSA's advice on which crypto to use?

Re:The NSA??? (1)

Noughmad (1044096) | about a year ago | (#44491535)

Is there someone you think is better qualified?

Re:The NSA??? (0)

Anonymous Coward | about a year ago | (#44491943)

I don't know about "better qualified" but I do know about "more trustworthy".

What patents? (1)

Hentes (2461350) | about a year ago | (#44491367)

You can't patent math.

Re:What patents? (4, Informative)

niado (1650369) | about a year ago | (#44491541)

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:What patents? (0)

Anonymous Coward | about a year ago | (#44491557)

if apple can patent input gestures, someone can patent math.. o wait.. they can't.

Re:What patents? (0)

Anonymous Coward | about a year ago | (#44492409)

An implementation of math is just math. From the first link. https://www.google.com/patents/WO1999030458A1?cl=en&dq=elliptic+curve+cryptography+blackberry&hl=en&sa=X&ei=pIEBUtuUOrP3yAHotYCYCg&ved=0CDQQ6AEwAA just describes a more effecient way of calculating certain terms associated with an elliptical curve. The enumerated claims are nothing more than descriptions for mathematical algorithms.

So THAT'S why governments want all data (0)

Anonymous Coward | about a year ago | (#44491407)

In many countries encryption of past communications will be breakable before criminal statutes of limitations run out, and that's just for the crimes that aren't so serious that they have no time limit.

Does this mean discrete log is NOT NP complete? (0)

Anonymous Coward | about a year ago | (#44491465)

The old saw was that a solution to any NP complete problem is a solution to every NP complete problem. Therefore, if both discrete log & elliptic curve problems were NP complete, this research would break both of them. If, however, discrete log isn't NP complete, you can come up with a fast solution for that problem and still be OK using elliptic curves.

Re:Does this mean discrete log is NOT NP complete? (1)

JoshuaZ (1134087) | about a year ago | (#44491629)

Discrete log has been believed to almost certainly not be NP-complete since well before this. We have much better than exponential time algorithms for discrete log so it would contradict the exponential time hypothesis for it to be NP complete http://en.wikipedia.org/wiki/Exponential_time_hypothesis [wikipedia.org] . Second, discrete log is closely related to factoring which llives in NP intersect co-NP. Since factoring lives in that intersection, if factoring is NP complete then then the polynomial hierarchy would collapse http://en.wikipedia.org/wiki/Polynomial_hierarchy [wikipedia.org] which is largely believed to not be the case.

EC is also based on discrete log (0)

Anonymous Coward | about a year ago | (#44491481)

I don't see how moving to Elliptic Curve crypto helps, since it's also based on the discrete log problem. Search for the term here: http://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography

Re:EC is also based on discrete log (1)

JoshuaZ (1134087) | about a year ago | (#44491573)

They are discrete logs over different groups. Joux's work and related stuff being referred to is for (Z/nZ)*, that is the discrete log over the group of units under in the integers modulo n. That problem is of course, closely connected to prime factorization. In contrast, ECC uses the discrete log over elliptic curve groups, which are also abelian groups but as of yet do not have any similar sort of breakthrough. In fact, this isn't a new situation. Discrete log has been harder over elliptic curves than over (Z/nZ)* since the mid 1990s. It is however worth noting one potential vulnerability that both share: any form of discrete log is efficiently solveable on quantum computer. So if one is thinking in the really long-term then ECC doesn't look much better.

Wasn't this the premise of the movie Sneakers? (2)

UnknowingFool (672806) | about a year ago | (#44491505)

From what I remember some mathematician had figured out a shorter way to solve the discrete problem and built a black box to do it. The main characters then stole his machine.

Re:Wasn't this the premise of the movie Sneakers? (0)

Anonymous Coward | about a year ago | (#44492111)

I thought the black box had a super-duper factoring algorithm.

Software patents (1)

ratm999 (1070324) | about a year ago | (#44491645)

Maybe this will finally spur the abolishment of software patents.

Go patents on math! (1)

viperidaenz (2515578) | about a year ago | (#44491699)

Patents have now become an issue of national security.

Re:Go patents on math! (2)

amorsen (7485) | about a year ago | (#44492205)

Patents have been an issue of national security for a while. Several countries, including the US, has secret patents. It takes someone wiser than me to explain how that promotes the progress of science and useful arts.

I've been working on RSA for over ten years... (3, Interesting)

Panaflex (13191) | about a year ago | (#44492005)

I'm surprised to see other people going in the direction I've been going for about 3 years now. Really. I thought I was quite alone in my path, LOL.

I need to read this paper still, but if it's taking the same path I did, then it's not a peachy as some think.

I'm only am amateur, so take this from the point of view as someone who kicks back with a beer and enjoys solving impossible computational problems.

I don't think it's that close to being broken... I think it'll take a huge computing effort (think multi-terabyte databases) to generate the tables across the PQ space required so that existing problems can be used to quickly find paths and intersections. At the beginning you're looking at only a VERY SMALL speedup from modern sieving, but once the tables get generated (years of effort) you'll eventually see faster and faster improvements. At least, that's with my algorithm, which I'm sure is far from perfect and only works on a certain set of primes right now. Which is about 20%. Which is far from optimal.

So yeah, progress. But I'm unconvinced that this will work for all primes.

I'm going to read the paper now... which I'm sure is far better than what I've been doing.

I doubt this article should be taken too seriously (4, Interesting)

mstefanro (1965558) | about a year ago | (#44492149)

There does not appear to exist any single piece of evidence that DLP (discrete logarithm problem)
will benefit from algorithms running in polynomial time. The recent work of Antoine Joux that they
are referring to (one of which I assume to be http://arxiv.org/pdf/1306.4244v1.pdf [arxiv.org] ) provides
improvements of quasi-polynomial agorithms for breaking DLP. But there is no reason to believe
that these improvements can lead to a polynomial-time attack. And as long as this does not happen,
those attacks can still be defeated by increasing the key size.

Don't get your knickers in a knot just yet . . . (2)

mmell (832646) | about a year ago | (#44492239)

Please remember - when new tools give cryptographers the ability to exploit weaknesses in existing cryptosystems it also gives them the ability to device cryptosystems immune to those exploits.

(if you can get a trusted version with no 'escrow' technology built in, that is)

As I recall, the guys who wrote PGP back in the day almost went to prison for publishing the source code - despite the fact that the RSA algorithm in use was already publicly documented (in Scientific American IIRC). "The Powers that Be" learned from that debacle and have far more reliable mechanisms for gaining access to everything you do in the clear if they want it (for example, the TCM in my new HP PC is turned on and enforcing - I can turn it off, but what other little goodies have manufacturers hidden in the firmware for me to discover?).

Moral of the story - IPv4 is exhausted, go to IPv6. BIND4 is obsolete, go to BIND8. NFS is dated and insecure, go to NFSv4. RSA is at risk of being compromised by advances in mathematics, go to [something better]. Really - is cryptography supposed to be carved in stone? I know that worked for the Egyptians, but anything related to the technology field...

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...