tylerl · September 24, 2011 08:27 · Dec 3, 2011 · Sep 24, 2011 · Sep 24, 2011 · Sep 24, 2011
diff --git a/rsa.py b/rsa.py
@@ -20,28 +20,32 @@
 #####################################################################
 # Next, some functions we'll need in a moment:
 #####################################################################
-# Note that "%" is the modulo operator, while // is integer (round-down) division
+# 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. slow) primality test.
+# Brute-force (i.e. try every possibility) primality test.
 def isPrime(x):
-	if x%2==0 and x>2: return False
-	i=3; sqrt=x**.5
+	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 mod_inverse(x,y):
-
-	# 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) )
-
+def find_inverse(x,y):
 	inv = eea(x,y)[0]
 	if inv < 1: inv += y #we only want positive values
 	return inv
@@ -66,7 +70,7 @@ def eea(a,b):
 MOD=P*Q
 
 # Private exponent is inverse of public exponent with respect to (mod T)
-D = mod_inverse(E,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

diff --git a/rsa.py b/rsa.py
@@ -75,6 +75,10 @@ def eea(a,b):
 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
 #####################################################################

diff --git a/rsa.py b/rsa.py
@@ -25,8 +25,8 @@
 # Brute-force (i.e. slow) primality test.
 def isPrime(x):
 	if x%2==0 and x>2: return False
-	i=3;sq=x**.5
-	while i<sq:
+	i=3; sqrt=x**.5
+	while i<sqrt:
 		if x%i==0: return False
 		i+=2
 	return True
@@ -43,17 +43,15 @@ def eea(a,b):
 		return (t, s-(q*t) )
 
 	inv = eea(x,y)[0]
-	if inv < 1: inv += y
+	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,))
+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
@@ -66,10 +64,13 @@ def eea(a,b):
 
 # 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 = mod_inverse(E,T)
 
-# The modulus is always necessary, while either E or D is the exponent, 
-# depending on which key we're using
+# 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)

diff --git a/rsa.py b/rsa.py
@@ -0,0 +1,117 @@
+#!/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 that "%" is the modulo operator, while // is integer (round-down) division
+
+# Brute-force (i.e. slow) primality test.
+def isPrime(x):
+	if x%2==0 and x>2: return False
+	i=3;sq=x**.5
+	while i<sq:
+		if x%i==0: return False
+		i+=2
+	return True
+
+# Find the multiplicative inverse of x (mod y)
+# see: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
+def mod_inverse(x,y):
+
+	# 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) )
+
+	inv = eea(x,y)[0]
+	if inv < 1: inv += y
+	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
+D = mod_inverse(E,T)
+
+# The modulus is always necessary, while either E or D is the exponent, 
+# depending on which key we're using
+
+print "public key: (MOD: %i, E: %i)" % (MOD,E)
+print "private key: (MOD: %i, D: %i)" % (MOD,D)
+
+#####################################################################
+# 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)
No results found