smH5B5uw

1︠d25246da-db2c-4a79-8f98-565dcd306144r︠
2
3def convolution(f,g):
4
5return (f * g) % (x^n-1)
6
7def balancedmod(f,q):
8
9g = list(((f + q//2) % q) - q//2 for i in range(n))
10
11return Zx(g)
12
13
14def randomdpoly():
15
16assert d <= n
17
18result = n*[0]
19
20for j in range(d):
21
22while True:
23
24r = randrange(n)
25
26if not result[r]: break
27
28result[r] = 1-2*randrange(2)
29
30return Zx(result)
31
32
33def invertmodprime(f,p):
34
35T = Zx.change_ring(Integers(p)).quotient(x^n-1)
36
37return Zx(lift(1 / T(f)))
38
39
40def invertmodpowerof2(f,q):
41
42assert q.is_power_of(2)
43
44g = invertmodprime(f,2)
45
46while True:
47
48r = balancedmod(convolution(g,f),q)
49
50if r == 1: return g
51
52g = balancedmod(convolution(g,2 - r),q)
53
54def keypair():
55
56while True:
57
58try:
59
60f = randomdpoly()
61
62f3 = invertmodprime(f,3)
63
64fq = invertmodpowerof2(f,q)
65
66break
67
68except:
69
70pass
71
72g = randomdpoly()
73
74publickey = balancedmod(3 * convolution(fq,g),q)
75
76secretkey = f,f3
77
78return publickey,secretkey
79
80
81
82def randommessage():
83
84result = list(randrange(3) - 1 for j in range(n))
85
86return Zx(result)
87
88
89
90n = 7
91
92d = 5
93
94q = 256
95
96publickey,secretkey = keypair()
97
98publickey