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
|
import numpy as np
# 1. 填入公钥基向量
basis = np.array([
[154, -4, 2, 2, -1, 4, 4, 0, -4, 4, -3, -2, -1, -4],
[-1, 162, 4, -2, 3, 2, -4, 0, -1, -2, -4, -2, -3, 2],
[-4, 5, 152, -2, -4, -4, 1, -3, 4, -2, 1, -4, -4, 2],
[-1, 2, 2, 141, 5, -3, 1, -2, 2, 2, 4, 1, -3, 2],
[-5, -16, -16, -838, 171, 23, 0, 224, -15, -5, -20, 0, 30, -14],
[-1, 5, -2, 2, 3, 103, -3, 2, -3, 0, -4, -5, -4, 4],
[5, -5, 1, 3, -1, -2, 105, 1, -3, -3, -3, 0, 1, -2],
[-1, -8, -6, -420, -10, 10, 0, 111, -10, -4, -12, 1, 14, -8],
[-4, -4, -2, 2, 2, -102, 0, -2, 150, -2, 3, 7, -1, -2],
[5, 2, -1, -3, 3, -2, 0, -3, 3, 113, -1, 0, 4, -4],
[0, -1, -4, 3, 0, -4, 4, -3, 0, 2, 124, 4, 5, -4],
[4, 3, -3, 3, -4, 3, 3, 5, 1, 4, -4, 101, 5, -2],
[0, 4, -1, 4, 1, -2, -4, 3, 4, 4, 4, 3, 125, -5],
[-1, 4, 4, -2, 4, 0, -1, 1, -3, 3, 2, -5, 3, 142]
])
# 2. 填入密文向量
ciphertext = np.array([149, 143, -15, -684, 179, -78, 111, 229, 134, 4, 104, 113, 156, -27])
def solve_cvp(B, c):
# Babai's Rounding 技术
# c = m * B => m = c * B_inv
B_inv = np.linalg.inv(B)
m_approx = np.dot(c, B_inv)
# 对系数进行取整,还原 0/1 序列
m_bits = np.round(m_approx).astype(int)
return m_bits
# 3. 计算并输出结果
m = solve_cvp(basis, ciphertext)
print("解出的比特序列: ", " ".join(map(str, m)))
# 验证(可选)
reconstructed = np.dot(m, basis)
error = ciphertext - reconstructed
print(f"误差向量: {error} (应该都在 -3 到 3 之间)")
|