LCG与模运算在CTF密码学中的应用

1. LCG问题解析

基本概念

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

Xₙ₊₁ = (a*Xₙ + c) mod m

其中：

• Xₙ是当前状态
• a是乘数
• c是增量
• m是模数

CTF中的解法

在CTF中，LCG问题通常需要从已知输出序列反推初始种子seed：

1. 如果有足够多的连续输出，可以通过解线性方程组恢复参数a, c, m
2. 已知参数的情况下，可以通过逆运算求得前一个状态：

   Xₙ = (Xₙ₊₁ - c) * a⁻¹ mod m
   

   其中a⁻¹是a在模m下的乘法逆元

2. 模运算与移位问题

问题描述

给定flag转换为大整数M后左移10000位(即乘以2¹⁰⁰⁰⁰)，要求：

M * 2¹⁰⁰⁰⁰ ≡ K (mod 10¹²⁵)

解决步骤

1. 模数分解：

   10¹²⁵ = 2¹²⁵ * 5¹²⁵
   

2. 验证可解性：

   • 检查K是否能被2¹²⁵整除
   • 如果K ≡ 0 mod 2¹²⁵，则方程有解

3. 简化方程：
   两边除以2¹²⁵：

   M * 2⁹⁸⁷⁵ ≡ K' (mod 5¹²⁵)
   

   其中K' = K / 2¹²⁵

4. 求逆元：

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

5. 最终解：

   M ≡ K' * (2⁹⁸⁷⁵)⁻¹ mod 5¹²⁵
   

3. Ununicast任务解析

问题特征

需要通过模逆运算消除多余的(i+1)因子，然后使用中国剩余定理(CRT)合并同余方程。

解决步骤

1. 处理同余方程：
   对于每个方程，通过乘以(i+1)的逆元来消除该因子

2. 应用CRT：

   • 将所有处理后的同余方程合并
   • 求得mᵉ的值

3. 低指数攻击：

   • 爆破e的可能范围
   • 对mᵉ开e次方恢复m

4. RSA相关攻击方法

Part1: 基于二项式定理的攻击

数学原理

给定hint = (2024p+2025)ᵟ - 2025ⁿ：

1. 展开(2024p+2025)ᵟ：

   (2024p+2025)ᵟ ≡ 2025ᵟ mod p
   

   因为除常数项外所有项都含p

2. 根据费马小定理：

   2025ⁿ = 2025ᵖ*ᵟ ≡ (2025ᵖ)ᵟ ≡ 2025ᵟ mod p
   

3. 因此：

   hint ≡ 2025ᵟ - 2025ᵟ ≡ 0 mod p
   

   所以p | hint

攻击步骤

1. 计算x = hint - 2025ⁿ
2. 计算gcd(x, n)得到p

Part2: 两种攻击方法

(原文未详细说明，可能是以下两种常见方法)

1. 小指数攻击：当e很小时，直接对密文开e次方
2. 共模攻击：相同n不同e的情况下，使用扩展欧几里得算法恢复明文

Part3: 基于模运算的分析

数学原理

给定hint = (g+1111p)ᵉ mod n：

1. 模p分析：

   hint ≡ (g+1111p)ᵉ ≡ gᵉ mod p
   

2. 计算x = hint - gᵉ：

   x ≡ 0 mod p ⇒ p | x
   

攻击步骤

1. 计算x = hint - gᵉ
2. 计算gcd(x, n)得到p

5. 关键工具与技术

1. 中国剩余定理(CRT)：

   • 用于合并多个同余方程
   • 特别适用于模数分解后的情况

2. 模逆元计算：

   • 使用扩展欧几里得算法
   • 条件：gcd(a,m) = 1

3. 费马小定理：

   • 对于素数p和a不被p整除：

     aᵖ⁻¹ ≡ 1 mod p
     

   • 推论：aᵏ ≡ aᵏ mod (p-1) mod p

4. GCD计算：

   • 用于恢复共享因子
   • 欧几里得算法及其扩展形式

5. 二项式定理应用：

   • 展开多项式时识别可忽略的项
   • 在模运算中简化表达式

6. 实际应用建议

1. 对于LCG问题：

   • 确保有足够的状态序列来恢复参数
   • 注意逆运算时的模数条件

2. 对于模运算问题：

   • 优先考虑模数分解
   • 验证方程的可解性
   • 合理使用CRT

3. 对于RSA相关问题：

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

4. 编码实现时：

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