Book Imai Matsumoto 5x5 Example.sagews

# We will be working in a polynomial ring with variables x1,x2,x3,x4,x5 where the coeffients are F2 with lexographic order
P.<x1,x2,x3,x4,x5> = PolynomialRing(FiniteField(2),order="lex")
# Sets up our polynomial ring
Pq.<x> = PolynomialRing(P, 'lex')
# The quotient ring is modulo an irreducible polynomial
S = Pq.quotient(x^5 + x^4 + x^3 + x + 1, 'a')
# distinguishing the x we use in our basis as a
a = S.gen()
# establishing A as an 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]]);
#var('aa,bb,cc,dd')
#A = matrix(FiniteField(2), [[aa,bb],[cc,dd]])
# establishing B as an 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]]);
# establishing c as our constant vector
c = vector(FiniteField(2), [1,0,1,1,1])
# establishing d as our constant vector
d = vector(FiniteField(2), [1,0,1,0,0])
# establishing X as our private key
#X = vector([x1,x2,x3,x4,x5])
X = vector([1,0,1,0,0])
print "private key: " + str(X)
print "theta=3, h=9, h'=7"
# finding the inverse matrix of A
Ainv = A.inverse()
# finding the inverse matrix of B
Binv = B.inverse()
# performing an affine transformation from x to u
# observe that A and c are vectors/matrices in F2
# X is a vector of variables X = <x1,...,xn> where n is defines ??
# observe that u is a n x 1 vector with entries in polynomial ring variables x1...xn, over F2
u = A*X + c
# performing an affine transformation from u to v
# since g.c.d.(h,q^n-1)=1, v = u^h = u*u^(q^theta)
# since g.c.d.(5,3) = 1, v = u^5 = u*u^4
# v is in the quotient ring a represents the basis
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]])
# performing an affine transformation from v to y
y = Binv*(v - d)
# y is our public key
print "public key: " + str(y)

# now decrypting public key knowing A, B, c, and d
# establishing Y as a vector
Y = vector(y)
# performing the affine transformation from Y to v
v = B*Y + d
v
# performing the affine transformation from v to u
# u = v^h'
# u = v^4
u = (v[0] + v[1]*a + v[2]*a^2 + v[3]*a^3 + v[4]*a^4)^7
u
# establishing u as a vector
u = vector([u[0],u[1],u[2],u[3],u[4]])
# performing the affine transformation from u to x
x = Ainv*(u - c)
print "x calculated using Alice's method: " + str(x)

# Our own division algorithm
def poly_div(f, G):
    # setting up dividend as t
    t = f;
    # establishing the leading term of t
    cur_lt = t.lt()
    # establishing a zero polynomial
    zero_poly = 0*f;
    # establishing divr as the zero polynomial
    divr = zero_poly
    # Starting the count at 0
    count = 0
    # while the current leading term is not zero
    while cur_lt != zero_poly:
        # establishing a for loop from 0 to the length of G
        for n in range(0,len(G)):
            # establishing the leading term of the current polynomial of G
            cur_g_lt = G[n].lt()
            # establishing q as the quotient and r as remainder from dividing leading term of                   dividend by leading term of currently polynomial of G
            (q,r) = cur_lt.quo_rem(cur_g_lt)
            # if the quotient is not equal to the zero polynomial
            if (q != zero_poly):
                # end of loop
                break;
        # if q is not equal to zero polynomial
        if (q != zero_poly):
            # subtracts quotient times current polynomial of G from divident
            t = t - q*G[n]
        # if q is equal to zero polynomial
        else:
            # adds current leading term to remainder
            divr = divr + cur_lt
            # subtracts remainder from divident
            t = t - cur_lt
        # adds one to count
        count = count + 1;
        # establishes a new current leading term of divident
        cur_lt = t.lt()
    print "final remainder: " + str(divr)
    return(divr)

print "Calculating Grobner Basis with our own Algorithm"

