In this problem you will implement the three component algorithms of the RSA cry

Question

In this problem you will implement the three component algorithms of the RSA cryptographic protocol described in lecture.

Define a Python function generate(k) that takes a single integer input k and returns a tuple (n,e,d) corresponding to the public values n and e and private key d in the RSA cryptographic protocol. The output n must be the product of two distinct, randomly chosen k-digit primes. You may import and use the Python random number generator (from random import random or from random import randint), and you may want to reuse the extended Euclidean algorithm implementation provided in the previous homework assignment.

Define a Python function encrypt(m, t) that takes two inputs: an integer m and a tuple (n,e) representing an RSA public key. It should return a single integer: the RSA ciphertext c.

Define a Python function decrypt(c, t) that takes two inputs: an integer c representing the ciphertext and a tuple of two integers (n,d) representing an RSA private key. It should decrypt c and return the original message m.

Explanation / Answer

import random
'''
Euclid's algorithm for determining the greatest common divisor
Use iteration to make it faster for larger integers
'''
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
'''
Euclid's extended algorithm for finding the multiplicative inverse of two numbers
'''
def multiplicative_inverse(e, phi):
d = 0
x1 = 0
x2 = 1
y1 = 1
temp_phi = phi
while e > 0:
temp1 = temp_phi/e
temp2 = temp_phi - temp1 * e
temp_phi = e
e = temp2
x = x2- temp1* x1
y = d - temp1 * y1
x2 = x1
x1 = x
d = y1
y1 = y
if temp_phi == 1:
return d + phi
'''
Tests to see if a number is prime.
'''
def is_prime(num):
if num == 2:
return True
if num < 2 or num % 2 == 0:
return False
for n in xrange(3, int(num**0.5)+2, 2):
if num % n == 0:
return False
return True
def generate_keypair(p, q):
if not (is_prime(p) and is_prime(q)):
raise ValueError('Both numbers must be prime.')
elif p == q:
raise ValueError('p and q cannot be equal')
#n = pq
n = p * q
#Phi is the totient of n
phi = (p-1) * (q-1)
#Choose an integer e such that e and phi(n) are coprime
e = random.randrange(1, phi)
#Use Euclid's Algorithm to verify that e and phi(n) are comprime
g = gcd(e, phi)
while g != 1:
e = random.randrange(1, phi)
g = gcd(e, phi)
#Use Extended Euclid's Algorithm to generate the private key
d = multiplicative_inverse(e, phi)
#Return public and private keypair
#Public key is (e, n) and private key is (d, n)
return ((e, n), (d, n))
def encrypt(pk, plaintext):
#Unpack the key into it's components
key, n = pk
#Convert each letter in the plaintext to numbers based on the character using a^b mod m
cipher = [(ord(char) ** key) % n for char in plaintext]
#Return the array of bytes
return cipher
def decrypt(pk, ciphertext):
#Unpack the key into its components
key, n = pk
#Generate the plaintext based on the ciphertext and key using a^b mod m
plain = [chr((char ** key) % n) for char in ciphertext]
#Return the array of bytes as a string
return ''.join(plain)
if __name__ == '__main__':
'''
Detect if the script is being run directly by the user
'''
print "RSA Encrypter/ Decrypter"
p = int(raw_input("Enter a prime number (17, 19, 23, etc): "))
q = int(raw_input("Enter another prime number (Not one you entered above): "))
print "Generating your public/private keypairs now . . ."
public, private = generate_keypair(p, q)
print "Your public key is ", public ," and your private key is ", private
message = raw_input("Enter a message to encrypt with your private key: ")
encrypted_msg = encrypt(private, message)
print "Your encrypted message is: "
print ''.join(map(lambda x: str(x), encrypted_msg))
print "Decrypting message with public key ", public ," . . ."
print "Your message is:"
print decrypt(public, encrypted_msg)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.