格基规约在CTF中的简单应用

1. 格密码简介

格密码(Lattice-based Cryptography)是后量子密码学的重要分支。2020年7月22日，NIST公布的后量子密码标准竞赛第三轮入选算法中，有5个属于格密码范畴。格密码的安全性基于格中的数学难题，如最短向量问题(SVP)和最近向量问题(CVP)。

2. 基础概念

2.1 格的定义

给定一组线性无关的基向量 v₁, v₂, ..., vₙ，这些基向量的所有整系数线性组合形成的集合称为格：

L = {a₁v₁ + a₂v₂ + ... + aₙvₙ | aᵢ ∈ ℤ}

2.2 格中的困难问题

1. 最短向量问题(SVP)：在格中找到最短的非零向量
2. 最近向量问题(CVP)：给定一个不在格中的向量v，找到格中离v最近的向量u

2.3 LLL算法

LLL(Lenstra-Lenstra-Lovász)算法是一种格基约化算法，可以看作是二维格上高斯约化算法在高维格上的扩展。它能找到近似最短向量，在较低维度的格中效果较好。

3. CTF中的典型应用

3.1 背包加密问题

3.1.1 问题描述

给定一个数组c和结果enc，求解xᵢ ∈ {0,1}使得：

enc ≡ ∑ cᵢxᵢ mod p

3.1.2 解题步骤

1. 构造(n+1)×(n+1)的矩阵：

   [1 0 ... 0 c₀]
   [0 1 ... 0 c₁]
   [...      ...]
   [0 0 ... 1 cₙ]
   [0 0 ... 0 -enc]
   

2. 应用LLL算法约化基

3. 寻找全由0和1组成的行向量，即为解

3.1.3 示例代码

c = [...] # 无序序列
p = ...   # 模数
enc = ... # 加密结果

for i in range(30):  # 考虑模数带来的多解可能
    current_enc = enc + i*p
    nbit = len(c)
    
    A = Matrix(ZZ, nbit+1, nbit+1)
    for i in range(nbit):
        A[i,i] = 1
    for i in range(nbit):
        A[i,nbit] = c[i]
    A[nbit,nbit] = -current_enc
    
    res = A.LLL()
    for row in res:
        if all(x in (0,1) for x in row[:-1]):
            solution = row[:-1]
            print(''.join(str(x) for x in solution))
            break

3.2 NTRU加密系统

3.2.1 算法描述

1. 选择公共参数q
2. 选择小整数f,g满足f ≪ g
3. 计算公钥：h ≡ f⁻¹ * g mod q
4. 加密：c ≡ r*h + m mod q
5. 解密：
   • a ≡ f*c mod q
   • b ≡ a mod g
   • m ≡ b*f⁻¹ mod g

3.2.2 攻击方法

寻找满足F*h ≡ G mod q的(F,G)，可以构造格：

[[1, h],
 [0, q]]

应用LLL算法找到最短向量(F,G)，即可用于解密。

3.3 [羊城杯 2022]LRSA题目解析

3.3.1 题目分析

给定：

• P²Q和PQ²，可求出P和Q
• t = (pP - 58P + q) mod Q
• 目标：恢复p,q

3.3.2 解题步骤

1. 计算PQ = gcd(P²Q, PQ²)

2. 分别求出P和Q

3. 构造格：

   [[1, P],
    [0, Q]]
   

4. 应用LLL找到最短向量(p-58, t-q)

5. 恢复p和q

6. 正常RSA解密

3.3.3 示例代码

from Crypto.Util.number import *

B = 1023
PPQ = 1755077239... # 题目给定的大数
PQQ = 1763250373... # 题目给定的大数
t = 44
c = 4364802217...  # 密文
e = 65537

# 计算P和Q
PQ = gcd(PPQ, PQQ)
P = PPQ // PQ
Q = PQQ // PQ

# 构造格并应用LLL
L = matrix(ZZ, [[1, P], [0, Q]])
v = L.LLL()[0]
p_58, t_q = map(abs, v)

# 恢复p和q
p = p_58 + 58
q = t_q + t

# RSA解密
n = p*q
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# 输出: DASCTF{8f3djoj9wedj2_dkc903cwckckdk}

4. 总结

1. 背包问题可以通过构造特定格并应用LLL算法解决
2. NTRU等格密码系统可能因参数选择不当而被LLL攻击
3. 在CTF中，遇到模方程、小未知数等问题时，可考虑格基约化方法
4. LLL算法在低维格中效果较好，高维时效果会下降

5. 关键点

1. 问题转换：将加密问题转化为寻找格中短向量的问题
2. 矩阵构造：正确构造格基矩阵是应用LLL的关键
3. 参数范围：LLL适用于小未知数情况，大数效果不佳
4. 多解处理：模运算可能带来多解，需要遍历可能的解空间

6. 参考资料

1. 格密码学习笔记 - gal2xy's blog
2. 格密码简介 - lazzzaro's blog
3. 格密码基础 - ruanx.net
4. NIST后量子密码标准化项目