Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a spin off from: Use multiple computers for faster brute force

Here's at least one source which says that quantum computers are on the way to being able to break RSA in the not too distant future. I am not a security expert, and don't know the difference between that and AES, but might this throw a monkey wrench into this idea that it's impossible to crack these modern encryption mechanisms?

MIT's new 5-atom quantum computer could make today's encryption obsolete

Perhaps some of you who are more knowledgeable on the subject could weigh in?

share|improve this question
1  
If I don't err from what I read from literatures, quantum computers could only reduce the block length (and key length) "effectively" to one half of the nominal values. Thus I recently pointed out a simply way to do that doubling for a given block cipher in order to counterbalance the potential risk of adversary's having quantum computers available. See s13.zetaboards.com/Crypto/topic/7504586/1/ – Mok-Kong Shen Mar 6 at 12:46
1  
@Mok-KongShen, you err. Shor's algorithm cracks factoring in polynomial, as opposed to exponential, time. – user1717828 Mar 6 at 17:47
5  
@user1717828 that's why you use eliptic curves and not prime factorization. But that has nothing to do with AES. – JDługosz Mar 6 at 17:58
    
@JDługosz Elliptic Curves get their strength from the discrete log problem, which is also broken by Shor's in poly-time. Not to mention that ECC has much shorter key lengths, making ECC more vulnerable to quantum computers than RSA is. – Mike Ounsworth Mar 10 at 17:53
    
It's rumored that quantum computers might be able to crack every AES encryption because it will be that good at finding prime numbers. But on the other hand it will allow for quantum cryptography which can be mathematically proven to be not crackable (because it utilizes one time keypad encryption). Bit this is very new technology. We thought that nuclear might be magical and help us propel into a new magical world where clean energy is cheap, we can heal illnesses with it, everyone will be happy, ... it's not like that. It's not like it but it was hyped. Quantum comouters are hyped atm too – Jonas Dralle Apr 4 at 14:29
up vote 92 down vote accepted

Quantum computing will change the encryption game, but it is not yet clear how much it will change. It's not clear because we are not yet certain what sorts of problems quantum computers can solve. As mentioned, RSA is dramatically weakened by quantum computing because the factoring of primes can be done in polynomial time using Shor's Algorithm. However, not all cryptographic routines are known to be as weak vs. quantum computing.

You may have heard of P (polynomial time), NP (nondeterministic polynomial time -- problems that given the right answer can be checked in polynomial time), and NP-Complete (the hardest NP problems). Prime factorization of large composite numbers is known to be an NP problem and is thought by many to not be P problem. That means a conventional computer would most likely¹ need super-polynomial time (at best sub-exponential time like GNFS) to do the factorization and RSA encryption depends on this. NP-complete is a slightly more demanding class of problem. Any instance of an NP problem can be reduced to an instance of an NP-complete problem. (This is true even if the NP problem is another NP-complete problem.) This means if you ever found a polynomial time solution for an NP-complete problem, you would have a polynomial time solution for every NP problem. If you did so using a classical computer, you would have proven P = NP.

Quantum computers have their own complexity class. BQP is the class of problems that can be [statistically] solved by a quantum computer in polynomial time. It is known that factorization is in BQP, because we have Shor's algorithm. What is yet unknown is whether BQP contains NP-complete or not. It is currently theorized that it does not, meaning there are NP-complete problems that still take exponential time, even with a quantum computer, but the mathematicians are still crunching away at that theory.

