# 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()