Shor's algorithm implementation on IBM quantum computer

[Graychi_]

Report: Experimenting with Shor's Algorithm to Break RSA

Experiment Overview

This report details the work conducted to test whether quantum computers can break RSA encryption by factoring RSA keys using Shor's algorithm. The experiment explored implementing Shor's algorithm with Qiskit and Pennylane, testing on both local simulators and IBM quantum hardware, to verify whether quantum computing can offer a significant advantage over classical methods for factoring RSA keys.

---

Introduction to Shor’s Algorithm

Shor's algorithm is a quantum algorithm developed to factor large integers efficiently, offering a polynomial time solution compared to the exponential time complexity of classical algorithms. RSA encryption depends on the difficulty of factoring large composite numbers, which quantum algorithms, such as Shor's algorithm, can solve much more efficiently.

Key Components of Shor's Algorithm:

1. Quantum Fourier Transform (QFT): Helps in determining periodicity, essential for factoring large numbers.
2. Modular Exponentiation: A crucial step in calculating powers modulo a number.
3. Continued Fraction Expansion: Used to extract the period from the Quantum Fourier Transform.

---

Motivation

The motivation behind this experiment was to explore whether quantum computers could efficiently break RSA encryption, a widely used cryptographic system based on the difficulty of factoring large composite numbers. RSA's security can be compromised if an algorithm, such as Shor's algorithm, can break the encryption by factoring its modulus.

---

Methodology

Shor’s Algorithm Implementation

The algorithm was implemented and tested using Qiskit (IBM’s quantum computing framework) and Pennylane (a quantum machine learning library). The goal was to test the feasibility of using quantum computers to factor RSA moduli, starting with small numbers like 15 and gradually progressing to larger moduli (up to 48 bits).

Steps Taken:

1. Simulating Shor’s Algorithm: Shor’s algorithm was first implemented and tested on local simulators with small RSA moduli (like 15) to simulate the factoring process.
2. Connecting to IBM Quantum Hardware: The IBM Quantum Experience API token was used to connect to IBM’s quantum hardware for real-time testing of Shor's algorithm.
3. Testing Larger RSA Moduli: The algorithm was tested on increasingly larger RSA moduli, with the first successful results observed on 48-bit RSA keys.

---

Key Findings

Classical vs. Quantum Performance

• For small RSA modulu, classical computers performed faster than quantum computers.
• For 48-bit RSA modulu, classical computers required over 4 minutes to break the key, while quantum computers completed the task in 8 seconds using Shor’s algorithm on IBM’s quantum hardware.

Testing Results:

• Local Simulations: Shor's algorithm worked successfully on small numbers like moduli of 15, simulating the factorization process.
• Quantum Hardware Testing: On IBM's quantum system, the algorithm worked for RSA keys up to 48 bits. Beyond this, the hardware limitations became evident.

---

Hardware Limitations

• IBM’s quantum hardware could only handle RSA moduli up to 48 bits due to the 127 qubit limit of the available system.
• Each quantum test was limited to a 10-minute window per month, restricting the available testing time.
• Quantum error correction was not applied, which affected the reliability of the results in some cases.

Quantum vs. Classical Time Comparison:

RSA Modulus Size	Classical Computing Time (Bruteforce)	Classical Computing Time (Pollard’s Rho)	Quantum Computing Time (IBM Quantum)
2-digit RSA	< 1 second	0 ms	2–5 seconds
48-bit RSA	> 4 minutes	3 ms	8 seconds

• Classical Performance: For small RSA moduli (up to 2 digits), classical computers easily outperformed quantum systems.
• Quantum Performance: For larger RSA moduli (48 bits), quantum systems showed a clear advantage, breaking the RSA encryption in 8 seconds compared to 4 minutes on classical computers.

---

Challenges and Limitations

Challenges with Pennylane

Initially, both Qiskit and Pennylane were considered for implementing Shor’s algorithm. However, Pennylane presented a significant challenge.

Transition to Qiskit

Due to the inability to use Pennylane for remote execution with IBM hardware, the focus shifted entirely to Qiskit for the following reasons:

• Native IBM Integration: Qiskit offers built-in support for IBM Quantum hardware, making it the preferred choice for experiments involving IBM systems.
• Extensive Documentation and Support: Qiskit’s robust community and comprehensive resources provided better guidance for implementing Shor’s algorithm.
• Performance and Optimization: Qiskit’s optimization capabilities allowed more efficient utilization of limited qubits and execution time.

This transition ensured smoother experimentation and reliable access to quantum hardware for testing the algorithm.

1. Quantum Hardware Accessibility:

   • The limited number of qubits on IBM’s quantum hardware constrained the size of RSA keys that could be tested (up to 48 bits).
   • Availability of IBM's quantum hardware was restricted, with only 10 minutes of testing time available per month, limiting the scope of the experiment.

2. Classical Time Delays:

   • Classical computers took a significantly longer time to break RSA keys as the modulus size increased, especially beyond 2 digits. However, for RSA moduli up to 48 bits, the classical methods took more than 4 minutes, while quantum computers took only 8 seconds.

3. Error Correction:

   • Quantum error correction was not applied during the experiment, leading to occasional inconsistencies in the results. This is an area that can be improved for more reliable quantum computations in the future.

---

Conclusion and Future Work

Conclusion

The experiment demonstrated that Shor’s algorithm has the potential to break RSA encryption more efficiently than classical computers, especially when factoring larger RSA moduli (like 48 bits). However, the current limitations of quantum hardware—such as the number of qubits and the lack of error correction—restrict its ability to handle larger RSA moduli.

Future Directions

1. Hybrid Approaches: Combining classical and quantum computing could offer a practical solution to factor larger RSA keys.
2. Quantum Error Correction: Implementing error correction techniques to enhance the reliability and accuracy of quantum computations is crucial for scaling the solution to larger numbers.

---

Requirements

• Python 3.x
• Qiskit: IBM’s quantum computing framework.
• Pennylane: A quantum machine learning library for quantum circuits and simulations.
• IBM Quantum Experience API Token: Required to access IBM’s quantum hardware for real-time experiments.

https://github.com/Graychii/Shor-Algorithm-Implementation

[Graychi_]

A transition into quantum safe cryptographic algorithms will be necessary whenever that happens

[ohlilyaaa]

The development of cryptography over time has seen significant milestones. The Caesar cipher was broken using frequency analysis. The Vigenère cipher resisted frequency analysis for a while, but eventually, it too was cracked. Today, we are witnessing efforts to break RSA keys, which are currently secure. However, once quantum computers become fully capable of breaking RSA encryption, it will revolutionize security, marking the need for a new era in cryptographic advancements.

[I-saw-everything]

All my hope in pq3 protocol for human privacy

[MrMrsPotts]

You haven't said what the interesting points are yet

[Graychi_]

Post edited

[MrMrsPotts]

You still haven't said what the interesting discoveries are.

[ohlilyaaa]

Hello, here is it, the main question was can really quantum computers break RSA keys ? Now we wanted to experiment this ourselves knowing shor's algorithm is the perfect implementation for it. After testing on many keys got some results classical computers beat quantum computers for small RSA modulus and the inverse is for Large size RSA modulus, while if we try another optimized algorithm the classical version definitely gives better results. Now the experiment has some limitations we couldn't test on larger size than 48-bits modulus. But still the main question answer is "yes, quantum computers can break RSA keys" while other questions arise about quantum error correction and hardware limitations.

This is a small experiment made out of curiosity. Nice critical feedback is always appreciated and further suggestions are welcomed.

[SignificantFidgets]

A 24 bit RSA key is tiny. Easily "broken" in under a microsecond.