· 5 years ago · Dec 04, 2019, 09:02 PM
1N = 31
2p = 3
3q = 17
4d = 14
5
6Fp = GF(p)
7Fq = GF(q)
8
9FZ.<a> = PolynomialRing(ZZ)
10Rz.<x> = FZ.quotient((a**N)-1)
11
12FQ.<b> = PolynomialRing(GF(q))
13Rq.<y> = FQ.quotient((b**N)-1)
14
15FP.<c> = PolynomialRing(GF(p))
16Rp.<z> = FP.quotient((c**N)-1)
17
18
19
20def losuj_m(N, y):
21 mm = []
22 for i in range(0, N-1):
23 x = randint(int(-1 * y),int(y))
24 m_list.append(x)
25
26 m = list_to_Fz(mm)
27 return m_list, m
28
29
30def losuj_g_r(N, d):
31 flag_func = 1
32 g_list_1 = []
33 for i in range(0, d):
34 num = randint(0, N)
35 flag = 1
36 while(flag):
37 if num not in g_list_1:
38 flag = 0
39 else:
40 num = randint(0, N)
41 g_list_1.append(num)
42 g_list_11 = []
43 for i in range(d):
44 num = randint(0, N)
45 flag = 1
46 while(flag):
47 if num not in g_list_1 and num not in g_list_11:
48 flag = 0
49 else:
50 num = randint(0, N)
51 g_list_11.append(num)
52 gtab = []
53 for i in range(N):
54 if i in g_list_1:
55 gtab.append(1)
56 elif i in g_list_11:
57 gtab.append(-1)
58 else:
59 gtab.append(0)
60 g = list_to_Fz(gtab)
61 return gtab, g
62
63def rand_f(N, d):
64 flag_func = 1
65 while(flag_func):
66 flag_func = 0
67 f_list_1 = []
68 for i in range(0, d + 1):
69 num = randint(0, N - 1)
70 flag = 1
71 while(flag):
72 if num not in f_list_1:
73 flag = 0
74 else:
75 num = randint(0, N - 1)
76 f_list_1.append(num)
77 f_list_11 = []
78 for i in range(d):
79 num = randint(0, N - 1)
80 flag = 1
81 while(flag):
82 if num not in f_list_1 and num not in f_list_11:
83 flag = 0
84 else:
85 num = randint(0, N - 1)
86 f_list_11.append(num)
87 ftab = []
88 for i in range(N):
89 if i in f_list_1:
90 ftab.append(1)
91 elif i in f_list_11:
92 ftab.append(-1)
93 else:
94 ftab.append(0)
95 fq = list_to_Fq(ftab)
96 fp = list_to_Fp(ftab)
97 try:
98 fqprim = fq**(-1)
99 except ZeroDivisionError as e:
100 flag_func = 1
101 try:
102 fpprim = fp**(-1)
103 except ZeroDivisionError as e:
104 flag_func = 1
105 f = list_to_Fz(ftab)
106 return f, fp, fq, fpprim, fqprim
107
108
109
110
111
112def central_lift(alist, q):
113 alistnext = []
114 w = 0
115 for a in alist:
116 if q*0.5 < a:
117 w = a - q
118 alistnext.append(a-q)
119 elif a < -1* q * 0.5:
120 w = a + q
121 alistnext.append(a + q)
122 else:
123 alistnext.append(a)
124 w = a
125 return alistnext
126def a_to_list(a):
127 alist = []
128 for an in a:
129 alist.append(int(an))
130 return alist
131def list_to_Fz(ftab):
132 f = 0
133 for n in range(len(ftab)):
134 f += ftab[n]*x**n
135 return f
136
137def list_to_Fq(ftab):
138 f = 0
139 for n in range(len(ftab)):
140 f += ftab[n]*y**n
141 return f
142
143def list_to_Fp(ftab):
144 f = 0
145 for n in range(len(ftab)):
146 f += ftab[n]*z**n
147 return f
148
149
150
151
152
153
154
155
156f, fp, fq, fpprim, fqprim = rand_f(N, d)
157print("Klucz prywatny: ", f, fp)
158
159
160
161gtab, g = losuj_g_r(N, d)
162g_w_Rq = list_to_Fq(gtab)
163h = p * fqprim * g_w_Rq
164print("Klucz publiczny: ", h)
165
166
167
168rtab, r = losuj_g_r(N, d)
169mtab, m = losuj_m(N, p*0.5)
170mpierwsze = m
171m_w_Rq = list_to_Fq(mtab)
172r_w_Rq = list_to_Fq(rtab)
173e = r_w_Rq * h + m_w_Rq
174
175
176
177a = e * fq
178alist = a_to_list(a)
179a_list = central_lift(alist, q)
180a = list_to_Fp(a_list)
181m_w_p = a*fpprim
182mlist = a_to_list(m_w_p)
183mp = central_lift(mlist, p)
184
185
186mpp = list_to_Fz(mp)
187print(mpp)
188\end{lstlisting}
189\newpage
190\section{NTRU wersja 1998 - kod źródłowy}
191\begin{lstlisting}
192Zx.<x> = ZZ[]
193n = 107
194d = 14
195q = 64
196
197def inv(f,p):
198 T = Zx.change_ring(Integers(p)).quotient(x^n-1)
199 x = Zx(lift(1 / T(f)))
200 return x
201
202def invert2(f,q):
203 assert q.is_power_of(2)
204 g = inv(f,2)
205 while True:
206 r = balancedmod(convolution(g,f),q)
207 if r == 1:
208 return g
209 g = balancedmod(convolution(g,2 - r),q)
210
211
212def convolution(f,g):
213 a = (f * g) % (x^n-1)
214 return a
215
216def balancedmod(f,q):
217 g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
218 b = Zx(g)
219 return b
220
221def rpoly():
222 assert d <= n
223 result = n*[0]
224 for j in range(d):
225 while True:
226 r = randrange(n)
227 if not result[r]: break
228 result[r] = 1-2*randrange(2)
229 r = Zx(result)
230 return r
231
232
233
234
235def key():
236 flag = 1
237 while flag:
238 flag = 0
239 try:
240 f = rpoly()
241 f3 = inv(f,3)
242 fq = invert2(f,q)
243 except:
244 flag = 1
245 g = rpoly()
246 h = balancedmod(3 * convolution(fq,g),q)
247 secretkey = f,f3
248 return h,secretkey
249
250
251def rmessage():
252 result = list(randrange(3) - 1 for j in range(n))
253 r = Zx(result)
254 return r
255
256def enc(message,h):
257 r = rpoly()
258 balance = balancedmod(convolution(h,r) + message,q)
259 return balance
260
261
262def dec(ciphertext,secretkey):
263 f,f3 = secretkey
264 a = balancedmod(convolution(ciphertext,f),q)
265 balancedmod(convolution(a,f3),3)
266 return balance
267
268
269
270
271h, secretkey, = key()
272m = rmessage()
273c = enc(m, h)
274if m == dec(c, secretkey):
275 print " it 'working"
276else:
277 print "no it' s not working"