Skip to content

Instantly share code, notes, and snippets.

@nathandarnell
Forked from tylerl/rsa.py
Created January 13, 2017 19:42
Show Gist options
  • Save nathandarnell/eda20076cf682e9b8eae83889352ba47 to your computer and use it in GitHub Desktop.
Save nathandarnell/eda20076cf682e9b8eae83889352ba47 to your computer and use it in GitHub Desktop.
RSA Explained in Python
#!/usr/bin/env python
# This example demonstrates RSA public-key cryptography in an
# easy-to-follow manner. It works on integers alone, and uses much smaller numbers
# for the sake of clarity.
#####################################################################
# First we pick our primes. These will determine our keys.
#####################################################################
# Pick P,Q,and E such that:
# 1: P and Q are prime; picked at random.
# 2: 1 < E < (P-1)*(Q-1) and E is co-prime with (P-1)*(Q-1)
P=97 # First prime
Q=83 # Second prime
E=53 # usually a constant; 0x10001 is common, prime is best
#####################################################################
# Next, some functions we'll need in a moment:
#####################################################################
# Note on what these operators do:
# % is the modulus (remainder) operator: 10 % 3 is 1
# // is integer (round-down) division: 10 // 3 is 3
# ** is exponent (2**3 is 2 to the 3rd power)
# Brute-force (i.e. try every possibility) primality test.
def isPrime(x):
if x%2==0 and x>2: return False # False for all even numbers
i=3 # we don't divide by 1 or 2
sqrt=x**.5
while i<sqrt:
if x%i==0: return False
i+=2
return True
# Part of find_inverse below
# See: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
def eea(a,b):
if b==0:return (1,0)
(q,r) = (a//b,a%b)
(s,t) = eea(b,r)
return (t, s-(q*t) )
# Find the multiplicative inverse of x (mod y)
# see: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
def find_inverse(x,y):
inv = eea(x,y)[0]
if inv < 1: inv += y #we only want positive values
return inv
#####################################################################
# Make sure the numbers we picked above are valid.
#####################################################################
if not isPrime(P): raise Exception("P (%i) is not prime" % (P,))
if not isPrime(Q): raise Exception("Q (%i) is not prime" % (Q,))
T=(P-1)*(Q-1) # Euler's totient (intermediate result)
# Assuming E is prime, we just have to check against T
if E<1 or E > T: raise Exception("E must be > 1 and < T")
if T%E==0: raise Exception("E is not coprime with T")
#####################################################################
# Now that we've validated our random numbers, we derive our keys.
#####################################################################
# Product of P and Q is our modulus; the part determines as the "key size".
MOD=P*Q
# Private exponent is inverse of public exponent with respect to (mod T)
D = find_inverse(E,T)
# The modulus is always needed, while either E or D is the exponent, depending on
# which key we're using. D is much harder for an adversary to derive, so we call
# that one the "private" key.
print "public key: (MOD: %i, E: %i)" % (MOD,E)
print "private key: (MOD: %i, D: %i)" % (MOD,D)
# Note that P, Q, and T can now be discarded, but they're usually
# kept around so that a more efficient encryption algorithm can be used.
# http://en.wikipedia.org/wiki/RSA#Using_the_Chinese_remainder_algorithm
#####################################################################
# We have our keys, let's do some encryption
#####################################################################
# Here I only focus on whether you're applying the private key or
# applying the public key, since either one will reverse the other.
import sys
print "Enter \">NUMBER\" to apply private key and \"<NUMBER\" to apply public key; \"Q\" to quit."
while True:
sys.stdout.write("? ")
line=sys.stdin.readline().strip()
if not line: break
if line=='q' or line=='Q': break
if line[0]=='<': key = E
elif line[0]=='>': key = D
else:
print "Must start with either < or >"
print "Enter \">NUMBER\" to apply private key and \"<NUMBER\" to apply public key; \"Q\" to quit."
continue
line=line[1:]
try: before=int(line)
except ValueError:
print "not a number: \"%s\"" % (line)
print "Enter \">NUMBER\" to apply private key and \"<NUMBER\" to apply public key; \"Q\" to quit."
continue
if before >= MOD:
print "Only values up to %i can be encoded with this key (choose bigger primes next time)" % (MOD,)
continue
# Note that the pow() built-in does modulo exponentation. That's handy, since it saves us having to
# implement that ablity.
# http://en.wikipedia.org/wiki/Modular_exponentiation
after = pow(before,key,MOD) #encrypt/decrypt using this ONE command. Surprisingly simple.
if key == D: print "PRIVATE(%i) >> %i" %(before,after)
else: print "PUBLIC(%i) >> %i" %(before,after)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment