# RSA implementation in Python

This Python script below implements the basic RSA encryption and decryption operations without any concern about padding or character encoding. Nevertheless, it has all the primitive machinery needed to encrypt and decrypt messages using the RSA public-key algorithm. The getprime() function is in charge of generating primes of the required size and, for this purpose, uses a probabilistic algorithm, the Miller-Rabin primality test. The inv() function, which calculates modular multiplicative inverses, gets a helping hand from the Extended Euclidean algorithm xgcd() function. The genRSA() function is pretty straightforward: it generates the standard public-key small exponent, 3 or 65537 (hex 10001), depending on the size of modulus (a small public exponent speeds up both the encryption and signature verification operations).

```#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: RSA implementation in Python 3
#
# Date: 2012-01-30
#
#          (CC BY-NC-SA 3.0)
#===========================================================
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)

# Second test: random primes (key size: 512 to 4096 bits)
for n in [256, 512, 1024, 2048]:
t1 = time()
p5 = getPrime(n)
t2 = time()
print("Elapsed time for {:0d}-bit prime ".format(n), end = "")
print("generation: {:0.3f} s".format(round(t2 - t1, 3)))
t3 = time()
p6 = getPrime(n)
t4 = time()
print("Elapsed time for {:0d}-bit prime ".format(n), end = "")
print("generation: {:0.3f} s".format(round(t4 - t3, 3)))
testCase(p5, p6, "It's all greek to me")
```

The first test uses the famous 425-bit key pair belonging to RSA-129, a challenge published in Martin Gardner’s column in Scientific American back in 1977. RSA-129 owes its name to the 129-digit number that expresses the product of two (unknown at the time) primes.

```RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429 35706935245733897830597123563958705058989075147599290026879543541
```

This challenge, posed by the inventors of the RSA algorithm (Rivest, Shamir & Adleman), was solved only in 1994. The decrypted plaintext was the phrase “The Magic Words are Squeamish Ossifrage”. The second test was done with pairs of randomly generated primes. Their key sizes (as a matter of fact, the size of the modulus) are 512, 1024 and 2048 bits (the key size most used in SSL certificates is 1024 bits). The output of this Python script is shown below.

```Key size: 425 bits
Prime #1:
87c296ed480f9ab17885decd31197d617779c0dac70c3234996e1
Prime #2:
4fa84812157119acc8ecca98c404b2e5ee24ce18f60ea818091895
Plaintext: The Magic Words are Squeamish Ossifrage
Ciphertext:
1ae01ccda1945493cc02be7d739ded0c56d8cd9c996ee8
Recovered plaintext: The Magic Words are Squeamish Ossifrage

Elapsed time for 256-bit prime generation: 0.108 s
Elapsed time for 256-bit prime generation: 0.018 s
Key size: 511 bits
Prime #1:
7a29e838f6afe351c24b0dfee0b12d32e092c6ec129382b75b224f749e9785c9
Prime #2:
caffe728fa460b4f009a7647bdbb0763868206942a4ced79aefd36a6b05f539b
Plaintext: It's all greek to me
Ciphertext:
00005741fdf3f6f20fc16524c9a1c80f62e7a293aaff5238f319692e4c469443
10d2272ed76d6a9a884372c2eae03e2d3b8c10df04353d459659a3f8c3e63be3
2c6d
Recovered plaintext: It's all greek to me

Elapsed time for 512-bit prime generation: 0.162 s
Elapsed time for 512-bit prime generation: 0.576 s
Key size: 1015 bits
Prime #1:
5ef0fcba9c6044ecd3c98aa22981e1f75f8779ba5f72fa33ab4da89d4abfc357
Prime #2:
2aabce36a668c2f8e161521238d2be8541d286e612b6572e4c1531f8218dfe0e
08de2e177b02c2ab1a76056eca13920e2847bfdffffdb6b2b9fe874849c3637
Plaintext: It's all greek to me
Ciphertext:
00006d1c01974161e2c4710ec423076bbab8107cf31d2d2ecfd6127ca6dc142e
aa7f37d93281222684227892c82575ef93491ffa802003efac9085e3e8076000
a205c367ed6d7270e1ab02da80522264238e3cb93aff81e53eeec7910d5013c8
a4
Recovered plaintext: It's all greek to me

Elapsed time for 1024-bit prime generation: 7.189 s
Elapsed time for 1024-bit prime generation: 8.921 s
Key size: 2047 bits
Prime #1:
7843d991e4fa29466f4e0fa385f0b8612db5d51c0f09f0fca801339155cd1ca2
fde3b810569de371e99e8d1e3d127a9b4d7f07944d64c7d9da973252b73dd1ed
847183c1a855b65817411cfea22c05b58764d5bb016770feef93d6cb5e6274e3
fce2c5fb251bb41a8ba879cd5a2d6755c591e921c6aa08327ef6b6e8f1cf1a1b
Prime #2:
e751af1ed509106fdd814d52778da0cf6998b768bafd16a10ec91c4becf05856
9e96007661d4525cb0b40b20247aa879657c4550d3d58a74ab23666b504febaf
5de5b40f3cc7b8c766e5d426fa37d9832b91fef718e4f117984168a2eeb087bc
Plaintext: It's all greek to me
Ciphertext:
000056ce1bab323cc03876dc786cdc9f53e406a4e321a2e8233ed648f93d0026