Shor's algorithm
A quantum algorithm, published by Peter Shor in 1994, that could factor large numbers and solve discrete logarithms quickly on a big enough quantum computer.
In more detail
Those two problems are what make RSA, Diffie-Hellman and elliptic curve cryptography hard to break, so Shor's algorithm would break all of them, along with the certificates and signatures built on them. Making the key bigger does not help much, because the algorithm's running time grows only slowly with key size. This threat is the reason post-quantum algorithms are being deployed now.
Example
Breaks: RSA, Diffie-Hellman, elliptic curves. Does not break: AES-256, SHA-256.Related terms
- quantum computer — A computer that uses the physics of quantum states to solve certain kinds of mathematical problems far faster than ordinary computers can.
- Grover's algorithm — A quantum search algorithm that could find a secret key in roughly the square root of the number of tries an ordinary search needs.
- RSA — A widely used public-key algorithm, named after its inventors Rivest, Shamir and Adleman, used for digital signatures and for encrypting small secrets such as keys.
- post-quantum cryptography — Public key algorithms designed to stay secure even against attackers with a large quantum computer, while still running on ordinary computers.
Taught in
- Post-Quantum Cryptography & Key Lifecycles — Cybersecurity Fundamentals, GRC & Cryptography