#!/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