Integer factorization sits in an interesting middle ground. We know it is part of BQP (because we found Shor's algorithm). We also know that it is a problem within NP (it is NP because the factorization can be proven in polynomial time just by multiplying the numbers back together). What we don't yet know is whether it is P, NP-but-not-P, or NP-complete. Nobody has been able to prove it one way or another. It could actually be a P problem, solvable with a classical computer in polynomial time, making it very weak for encryption purposes. It could be a NP-complete problem, which given that we know it is in BQP, would imply that quantum computers can solve any NP problem in polynomial time, which would be a major blow to cryptography in general.

Many upcoming encryption algorithms are starting to use other problems besides prime factorization as their root. In particular, a set of problems based on lattices are thought to be particularly hard to break using quantum computers. If all NP problems are part of BQP, this won't help any, but we're still figuring that detail out to this day.

As it turns out, AES is not affected by Shor's algorithm. Grover's algorithm allows brute-forcing an n-bit key in O(2n/2) time instead of the O(2n) time required by classical computers. Therefore, an 128-bit AES key could be brute forced in O(264) time by a sufficiently powerful quantum computer that can do Grover's algorithm with 128+ qubits for 2^64 time.

¹ The wise and challenging commenters below are picking away at the imprecision in my wording. Technically it is not known whether NP problems requires exponential time or not. It is possible that the NP class of problems and the P class of problems are the same. However, most mathematicians believe it is much more likely that P != NP, simply because so far it doesn't look like it. If we want to talk in betting terms, just look at how much you could make answering the question. if you prove P and NP are distinct, you can earn the Clay prize of a million dollars, and maybe get a cushy job offer for being so smart. If you prove they are the same, I would expect the NSA to be willing to pay quite a lot more for you to be silent about your discovery, and instead hand over your papers to their mathematicians.

If you are very interested in the topic of quantum computing and encryption, I highly recommend reading up on the different complexity classes such as P and NP. They're worth your time.

share|improve this answer
14  
While Shor's algorithm(s) don't affect AES, Grover's algorithm certainly does. This can however be mitigated by using AES-256 instead of AES-128. – SEJPM Mar 6 at 10:53
1  
Wonderful summary. – Michael Kjörling Mar 7 at 9:19
2  
The tl:dr for the above is: We think Quantum computation will halve the effective keylength of AES and other symmetric algorithms. So double your AES keylength, and you are good to go. (AES-256 is probably good enough unless you need to protect high value assets for decades.) On the other hand, quantum computation completely screws RSA and Elliptic curve asymmetric algorithms. There are other algorithms that we think are OK, but we aren't sure (yet). Get ready for much bigger keys in future. – Martin Bonner Mar 7 at 9:36
1  
If you have a practical P algorithm for a problem in NP, the implications are much larger than "cryptography breaks". Any proof you can write down becomes easy to find. Any proof. Most of logic collapses into tautology (anything problem whose solution we can possibly understand) and inaccessible problems (problems whose solutions are so complex we cannot understand them). This includes constructive proof, so it covers questions like "is there an algorithm so solve X?": any algorithm that can be shown correct becomes easy to discover. NSA isn't rich enough. – Yakk Mar 7 at 21:40
1  
@Yakk Point the first please show that "most of logic" has relatively short proofs. Point the second, it's meaningless to talk about complexity of a single problem. The fact that X has a short proof does not mean that every problem in the language has a short proof. What you can say is that if every member X of a language L has a witness W that can be verified in time polynomial to the length of W, and W has length bounded by some function f(X) from the length of X, then P=NP implies that deciding L is in O(f(X)*p(X)) with polynomial p. Note that e.g. first order logic has no such f. – Taemyr Mar 8 at 11:06

It's not impossible to crack any of those algorithms. The problem is not whether you can brute force AES or not, it's about how much time it would take and whether if it is feasible or not.

If you want to crack AES with brute force using normal computers, it would take you to search 2^128 keys which will require minimum 2^128 operations.

On the other hand, using quantum computer and search algorithm such as Grover's algorithm you will be able to go through the same number of keys in (2^128)^0.5 operations.

share|improve this answer
3  
As far as i know , when you are calculating the complexity of an algorithm, you measure it in terms of number of operations you will have to do and the input's size. not the computation power. and in cryptography it's usually said that the key is secure if it takes more that 2^90 operations to break it . Now trying to break 128 bit AES with the mentioned above algorithm will require the number which you got from your calculations . Which if you tried to convert to 2^x form, you will find that it's smaller that 2^90 (you can tell that by subtracting the number you got from 2^90) – HSN Mar 6 at 1:11
2  
(2^128)^0.5 = 2^64 which is close to DES' key size (2^56) so it's not secure. Now how much time do you need ? it's really hard to answer that question since there are many variables . Your computation power , the program which you are using to brute force , the platform which you're using, the language which you wrote your password cracker with . And here we are not taking into account whether you will be designing your cracker to be software based or hardware based . however, take into account that DES with 56 bits key size got broken in around 22 hours in 1999 !!! – HSN Mar 6 at 1:27
5  
@BuvinJ (2^128)^0.5 and 2^(128^0.5) are very different numbers. – hobbs Mar 6 at 7:44
1  
@Jason C It made sense when I first asked. Now, that irony is growing ever more apparent! – BuvinJ Mar 7 at 3:42
1  
@aroth You are wrong abount AES-128. 2^128 would require 72 more moore's law iterations then 2^56, unless you're counting quantum computer among the modern hardware already. – Cthulhu Mar 7 at 9:02

One has to note here that quantum computers can be used to implement security protocols that are much better than what can be done using only classical computing. So, the real problem is at its root that the more advanced technology (in case of this question this is the hypothetical case of quantum computing becoming available) is not available to everyone.

share|improve this answer
    
Well real quantum computers that can maintain the type of quantum coherence to factor large integers or do discrete logs over finite fields (incl elliptic curves) aren't available to anyone (unless secret unpublished quantum computing research has made huge advances -- talking decades -- ahead of published research). – dr jimbob Mar 6 at 21:02
    
Sorry, I have to downvote this. A) Apart from Quantum Key Distribution, I'm not aware of any proposed quantum security protocols - can you include some links in your answer? and B) Large-scale quantum computers are estimated to cost $1 billion USD, and to require a dedicated nuclear power plant, so the real real problem is that not everyone has $1 billion USD to spend on encryption, and a nuclear plant in their backyard. – Mike Ounsworth Mar 10 at 18:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.