# the quotient ring modulo an irreducible polynomial, Pq.<x> = PolynomialRing(P, 'lex') S = Pq.quotient(x^5 + x^4 + x^3 + x + 1, 'a') # We explicitly refer to the basis variables in the quotient ring as "a" # these are the betas a = S.gen() # set up the x plaintext tuple P.<x1,x2,x3,x4,x5> = PolynomialRing(FiniteField(2),order="lex") # we implicitly assume n=5, theta=3, h=9, h'=7 in this code print "n=5, theta=3, h=9, h'=7" # establish the necessary private key variables, A,B,c,d # for the public key, we compute: # 1) u = Ax + c, 2) v* = (u*)^h, 3) y = B^(-1)(v - d) # A invertible 2x2 matrix A = matrix(FiniteField(2), [[1,0,1,1,0],[0,1,1,0,1],[1,1,0,0,1],[0,1,0,1,0],[0,0,0,1,1]]); # B invertible 2x2 matrix B = matrix(FiniteField(2), [[1,0,0,1,1],[0,0,1,1,0],[1,1,0,0,1],[1,1,0,0,0],[1,0,0,0,0]]); # c offset vector c = vector(FiniteField(2), [1,0,1,1,1]) # d offset vector d = vector(FiniteField(2), [1,0,1,0,0]) # this is for Bob, generating his public key #X = vector([x1,x2,x3,x4,x5]) # this is for Alice, computing a ciphter text to send a message to Bob X = vector([1,0,1,1,1]) #X = vector([1,0,0,0,0]) print "plaintext or private key : " + str(X) # finding the inverse matrix of A Ainv = A.inverse() # finding the inverse matrix of B Binv = B.inverse() # step 1: u = Ax + c u = A*X + c # step 2: v* = (u*)^h # recall that h = 9, and so q^theta + 1 -> 9 = 2^3 + 1, or theta = 3 # therefore, we have u^9 = u^8u, which can be calculated as follows # notice that a represents the basis variable beta or X here v = (u[0] + u[1]*a + u[2]*a^2 + u[3]*a^3 + u[4]*a^4)*(u[0] + u[1]*a^8 + u[2]*a^16 + u[3]*a^24 + u[4]*a^32) # establishing v as a vector v = vector([v[0],v[1],v[2],v[3],v[4]]) # step 3: y = B^(-1)(v - d) y = Binv*(v - d) # y is our public key print "public key or ciphertext: " + str(y)
n=5, theta=3, h=9, h'=7
plaintext or private key : (1, 0, 1, 1, 1)
public key or ciphertext: (1, 1, 1, 1, 1)