5emJrRmt

1def genUnimodular(n):
2    R=Integers()
3    A = matrix(QQ, n, n, 1)
4    for i in range(0,n):
5                A[i,0]=R.random_element()
6    if A[0,0]==0:
7        A[0,0]=1
8    if A.det()==1 or A.det()==-1:
9        return A
10    else:
11        return genUnimodular(n)
12
13def genBasis(n):
14    R=Integers()
15    A = matrix(QQ, n, n, 1)
16    for i in range(0,n):
17                A[i,0]=R.random_element(-10,10)
18    if A[0,0]==0:
19        A[0,0]=1
20        
21    k=R.random_element(1,500)
22    I=matrix(ZZ, n,  n, 1)
23    B=k*I
24    B+=A
25    return B
26
27def orthogonalizegs(A):
28    for column in range(0, A.ncols()):
29        u_n = A.column(column)
30        v_n = u_n
31        vec_sum = vector(QQ, A.nrows())
32        x = 0        
33        while(x<column):
34            v_temp = A.column(x)
35            v_temp = (v_temp.dot_product(u_n)/(v_temp.norm()^2))*v_temp
36            vec_sum+=v_temp
37            x=x+1
38        v_n = v_n - vec_sum
39        for i in range(0, A.nrows()):
40            A[i, column]=v_n[i]
41    return A
42
43
44
45def genKeys(n):
46    R=genBasis(n)
47    U=genUnimodular(n)
48    B=U*R
49    return R,B, n
50    
51def enc(B, m, n,e):
52    v=m*B
53    c=v+e
54    return c
55
56def dec(R, B, c):
57    n=R.nrows()
58    cR = c*(R.inverse())
59    for i in range(n):
60        cR[i]=round(cR[i])
61    v=cR*R
62    m=v*B.inverse()
63    return m
64
65n=50
66B=genBasis(n)
67U=genUnimodularEmb(n)
68Bpr=U*B
69
70
71
72for i in range(200):
73    m=random_vector(ZZ,n)
74    e=random_vector(ZZ,n,-3,3)
75    cipher=enc(Bpr, m, n,e)
76    decipher=dec(B,Bpr,cipher)
77    if decipher==m:
78        print "OK"
79    else:
80        print "BAD"
81def balancedmod(f,q,n):
82    g = list(((f[i] + q//2) % q) - q//2 for i in range(n))  
83    return Zx(g)
84
85def randomMessage(n):
86    result = list(randrange(3) - 1 for j in range(n))
87    return Zx(result)
88def invertmodprime(f,p,n):
89    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
90    return Zx(lift(1 / T(f)))
91def invertmodpowerof2(f,q,n):
92    assert q.is_power_of(2)
93    g = invertmodprime(f,2,n)
94    while True:
95        r = balancedmod(convolution(g,f,n),q,n)
96        if r == 1: return g
97        g = balancedmod(convolution(g,2 - r,n),q,n)
98
99
100def convolution(f,g,n):
101      return (f * g) % (x^n-1)
102
103
104def randompoly(n, d):
105    assert d <= n
106    result = n*[0]
107    for j in range(d):
108        while True:
109            r = randrange(n)
110            if not result[r]: break
111        result[r] = 1-2*randrange(2)
112    return Zx(result)
113    
114def encrypt(message, publickey, n, d, q):
115    r = randompoly(n,d)
116    return balancedmod(convolution(publickey,r,n) + message, q,n)
117
118def decrypt(ciphertext,secretkey,n):
119    f,f3 = secretkey
120    a = balancedmod(convolution(ciphertext,f,n),q,n)
121    return balancedmod(convolution(a,f3,n),3,n)
122
123def keypair(n,d,q):
124    Zx.<x> = ZZ[]
125    while True:
126        try:
127            f = randompoly(n,d)
128            f3 = invertmodprime(f,3,n)
129            fq = invertmodpowerof2(f,q,n)
130            break
131        except Exception as e:
132            pass
133    g = randompoly(n, d)
134    publickey = balancedmod(3 * convolution(fq,g,n),q,n)
135    secretkey = f,f3
136    return publickey,secretkey
137
138
139
140Zx.<x> = ZZ[]