Find the lattice

发表于 更新于 分类于 阅读次数：

Find the Lattice

Challenge files:

问题分析

该挑战涉及一个基于格的加密系统。加密过程使用公钥 加密消息 ，生成密文 。解密需要私钥 。从代码中可知，加密算法满足关系式 ，即存在整数 使得 。这可以表示为向量关系：

因此，向量 是由基向量 和 张成的二维格中的一个短向量。由于 和 的大小约为 ，而格的行列式为 ，因此 很可能是格中的一个短向量，可以通过格约化算法找到。

攻击原理

使用高斯格约化算法（Gaussian Lattice Reduction）可以将格基约化为最短基向量。在二维格中，该算法能高效找到最短向量。通过将基向量 和 约化，我们有望得到向量 ，从而恢复私钥。

算法步骤

高斯格约化算法步骤如下：

  1. 初始化两个基向量 和 ，其中 为较短的向量。
  2. 计算投影系数 。
  3. 如果 ，则更新 。
  4. 交换 和 ，重复步骤2-3，直到 不再变化。
  5. 最终得到的 和 是约化后的基，其中较短的向量即为 。

代码实现

以下Python代码实现了攻击过程：

  • 从 读取公钥 和密文 。
  • 使用高斯格约化找到私钥 。
  • 使用解密函数恢复明文 。
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
62
63
64
65
66
67
68
69
70
71
72
from Crypto.Util.number import long_to_bytes
import math

def gaussian_reduction(v1, v2):
    # 确保 v1 是较短的向量
    if math.sqrt(v1[0]**2 + v1[1]**2) > math.sqrt(v2[0]**2 + v2[1]**2):
        v1, v2 = v2, v1
    while True:
        # 计算投影系数
        m = round((v2[0]*v1[0] + v2[1]*v1[1]) / (v1[0]**2 + v1[1]**2))
        if m == 0:
            break
        # 更新 v2
        v2 = (v2[0] - m * v1[0], v2[1] - m * v1[1])
        # 交换 v1 和 v2
        v1, v2 = v2, v1
    return v1, v2

def decrypt(q, h, f, g, e):
    a = (f * e) % q
    # 计算 f 模 g 的逆元
    try:
        f_inv = pow(f, -1, g)
    except:
        return None
    m = (a * f_inv) % g
    return m

# 从 output.txt 读取数据
with open('output.txt', 'r') as f:
    data = f.read()
    # 解析公钥和密文
    lines = data.split('\n')
    q_h_line = lines[0].split('Public key:')[1].strip()
    q_h = eval(q_h_line)
    q, h = q_h
    e_line = lines[1].split('Encrypted Flag:')[1].strip()
    e = int(e_line)

# 定义格基向量
v1 = (1, h)
v2 = (0, q)

# 应用高斯约化
v1_red, v2_red = gaussian_reduction(v1, v2)

# 较短的向量应该是 (f, g)
if math.sqrt(v1_red[0]**2 + v1_red[1]**2) < math.sqrt(v2_red[0]**2 + v2_red[1]**2):
    f, g = v1_red
else:
    f, g = v2_red

# 解密消息
m = decrypt(q, h, f, g, e)
if m is not None:
    flag = long_to_bytes(m)
    print("Flag:", flag.decode())
else:
    print("Decryption failed. Trying alternative vector...")
    # 如果失败，尝试另一个向量
    if math.sqrt(v1_red[0]**2 + v1_red[1]**2) < math.sqrt(v2_red[0]**2 + v2_red[1]**2):
        f, g = v2_red
    else:
        f, g = v1_red
    f = abs(f)
    g = abs(g)
    m = decrypt(q, h, f, g, e)
    if m is not None:
        flag = long_to_bytes(m)
        print("Flag:", flag.decode())
    else:
        print("Decryption still failed. Check the lattice reduction.")

总结

本挑战展示了如何利用格约化攻击基于格的加密系统。通过将加密问题转化为格中的短向量问题，并使用高斯约化算法，可以有效地恢复私钥并解密消息。这种方法在密码分析中常见，强调了设计加密系统时避免线性结构的重要性。