2025年能源网络安全大赛Crypto赛题解析教学文档<\/h1>

一、NumberTheory题目解析<\/h2>

1.1 题目分析<\/h3>
题目源码分析：<\/strong><\/p>
from<\/span> Crypto.Util.number import<\/span> *<\/span>
<\/span><\/span>import<\/span> hint
<\/span><\/span>
<\/span><\/span>flag=<\/span>b<\/span>'xxx'<\/span>
<\/span><\/span>e=<\/span>65537<\/span>
<\/span><\/span>p=<\/span>getPrime(512<\/span>)
<\/span><\/span>q=<\/span>getPrime(512<\/span>)
<\/span><\/span>n=<\/span>p*<\/span>q
<\/span><\/span>m=<\/span>bytes_to_long(flag)
<\/span><\/span>c=<\/span>pow(m,e,n)
<\/span><\/span>k=<\/span>getPrime(1024<\/span>)
<\/span><\/span>assert<\/span> hint +<\/span> 233<\/span> *<\/span> k ==<\/span> 233<\/span> *<\/span> k *<\/span> p
<\/span><\/span>print(n)
<\/span><\/span>print(c)
<\/span><\/span>print(hint)
<\/span><\/span><\/code><\/pre>关键信息：<\/strong><\/p>

RSA加密系统，使用标准参数（e=65537）<\/li>
特殊构造：hint + 233 * k = 233 * k * p<\/code><\/li>
给出n、c、hint三个值<\/li>
<\/ul>
1.2 数学原理推导<\/h3>
从断言条件推导：<\/p>
hint + 233*k = 233*k*p
⇒ hint = 233*k*p - 233*k
⇒ hint = 233*k*(p-1)
<\/code><\/pre>
关键洞察：<\/strong><\/p>

hint包含p-1的倍数信息<\/li>
可以利用费马小定理进行因数分解<\/li>
<\/ul>
1.3 解题方法<\/h3>
费马小定理应用：<\/strong>

对于任意整数a满足gcd(a, n)=1，有：<\/p>
a^(p-1) ≡ 1 (mod p)
a^(hint) ≡ a^(233*k*(p-1)) ≡ 1^(233*k) ≡ 1 (mod p)
<\/code><\/pre>
因此：<\/p>
a^(hint) - 1 ≡ 0 (mod p)
<\/code><\/pre>
这意味着a^(hint)-1<\/code>是p的倍数，同时它也是n的因数，因此：<\/p>
p = gcd(a^hint - 1, n)
<\/code><\/pre>
1.4 解题EXP详解<\/h3>
from<\/span> random import<\/span> randint
<\/span><\/span>from<\/span> Cryptodome.Util.number import<\/span> long_to_bytes
<\/span><\/span>from<\/span> gmpy2 import<\/span> gcd, invert
<\/span><\/span>
<\/span><\/span># 给定参数<\/span>
<\/span><\/span>e =<\/span> 65537<\/span>
<\/span><\/span>n =<\/span> 84099006955126261966925371456202769943592466221370095794235167154956697927281125181449320270460637820908574232493978429962263974458426503598700104493216727535451616752760724333653967152401716945549285008242019874215196489846481143398374860288545040874468108191037481101604627874268575884573685952474988256841<\/span>
<\/span><\/span>c =<\/span> 28098063654079651384124474197746356824080585622155888018279898490747561415908220072536298610509681898119018709183606442183944207485940115624047842734359988590155403601250406116023121958193303908964857108526965815235457652033182982467968474248778435731228104089366239566977364311197776651102290796373095167764<\/span>
<\/span><\/span>hint =<\/span> 411245630228311610573345621334618725748702407327926883063919892785851166202383809662483938501531987094884084543300939673794551515912845363503988032311234800260819110323258416786417746444373651130257247926678135654564298408894174083333804257126735899220917359603430399033328133462456659839525671074605146583034398735379485362144932899212206419889556154825755723979850750847762362288223441051219637465296077020565435562941976546609555729574021362954126496825972439730<\/span>
<\/span><\/span>
<\/span><\/span># 选择基数a（通常选择2或3）<\/span>
<\/span><\/span>a =<\/span> 2<\/span>
<\/span><\/span>
<\/span><\/span># 计算p = gcd(2^hint - 1, n)<\/span>
<\/span><\/span>p =<\/span> gcd(pow(a, hint, n) -<\/span> 1<\/span>, n)
<\/span><\/span>
<\/span><\/span># 计算q<\/span>
<\/span><\/span>q =<\/span> n \/\/<\/span> p
<\/span><\/span>
<\/span><\/span># 标准RSA解密流程<\/span>
<\/span><\/span>phi =<\/span> (p-<\/span>1<\/span>) *<\/span> (q-<\/span>1<\/span>)
<\/span><\/span>d =<\/span> invert(e, phi)
<\/span><\/span>m =<\/span> pow(c, d, n)
<\/span><\/span>
<\/span><\/span># 转换为明文<\/span>
<\/span><\/span>flag =<\/span> long_to_bytes(m)
<\/span><\/span>print(flag)
<\/span><\/span><\/code><\/pre>1.5 技术要点总结<\/h3>

