The Shor algorithm, designed to factor large numbers in record time on a quantum computer, is shaking the world of cryptography. A recent announcement suggests that a team has used this algorithm to break an encryption key for the first time. But what is the reality, and what are the implications for digital security? This article explores this breakthrough, its limitations, and its potential consequences for the future of data security.
What is the Shor algorithm?
Developed by mathematician Peter Shor in 1994, the Shor algorithm is a quantum method for factoring very large integers in polynomial time, unlike classical algorithms which require exponential time. This capability directly threatens encryption systems like RSA, which rely on the difficulty of factoring large numbers to ensure security.
In other words, a sufficiently powerful quantum computer running the Shor algorithm could break the encryption keys used in many applications, from banking transactions to secure communications.
A first key broken? What the announcement says
A team reportedly succeeded in using the Shor algorithm to factor a number related to an encryption key, potentially marking a world first. However, it is crucial to qualify this information. The experiment would have been performed on a quantum computer with a limited number of qubits, and the broken key would be small in size, far from current cryptography standards (such as 2048-bit RSA keys).
According to the technical details shared, the team would have factored a number on the order of a few hundred bits, an impressive feat but still far from being a threat to modern systems. Indeed, current quantum computers, such as those from IBM or Google, do not yet have the power necessary to attack key sizes used in everyday life.
Current limitations of the Shor algorithm
Although this announcement is an important step, several obstacles remain before the Shor algorithm becomes a concrete threat to cryptography:
- Power of quantum computers: Current machines do not have enough stable qubits to run the algorithm on large numbers. Qubits must not only be numerous, but also resistant to errors, which requires advances in quantum error correction.
- Implementation complexity: The Shor algorithm requires considerable resources, even on modest numbers. Current tests focus on numbers much smaller than those used in real systems.
- Execution time: Even with a quantum computer, breaking a 2048-bit RSA key would still take years with current technologies.
Thus, while this experiment is a proof of concept, it does not mean that systems like RSA or ECC (Elliptic Curve Cryptography) are immediately vulnerable.
Toward post-quantum cryptography
Facing the potential threat of quantum computing, security experts are already working on solutions. Post-quantum cryptography aims to develop algorithms resistant to attacks by quantum computers. The NIST (National Institute of Standards and Technology) has launched a process to standardize these new algorithms, with proposals like Kyber or Dilithium gaining in popularity.
Furthermore, initiatives like those of the National Agency for Information Systems Security (ANSSI) in France highlight the importance of preparing the transition to these new standards. Organizations and governments are encouraged to audit their systems and plan a gradual migration to avoid a sharp break when quantum computers become more powerful.
Implications for the future
This breakthrough, while limited, reminds us of the urgency of preparing for the quantum era. The implications are far-reaching:
- Data security: Organizations must invest in systems resilient to quantum attacks.
- Research and development: Progress in quantum computing requires increased funding to develop both quantum computers and defenses against their capabilities.
- Digital trust: A successful transition to post-quantum cryptography is essential to maintain trust in digital infrastructures.
The announcement marks a symbolic step in the history of the Shor algorithm and quantum computing. However, it is too early to speak of an imminent threat to modern cryptography. This experiment proves that progress in this field is accelerating, and it is imperative to continue investing in research to anticipate tomorrow’s challenges.
Sources
https://arxiv.org/abs/2507.10592
https://stevetipp.github.io/Qwork.github.io
https://stevetipp.github.io/Qwork.github.io/experiment75.html