The Threat to Classical Cryptography
The threat of quantum computing to classical cryptography is largely confined to asymmetric encryption methods. Although Grover’s algorithm can break symmetric ciphers, it has been argued that increasing the key size can effectively fend off such attacks. Shor’s algorithm (and its variants), on the other hand, can solve all three hard-to-solve mathematical problems that current asymmetric encryption methods rely on for their security, one of which is prime factorization.5
RSA is the most prominent instance of an asymmetric encryption method using prime factorization. In simple language, the private key in the RSA encryption protocol is constructed using a pair of randomly selected prime numbers the product of which is a semiprime. The corresponding public key is derived from this semiprime. When transmitting a message, the sender employs the public key, acquired from the intended recipient, to perform the encryption. Upon receiving the encrypted message, the recipient employs the private key, generated from the primes, for decryption.
The RSA encryption key can be broken by factoring the semiprime, here denoted N, that is, by finding the (only) two prime numbers of which N is the product. For illustration, let’s assume N equals 35. Factorizing N is straightforward as it is immediately recognized as the product of 5 and 7, the (only) two prime numbers that generate the semiprime 35.
Modern implementations of RSA ciphers use prime numbers that are hundreds of digits in length. For instance, the RSA number of the 2048-bit RSA protocol that had been generated for the RSA Factoring Challenge launched in 1991 has 617 decimal digits. There is no known algorithm that allows classical computers to determine in a practical amount of time the prime factors of numbers that large.6 Nonetheless, Shor's algorithm, introduced in 1994, has demonstrated the capability to solve the factorization problem in polynomial time using quantum computing, thus providing the theoretical basis for breaking RSA.7
The implementation of Shor’s algorithm poses a formidable physical challenge. This is because today’s (physical) qubits are subject to errors, which are related to hardware limitations and noise from the surrounding environment.8 A 2019 experimental study of Shor’s factoring algorithm on an IBM Q quantum computer reports “excellent” performance in factoring the number 15 (3x5), whereas “deviations from the theoretical results become more noticeable” for 21 (3x7), and the factoring of the number 35 (5x7) failed due to accumulating errors.9 Remarkably, the semi-prime 35 is composed of just two decimal digits, a far cry from the 617 decimal-digit RSA number generated for the RSA Factoring Challenge using the 2048-bit protocol.
Although quantum computers have successfully factored larger numbers using alternative algorithms, these methods resemble classical brute-force methods for factor checking. Unlike Shor's algorithm, these approaches are not anticipated to surpass the performance of classical factorization algorithms.10
The breaking of a sufficiently strong RSA encryption key using Shor’s algorithm may be many years away.11 Large-scale quantum computing requires techniques that keep the errors generated by (physical) qubits from multiplying and spreading. Current error correction methods focus on the encoding of information into multiple physical qubits that are grouped into logical qubits.12
Post-Quantum Cryptography (PQC)
In 2016, National Institute of Standards and Technology (NIST) summoned the global community of cryptographers to create and assess encryption methods capable of resisting attacks from an advanced quantum computer, surpassing the power of today's limited machines. By 2022, NIST had selected the first set of encryption tools designed to withstand assaults from future quantum and classical computers alike. These four chosen encryption algorithms are on track to become integral to NIST’s post-quantum cryptographic standard, expected to be finalized by 2024.13
Notably, only one candidate has been put forth for key exchange, whereas the other three algorithms are digital signature schemes. The security of the public-key encryption algorithm CRYSTALS-Kyber is based on a hard-to-solve problem known as the shortest vector problem (SVP). Solving a large SVP instance to recover the private key is considered infeasible even for quantum computers.14
NIST suggests that over the next two decades, there is a plausible chance of quantum computers reaching a scale where they could potentially compromise all currently used public-key encryption methods. The joint factsheet on quantum readiness urges organizations to start preparing early by creating quantum-readiness roadmaps, conducting risk assessments, and engaging vendors. This is essential because data being targeted by threat actors today might still require protection in the future.
This blog was authored by Frank Schmid and reflects his thoughts; however, it was enhanced using Generative AI prior to Gen Re’s editorial and legal review.