# Alfonso Cevallos. March 31 2015.
# Please report any mistakes.
# Rules of the game: do not use Python integers, only bit lists!
# New functions this week:
# Bitify(n): converts a Python integer n into a bit list
# RandOdd(n): generates an odd number of exactly bit size n
# RandTo(N): generates a random number between 1 and N-1
# ExGCD(A,B): computes the cgd G of A and B, as well as numbers X,Y such that AX + BY = G
# IsPrime(N): tests if N is prime, with exponentially small error probability
# PrimeGen(n): generates a prime number of exactly bit size n
# RSA(n): produces public and private keys for an RSA scheme, where N = PQ has at least 2n bits.
# Test functions for PrimeGen and RSA
import math
import os
import random
import time
def Leading1(A): #Traverse the list starting from most significant bit, until we find the first 1.
for i in xrange(len(A) - 1, -1, -1):
if A[i] != 0: return i
else: A.pop() #Remove unnecessary zeros on the fly
return -1
def Intify(A): # Convert a bit list into a Python integer
s = 0 # We use this only for checking correctness of our algorithms
for b in reversed(A):
s = 2*s + b
return s
def Add(A, B): # Add two bit lists
if Leading1(A) < Leading1(B): A,B = B,A #swaps the pointers, to ensure len(A)>=len(B)
Out = []
carry = 0
for i in range(len(A)):
if i < len(B): h = carry + A[i] + B[i]
else: h = carry + A[i]
Out.append(h % 2)
if h > 1: carry = 1
else: carry = 0
if carry == 1: Out.append(1)
return Out
def Sub(A, B): # Compute A-B
if Leading1(A)=len(B), else report error
Out = []
carry = 0
for i in range(len(A)):
if i < len(B): h = A[i] - B[i] - carry
else: h = A[i] - carry
Out.append(h % 2)
if h < 0: carry = 1
else: carry = 0
if carry == 1: return -1 # if the last carry is 1, L2 was bigger than L1. Report an error
Leading1(Out) # this line removes any leading zeros
return Out
def SimpleMult(A, B): # Standard multiplication A * B
if Leading1(A) < Leading1(B): A,B = B,A # remove leading zeros and ensure len(L1)>=len(L2)
Out = []
for b in reversed(B):
Out.insert(0,0)
if b==1: Out = Add(Out,A)
return Out
def Mult(A, B): # Our standard multiplication: the hybrid multiplication.
limit = 60
if Leading1(A) < Leading1(B): A,B = B,A # swap the pointers, to ensure len(a)>=len(b)
if len(A) < limit: return SimpleMult(A,B) #Use simple multiplication
k = len(A) // 2 # split the lists at this point
A0 = A[:k]
A1 = A[k:]
B0 = B[:k]
B1 = B[k:] # we have A*B = (A1*2^k + A0) * (B1*2^k + B0)
S2 = Mult(A1, B1)
S0 = Mult(A0, B0)
SS = Mult(Add(A1, A0), Add(B1, B0))
S1 = Sub(SS, Add(S2, S0)) # we have A*B = (S2*2^k + S1)*2^k + S0
return Add(([0]*k + Add(([0]*k + S2), S1)), S0)
def Div(A, B): #Computes division with remainder. Outputs Q,R, with A = BQ + R, R < B.
if Leading1(B) == -1: return -1 # If B = 0, report an error.
Q,R = [],[]
for b in reversed(A):
R.insert(0,b)
difference = -1 #if R < B, difference is -1 (code for error), else difference = R - B
if len(R) >= len(B): difference = Sub(R,B)
if difference != -1: # Case when R >= B
R = difference
Q.insert(0,1)
else: # Case when R is still smaller than B
if Q!=[]: Q.insert(0,0)
Leading1(R) # this line removes any leading zeros from R
return Q,R
def FME(A, E, N): # Computes A^E mod N, using fast modular exponentiation.
Out = [1]
for b in reversed(E):
Out = Mult(Out,Out) # Square it
if b==1: Out = Mult(Out, A) # Multiply it by A
Q, Out = Div(Out, N) # Reduce it mod N
return Out
# New functions this week:
def Bitify(n): # Convert a Python integer into a bit list
m = n
N = []
while m > 0:
N.append(m%2)
m = m/2
return N
def RandOdd(n): # Generate a random n-bit odd number. The first and the last bits are forced to be 1
A = [1] #Here n is assumed to be an integer, not a list.
for i in range(n - 2):
A.append(random.randint(0, 1))
A.append(1)
return A
def RandTo(N):
# Generates a bit list corresponding to a number between 1 and N-1.
# We only use random bits, and apply the rejection sampling technique.
# Generates a random number A, of the same bit size as N, starting from the most significant bit,
# and as soon as we detect that A > N, we restart the process.
while True:
A=[]
AequalN = True #this condition means that N and A are equal, bit by bit, up to this point
for b in reversed(N): #as we generate A, we compare it to N bit by bit
A.insert(0,random.randint(0,1))
if AequalN:
if A[0]>b: break #if A is bigger than N, discard A and restart
if A[0]-1: #finally check that A is neither equal to N, or zero.
return A
def ExGCD(A, B):
# Computes (G,X,Y,s), where G = gcd(A,B) = sXA - sYB
# The fourth entry s is either 1 or -1. s is the sign of X, -s is the sign of Y.
# We apply this trick because our machinery can't handle negative numbers.
if Leading1(A) == -1 and Leading1(B) == -1: return -1 # Error message for case A = B = 0
if Sub(A,B)==-1: # Case A < B
G, X, Y, s = ExGCD(B,A)
return G, Y, X, -s
if Leading1(B)==-1: return A,[1],[0],1 # Base case B = 0
Q,R = Div(A,B)
G, X, Y, s = ExGCD(B,R)
return G, Y, Add(X, Mult(Y, Q)), -s
def isPrime(N):
# Checks if N is prime, with up to k = 1.1*size(N) iterations of Miller-Rabin.
# Outputs True if N is prime (with exponentially small error probability), False if N is composite.
l = 1
while N[l]==0: l += 1
Q = N[l:] # Q and l are such that N = Q*2^l + 1, with Q odd (we assume N is odd).
for k in range(int(1.1*len(N))): # these are the k iterations of MR
A = RandTo(N) # Pick at random a number between 1 and N-1
A = FME(A,Q,N) # Compute A^Q mod N
for i in range(l):
A2 = Mult(A,A)
A2 = Div(A2,N)[1]
if len(A2) == 1 and len(A) != 1 and len(Sub(N,A)) != 1: return False
A = A2
if len(A) != 1: return False
return True
def PrimeGen(n): # Generates a prime N of size n, using our prime testing algorithm
while True:
N = RandOdd(n)
if isPrime(N): return N
def RSA(n): # Generates N, E, Y, where (N,E) is public key and (N,Y) is private key
# Where N has at least 2n bits, and E*Y = 1 mod Phi(N)
P = PrimeGen(n)
Q = PrimeGen(n+1)
N = Mult(P, Q)
Phi = Sub(Add(N, [1]), Add(P, Q)) # Phi(N) = (P-1)(Q-1) = (N+1) - (P+Q)
while True:
E = RandOdd(n) # E is chosen at random, such that it's coprime with Phi(N)
G,X,Y,s = ExGCD(Phi,E)
if len(G)==1: break
if s == 1: Y = Sub(Phi, Y) # Correct from -Y to Y (see the code for ExGCD)
return N, E, Y
def Crypt(M,E,N):
# If M is original message, and N,E is the public key, it computes the coded message S = M^E mod N
# If M is the coded message, and N,E is the private key, it computes the original message S = M^E mod N
return FME(M,E,N)
def TestPrimeGen():
for i in range(1,6):
time0 = time.time()
N = PrimeGen(10*i)
duration = time.time() - time0
n = Intify(N)
print "A prime of bit size ", 10*i, " is ", n
print "It was found in ", duration, " seconds."
print "\n"
def TestRSA():
M = [1,1,1,0,0,0,1,1,1]
print "Suppose we want to code the message M = ", M
print "We build an RSA scheme, with n = 5:"
N, E, Y = RSA(5)
print "The public key is N = ", N, ", E = ", E
print "The private key is N = ", N, ", Y = ", Y
S = Crypt(M,E,N)
print "Now the coded message is S = M^E mod N = ", S
D = Crypt(S,Y,N)
print "And the decoded message is D = S^Y mod N = ", D, " = M"
n = 9379
e = 43
y = 2563
s = 2982
N = Bitify(n)
E = Bitify(e)
Y = Bitify(y)
S = Bitify(s)
D = Crypt(S,Y,N)
d = Intify(D)
print "\nIn the provided example, we have n = ", n, ", e = ", e, ", y = ", y, ", and s = ", s
print "Then the decoded message is d = ", d
print "To check for correctness if we verify that d^e mod n = ", Intify(Crypt(D,E,N)), " = s"
TestPrimeGen()
TestRSA()