PolarD&N--2025春季个人挑战赛--Crypto-WP-先知社区

LCG

task:

普通的LCG问题，只需要逆运算求得初始种子seed即可。

exp:

beginner

task:

原题是给定一个flag，将其转换为大整数M后左移10000位，也就是乘以2^10000，得到的十进制数的最后125位要与给定的字符串匹配。

可以表达为：M * 2^10000 ≡ K (mod 10^125)

其中，K是给定的那个大整数值。这里的关键是将模数分解为2^125和5^125，然后应用中国剩余定理（CRT）来分步解决。

根据之前的分析，首先需要处理的是模数分解后的两个部分。因为10^125 = 2^125 * 5^125，而K必须被2^125整除，否则方程无解。验证之后，K确实能被2^125整除，所以可以将方程两边同时除以2^125，得到：M * 2^(10000 - 125) ≡ K' (mod 5^125)

这里，10000 - 125 = 9875，也就是原方程中的指数从10000减少到9875，因为我们在两边都除以了2^125。

所以新的方程变为：M * 2^9875 ≡ K' (mod 5^125)

接下来需要求解M，这就需要计算2^9875在模5^125下的逆元。逆元的存在性需要2^9875和5^125互质，显然5^125是5的幂，而2和5互质，因此2^9875与5^125互质，逆元存在。

计算逆元后，方程的解为：M ≡ K' * (2^9875的逆元) mod 5^125

exp:

Ununicast

task:

这里需要通过模逆运算，消除多余的

(i+1)

因子。然后再通过中国剩余定理合并所有同余方程，求得m^e,再通过低指数攻击爆破e的范围求得m

exp:

RSA1-2

task:

part1：

根据二项式定理展开，除常数项外，所有项均含

，因此模

时：

(2024p+2025)^q≡2025^qmod p

-->(2024p+2025)^q−2025^n≡0modp

因为

n = p*q

，所以

2025^n ≡ 2025^{p*q} ≡ (2025^p)^q ≡ 2025^q \mod p

（费马小定理）。因此：

hint−2025^n≡2025^q−2025^q≡0mod p

所以

x = hint - 2025^n

是

的倍数，用

gcd(x, n)

即可提取出

。

exp:

part3:

根据题目中的

hint

定义：

通过模运算分析：

模

：

hint≡(g+1111p)^e mod p≡g^emod p

计算

x = hint - g^e

：

x ≡ 0 mod p

⇒ p=gcd⁡(x,n)

exp:

part2：

这个攻击知道两种方法：