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, NP, and NP-Complete. Prime factorization of large composite numbers is a NP problem. That means a conventional computer needs exponential time to do the factorization, and RSA encryption depends on this. NP-complete is a slightly more demanding class of problem. Any NP problem can be reduced to a NP-complete problem, even other NP-complete problems. This means if you ever found a polynomial time solution for a 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.
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.
As it turns out, AES is not affected by Shor’s algorithm. There is no currently known quantum algorithm to break AES. However, the field is still growing, so its entirely possible someone will invent a way in the coming years. Encryption has always been a spy vs. spy game. It’s never over.
it’s not impossible to crack any of those algorithms. The problem is not weather 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 .
Will quantum computers render AES obsolete? – security.stackexchange.com #JHedzWorlD
No comments:
Post a Comment