#README: #1)Run the SageCell below #2)Scroll to the bottom of this worksheet and follow instructions to use the key exchange with Toy AES encryption
def chooseRandomEllipticCurveWithPoint(q): ''' Randomly generates an elliptic curve over a finite field that has a solution. Takes in a variable q that defines our finite field F_q. Returns, the point (x,y), the coefficients A, B for the elliptic curve y^2 = x^3 + Ax + B, and q. ''' R = Zmod(q) A = R.random_element() x = R.random_element() y = R.random_element() B = y^2 - (x^3 + A*x) detE = 4*A^3 + 27*B^2 # checks whether elliptic curve is legal if detE == 0: return chooseRandomEllipticCurve(q) # if not legal, tries again return (x, y, A, B, q) def addPoints(x1, y1, x2, y2, A, B, q): ''' Point Addition over curve y^2 = x^3 + Ax + B in F_q ''' if((x2,y2) == (oo,oo)):# P + O = P return (x1,y1) if (x1 == x2 and y1 != y2):# P + -P = O return (oo, oo) if x1 != x2:# P + Q = R m = ((y2-y1)/(x2-x1)) if (x1,y1) == (x2,y2):# P + P = 2P m = ((3*(x1)^2 + A)/(2*y1)) x3 = (m^2 - x1 - x2)%q y3 = (-((m*x3) + y1 - m*x1))%q return (x3, y3) def doubleAndAdd(p, x, y, A, B, q): ''' Returns a p multiple of a generating point g = (x,y) on the elliptic curve y^2 = x^3 + Ax + B over the finite field F_q ''' binaryArray = p.bits()#binary representation of p length = len(binaryArray) storageArray = []# holds the doubled points in place of the corresponding power of 2 counter = length g = (x,y)# generating point storageArray.append(g) while(counter != 1): g = addPoints(g[0],g[1],g[0],g[1],A,B,q)# doubles the point g storageArray.append(g) counter -= 1 counter = 0 pointMult = (oo,oo) # adds doubled points that correspond to the 1's of p's binary representation while(counter != len(binaryArray)): if(binaryArray[counter] == 1): pointMult = addPoints(storageArray[counter][0],storageArray[counter][1],pointMult[0],pointMult[1], A, B, q) counter += 1 return pointMult def Alice(x,y,A,B,q): ''' Takes in a point P = (x,y), the coefficients for the elliptic curve and prime q. Returns na, Alice's private mulitple and na*P = Qa, Alice's public point on the curve ''' na = ZZ.random_element(q) Qa = doubleAndAdd(na, x, y, A, B, q) return (na,Qa) def Bob(x,y,A,B,q): ''' Takes in a point P = (x,y), the coefficients for the elliptic curve and prime q. Returns nb, Bob's private mulitple and nb*P = Qb, Bob's public point on the curve ''' nb = ZZ.random_element(q) Qb = doubleAndAdd(nb, x, y, A, B, q) return (nb,Qb) def sharedValue(na, nb, Qa, Qb, A, B, q): ''' takes in Alice & Bob's private keys along with their public points, to compute their shared secret point returns their shared secret point na*Qb = nb*Qa = secret shared point ''' AliceVal = doubleAndAdd(na, Qb[0], Qb[1], A, B , q) BobVal = doubleAndAdd(nb, Qa[0], Qa[1], A, B, q) return (AliceVal) from sage.crypto.util import ascii_to_bin from sage.crypto.util import bin_to_ascii def encrypt(plainText, key): ''' Takes plainText and an encryption key as input and uses row shifts and column swaps to scramble the bit representation of the ciperText Returns cipherText ''' cryptKey = Integer(key) # encodes ascii representation of plainText to binary representation plainBinBits = ascii_to_bin(plainText) plainBits = [] # converts 'MonoidString' binary representation to usable Integer representation for i in xrange(len(plainBinBits)): if str(plainBinBits[i]) == '0': plainBits.append(0) else: plainBits.append(1) # nxm Matrix, we set the n dimension to 8 because an ascii character has an 8 bit representation nDim = 8 mDim = (len(plainBits))/8 perMat = Matrix(nDim, mDim) appendVector = range(mDim) # populates a matrix with the bit representation for i in xrange(nDim): for j in xrange(mDim): appendVector[j] = (plainBits[i*mDim + j]) perMat[i] = appendVector # we apply the permutation key mod 5 times for i in xrange((cryptKey%5) + 1): # shifts the rows count = 0 for j in xrange(nDim): subVec = perMat[j] if count >= mDim: count = 0 for k in xrange(count): temp = subVec[0] subVec = list(subVec) subVec.append(temp) subVec = subVec[1:mDim+1:1] perMat[j] = subVec count += 1 # swaps the columns for k in xrange((cryptKey%mDim)): perMat[:,k], perMat[:,mDim-1]= perMat[:,mDim-1],perMat[:,k] cipherBits = [] # Takes bits from Matrix form to list form so they can be interpreted as ascii characters for i in xrange(nDim): for j in xrange(mDim): cipherBits.append(perMat[i][j]) cipherText = bin_to_ascii(cipherBits) return cipherText def decrypt(cipherText, key): ''' Takes a cipherText and a key to encrypt Decrypts the cipherText by reversing row shifts and column swaps of encrypt() ''' cryptKey = Integer(key) #encodes ascii representation to binary representation cipherBinBits = ascii_to_bin(cipherText) cipherBits = [] # changes binary representation to Integer for i in xrange(len(cipherBinBits)): if str(cipherBinBits[i]) == '0': cipherBits.append(0) else: cipherBits.append(1) # n dimension is 8 because an ascii charachter has 8-bit binary encoding nDim = 8 mDim = (len(cipherBinBits))/8 perMat = Matrix(nDim, mDim) appendVector = range(mDim) #populates the perMat matrix for i in xrange(nDim): for j in xrange(mDim): appendVector[j] = (cipherBits[i*mDim + j]) perMat[i] = appendVector # we chose to apply the permutation key mod 5 times for i in xrange((cryptKey%5) + 1): #swaps the columns for j in xrange((cryptKey%mDim)-1, -1, -1): perMat[:,mDim-1], perMat[:,j]= perMat[:,j],perMat[:,mDim-1] count = nDim%mDim #shifts the rows for k in xrange(nDim - 1, 0, -1): subVec = perMat[k] if(count == 0): count = mDim for n in xrange(count-1, 0, -1): subVec = list(subVec) temp = subVec[0:mDim - 1:1] temp2 = subVec[mDim - 1] subVec = [temp2] for l in xrange(len(temp)): subVec.append(temp[l]) perMat[k] = subVec count -= 1 decrypBits = [] # Takes decrypted bits from Matrix form to list form to be encoded as ascii characters for i in range(nDim): for j in xrange(mDim): tempBit = perMat[i][j] decrypBits.append(tempBit) decryptText = bin_to_ascii(decrypBits) return decryptText
#Follow inline comment instructions #TODO: input a prime number chooseRandomEllipticCurveWithPoint(47)
'\nFollow inline comment instructions\n'
(16, 46, 20, 3, 47)
#take output from previous cell and copy into the inputs for Alice() and Bob() methods Al = Alice(16, 46, 20, 3, 47)#<--- copy paste Bo = Bob(16, 46, 20, 3, 47)#<--- copy paste # Al and Bo hold point Qa and Qb respectively which are their public keys sharedVal = sharedValue(Al[0], Bo[0], Al[1], Bo[1], 20, 3, 47)#<--- copy/paste last 3 entries from the random elliptic curve #READ: if you get an error at this step, run the cell again because the shared point is (oo,oo), #running again will pick a new point. # we use the x-coordinate of their shared secret point secretKey = sharedVal[0] #in place of the message in quotations, you can input your own message to encrypt then decrypt cipher = encrypt("Hi Professor Viray! This is a pre-encrypted message!", secretKey) plain = decrypt(cipher, secretKey) print "secret key = " + str(secretKey) print "encrypted message : " cipher print "decrypted message : " plain
secret key = 34
encrypted message :
'\x12CI\x02\xb2ofessnD\x1b\xcd.L.D\x99\x81\xa1\xa5\xcd\x08\x80\x9b0\x908i)\xc5\x16\xe66\\\x9am\xaa\xc8A\xabpt1Y\xda\x91kf6\x0b'
decrypted message :
'Hi Professor Viray! This is a pre-encrypted message!'