Practical Cryptography — Part XII
Quantum Computers
These machines use properties of quantum physics to perform computations on stored data. Instead of bits, they use qubits, which are made using physical systems like the spin of the electron or the orientation of a photon.
Qubits can different different things, simultaneously, in sharp contrast to classical computers which use bits, which store either 0 and 1 values.
It’s not to say that quantum computers are all-powerful or “faster” computers. They are often very efficient for certain problems and quite weak for others.
Quantum-Unsafe Cryptosystems
Using Shor’s algorithm, a k-bit number can be factored in the time of order O(k³) using a 5k+1 qubits quantum computer.
Hence 256-bit numbers can be factorized using 1281 qubits in 72*256³ quantum operations.
~1.2 billion operations == ~less than 1 second with a capable machine
- RSA
- ECC
- ECDSA
- ECDH
Quantum-Safe Cryptosystems
Traditional computers can find a collision for 256-bit hashes in 2¹²⁸ steps (birthday attack)
Quantum computers might find a collision for the same in 2⁸⁶ steps, in theory, but it might cost significantly more.
- Cryptographic Hashes: SHA256 and SHA3–256 are probably quantum safe. SHA384, SHA512, SHA3–384, SHA3–521 are generally considered quantum safe.
- Symmetric Key Ciphers: 128-bit algorithms are quantum-attack-able, but 256-bit symmetric ciphers like AES-256 are generally considered quantum-safe.
- MAC algorithms
