黄河流域WP

1.Lattice

LWE问题

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生成密钥

t \in Z^n,s=(1|t),A \in Z^{N\times n},e \in Z^{N} \
b = At +e \
P = (b|-A)```
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)