public
Last active

RSA Explained in Python

  • Download Gist
rsa.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
#!/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)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.