· 7 years ago · Jan 26, 2019, 04:12 PM
1import time
2B = matrix(ZZ,[[1137,0,0,0 ,0,0,0 ,0,0,0],
3[ 0 ,1770, 0, 0, 0 , 0 , 0 , 0 , 0 , 0],
4[ 0 , 0, 1500 , 0, 0, 0 , 0 , 0, 0, 0],
5[ 0 , 0, 0, 1997 , 0 , 0 , 0 , 0 , 0 , 0],
6[ 0 , 0 , 0 , 0, 1545, 0, 0, 0, 0, 0],
7[ 0, 0, 0, 0, 0, 1452, 0, 0 , 0, 0],
8[ 0, 0, 0, 0 , 0 , 0, 1030, 0 , 0 , 0],
9[ 0, 0 , 0 , 0 , 0 , 0, 0, 2000 , 0 , 0],
10[ 0, 0 , 0, 0 , 0 , 0 , 0 , 0, 1945, 0],
11[ 0, 0 , 0 , 0 , 0 , 0 , 0 , 0, 0, 1428]])
12U = matrix(ZZ,[[3,-1,-17,50,88,-295,539,-191,1848,6650],
13[1, 4, 10, -26, -56, 168, -259, 288, -450, -799],
14[2, 2, 3, -6, -19, 54, -62, 163, 102, 960],
15[0, 2, 10, -23, -41, 138, -246, 123, -780, -2668],
16[-5,-10, -25, 61, 139, -420, 626, -784, 896, 869],
17[-1, 2, 12, -34, -64, 207, -359, 205, -1057, -3478],
18[0, -5, -16, 44, 84, -267, 448, -327, 1169, 3512],
19[4, 16, 38, -104, -226, 672, -1028, 1175, -1702, -2725],
20[-5,-15, -30, 85, 202, -584, 837, -1199, 818, -858],
21[2, 2, 0, 3, -5, 2, 35, 145, 473, 2365]])
22
23N = vector(ZZ,[569638, -295592, -4258501, 16674949, 22705321, -71532778, 92713388, -63794003, 600258123, 1585865397])
24d = vector(ZZ,[17054, -8850, -127500, 499247, 679801, -2141700, 2775849, -1910000, 17971799, 47481001])
25
26def GGHdec(B,U,c):
27 pom=c*(B^(-1))
28 for j in [0..9]:
29 pom[j]=round(pom[j])
30 M=pom*U^(-1)
31 return M
32
33
34def balancedmod(f,q,n):
35 g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
36 return Zx(g)
37
38def randomMessage(n):
39 result = list(randrange(3) - 1 for j in range(n))
40 return Zx(result)
41def invertmodprime(f,p,n):
42 T = Zx.change_ring(Integers(p)).quotient(x^n-1)
43 return Zx(lift(1 / T(f)))
44def invertmodpowerof2(f,q,n):
45 assert q.is_power_of(2)
46 g = invertmodprime(f,2,n)
47 while True:
48 r = balancedmod(convolution(g,f,n),q,n)
49 if r == 1: return g
50 g = balancedmod(convolution(g,2 - r,n),q,n)
51
52
53def convolution(f,g,n):
54 return (f * g) % (x^n-1)
55
56
57def randompoly(n, d):
58 assert d <= n
59 result = n*[0]
60 for j in range(d):
61 while True:
62 r = randrange(n)
63 if not result[r]: break
64 result[r] = 1-2*randrange(2)
65 return Zx(result)
66
67def NTRUenc(message, publickey, n, d, q):
68 r = randompoly(n,d)
69 return balancedmod(convolution(publickey,r,n) + message, q,n)
70
71def NTRUdec(ciphertext,secretkey,n,p):
72 f,fp = secretkey
73 a = balancedmod(convolution(ciphertext,f,n),q,n)
74 return balancedmod(convolution(a,fp,n),p,n)
75
76def NTRUgen(p,q,n,d):
77 Zx.<x> = ZZ[]
78 while True:
79 try:
80 f = randompoly(n,d)
81 fp = invertmodprime(f,p,n)
82 fq = invertmodpowerof2(f,q,n)
83 break
84 except Exception as e:
85 pass
86 g = randompoly(n, d)
87 publickey = balancedmod(p * convolution(fq,g,n),q,n)
88 secretkey = f,fp
89 return publickey,secretkey
90
91
92Zx.<x> = ZZ[]
93Nv=GGHdec(B,U,N)
94dv=GGHdec(B,U,d)
95p = 3
96q = 128
97Np=Nv[0]
98dp=dv[0]
99
100
101
102times = []
103avTime=0
104NUM_OF_TESTS=50000
105results=[]
106it=0
107
108while(it<NUM_OF_TESTS):
109
110
111 start=time.time()
112 pk,sk=NTRUgen(p,q,Np,dp)
113 end=time.time()
114
115 message=randomMessage(Np)
116 cipher=NTRUenc(message,pk,Np,dp,q)
117 decipher=NTRUdec(cipher,sk,Np,p)
118
119
120
121
122
123 if message==decipher:
124 results.append(1)
125 itTime=end-start
126 times.append(itTime)
127 else:
128 results.append(0)
129 it+=1
130
131
132sucSum=0;
133for i in range(0, NUM_OF_TESTS):
134 if results[i]==1:
135 sucSum+=1
136
137totalTime=0
138for i in range(0,len(times)):
139 totalTime+=times[i]
140
141avTime=totalTime/len(times)
142
143
144
145print ("Skutecznosc NTRU przy zadanych prametrach w procentach: %f ") % (sucSum/NUM_OF_TESTS * 100)
146print ("Czas dla %d generacji to: %f") % (NUM_OF_TESTS, totalTime)
147print ("Sredni czas generacji: %f") % (avTime)
148
149
150
151print p
152print q
153print Np
154print dp