Skip to content

Instantly share code, notes, and snippets.

@tylerkerr

tylerkerr/toy-rsa.py

Last active Oct 19, 2016
Embed
What would you like to do?
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment