Quantum computing with cybersecurity

A. Background knowledge for quantum computing

0. What is it?

In classical computing, it uses bits such as 0 and 1 to store information; however, in quantum computing, it brings in the concept of quantum physics, using qubits instead of bits, which allows computers to calculate and deal with larger numbers of information.

1. Qubits

In classical computing, we use bits such 0 and 1, but in quantum computing we use qubits instead. N qubits in quantum computing can exist as a superposition of the 2^N possible states. So the number of operations required to arrive at the same result is exponentially small.

---

A simple explanation and example: 2 qubits in qc can exist in 4 different states in classcial computing:
2 qubits in QC result in 4 different states in classical computing:

-	-
0	1
1	0
0	1
1	1

---

Because of this specialty, it poses a great harm to current cubersecurity, for it has the potential to find factors way faster than classical computing since encryption nowadays are mostly relied on factoriztion of big prime numbers.

2. Five main ideas of quantum computing

a. superposition

b. gates

c. measurement

d. interference

e. entanglement

3. Quantum circuits

4. Bloch Sphere

5. Myth

It's not a replacement of classical computers. It doesn't give us any particular improvement if we're just watching videos, browsing websites, etc.

B. Abstract

Rule: All students should display an abstract with their project. Abstracts should be no more than 250 words and should include the (a) the purpose of the experiment, (b) procedures used, (c ) data collected, and (d) conclusions. Abstracts should not include acknowledgments of work or procedures done by the mentor.

• Rules of ISEF

C. RSA cryptography

• RSA explanation
• Example in case:

Imagine two individuals, Alice and Bob, who want to communicate securely using RSA encryption. They each have their own pair of keys: a public key (for encryption) and a private key (for decryption).

1. Key Generation:

   • Alice:

     • Alice selects two small prime numbers, let's say p = 11 and q = 13.
     • She calculates n = p * q = 11 * 13 = 143.
     • Alice also chooses a public exponent e, often 7, which is relatively prime to (p-1)(q-1), so in this case, e = 7.
     • Her public key is (n, e) = (143, 7).
     • To calculate her private key d, she finds the modular multiplicative inverse of e modulo φ(n), where φ(n) = (p-1)(q-1) = 10 * 12 = 120.
     • The modular multiplicative inverse of 7 modulo 120 is 103, so her private key is (n, d) = (143, 103).

   • Bob:

     • Bob also follows the same steps to generate his own key pair, which includes a public key (n, e) and a private key (n, d).

2. Encryption:

   • Suppose Alice wants to send a secret message M = 42 to Bob.
   • She uses Bob's public key (n, e) = (143, 7) to encrypt the message:
     • Ciphertext C = M^e mod n = 42^7 mod 143 = 42,144,564,809,848 mod 143 = 131.

3. Decryption:

   • Bob receives the ciphertext C = 131. To decrypt it, he uses his private key (n, d) = (143, 103).
   • Bob calculates M = C^d mod n = 131^103 mod 143.
   • The result of this computation, when reduced modulo 143, is M = 42.

Now, Bob has successfully decrypted the message, and the original message M = 42 is revealed.

In this simplified example, we used very small numbers for the sake of clarity. In real-world applications, the numbers involved in RSA encryption are much larger to provide strong security. The security of RSA relies on the difficulty of factoring large numbers into their prime factors.

D. Sohr's algorithm

• Sohr's algorithm explanation
• Sohr's algorithm on Qiskit
  An algorithm for quantum computing developed in 1994 by Peter Shor.
  

E. Experiment design

Idea: Encrypt different plaintexts using different prime numbers through RSA algorithm, but the prime numbers will keep being added up. Then, I'll decrypt the encrypted messages with both classical and quantum computing, and then compare the time duration of decryption between them. For the quantum computing, I'll use the Qiskit in order to program on quantum computer, using pycharm for the classical. I'm assuming that the classical computing can no longer decrypt after a certain prime number, which proves the threat of quantum computing and the vulnerability of classical ones.

---

Variables: plaintexts, prime numbers

​​​​1. Change in prime numbers 
​​​​
​​​​2. Change in plaintexts

F. Qiskit

• Qiskit
  A open-source toolkit for useful quantum computing.
  Use this to simulate how quantum computing decrypt the encrypted messages.

G. Pycharm

Source code: