CTF实战分享 | Crypto-RSA(二)
内容提要
本文介绍了几个RSA密码学题目的解题思路和代码实现，包括欧拉定理、威尔逊定理和二次剩余等数论知识。通过分析和计算题目参数，得到了明文的解密结果。
延伸解读
从“参数齐全”到“数论技巧”：RSA 解题的阶梯
本文的题目展示了 RSA 攻击的典型进阶路径：第一题直接给出 p、q、e、c，只需计算私钥 d 即可解密；后续题目则逐步隐藏参数，需要利用中国剩余定理、威尔逊定理、欧拉定理和二次剩余等数论工具。读者可以从中体会到，CTF 中的 RSA 题往往不是单纯计算，而是识别题目条件背后的数学结构，从而选择对应的攻击方法。
多素数 RSA 与多项式求根：分解 n 后的组合策略
在 [0ctf 2016]rsa 中，n 被分解为三个素数 p、q、r，且 e=3。由于 m^e ≡ c (mod n)，可以分别在模 p、q、r 下求多项式 x^3 - c 的根，再用中国剩余定理组合出所有可能的明文。这提示我们，当 n 含有多个因子时，分解后利用小指数和 CRT 是常见思路，但需注意可能产生多个候选解，需要遍历筛选。
已知平方关系时如何恢复因子：开方与整除
在 [HDCTF 2023]Normal_Rsa(revenge) 中，题目给出了 P = p^2 mod n 和 Q = q^2 mod n。由于 p、q 远小于 n，直接对 P、Q 开平方即可恢复 p、q，再通过 n // (p*q) 得到 r。这说明当题目泄露与因子相关的平方值时，若没有模 n 回绕，整数开方就能直接分解 n，无需复杂计算。
利用最低位泄露：ROR 题中的比特逐位恢复
在 [zer0pts 2020]ROR 中，每行输出是循环右移后明文的 e 次幂模 N。由于 N 是偶数，对 2 取模后，幂运算的结果最低位等于循环右移后明文的最低位。遍历所有行并提取最低位，再反转顺序，即可逐位拼出原始明文。这展示了当模数为偶数时，奇偶性等简单性质可能成为破解的突破口。
Q&A
RSA题目中已知p、q、e、c，如何快速求出明文？
计算n=p*q，欧拉函数φ(n)=(p-1)*(q-1)，私钥d为e模φ(n)的逆元，即d=gmpy2.invert(e,phi)，然后明文m=pow(c,d,n)，最后用long_to_bytes(m)转换为字节。
当RSA的模数n可以分解为三个素数p、q、r，且e=3时，如何利用中国剩余定理求解明文？
分别构造多项式f(x)=x^e - c在模p、q、r下的根，得到每个模下的解集，然后对这些解集进行笛卡尔积组合，每组解使用中国剩余定理（CRT）合并，得到候选明文列表，最后遍历列表转换为字节找到flag。
RSA题目中给出P=pow(p,2,n)和Q=pow(q,2,n)，如何分解n？
由于P ≡ p^2 (mod n)，Q ≡ q^2 (mod n)，且n=p*q*r，可以对P和Q分别开平方根得到p和q（因为p和q是素数且小于n），然后r = n // (p*q)，从而分解n。
RSA题目中给出hint = p^3 - q^5和n = p*q，如何求解p和q？
建立方程组：p^3 - q^5 = hint，p*q = n。使用符号计算库（如sympy）求解该非线性方程组，得到p和q的值，然后按常规RSA解密。
在RSA变种题目中，加密指数e很大且模数N未知，但已知N是2、3、7的幂次乘积，如何恢复明文？
观察密文ci = pow(ror(m, i, m.bit_length()), e, N)，由于N是偶数，ci的奇偶性与ror(m, i, m.bit_length())的奇偶性相同，而ror操作是循环移位，最低位对应m的某一位。收集所有ci的最低位，按顺序拼接并反转，即可得到m的二进制表示，进而转换为字节。
如何利用威尔逊定理解决RSA题目中涉及阶乘的加密？
题目中m经过多次乘法：for i in range(1, p-q): m = m*i % n，得到m1 = m*(p-q-1)! % n。利用威尔逊定理：(p-1)! ≡ -1 mod p，通过构造m1 * (p-q)*...*(p-1) ≡ m*(p-1)! ≡ -m mod p，从而解出m ≡ -m1 * inv( (p-q)*...*(p-1) ) mod p。
RSA题目中密文c = pow(m, n-p-q+3, n)，如何利用欧拉定理解密？
由欧拉定理，m^φ(n) ≡ 1 mod n，其中φ(n)=n-p-q+1。因此c ≡ m^(n-p-q+3) ≡ m^2 * m^φ(n) ≡ m^2 mod n。所以m^2 ≡ c mod n，遍历k，对c+k*n开平方根，找到整数平方根即为m。
RSA题目中给出r是素数且r%4=3，a=pow(p,2,r)，如何利用二次剩余求解p？
因为r%4=3，且a是p^2 mod r，所以p是a模r的二次剩余。由于r≡3 mod 4，平方根为p ≡ a^((r+1)/4) mod r 或 p ≡ -a^((r+1)/4) mod r。结合n=p*q，可以通过尝试这些根来分解n。
