Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# tylerkerr/toy-rsa.py

Last active Oct 19, 2016
 #!/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
to join this conversation on GitHub. Already have an account? Sign in to comment