S2TViVfe

1Zx.<x> = ZZ[]
2def createfg(r_degree, positive_r, negative_r):
3    r = 0
4
5    for i in range(N):
6        D[i] = 0
7
8    while(positive_r > 0):
9        i = randint(0,N-1)
10        if(D[i] == 0):
11            D[i] = 1
12            positive_r = positive_r - 1
13
14    while(negative_r > 0):
15        i = randint(0,N-1)
16        if(D[i] == 0):
17            D[i] = -1
18            negative_r = negative_r - 1
19
20    for i in range(r_degree):
21        r = r + D[i] * x^i
22
23    return r
24
25def randomdpoly(N):
26    l = []
27    for i in range(N):
28        rnd = randint(1,q)
29        l.append(rnd)
30    return Zx(l)
31
32def invertmodprime(f,p):
33    print "działa?"
34    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
35    print "nie"
36    return Zx(lift(1 / T(f)))
37
38def balancedmod(f,q):
39    g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
40    return Zx(g)
41
42def invertmodpowerof2(f,q):
43    assert q.is_power_of(2)
44    g = invertmodprime(f,2)
45    while True:
46        r = balancedmod(convolution(g,f),q)
47        if r == 1: return g
48        g = balancedmod(convolution(g,2 - r),q)
49
50def convolution(f,g):
51    return (f * g) % (x^n-1)
52
53def keypair(p,q,N,d):
54    f = createfg(N,d,d-1)
55    print f
56    fp = invertmodprime(f,p)
57    print fp
58    fq = invertmodpowerof2(f,q)
59    g = createfg(N,d-1,d-1)
60    publickey = balancedmod(3 * convolution(fq,g),q)
61    show(publickey)
62    secretkey = f,fp
63    return publickey,secretkey
64
65D = dict()
66d = 4
67N = 11
68p = 3
69q = 32
70
71h, secret = keypair(p,q,N,d)
72m = Zx([1,1,1,1])
73e = (r*h+m)%(x^N-1)
74e = e%q
75
76show("Oryginalna wiadomość")
77show(m)
78show("Zaszyfrowana wiadomość")
79show(e)
80
81a = f*e
82a = a%(x^N-1)
83a = a%q
84
85for i in range(N):
86    if(a[i] < -q/2):
87        a = a + q * x^i
88    if(a[i] > q/2):
89        a = a - q * x^i
90
91b = a%p
92
93for i in range(N):
94    if(a[i] < -p/2):
95        a = a + p * x^i
96    if(a[i] > p/2):
97        a = a - p * x^i
98
99c = (fp*b)%(x^N-1)
100c = c%p
101
102for i in range(N):
103    if(c[i] <= -p/2):
104        c = c + p * x^i
105    if(c[i] >= p/2):
106        c = c - p * x^i
107
108show("Odszyfrowana wiadomość")
109show(c)