Question

Write a program in Python implement the RSA algorithm for cryptography.

Set up:

1.Choose two large primes, p and q. (There are a number of sites on-line where you can find large primes.)

2.Compute n = p * q, and Φ = (p-1)(q-1).

3.Select an integer e, with 1 < e < Φ , gcd(e, Φ) = 1.

4.Compute the integer d, 1 < d < Φ such that ed ≡ 1 (mod Φ). The numbers e and d are called inverses (mod Φ). To do this, I suggest two possibilities:

a)Research the BigInteger class in Java. It has a method to compute inverses modulo a specified number. (It also has other methods that would be useful!)

b)Look up the Extended Euclidean Algorithm. This is an algorithm to find d. Save this number d in a constant or variable.

5. (Make n and e public)

Encryption:

1. Convert the message into numbers, using the ASCII representation for characters. (For example, in ASCII, A = 65, B = 66, ... , space = 32, period = 46. You may find an ASCII table online.)

2. Obtain the public key (n, e) of who you want to send a message to. (You should choose yourself for testing purposes. Then try a classmate's.)

3. Encipher each letter (now a number, say m) by computing c ≡ m^e (mod n).

Decryption:

1.When you receive a string of numbers, such as 1743 452 625, use your private key d to compute 1743^d (mod n), 452^d (mod n) and 625^d (mod n). This n is from your public key.

2.Take the results of these and translate back into letters, using the same scheme as above.

Answer 1

This is Python 3 Code.

rsa.py

from random import randrange, getrandbits
from itertools import repeat
from functools import reduce

def getPrime(n):
"""Get a n-bit pseudo-random prime"""
def isProbablePrime(n, t = 7):
"""Miller-Rabin primality test"""
def isComposite(a):
"""Check if n is composite"""
if pow(a, d, n) == 1:
return False
for i in range(s):
if pow(a, 2 ** i * d, n) == n - 1:
return False
return True

assert n > 0
if n < 3:
return [False, False, True][n]
elif not n & 1:
return False
else:
s, d = 0, n - 1
while not d & 1:
s += 1
d >>= 1
for _ in repeat(None, t):
if isComposite(randrange(2, n)):
return False
return True   

p = getrandbits(n)
while not isProbablePrime(p):
p = getrandbits(n)
return p

def inv(p, q):
"""Multiplicative inverse"""
def xgcd(x, y):
"""Extended Euclidean Algorithm"""
s1, s0 = 0, 1
t1, t0 = 1, 0
while y:
q = x // y
x, y = y, x % y
s1, s0 = s0 - q * s1, s1
t1, t0 = t0 - q * t1, t1
return x, s0, t0

s, t = xgcd(p, q)[0:2]
assert s == 1
if t < 0:
t += q
return t

def genRSA(p, q):
"""Generate public and private keys"""
phi, mod = (p - 1) * (q - 1), p * q
if mod < 65537:
return (3, inv(3, phi), mod)
else:
return (65537, inv(65537, phi), mod)

def text2Int(text):
"""Convert a text string into an integer"""
return reduce(lambda x, y : (x << 8) + y, map(ord, text))

def int2Text(number, size):
"""Convert an integer into a text string"""
text = "".join([chr((number >> j) & 0xff)
for j in reversed(range(0, size << 3, 8))])
return text.lstrip("\x00")

def int2List(number, size):
"""Convert an integer into a list of small integers"""
return [(number >> j) & 0xff
for j in reversed(range(0, size << 3, 8))]

def list2Int(listInt):
"""Convert a list of small integers into an integer"""
return reduce(lambda x, y : (x << 8) + y, listInt)

def modSize(mod):
"""Return length (in bytes) of modulus"""
modSize = len("{:02x}".format(mod)) // 2
return modSize

def encrypt(ptext, pk, mod):
"""Encrypt message with public key"""
size = modSize(mod)
output = []
while ptext:
nbytes = min(len(ptext), size - 1)
aux1 = text2Int(ptext[:nbytes])
assert aux1 < mod
aux2 = pow(aux1, pk, mod)
output += int2List(aux2, size + 2)
ptext = ptext[size:]
return output

def decrypt(ctext, sk, p, q):
"""Decrypt message with private key
using the Chinese Remainder Theorem"""
mod = p * q
size = modSize(mod)
output = ""
while ctext:
aux3 = list2Int(ctext[:size + 2])
assert aux3 < mod
m1 = pow(aux3, sk % (p - 1), p)
m2 = pow(aux3, sk % (q - 1), q)
h = (inv(q, p) * (m1 - m2)) % p
aux4 = m2 + h * q
output += int2Text(aux4, size)
ctext = ctext[size + 2:]
return output

if __name__ == "__main__":

from math import log10
from time import time

def printHexList(intList):
"""Print ciphertext in hex"""
for index, elem in enumerate(intList):
if index % 32 == 0:
print()
print("{:02x}".format(elem), end = "")
print()

def printLargeInteger(number):
"""Print long primes in a formatted way"""
string = "{:02x}".format(number)
for j in range(len(string)):
if j % 64 == 0:
print()
print(string[j], end = "")
print()

def testCase(p, q, msg, nTimes = 1):
"""Execute test case: generate keys, encrypt message and
decrypt resulting ciphertext"""
print("Key size: {:0d} bits".format(round(log10(p * q) / log10(2))))
print("Prime #1:", end = "")
printLargeInteger(p)
print("Prime #2:", end = "")
printLargeInteger(q)
print("Plaintext:", msg)
pk, sk, mod = genRSA(p, q)
ctext = encrypt(msg, pk, mod)
print("Ciphertext:", end = "")
printHexList(ctext)
ptext = decrypt(ctext, sk, p, q)
print("Recovered plaintext:", ptext, "\n")

# First test: RSA-129 (see http://en.wikipedia.org/wiki/RSA_numbers#RSA-129)
p1 = 3490529510847650949147849619903898133417764638493387843990820577
p2 = 32769132993266709549961988190834461413177642967992942539798288533
testCase(p1, p2, "The Magic Words are Squeamish Ossifrage", 1000)
  
OUTPUT:
$python rsa.py
Key size: 425 bits
Prime #1:
87c296ed480f9ab17885decd31197d617779c0dac70c3234996e1
Prime #2:
4fa84812157119acc8ecca98c404b2e5ee24ce18f60ea818091895
Plaintext: The Magic Words are Squeamish Ossifrage
Ciphertext:
000100d00ec048028f8de9998bfcdb271ad5d34ab70a3990ebdfdd30a32ae15e
1ae01ccda1945493cc02be7d739ded0c56d8cd9c996ee8
Recovered plaintext: The Magic Words are Squeamish Ossifrage