X54auTHw

1Zx.<x> = ZZ[]
2n = 11
3d = 3
4q = 32
5p = 3
6
7# FUNKCJE MATEMATYCZNE
8def convolution(f,g):
9      return ((f * g) % (x^n-1))
10
11def balancedmod(f,q):
12    g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
13    return (Zx(g))
14
15def randomdpoly():
16    assert (d <= n)
17    result = n*[0]
18    for j in range(d):
19        while True:
20            r = randrange(n)
21            if (not result[r]):
22                break
23        result[r] = 1-2*randrange(2)
24    return (Zx(result))
25
26def invertmodprime(f,p):
27    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
28    return (Zx(lift(1 / T(f))))
29
30def invertmodpowerof2(f,q):
31    assert q.is_power_of(2)
32    g = invertmodprime(f,2)
33    while True:
34        r = balancedmod(convolution(g,f),q)
35        if (r == 1):
36            return g
37        g = balancedmod(convolution(g,2 - r),q)
38
39# GENEROWANIE KLUCZY
40def keypair():
41    while True:
42        try:
43            f = randomdpoly()
44            f3 = invertmodprime(f,3)
45            fq = invertmodpowerof2(f,q)
46            break
47        except:
48            pass
49    g = randomdpoly()
50    publickey = balancedmod(3 * convolution(fq,g),q)
51    secretkey = f,f3
52    return publickey,secretkey
53
54# GENEROWANIE WIADOMOSCI
55def randommessage():
56    result = list(randrange(3) - 1 for j in range(n))
57    return (Zx(result))
58
59# SZYFROWANIE
60def encrypt(message,publickey):
61    r = randomdpoly()
62    return balancedmod(convolution(publickey,r) + message,q)
63# ODSZYFROWYWANIE
64def decrypt(ciphertext,secretkey):
65    f,f3 = secretkey
66    a = balancedmod(convolution(ciphertext,f),q)
67    return balancedmod(convolution(a,f3),3)
68
69
70publickey,secretkey = keypair()
71print '\nKLUCZ PUBLICZNY'
72publickey
73print'\nKLUCZ PRYWATNY'
74secretkey
75
76message=randommessage()
77print'\nWIADOMOSC'
78message
79
80encrypted=encrypt(message,publickey)
81print'\nWIADOMOSC ZASZYFROWANA'
82encrypted
83
84decrypted = decrypt(encrypted,secretkey)
85print'\nWIADOMOSC ODSZYFROWANA'
86decrypted
87# SPRAWDZENIE
88if (message == decrypted):
89    print'\nWIADOMOSC ZASZYFROWANA I ODSZYFROWANA ZGADZAJA SIE'
90else:
91    print'\nWIADOMOSCI SIE NIE ZGADZAJA'