LCG与模运算在CTF密码学中的应用<\/h1>

1. LCG问题解析<\/h2>

基本概念<\/h3>

线性同余生成器(LCG)是一种伪随机数生成算法，其递推公式为：<\/p>

Xₙ₊₁ = (a*Xₙ + c) mod m
<\/code><\/pre>
其中：<\/p>

Xₙ是当前状态<\/li>
a是乘数<\/li>
c是增量<\/li>
m是模数<\/li>
<\/ul>
CTF中的解法<\/h3>
在CTF中，LCG问题通常需要从已知输出序列反推初始种子seed：<\/p>

如果有足够多的连续输出，可以通过解线性方程组恢复参数a, c, m<\/li>
已知参数的情况下，可以通过逆运算求得前一个状态：
Xₙ = (Xₙ₊₁ - c) * a⁻¹ mod m
<\/code><\/pre>
其中a⁻¹是a在模m下的乘法逆元<\/li>
<\/ol>
2. 模运算与移位问题<\/h2>
问题描述<\/h3>
给定flag转换为大整数M后左移10000位(即乘以2¹⁰⁰⁰⁰)，要求：<\/p>
M * 2¹⁰⁰⁰⁰ ≡ K (mod 10¹²⁵)
<\/code><\/pre>
解决步骤<\/h3>


模数分解<\/strong>：<\/p>
10¹²⁵ = 2¹²⁵ * 5¹²⁵
<\/code><\/pre>
<\/li>

验证可解性<\/strong>：<\/p>

检查K是否能被2¹²⁵整除<\/li>
如果K ≡ 0 mod 2¹²⁵，则方程有解<\/li>
<\/ul>
<\/li>

简化方程<\/strong>：

两边除以2¹²⁵：<\/p>
M * 2⁹⁸⁷⁵ ≡ K' (mod 5¹²⁵)
<\/code><\/pre>
其中K' = K \/ 2¹²⁵<\/p>
<\/li>

求逆元<\/strong>：<\/p>

因为gcd(2,5)=1，所以2⁹⁸⁷⁵在模5¹²⁵下有逆元<\/li>
计算(2⁹⁸⁷⁵)⁻¹ mod 5¹²⁵<\/li>
<\/ul>
<\/li>

最终解<\/strong>：<\/p>
M ≡ K' * (2⁹⁸⁷⁵)⁻¹ mod 5¹²⁵
<\/code><\/pre>
<\/li>
<\/ol>
3. Ununicast任务解析<\/h2>
问题特征<\/h3>
需要通过模逆运算消除多余的(i+1)因子，然后使用中国剩余定理(CRT)合并同余方程。<\/p>
解决步骤<\/h3>


处理同余方程<\/strong>：

对于每个方程，通过乘以(i+1)的逆元来消除该因子<\/p>
<\/li>

应用CRT<\/strong>：<\/p>

将所有处理后的同余方程合并<\/li>
求得mᵉ的值<\/li>
<\/ul>
<\/li>

低指数攻击<\/strong>：<\/p>

爆破e的可能范围<\/li>
对mᵉ开e次方恢复m<\/li>
<\/ul>
<\/li>
<\/ol>
4. RSA相关攻击方法<\/h2>
Part1: 基于二项式定理的攻击<\/h3>
数学原理<\/h4>
给定hint = (2024p+2025)ᵟ - 2025ⁿ：<\/p>


展开(2024p+2025)ᵟ：<\/p>
(2024p+2025)ᵟ ≡ 2025ᵟ mod p
<\/code><\/pre>
因为除常数项外所有项都含p<\/p>
<\/li>

根据费马小定理：<\/p>
2025ⁿ = 2025ᵖ*ᵟ ≡ (2025ᵖ)ᵟ ≡ 2025ᵟ mod p
<\/code><\/pre>
<\/li>

因此：<\/p>
hint ≡ 2025ᵟ - 2025ᵟ ≡ 0 mod p
<\/code><\/pre>
所以p | hint<\/p>
<\/li>
<\/ol>
攻击步骤<\/h4>

计算x = hint - 2025ⁿ<\/li>
计算gcd(x, n)得到p<\/li>
<\/ol>
Part2: 两种攻击方法<\/h3>
(原文未详细说明，可能是以下两种常见方法)<\/p>

小指数攻击<\/strong>：当e很小时，直接对密文开e次方<\/li>
共模攻击<\/strong>：相同n不同e的情况下，使用扩展欧几里得算法恢复明文<\/li>
<\/ol>
Part3: 基于模运算的分析<\/h3>
数学原理<\/h4>
给定hint = (g+1111p)ᵉ mod n：<\/p>

模p分析：
hint ≡ (g+1111p)ᵉ ≡ gᵉ mod p
<\/code><\/pre>
<\/li>
计算x = hint - gᵉ：
x ≡ 0 mod p ⇒ p | x
<\/code><\/pre>
<\/li>
<\/ol>
攻击步骤<\/h4>

计算x = hint - gᵉ<\/li>
计算gcd(x, n)得到p<\/li>
<\/ol>
5. 关键工具与技术<\/h2>


中国剩余定理(CRT)<\/strong>：<\/p>

用于合并多个同余方程<\/li>
特别适用于模数分解后的情况<\/li>
<\/ul>
<\/li>

模逆元计算<\/strong>：<\/p>

使用扩展欧几里得算法<\/li>
条件：gcd(a,m) = 1<\/li>
<\/ul>
<\/li>

费马小定理<\/strong>：<\/p>

对于素数p和a不被p整除：
aᵖ⁻¹ ≡ 1 mod p
<\/code><\/pre>
<\/li>
推论：aᵏ ≡ aᵏ mod (p-1) mod p<\/li>
<\/ul>
<\/li>

GCD计算<\/strong>：<\/p>

用于恢复共享因子<\/li>
欧几里得算法及其扩展形式<\/li>
<\/ul>
<\/li>

二项式定理应用<\/strong>：<\/p>

展开多项式时识别可忽略的项<\/li>
在模运算中简化表达式<\/li>
<\/ul>
<\/li>
<\/ol>
6. 实际应用建议<\/h2>


对于LCG问题：<\/p>

确保有足够的状态序列来恢复参数<\/li>
注意逆运算时的模数条件<\/li>
<\/ul>
<\/li>

对于模运算问题：<\/p>

优先考虑模数分解<\/li>
验证方程的可解性<\/li>
合理使用CRT<\/li>
<\/ul>
<\/li>

对于RSA相关问题：<\/p>

注意观察数学结构中的特殊形式<\/li>
灵活应用数论定理<\/li>
尝试构造与模数相关的表达式来恢复因子<\/li>
<\/ul>
<\/li>

编码实现时：<\/p>

使用大整数运算库(如Python的gmpy2)<\/li>
注意计算效率，特别是大指数运算<\/li>
验证中间结果的正确性<\/li>
<\/ul>
<\/li>
<\/ol>

LCG与模运算在CTF密码学中的应用<\/h1>

1. LCG问题解析<\/h2>

2. 模运算与移位问题<\/h2>

3. Ununicast任务解析<\/h2>

问题特征<\/h3> 需要通过模逆运算消除多余的(i+1)因子，然后使用中国剩余定理(CRT)合并同余方程。<\/p>

4. RSA相关攻击方法<\/h2>

Part1: 基于二项式定理的攻击<\/h3>

Part3: 基于模运算的分析<\/h3>

问题特征<\/h3>
需要通过模逆运算消除多余的(i+1)因子，然后使用中国剩余定理(CRT)合并同余方程。<\/p>