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
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
# (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: 000100d00ec048028f8de9998bfcdb271ad5d34ab70a3990ebdfdd30a32ae15e 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: 37f8ab0bbdeca6af2a8a8874844472add93745cb98a6224175c6528c1e3c2f26 5ef0fcba9c6044ecd3c98aa22981e1f75f8779ba5f72fa33ab4da89d4abfc357 Prime #2: 2aabce36a668c2f8e161521238d2be8541d286e612b6572e4c1531f8218dfe0e 08de2e177b02c2ab1a76056eca13920e2847bfdffffdb6b2b9fe874849c3637 Plaintext: It's all greek to me Ciphertext: 00006d1c01974161e2c4710ec423076bbab8107cf31d2d2ecfd6127ca6dc142e aa7f37d93281222684227892c82575ef93491ffa802003efac9085e3e8076000 63780dd7ea03b1418e7cdb17dec38b533913d2e11f37de1f364dd96e559add5b 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 8ad09364d9f57c6534d5332eb78eacf9f5cdaa12f95aee44de0d1df475ec52ff Plaintext: It's all greek to me Ciphertext: 000056ce1bab323cc03876dc786cdc9f53e406a4e321a2e8233ed648f93d0026 3b9504faa72bfbf2d97b166f320344596bb2634addd2766ef9e4816841a76b95 ba3c5b899bd559222162d5580924ef073ba7118023710cebc901a20f51603acb 5a797e84ea7cf853d3b2031f3263879d3afb3d05bd74f15219b877753b3182ef a93cdfc015db601b8fd93540e1e50d1b9676e152769268039484cdd821f9291b 93f408d1e8c851fb79b143a80d7ef03629f3c11c81f8188a35076df9a88df1ba 5da77de10857a9c7238122f3818c4011a6cbe4e702c8b481789edca59ab74606 3608ca5c98f6126ddec1a3eb972021b9297c7d4d2c38f50f8105745eb3110977 f76a Recovered plaintext: It's all greek to me
I will comment on code details in another post.
João H de A Franco 