数学洞察力<\/strong>：识别hint与p-1的关系是关键<\/li>
费马小定理应用<\/strong>：利用模运算性质进行因数分解<\/li>
计算优化<\/strong>：使用模幂运算避免大数计算<\/li>
完整性验证<\/strong>：确保p*q=n且p、q为素数<\/li>
<\/ol>
二、easy_lwe题目解析<\/h2>
2.1 题目分析<\/h3>
题目源码分析：<\/strong><\/p>
from<\/span> Crypto.Util.number import<\/span> *<\/span>
<\/span><\/span>from<\/span> secrets import<\/span> flag
<\/span><\/span>assert<\/span> len(flag) ==<\/span> 38<\/span>
<\/span><\/span>
<\/span><\/span>p =<\/span> getPrime(512<\/span>)
<\/span><\/span>m =<\/span> getPrime(512<\/span>)
<\/span><\/span>while<\/span> m ><\/span> p:
<\/span><\/span>    m =<\/span> getPrime(512<\/span>)
<\/span><\/span>
<\/span><\/span>aa =<\/span> []
<\/span><\/span>cc =<\/span> []
<\/span><\/span>bb =<\/span> []
<\/span><\/span>for<\/span> i in<\/span> range(30<\/span>):
<\/span><\/span>    a =<\/span> getPrime(512<\/span>)
<\/span><\/span>    b =<\/span> getPrime(400<\/span>)  # 小误差项<\/span>
<\/span><\/span>    c =<\/span> (a *<\/span> m +<\/span> b) %<\/span> p
<\/span><\/span>    aa.<\/span>append(a)
<\/span><\/span>    cc.<\/span>append(c)
<\/span><\/span>    bb.<\/span>append(b)
<\/span><\/span>
<\/span><\/span>enc =<\/span> pow(m, flag, p)
<\/span><\/span>print(f<\/span>'p = <\/span>{<\/span>p}<\/span>'<\/span>)
<\/span><\/span>print(f<\/span>'aa = <\/span>{<\/span>aa}<\/span>'<\/span>)
<\/span><\/span>print(f<\/span>'cc = <\/span>{<\/span>cc}<\/span>'<\/span>)
<\/span><\/span>print(f<\/span>'enc = <\/span>{<\/span>enc}<\/span>'<\/span>)
<\/span><\/span><\/code><\/pre>2.2 LWE问题背景<\/h3>
学习有错误问题（Learning With Errors, LWE）特征：<\/strong><\/p>

公钥：多个线性方程c_i ≡ a_i * m + b_i (mod p)<\/code><\/li>
私钥：秘密值m<\/li>
特点：每个方程包含小误差项b_i<\/li>
<\/ul>
密码学意义：<\/strong><\/p>

LWE是格密码学的基础问题<\/li>
具有抗量子计算攻击的特性<\/li>
在构建后量子密码系统中广泛应用<\/li>
<\/ul>
2.3 解题思路<\/h3>
方法一：格基约化攻击<\/h4>
由于b_i是400位素数，相对于512位的p和m较小，可以构建格进行攻击。<\/p>
格构造：<\/strong><\/p>
[ p  0  0 ... 0  0 ]
[ 0  p  0 ... 0  0 ]
[ ...    ...      ]
[ 0  0  0 ... p  0 ]
[ a1 a2 a3...an 1 ]
<\/code><\/pre>
目标向量包含秘密m和误差项b_i。<\/p>
方法二：线性代数方法<\/h4>
由于题目中b_i相对较小，可以通过消去误差项的方法求解。<\/p>
关键观察：<\/strong>

对于两个不同的方程：<\/p>
c_i ≡ a_i * m + b_i (mod p)
c_j ≡ a_j * m + b_j (mod p)
<\/code><\/pre>
相减消去m项可能不可行，但可以利用多个方程建立超定方程组。<\/p>
2.4 解题步骤<\/h3>

建立方程系统<\/strong>：30个方程，1个未知数m<\/li>
处理误差项<\/strong>：b_i相对较小（400位 vs 512位）<\/li>
求解m<\/strong>：使用格基约化或最小二乘法<\/li>
离散对数求解<\/strong>：已知enc = m^flag mod p，求解flag<\/li>
<\/ol>
2.5 技术实现要点<\/h3>
# 伪代码示例<\/span>
<\/span><\/span>def<\/span> solve_lwe<\/span>(p, aa, cc):
<\/span><\/span>    # 构建格或方程系统<\/span>
<\/span><\/span>    # 使用LLL算法或BKZ算法进行格基约化<\/span>
<\/span><\/span>    # 提取短向量得到秘密值m<\/span>
<\/span><\/span>    return<\/span> m
<\/span><\/span>
<\/span><\/span>def<\/span> solve_dlp<\/span>(m, enc, p):
<\/span><\/span>    # 求解离散对数问题 enc = m^flag mod p<\/span>
<\/span><\/span>    # 使用Pohlig-Hellman、BSGS或index calculus方法<\/span>
<\/span><\/span>    return<\/span> flag
<\/span><\/span><\/code><\/pre>三、综合技术总结<\/h2>
3.1 密码学知识点<\/h3>

数论基础<\/strong>：费马小定理、模运算、素数性质<\/li>
RSA密码系统<\/strong>：密钥生成、加密解密、因数分解<\/li>
格密码学<\/strong>：LWE问题、格基约化算法<\/li>
离散对数问题<\/strong>：在有限域中的难解性问题<\/li>
<\/ol>
3.2 解题技巧<\/h3>

数学关系识别<\/strong>：从题目条件中挖掘隐藏的数学关系<\/li>
参数大小分析<\/strong>：识别不同参数的大小关系（如误差项相对大小）<\/li>
算法选择<\/strong>：根据问题特点选择合适的密码分析算法<\/li>
计算优化<\/strong>：使用高效的数论计算库（如gmpy2）<\/li>
<\/ol>
3.3 实际应用意义<\/h3>
这些题目体现了现实密码系统中的常见漏洞：<\/p>

不当的参数生成可能导致安全问题<\/li>
侧信道信息（如hint）可能泄露关键信息<\/li>
误差项过小可能破坏LWE问题的安全性<\/li>
<\/ul>
通过此类题目的训练，可以加深对密码学原理的理解和实际密码分析能力的提升。<\/p>