· 6 years ago · Feb 03, 2019, 07:04 PM
1Zx.<x> = ZZ[]
2def GGH_deszyfruj(c, B, U):
3 B_odwrocone = B.inverse()
4 U_odwrocone = U.inverse()
5 cB = c * B_odwrocone
6 for i in range (0,len(cB)):
7 cB[i] = round(cB[i])
8 message = cB * U_odwrocone
9 return message[0]
10def Generuj(N):
11 result = list(randrange(3) - 1 for j in range(N))
12 return Zx(result)
13
14def balancedmod(f,q):
15 g = list(((f[i] + q//2) % q) - q//2 for i in range(N))
16 return Zx(g)
17
18def convolution(f,g):
19 return (f * g) % (x^N-1)
20
21def randomdpoly():
22 assert d <= N
23 result = N*[0]
24 for j in range(d):
25 while True:
26 r = randrange(N)
27 if not result[r]: break
28 result[r] = 1-2*randrange(2)
29 return Zx(result)
30
31def invertmodprime(f,p):
32 T = Zx.change_ring(Integers(p)).quotient(x^N-1)
33 return Zx(lift(1 / T(f)))
34
35def invertmodpowerof2(f,q):
36 assert q.is_power_of(2)
37 g = invertmodprime(f,2)
38 while True:
39 r = balancedmod(convolution(g,f),q)
40 if r == 1: return g
41 g = balancedmod(convolution(g,2 - r),q)
42
43def NTRUGen():
44 while True:
45 try:
46 f = randomdpoly()
47 f3 = invertmodprime(f,3)
48 fq = invertmodpowerof2(f,q)
49 break
50 except:
51 pass
52 g = randomdpoly()
53 publickey = balancedmod(3 * convolution(fq,g),q)
54 secretkey = f,f3
55 return publickey,secretkey
56def NTRUEnc(message,publickey):
57 r = randomdpoly()
58 return balancedmod(convolution(publickey,r) + message,q)
59def NTRUGGH_deszyfruj(ciphertext,secretkey):
60 f,f3 = secretkey
61 a = balancedmod(convolution(ciphertext,f),q)
62 return balancedmod(convolution(a,f3),3)
63p = 3
64q = 1024
65Npodane = vector(QQ, [-6798079, 26932753, 160499295, -95850074, -1136855281, -43887516, 3319792026, -3199571101, -10684832331, 38581594053])
66dpodane = vector(QQ, [-1057914, 4191261, 24976839, -14916150, -176916962, -6829759, 516624693, -497915962, -1662769294, 6004052100])
67B = matrix(QQ,[
68 [1781, 0, 0, 0, 0, 0, 0, 0, 0, 0],
69 [ 0, 1764, 0, 0, 0, 0, 0, 0, 0, 0],
70 [ 0, 0, 1821, 0, 0, 0, 0, 0, 0, 0],
71 [ 0, 0, 0, 1905, 0, 0, 0, 0, 0, 0],
72 [ 0, 0, 0, 0, 1870, 0, 0, 0, 0, 0],
73 [ 0, 0, 0, 0, 0, 1081, 0, 0, 0, 0],
74 [ 0, 0, 0, 0, 0, 0, 1414, 0, 0, 0],
75 [ 0, 0, 0, 0, 0, 0, 0, 1747, 0, 0],
76 [ 0, 0, 0, 0, 0, 0, 0, 0, 1322, 0],
77 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1550]
78 ]
79)
80
81U = matrix(QQ,[
82 [ -11, 44, 254, -145, -1752, -117, 6766, -5278, -23292, 71733],
83 [ 4, -15, -83, 43, 560, 25, -2186, 1770, 7311, -22564],
84 [ 5, -25, -134, 59, 867, 23, -3418, 2888, 11022 -34105],
85 [ -3, 11, 64, -34, -434, -23, 1684, -1341, -5706, 17603],
86 [ 2, -10, -59, 31, 397, 24, -1533, 1213, 5219, -16098],
87 [ -4, 20, 104, -45, -676, -13, 2678, -2287, -8556, 26482],
88 [ 5, -24, -127, 51, 811, 8, -3225, 2796, 10160, -31492],
89 [ 2, -6, -37, 22, 259, 15, -998, 771, 3465, -10677],
90 [ -4, 16, 92, -52, -633, -41, 2447, -1916, -8400, 25875],
91 [ 3, -17, -96, 44, 624, 28, -2432, 2004, 8010, -24761]
92 ]
93)
94
95N = GGH_deszyfruj(Npodane,B,U)
96d = GGH_deszyfruj(dpodane,B,U)
97d = next_prime(d)
98show(N)
99show(d)
100poprawne = 0
101niepoprawne = 0
102d = 11;
103for i in range(0,1):
104 publickey,secretkey = NTRUGen()
105 show(publickey)
106 show(secretkey)
107 m = Generuj(N)
108 show(m)
109 c = NTRUEnc(m,publickey)
110 if m == NTRUGGH_deszyfruj(c,secretkey):
111 poprawne += 1
112 else:
113 niepoprawne +=1
114show(poprawne)
115show(niepoprawne)
116show(N,d)