Cambridge University Press eBooks

Breaking cryptosystems

Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, Fernando G. S. L. Brandão

Published Apr 24, 2025• 0 citations

Publisher

Abstract

This chapter covers the potential use of quantum algorithms for cryptanalysis, that is, the breaking and weakening of cryptosystems. We discuss Shor’s algorithm for factoring and discrete logarithm, which render widely used public-key cryptosystems vulnerable to attack, given access to a sufficiently large-scale quantum computer. We present resource estimates from the literature for running Shor’s algorithm, and we discuss the outlook for postquantum cryptography, which aims to replace existing cryptosystems while being resistant to quantum attack. We also cover quantum approaches for weakening the security of cryptosystems based on Grover’s search algorithm.

DOI: 10.1017/9781009639651.008

Related papers

Quantum Cryptanalysis: Breaking Classical Encryption with Shor's and Grover's Algorithms

Godwin Olaoye

The advent of quantum computing presents a paradigm shift in the field of cryptanalysis, challenging the security of classical encryption schemes that underpin modern digital communications. This study explores the capabilities of quantum algorithms, particularly Shor's algorithm and Grover's algorithm, in undermining widely used cryptographic systems. Shor's algorithm poses a direct threat to publickey cryptosystems such as RSA and ECC by enabling efficient integer factorization and discrete logarithm computation, which are computationally infeasible for classical computers. Meanwhile, Grover's algorithm provides a quadratic speedup for bruteforce attacks on symmetric-key cryptosystems like AES, significantly reducing their effective security. Through theoretical analysis and simulation-based evaluation, this paper highlights the vulnerabilities of classical encryption in the face of quantum advances and underscores the urgent need for post-quantum cryptographic solutions. The findings emphasize the critical importance of transitioning to quantum-resistant algorithms to ensure long-term data confidentiality in a future dominated by quantum technologies.

Apr 10, 20253 citations

Introduction

Alexei Petrenko, Sergei Petrenko

In quantum cryptanalysis, Shor's algorithm provides exponential acceleration of solving factorization problems, discrete logarithm problem, and elliptic curve discrete logarithm problems, widely used in cryptographic applications in cyberspace. Shor's quantum algorithm can potentially crack most protocols and schemes of asymmetric encryption (public key cryptography). In general, all known quantum algorithms can be divided into two groups: providing exponential gain (for example, Shor's algorithm) and providing quadratic gain (for example, Grover's algorithm). Particular attention is paid to the Shor quantum algorithm and other polynomial algorithms capable of solving cryptanalysis problems with the required reliability and complexity in polynomial time. For quantum computing, all cryptographies are divided into quantum-secure and quantum-insecure. Algorithms and cryptosystems of symmetric encryption are attributed to quantum-secure but with at least twice the key length increased. This chapter presents an overview of the concepts discussed in the subsequent chapters of this book.

River Publishers eBooksFeb 7, 20230 citations

Quantum Computing-Based Cryptanalysis of Cryptographic Algorithms

Jincheng Zhang

This paper investigates the potential impact of quantum computing on the security of currently deployed cryptographic algorithms. The core premise is that the advent of powerful quantum computers, leveraging algorithms like Shor's algorithm and Grover's algorithm, poses a significant threat to widely used public-key cryptosystems and symmetric-key algorithms. We present a theoretical analysis of several key algorithms – RSA, ECC, and AES – examining their vulnerabilities when subjected to quantum attacks. Specifically, we explore the exponential speedup offered by Shor's algorithm for factoring large numbers, the impact on the key size of ECC, and the Grover's algorithm's influence on symmetric key search. Our work highlights the urgency of transitioning to post-quantum cryptography standards to mitigate the risks posed by this technological advancement. The goal is to provide a comprehensive understanding of the landscape of quantum cryptanalysis and its implications for the future of secure communication.

Sep 3, 20260 citations

Quantum Attacks on Modern Cryptography and Post-Quantum Cryptosystems

Zachary Marron

Cryptography is a critical technology in the modern computing industry, but the security of many cryptosystems relies on the difficulty of mathematical problems such as integer factorization and discrete logarithms. Large quantum computers can solve these problems efficiently, enabling the effective cryptanalysis of many common cryptosystems using such algorithms as Shor’s and Grover’s. If data integrity and security are to be preserved in the future, the algorithms that are vulnerable to quantum cryptanalytic techniques must be phased out in favor of quantum-proof cryptosystems. While quantum computer technology is still developing and is not yet capable of breaking commercial encryption, these steps can be taken immediately to ensure that the impending development of large quantum computers does not compromise sensitive data.

Jan 1, 20180 citations

Quantum Computing for Cryptanalysis: Breaking Modern Cryptographic Protocols

Jessica Roberts, Jennifer Leigh Clarke

Quantum computing poses a fundamental threat to modern cryptographic protocols by exploiting quantum algorithms that surpass classical computational limits. Shor’s algorithm can efficiently factor large integers, breaking RSA and other public-key cryptosystems, while Grover’s algorithm accelerates brute-force attacks against symmetric encryption. As quantum hardware advances, traditional cryptographic schemes risk obsolescence, necessitating the development of quantum-resistant cryptographic techniques. This paper explores the theoretical foundations of quantum cryptanalysis, examining key algorithms, their implications for cybersecurity, and the current state of post-quantum cryptographic solutions. By analyzing resource estimates for quantum attacks and potential mitigation strategies, this study provides a comprehensive overview of the evolving cryptographic landscape in the quantum era.

International Journal on Advanced Electrical and Computer EngineeringApr 15, 20250 citations

How quantum breaks encryption

Walt Powell

This chapter explores the cryptographic implications of quantum computing, offering a detailed yet accessible breakdown of how quantum systems fundamentally differ from classical ones and why that difference threatens modern digital security. It introduces key quantum concepts such as superposition and parallelism, and explains how these capabilities enable powerful algorithms like Shor's and Grover's to solve mathematical problems that underpin today's encryption systems. The chapter compares symmetric encryption (e.g., AES) and asymmetric encryption (e.g., RSA, ECC, Diffie-Hellman), showing why public-key infrastructure (PKI) is especially vulnerable to quantum attacks. The chapter provides a clear explanation of how Shor's Algorithm breaks RSA and ECC by efficiently factoring large integers and solving discrete logarithms – problems considered infeasible for classical computers. It also examines Grover's Algorithm, which weakens symmetric encryption by reducing brute-force search times, prompting recommendations to adopt longer key lengths such as AES-256. Real-world experiments from Google's Willow processor and China's Zuchongzhi 3.0 demonstrate meaningful progress in quantum hardware, indicating that the Q-Day scenario – when cryptographically relevant quantum computers emerge – is rapidly approaching.

CRC Press eBooksDec 12, 20250 citations