2025年能源网络安全大赛Crypto赛题解析教学文档

一、NumberTheory题目解析

1.1 题目分析

题目源码分析：

from Crypto.Util.number import *
import hint

flag=b'xxx'
e=65537
p=getPrime(512)
q=getPrime(512)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
k=getPrime(1024)
assert hint + 233 * k == 233 * k * p
print(n)
print(c)
print(hint)

关键信息：

• RSA加密系统，使用标准参数（e=65537）
• 特殊构造：hint + 233 * k = 233 * k * p
• 给出n、c、hint三个值

1.2 数学原理推导

从断言条件推导：

hint + 233*k = 233*k*p
⇒ hint = 233*k*p - 233*k
⇒ hint = 233*k*(p-1)

关键洞察：

• hint包含p-1的倍数信息
• 可以利用费马小定理进行因数分解

1.3 解题方法

费马小定理应用：
对于任意整数a满足gcd(a, n)=1，有：

a^(p-1) ≡ 1 (mod p)
a^(hint) ≡ a^(233*k*(p-1)) ≡ 1^(233*k) ≡ 1 (mod p)

因此：

a^(hint) - 1 ≡ 0 (mod p)

这意味着a^(hint)-1是p的倍数，同时它也是n的因数，因此：

p = gcd(a^hint - 1, n)

1.4 解题EXP详解

from random import randint
from Cryptodome.Util.number import long_to_bytes
from gmpy2 import gcd, invert

# 给定参数
e = 65537
n = 84099006955126261966925371456202769943592466221370095794235167154956697927281125181449320270460637820908574232493978429962263974458426503598700104493216727535451616752760724333653967152401716945549285008242019874215196489846481143398374860288545040874468108191037481101604627874268575884573685952474988256841
c = 28098063654079651384124474197746356824080585622155888018279898490747561415908220072536298610509681898119018709183606442183944207485940115624047842734359988590155403601250406116023121958193303908964857108526965815235457652033182982467968474248778435731228104089366239566977364311197776651102290796373095167764
hint = 411245630228311610573345621334618725748702407327926883063919892785851166202383809662483938501531987094884084543300939673794551515912845363503988032311234800260819110323258416786417746444373651130257247926678135654564298408894174083333804257126735899220917359603430399033328133462456659839525671074605146583034398735379485362144932899212206419889556154825755723979850750847762362288223441051219637465296077020565435562941976546609555729574021362954126496825972439730

# 选择基数a（通常选择2或3）
a = 2

# 计算p = gcd(2^hint - 1, n)
p = gcd(pow(a, hint, n) - 1, n)

# 计算q
q = n // p

# 标准RSA解密流程
phi = (p-1) * (q-1)
d = invert(e, phi)
m = pow(c, d, n)

# 转换为明文
flag = long_to_bytes(m)
print(flag)

1.5 技术要点总结

1. 数学洞察力：识别hint与p-1的关系是关键
2. 费马小定理应用：利用模运算性质进行因数分解
3. 计算优化：使用模幂运算避免大数计算
4. 完整性验证：确保p*q=n且p、q为素数

二、easy_lwe题目解析

2.1 题目分析

题目源码分析：

from Crypto.Util.number import *
from secrets import flag
assert len(flag) == 38

p = getPrime(512)
m = getPrime(512)
while m > p:
    m = getPrime(512)

aa = []
cc = []
bb = []
for i in range(30):
    a = getPrime(512)
    b = getPrime(400)  # 小误差项
    c = (a * m + b) % p
    aa.append(a)
    cc.append(c)
    bb.append(b)

enc = pow(m, flag, p)
print(f'p = {p}')
print(f'aa = {aa}')
print(f'cc = {cc}')
print(f'enc = {enc}')

2.2 LWE问题背景

学习有错误问题（Learning With Errors, LWE）特征：

• 公钥：多个线性方程c_i ≡ a_i * m + b_i (mod p)
• 私钥：秘密值m
• 特点：每个方程包含小误差项b_i

密码学意义：

• LWE是格密码学的基础问题
• 具有抗量子计算攻击的特性
• 在构建后量子密码系统中广泛应用

2.3 解题思路

方法一：格基约化攻击

由于b_i是400位素数，相对于512位的p和m较小，可以构建格进行攻击。

格构造：

[ p  0  0 ... 0  0 ]
[ 0  p  0 ... 0  0 ]
[ ...    ...      ]
[ 0  0  0 ... p  0 ]
[ a1 a2 a3...an 1 ]

目标向量包含秘密m和误差项b_i。

方法二：线性代数方法

由于题目中b_i相对较小，可以通过消去误差项的方法求解。

关键观察：
对于两个不同的方程：

c_i ≡ a_i * m + b_i (mod p)
c_j ≡ a_j * m + b_j (mod p)

相减消去m项可能不可行，但可以利用多个方程建立超定方程组。

2.4 解题步骤

1. 建立方程系统：30个方程，1个未知数m
2. 处理误差项：b_i相对较小（400位 vs 512位）
3. 求解m：使用格基约化或最小二乘法
4. 离散对数求解：已知enc = m^flag mod p，求解flag

2.5 技术实现要点

# 伪代码示例
def solve_lwe(p, aa, cc):
    # 构建格或方程系统
    # 使用LLL算法或BKZ算法进行格基约化
    # 提取短向量得到秘密值m
    return m

def solve_dlp(m, enc, p):
    # 求解离散对数问题 enc = m^flag mod p
    # 使用Pohlig-Hellman、BSGS或index calculus方法
    return flag

三、综合技术总结

3.1 密码学知识点

1. 数论基础：费马小定理、模运算、素数性质
2. RSA密码系统：密钥生成、加密解密、因数分解
3. 格密码学：LWE问题、格基约化算法
4. 离散对数问题：在有限域中的难解性问题

3.2 解题技巧

1. 数学关系识别：从题目条件中挖掘隐藏的数学关系
2. 参数大小分析：识别不同参数的大小关系（如误差项相对大小）
3. 算法选择：根据问题特点选择合适的密码分析算法
4. 计算优化：使用高效的数论计算库（如gmpy2）

3.3 实际应用意义

这些题目体现了现实密码系统中的常见漏洞：

• 不当的参数生成可能导致安全问题
• 侧信道信息（如hint）可能泄露关键信息
• 误差项过小可能破坏LWE问题的安全性

通过此类题目的训练，可以加深对密码学原理的理解和实际密码分析能力的提升。