黄河流域WP

1.Lattice

LWE问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def gen(q, n, N, sigma):
    t = np.random.randint(0, high=q // 2, size=n)
    s = np.concatenate([np.ones(1, dtype=np.int32), t])
    A = np.random.randint(0, high=q // 2, size=(N, n))
    e = np.round(np.random.randn(N) * sigma**2).astype(np.int32) % q
    b = ((np.dot(A, t) + e).reshape(-1, 1)) % q
    P = np.hstack([b, -A])
    return P, s


def enc(P, M, q):
    N = P.shape[0]
    n = len(M)
    r = np.random.randint(0, 2, (n, N))
    Z = np.zeros((n, P.shape[1]), dtype=np.int32)
    Z[:, 0] = 1
    C = np.zeros((n, P.shape[1]), dtype=np.int32)
    for i in range(n):
        C[i] = (np.dot(P.T, r[i]) + (np.floor(q / 2) * Z[i] * M[i])) % q
    return C


q = 127
n = 3
N = int(1.1 * n * np.log(q))
sigma = 1.0

P, s = gen(q, n, N, sigma)


gen生成密钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul
from c import C
# Babai's Nearest Plane algorithm
# from: http://mslc.ctf.su/wp/plaidctf-2016-sexec-crypto-300/
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small
q = 127
Z = GF(q)
N = 15
n = 3
b = vector(ZZ,[87, 57, 76, 75, 121, 47, 112, 74, 20, 89, 18, 35, 105, 44, 111])
A = matrix(ZZ,N,n,[
    [27, 52, 29],
    [41, 24, 60],
    [17, 55, 37],
    [46, 33, 21],
    [55, 33, 34],
    [4, 34, 45],
    [33, 44, 16],
    [44, 5, 25],
    [21, 16, 49],
    [21, 54, 24],
    [23, 53, 1],
    [40, 4, 29],
    [54, 2, 8],
    [24, 43, 36],
    [15, 15, 54]
])
A_values = A.T
b_values = b.change_ring(ZZ)

A = matrix(ZZ, N+n, N)
for i in range(N):
    A[i, i] = q
for x in range(N):
    for y in range(n):
        A[N + y, x] = A_values[y][x]
print("开始LLL算法")
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))
R = IntegerModRing(q)
M = Matrix(R, A_values)
t = M.solve_left(res)
s = vector(ZZ,[1]+list(t))
C = matrix(ZZ,728,4,C)
M = vector(Z,C*s)
print(M)