dybilar

10.26599/TST.2024.9010028 Factorization of RSA-2048 by Quantum Annealing on D-Wave QC

Published on
אם ירצה ה׳

Status:In Progress

Date: 07 Tevet 5785

C. Wang, J. Yu, Z. Pei, Q. Wang and C. Hong, "A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer," in Tsinghua Science and Technology, vol. 30, no. 3, pp. 1270-1282, June 2025, doi: 10.26599/TST.2024.9010028

TL;DR:

The paper demonstrates the first successful factorization of an RSA-2048 integer using the D-Wave quantum computer, highlighting the potential of quantum annealing (QA) in breaking modern cryptographic systems.

Spoiler:

The success is nuanced and hinges on the use of special integers. The paper states that it's a product of two prime numbers (p and q) where p and q differ by only two bits. The constraint that the two prime factors differ by only two bits significantly reduces the search space for the factorization algorithm. So it doesn't directly translate to breaking general RSA-2048 keys used in real-world applications.

Additional TL;DRs:

  1. For Cryptographers: This research indicates that quantum annealing could pose a significant threat to RSA encryption, necessitating the development of post-quantum cryptographic algorithms.

  2. For Quantum Computing Enthusiasts: The study showcases the practical application of D-Wave's quantum annealing in solving real-world problems like integer factorization, potentially expanding the scope of quantum computing applications.

  3. For Cybersecurity Professionals: The successful factorization of RSA-2048 using QA underscores the urgency to transition to quantum-resistant cryptographic methods to safeguard digital communications.

  4. For Mathematicians: This work provides a new approach to tackling the long-standing mathematical challenge of integer factorization, using quantum mechanics to navigate the vast solution space more efficiently.

  5. Non-Hype/Critical TL;DR: While the paper claims a breakthrough, it focuses on a special class of integers, suggesting that practical, large-scale factorization of arbitrary RSA-2048 keys might still be far off, especially for general-purpose integers.

Application:

The research addresses the challenge of integer factorization, which underpins the security of the RSA encryption system. By converting the factorization problem into a combinatorial optimization problem, the study uses quantum annealing to find the prime factors of a special class of integers (those where the two prime factors differ at only two bits), thus potentially undermining RSA-2048 encryption security.

Unexpected Findings:

  • Quantum Annealing Efficiency: The most surprising result is the efficiency of quantum annealing in solving a problem considered computationally infeasible for classical computers. This suggests that quantum computers might be closer to practical cryptanalysis than previously thought.

  • Special Integer Factorization: The ability to factorize special integers with only 6 qubits is unexpected, as it bypasses the need for a large number of qubits typically assumed necessary for quantum factorization.

  • Implications for RSA Security: The success in factoring RSA-2048, albeit for special integers, is alarming because it indicates that quantum computers might pose a threat to RSA encryption sooner than anticipated.

Key Terms:

  • Quantum Annealing (QA): A heuristic quantum algorithm that uses quantum tunneling to find the global minimum of an objective function, particularly effective in solving combinatorial optimization problems.

  • RSA Encryption: A widely used public-key cryptosystem based on the difficulty of factoring the product of two large prime numbers.

  • Integer Factorization: The decomposition of an integer into a product of smaller integers, which is computationally hard for large numbers on classical computers.

  • Ising Model: A mathematical model of ferromagnetism in statistical mechanics, used here to represent the optimization problem in quantum annealing.

  • Hamiltonian: In quantum mechanics, a mathematical operator corresponding to the total energy of the system, used in the context of quantum annealing to define the problem space.

  • Quantum Tunneling: A quantum mechanical phenomenon where particles can pass through barriers that classical physics would deem impenetrable, crucial for escaping local minima in optimization problems.

Approach:

  1. Outline the Research Methodology:
  2. Problem Transformation: Convert integer factorization into a combinatorial optimization problem.
  3. Quantum Annealing: Utilize D-Wave's quantum annealing hardware to perform the optimization.
  4. Data Collection: Collect results from multiple annealing runs to verify the consistency of solutions.

  5. Analysis: Analyze the annealing outcomes to ensure they represent valid factorizations.

  6. Describe Problem-Solving Techniques:

  7. Binary Multiplication Table: Construct a binary multiplication table to represent the factorization problem.
  8. Objective Function: Define an objective function based on the multiplication table, which guides the quantum annealing process.
  9. Quantum Annealing Process: The system evolves from an initial state to the ground state of the final Hamiltonian, which corresponds to the solution of the factorization problem.
  10. Classical Post-Processing: After obtaining annealing results, use classical methods to derive the actual prime factors.

Results and Evaluation:

  1. Key Findings:
  2. Successfully factored a 2048-bit integer using quantum annealing, marking a milestone in cryptanalysis.

  3. The method's efficiency for special integers suggests potential vulnerabilities in RSA encryption.

  4. Quantitative Results:

  5. RSA-2048 Factorization: The experiment successfully factored integers with a size of 2^2048 bits, specifically those where the prime factors differ by only two bits.

  6. Notable Achievements:

  7. First known factorization of an RSA-2048 integer using quantum computing.
  8. Verification of quantum annealing as a viable method for cryptanalysis, surpassing previous benchmarks.

Practical Deployment and Usability:

  • Real-World Applicability: This method can be applied to identify and potentially break RSA keys designed with certain vulnerabilities or special properties, guiding future key generation practices.
  • Ease of Use: While the quantum annealing process itself is automated, setting up the problem for quantum computation requires specialized knowledge in quantum algorithms and classical post-processing.
  • Examples:
  • Cryptographic Key Design: It can inform cryptographic designers about potential weaknesses in RSA key generation.
  • Cryptanalysis: It could be used by security researchers to test the strength of RSA keys or to simulate attacks on cryptographic systems.

Conflict of Interest:

  • Financial Interests: The authors are affiliated with institutions that might benefit from advancing quantum computing technologies.
  • Research Bias: There might be an inherent interest in promoting the capabilities of the D-Wave quantum computer, though the paper does acknowledge limitations and future research needs.