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
You can’t perform that action at this time.