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
#
# 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s