# establishes F as the public key
F = (x1*x2 + x1*x3 + x1*x4 + x1*x5 + x2*x3 + x2 + x3^2 + x3*x5 + x3 + x4^2 + x4 + x5^2 + x5 + 1, x1^2 + x1*x2 + x1*x5 + x2^2 + x2*x3 + x2*x4 + x2 + x3^2 + x3*x4 + x3*x5 + x4 + x5, x1^2 + x1*x2 + x1 + x2^2 + x2*x3 + x2*x5 + x3 + x4^2 + x4*x5 + x4 + x5^2 + x5 + 1, x1*x2 + x1*x4 + x1*x5 + x2^2 + x2 + x3^2 + x3*x5 + x3 + x4^2 + x4*x5 + x5, x1^2 + x1*x2 + x1*x4 + x1 + x2*x3 + x2*x4 + x2 + x3*x5 + x5^2)
# establishes I as the ideal generated by F
I = Ideal(F)
# calls in the buchberger code
from sage.rings.polynomial.toy_buchberger import *
# establishes G1 as the groebner basis calculated using sage's buchberger's algorithm
G1 = buchberger(I)
print "Grobner Basis Calculated by Sage: " + str(G1)
for polynomial in G1:
    print polynomial
# establishes B as the reduced groebner basis calculated by sage
B = I.groebner_basis();
print "Reduced Grobner Basis Calculated by Sage: " + str(B)

# establishes G as F
#G = F
# sets up Gp as an empty list
#Gp = [];
# while G does not equal Gp
while (G != Gp):
    # establishes t as the length of Gp
    t = len(Gp)
    # establishes Gp as A
    Gp = G;
    # establishes the zero polynomial
    zerof = Gp[0]*0;
    # sets up n as -1
    n = -1
    # while n is less than one less the length of Gp
    while (n < len(Gp)-1):
        # adds one to n
        n = n + 1
        # establishes m as one more than n
        m = n + 1
        # if m is less than t
        if (m < t):
            # establishes m as t
            m = t
        # while m is less than the length of Gp
        while (m < len(Gp)):
            print "S-pair for : m = " + str(m) + ", n = " + str(n)
            # sets L as the LCM of the leading monomial of the nth and mth polynomial of GP
            L = LCM(Gp[n].lm(), Gp[m].lm())
            # establishes sp1 as L divided nth polynomial of Gp
            sp1 = L//Gp[n].lt();
            # establishes sp 2 as L divided mth polynomial of Gp
            sp2 = L//Gp[m].lt()
            # establishes spair as sp1 times nth polynomial of Gp subtract sp2 times mth                         polynomial of Gp
            spair = sp1*Gp[n] - sp2*Gp[m];
            print "spair: " + str(spair)
            # establishes meeks as the spair divided by the polynomials of Gp
            meeks = poly_div(spair, Gp)
            print "post poly_div Gp: " + str(Gp)
            # if meeks is not equal to the zero polynomial
            if (meeks != zerof):
                # adds meeks to the list of G
                G = G + (meeks,)
                print "post poly_div G: " + str(G)
            # adds 1 to m
            m = m +1
# removes any repeat elements of G
G = uniq(G)
print "Grobner Basis calculated by our Algorithm: " + str(G)

