toy-rsa.py

#!/usr/bin/env python3

# toy RSA key generation/encryption/decryption
# this is only a demonstration of the underlying math - extremely unsafe!
# unmodified textbook RSA is both malleable and semantically insecure.

import subprocess
from gmpy import invert # requires gmpy for modular inversion

def ascii2int(string): # function for converting an ascii string to a single integer so that we can do math on it
    textint = 0
    for char in string:
        textint = textint * 256 + ord(char) # multiply the current integer before adding the ascii value of each character to it
    return(textint)

def int2ascii(integer): # function for converting an ascii string encoded as a single integer back to an ascii string
    newtext = ""
    while integer > 0:
        currentchar = integer % 256 # we strip off each encoded char, right to left, by checking integer mod 256
        newtext = chr(currentchar) + newtext # prepend the current decoded string with our result
        integer -= currentchar # subtract the result so we get a multiple of 256
        integer = integer // 256 # and divide by 256 so we can move on to the next encoded character
    return(newtext)

opensslbin = "/usr/local/Cellar/openssl/1.0.2g/bin/openssl" # requires openssl >= 1.0.0 to generate random primes

print("\n############ KEY GENERATION ############\n")

keysize = 256 # in bits

# randomly generate two prime numbers on the order of 2^keysize - 1 bits

print("generating a %s-bit modulus" % keysize)
p = int(subprocess.check_output([str(opensslbin),'prime','-generate','-bits',str(keysize-1)]))
print("random large prime p = %s" % format(p, 'x'))
q = int(subprocess.check_output([str(opensslbin),'prime','-generate','-bits',str(keysize-1)]))
print("random large prime q = %s" % format(q, 'x'))

# modulus n is p * q. n is public

n = p * q
print("\nmodulus n (p * q) = %s" % format(n, 'x'))

# now we need to calculate phi (euler's totient function) of n. 
# this is simply the count of numbers in the set of order n coprime to n. 
# per euler's generalization of fermat's little theorem, we can calculate phi of x simply: 
# where x is prime, phi(x) = x - 1. since n is not prime, we need to subtract 1 from each of the prime factors of n.

φn = (p - 1) * (q - 1)
print("\nφ(n) = (p - 1) * (q - 1) = %s" % format(φn, 'x'))

# the last step in key 

e = 0x10001 # e, the public exponent used for encryption, is usually statically set to 2^16 + 1 for performance reasons
print("\npublic/encryption exponent e (statically set) = %s" % format(e, 'x'))

d = int(invert(e, φn)) # d, the private exponent used for decryption, is the modular inversion (gcd(e, d) mod n = 1) of e
print("private/decryption exponent d (modular inversion of e mod φ(n)) = %s" % format(d, 'x'))


print("\n############ ENCRYPTION ############\n")

cleartext = input("enter text to encrypt (encoded length must be less than keysize): ")
m = ascii2int(cleartext) # convert plaintext ascii string to an int, m, that we can perform modular exponentiation on
print("\nencoded cleartext as integer m: %s" % format(m, 'x'))

c = pow(m, e, n) # encrypt using public key (e, n) by performing m ^ e mod n
print("\nciphertext (m ^ e mod n): %s" % format(c, 'x'))


print("\n############ DECRYPTION ############\n")

newclearint = pow(c, d, n) # decrypt using private key (d, n) by performing c ^ d mod n
print("decrypted ciphertext as int (c ^ d mod n): %s" % format(newclearint, 'x'))
print("decrypted ciphertext: %s" % int2ascii(newclearint)) # and convert the encoded string back to ascii