Question

Problem 3

In RSA, we will consider what happens when Alice makes the mistake of choosing p,q

too close together. Her method is as follows. She chooses p

a random large prime, and then chooses q

to be the smallest prime greater than p

. You are Eve, and Alice's public key is (e,n)

where e=13

and n

is

4149515568880992958512407863691161151012446232242436899995657329690652811412991293413200434314186514261288537546721977134041420919065144782418033157091025480140853599374890776565691

(Make sure to copy all of n, which has 181

digits).

Find Alice's private key d

using python

Answer 1

Python code for finding the Alice's private key using p as a random prime number and q is the smallest prime which is greater than p.  

import random
def isPrime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(n**0.5)
f = 5
while f <= r:
if n%f == 0: return False
if n%(f+2) == 0: return False
f +=6
return True
primes = [i for i in range(1,1000) if isPrime(i)]
p = random.choice(primes)
primes2 = [i for i in range(p,2000) if isPrime(i)]
q = random.choice(primes2)
n=p*q;
print("n = p * q = " + str(n) + "\n")
phi=(p-1)*(q-1)
print("Euler's function Z)]: " + str(phi) + "\n")
def gcd(a, b):
while b != 0:
c = a % b
a = b
b = c
return a
def modinv(a, m):
for x in range(1, m):
if (a * x) % m == 1:
return x
return None
e=13
d=modinv(e,phi)
print("Your private key is (d=" + str(d))
def encrypt_block(m):
c = modinv(m**e, n)
if c == None: print('No modular multiplicative inverse for block ' + str(m) + '.')
return c
def decrypt_block(c):
m = modinv(c**d, n)
if m == None: print('No modular multiplicative inverse for block ' + str(c) + '.')
return m
def encrypt_string(s):
return ''.join([chr(encrypt_block(ord(x))) for x in list(s)])
def decrypt_string(s):
return ''.join([chr(decrypt_block(ord(x))) for x in list(s)])