private key: (1, 0, 1, 0, 0) theta=3, h=9, h'=7 public key: (0, 0, 0, 1, 0) (0, 1, 1, 0, 0) a^4 + a^3 + a + 1 x calculated using Alice's method: (1, 0, 1, 0, 0) Calculating Grobner Basis with our own Algorithm Grobner Basis Calculated by Sage: Polynomial Sequence with 25 Polynomials in 5 Variables x1*x5 + x1 + x2*x4 + x2*x5 + x2 + x3^2 + x3*x4 + x3*x5 + x3 + x4^2 + x4*x5 + x5^2 + 1 x3^3 + x3^2*x5 + x3^2 + x3*x5^2 + x3 + x4*x5^2 + x4 + x5 + 1 x1 + x2^3 + x2^2 + x2*x3^2 + x2*x3*x4 + x2*x5^2 + x2 + x3^2 + x3*x4^2 + x3*x4 + x3*x5^2 + x3 + x4^3 + x4 + x5^3 + x5 + 1 x2*x3^2*x5 + x2*x3^2 + x2*x3*x4*x5 + x2*x3*x4 + x2*x3*x5^2 + x2*x3 + x2*x4^3 + x2*x4 + x2*x5 + x2 + x3^2*x4^2 + x3^2*x4*x5 + x3^2*x4 + x3^2*x5 + x3*x4^3 + x3*x4*x5^2 + x3*x4*x5 + x3*x4 + x3*x5^2 + x3*x5 + x4^4 + x4^3*x5 + x4^2*x5^2 + x4*x5^3 + x4*x5^2 + x4 + x5^4 + x5 x4^2 x4 x1^2 + x1*x2 + x1*x4 + x1 + x2*x3 + x2*x4 + x2 + x3*x5 + x5^2 x1^2 + x1*x2 + x1*x5 + x2^2 + x2*x3 + x2*x4 + x2 + x3^2 + x3*x4 + x3*x5 + x4 + x5 x2^2*x4 + x2^2*x5 + x2^2 + x2*x3^2 + x2*x3*x4 + x2*x3*x5 + x2*x3 + x2*x4^2 + x2*x4*x5 + x2*x4 + x2*x5^2 + x2 + x3^2 + x3*x4*x5 + x3*x5^2 + x3*x5 + x4^2*x5 + x4*x5^2 + x4*x5 + x4 + x5^3 + 1 x2^2*x3^2 + x2^2 + x2*x3^3 + x2*x3^2*x4 + x2*x3^2*x5 + x2*x3^2 + x2*x3*x4^2 + x2*x3*x4*x5 + x2*x3*x4 + x2*x3*x5^2 + x2*x3 + x2*x4^2*x5 + x2*x4^2 + x2*x4*x5^2 + x2*x4 + x2*x5^3 + x2*x5^2 + x2*x5 + x2 + x3^3 + x3^2*x4^2 + x3^2*x4*x5 + x3^2*x5^2 + x3^2*x5 + x3^2 + x3*x4^2 + x3*x4*x5^2 + x3*x4*x5 + x3*x5^3 + x3 + x4^2*x5 + x4^2 + x4*x5^3 + x4*x5 + x5^3 + x5^2 + x5 + 1 x3 + x4 + x5 + 1 x1*x4 + x2^2 + x2*x4 + x2*x5 + x2 + x3*x5 + x3 + x4^2 + x4*x5 + x4 + x5 + 1 x3^2*x5 + x3^2 + x3 + x4^3 + x5^3 + x5^2 x2*x3*x4^2 + x2*x4^3 + x2*x4*x5^2 + x2*x4 + x3^3*x4 + x3^2*x4*x5 + x3^2*x4 + x3*x4^2 + x4^4 + x4^3 + x4^2*x5^2 + x4*x5^3 + x4 + x5^2 x3*x4 + x3*x5 + x3 + x4^2 + 1 x5^2 x1*x3 + x2^2 + x2*x3 + x4*x5 + x4 + x5^2 + 1 x2 + x3 + 1 x3^3*x5 + x3^3 + x3*x5 + x3 + x4^4 + x4^3*x5 + x4^3 + x4^2*x5^2 + x4^2 x1^2 + x1*x2 + x1 + x2^2 + x2*x3 + x2*x5 + x3 + x4^2 + x4*x5 + x4 + x5^2 + x5 + 1 x2^3*x3 + x2^2*x3 + x2^2 + x2*x3^3 + x2*x3^2*x4 + x2*x3*x5^2 + x3^3 + x3^2*x4^2 + x3^2*x4 + x3^2*x5^2 + x3^2 + x3*x4^3 + x3*x4 + x3*x5^3 + x3*x5 + x3 + x4*x5 + x4 + x5^2 + 1 x2^2*x5 + x2^2 + x2*x4^2 + x2*x5^2 + x2 + x3^2*x4 + x3*x4^2 + x3*x4*x5 + x3*x4 + x3*x5^2 + x3 + x4^3 + x4^2 + x5^2 + 1 x1*x2 + x1*x4 + x1*x5 + x2^2 + x2 + x3^2 + x3*x5 + x3 + x4^2 + x4*x5 + x5 x1*x2 + x1*x3 + x1*x4 + x1*x5 + x2*x3 + x2 + x3^2 + x3*x5 + x3 + x4^2 + x4 + x5^2 + x5 + 1 x2^4 + x2*x3*x4^2 + x2*x4 + x2*x5^3 + x2*x5^2 + x2*x5 + x2 + x3^2*x4*x5 + x3^2*x4 + x3^2*x5^2 + x3^2 + x3*x4^3 + x3*x4^2 + x3*x4*x5^2 + x3*x5^3 + x3*x5^2 + x4^4 + x4^3*x5 + x4^3 + x4^2*x5^2 + x4^2 + x4 + x5^3 + x5 + 1 Reduced Grobner Basis Calculated by Sage: [x1 + 1, x2 + x5, x3 + x5 + 1, x4, x5^2]

Error in lines 58-80 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 995, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> NameError: name 'G' is not defined