Breaking RSA Encryption - Shor's Quantum Algorithm

Sep 24, 2023
   39

Python:


1. Create a '.py' file called RSA_module and copy and paste the following into it:


from __future__ import unicode_literals
from math import sqrt
import random
from random import randint as rand


def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)


def mod_inverse(a, m):
for x in range(1, m):
if (a * x) % m == 1:
return x
return -1


def isprime(n):
if n < 2:
return False
elif n == 2:
return True
else:
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True


def generate_keypair(keysize):
p = rand(1, 1000)
q = rand(1, 1000)
nMin = 1 << (keysize - 1)
nMax = (1 << keysize) - 1
primes = [2]
start = 1 << (keysize // 2 - 1)
stop = 1 << (keysize // 2 + 1)
if start >= stop:
return []
for i in range(3, stop + 1, 2):
for p in primes:
if i % p == 0:
break
else:
primes.append(i)
while (primes and primes[0] < start):
del primes[0]
while primes:
p = random.choice(primes)
primes.remove(p)
q_values = [q for q in primes if nMin <= p * q <= nMax]
if q_values:
q = random.choice(q_values)
break
print(p, q)
n = p * q
phi = (p - 1) * (q - 1)
e = random.randrange(1, phi)
g = gcd(e, phi)
while True:
e = random.randrange(1, phi)
g = gcd(e, phi)
d = mod_inverse(e, phi)
if g == 1 and e != d:
break


return ((e, n), (d, n))


def encrypt(msg_plaintext, package):
e, n = package
msg_ciphertext = [pow(ord(c), e, n) for c in msg_plaintext]
return ''.join(map(lambda x: str(x), msg_ciphertext)), msg_ciphertext


def decrypt(msg_ciphertext, package):
d, n = package
msg_plaintext = [chr(pow(c, d, n)) for c in msg_ciphertext]
return (''.join(msg_plaintext))


2. Import the module into your project:


import RSA_module

bit_length = int(input("Enter bit_length: "))


3. Generate and Encrypt your RSA keys:

public, private = RSA_module.generate_keypair(2**bit_length)

msg = input("\nWrite message: ")
encrypted_msg, encryption_obj = RSA_module.encrypt(msg, public)

print("\nEncrypted message: " + encrypted_msg)

decrypted_msg = RSA_module.decrypt(encryption_obj, private)

print("\nDecrypted message using RSA Algorithm: " + decrypted_msg)


4. Utilize the Shor's algorithm to crack the RSA keys:

from math import gcd,log
from random import randint
import numpy as np
from qiskit import *

qasm_sim = qiskit.Aer.get_backend('qasm_simulator')

def period(a,N):
available_qubits = 16
r=-1
if N >= 2**available_qubits:
print(str(N)+' is too big for IBMQX')
qr = QuantumRegister(available_qubits)
cr = ClassicalRegister(available_qubits)
qc = QuantumCircuit(qr,cr)
x0 = randint(1, N-1)
x_binary = np.zeros(available_qubits, dtype=bool)
for i in range(1, available_qubits + 1):
bit_state = (N%(2**i)!=0)
if bit_state:
N -= 2**(i-1)
x_binary[available_qubits-i] = bit_state
for i in range(0,available_qubits):
if x_binary[available_qubits-i-1]:
qc.x(qr[i])
x = x0
while np.logical_or(x != x0, r <= 0):
r+=1
qc.measure(qr, cr)
for i in range(0,3):
qc.x(qr[i])
qc.cx(qr[2],qr[1])
qc.cx(qr[1],qr[2])
qc.cx(qr[2],qr[1])
qc.cx(qr[1],qr[0])
qc.cx(qr[0],qr[1])
qc.cx(qr[1],qr[0])
qc.cx(qr[3],qr[0])
qc.cx(qr[0],qr[1])
qc.cx(qr[1],qr[0])
result = execute(qc,backend = qasm_sim, shots=1024).result()
counts = result.get_counts()
#print(qc)
results = [[],[]]
for key,value in counts.items():
results[0].append(key)
results[1].append(int(value))
s = results[0][np.argmax(np.array(results[1]))]
return r

def shors_breaker(N):
N = int(N)
while True:
a=randint(0,N-1)
g=gcd(a,N)
if g!=1 or N==1:
return g,N//g
else:
r=period(a,N)
if r % 2 != 0:
continue
elif pow(a,r//2,N)==-1:
continue
else:
p=gcd(pow(a,r//2)+1,N)
q=gcd(pow(a,r//2)-1,N)
if p==N or q==N:
continue
return p,q

def modular_inverse(a,m):
a = a % m;
for x in range(1, m) :
if ((a * x) % m == 1) :
return x
return 1

N_shor = public[1]
#assert N_shor>0,"Input must be positive"
p,q = shors_breaker(N_shor)
phi = (p-1) * (q-1)
d_shor = modular_inverse(public[0], phi)


5. Break the RSA encryption using Shor's Algorithm keys:

decrypted_msg = RSA_module.decrypt(encryption_obj, (d_shor,N_shor))

print('\nMessage Cracked using Shors Algorithm: ' + decrypted_msg + "\n")