知识点

正如前面所说的，如果按照正确的方式来进行 RSA 的密钥生成、密钥管理和加解密流程，本质上是不会有太多问题的。

但有时候，有些出题人会去魔改算法，从而给我们留下了可乘之机。

费马分解法

若两个质数 $p$ 和 $q$ 之间差异过小，则可以利用 费马分解法 进行模数 $n$​ 的分解。

设模数 $n$ 的一个平方根为 $r$ ，即 $r^2=n$​ ，而已知 $n$ 求解其平方根还是很容易的。

则此时质数 $p$ 和 $q$ 一定在 $r$​ 附近。且 $p,q$ 差异越小，两者都越接近 $r$ 。

这一点非常好理解，就不用证明了。

那么用在解题中，可以通过对 $n$ 开平方根，取整数部分，再在附近进行质数枚举，则能很快找到 $n$ 的因子。这个时间复杂度取决于 $p,q$ 之间的差异大小。

Pollard-Rho 算法

这个算法写出证明和方法相对较长，网上也有很多现成的轮子，很多工具中也自动集成了，如 sage，yafu。所以这里就只提一句，更多可以查阅这个文章，介绍的挺详细的。

Pollard-Rho 就是构建了一个伪随机数生成器，然后不停用生成的随机数去判断是不是模数 $n$ 的一个根。

欧拉函数

对于正整数 $n$ ，欧拉函数 $\varphi(n)$ 的意义是小于 $n$ 的正整数中与 $n$ 互质的数的数目。（PS：两个数 $a$ 和 $b$ 互质 $\Leftrightarrow gcd(a,b) = 1$​ 。

根据定义，很容易得到，对于任意质数 $p$ ，有 $\varphi(p)=p-1$ 。

已知任意一个数，求解欧拉函数可以利用唯一分解定理，将整数 $n$ 唯一分解。再利用各个质数的 $\varphi$​ 来求解。最终结果为:

$P={p_1,p_2…}$​ 为所有质数集合

特别地，当 $n = p \times q$ ，$p$ 和 $q$ 都是质数时，有 $\varphi(n)=\varphi(p) \times \varphi(q) = (p-1) \times (q-1)$ 。

当 $n = p \times q \times r$ ， $p$ ，$q$ 和 $r$ 都是质数时，有 $\varphi(n)=\varphi(p) \times \varphi(q) \times \varphi(r) = (p-1) \times (q-1) \times (r-1)$

例题

2020 全国大学生信息安全大赛线上初赛密码题 rsa

题目

题目描述如下：

小明经过研究，发现 RSA 加密算法可以推广，也就是它的模不仅仅是只能为两个素数的乘积，只要是 2 个以上不同的素数相乘都可以。

给出的文件 cipher.txt 也只有很简单的 $n,e,c$ 三个数。

1
2
3
n = 50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999
e = 65537
c = 45005399504992587510006608300548120810512973768886391125598523343330913326304417790989607300367232977960116381108873363343598357102136548218343380795022179607741940866191404186680657699739176842869814452906110393321567314747096161480003824583613027819960172221

题解

根据题目的提示信息，可以得知这是一个 multi-prime RSA 。通过分析可以知道 $n$​ 的二进制位数只有 863 ，同时多质因数，则说明 $n$ 的质因数至少有 $3$ 个。故每个质因数的平均二进制位数大约为 $863 \div 3 = 287.67$ ，而如果质因数的个数比 $3$ 个还多，则每个质因数的平均位数将更低，这说明这些质数其实都不大。

故有以下两种情况：

  1. 要么这些质数都很接近，则可以用前面讲的费马分解的方法进行攻击。
  2. 要么这些质数就不会很接近，则最小的质数的位数将比平均位数还要小，而此时最小的质数最大的可能情况下，其二进制位数也必然小于 $287$ 。则可以利用Pollard-Rho 进行攻击。

但事实上，使用 yafu 和 sage 分解了很久都是无法分解成功的。（应该是时间还不够久，至少我没耐心等了。

于是，就再来考虑情况，质数的个数有没有可能再多太多？显然，个数越多越不安全，最下的质数越小，越容易被 Pollard-Rho 计算出来；同时各个质数还应该差异足够大，否则容易被费马攻击。

这两点显示存在着矛盾，所以最后的结论是，质数个数一定是尽可能少的（不然 yafu 早就跑出来了）， 故 $3$​​ 的概率最大。同时差异比较大，所以可以考虑将枚举范围开大一些。

所以，可以用手动开方再进行枚举。

脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2

n = 50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999

# 这个阈值是怎么决定的？ 说起来都是泪，反正时间如果够的话，可以再开大一点，不然 yafu 早就跑出来了
Threshold = 1<<30


# 也可以用 gmpy2.next_prime() 去遍历，而不用 +1 毕竟对方肯定是质数嘛
# 但是事实上，好像这样更快 6 倍。。。。。。
for k in range(3, 5):
    p0 = gmpy2.iroot(n, k)[0]
    for i in range(Threshold):
        if n % (p0 + i) == 0:
            print(p0 + i)
            break
        if n % (p0 - i) == 0:
            print(p0 - i)
            break

于是可以成功跑出来一个质因数 $368751654879714877087975516875168751974879716873087714877516875971487715687518277898523$ 。

然后，就简单了 yafu 一瞬解出剩下的。

yafu分解成功

脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2
from Crypto.Util.number import long_to_bytes

n = 50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999
e = 65537
c = 45005399504992587510006608300548120810512973768886391125598523343330913326304417790989607300367232977960116381108873363343598357102136548218343380795022179607741940866191404186680657699739176842869814452906110393321567314747096161480003824583613027819960172221

p1 = 368751654879714877087975516875168751974879716873087714877516875971487715687518277898523
p2 = 368751654879714877087975516875168751974879716873087714877516875971487715687518438089619
p3 = 368751654879714877087975516875168751974879716873087714877516875971487715687516888458327

phi = (p1-1)*(p2-1)*(p3-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)

flag = long_to_bytes(m)
print(flag)
# b'flag{4e9f2a7f-bda9-4a46-af51-b29e0c61973e}'

结语

此外还有其他类似的，但都可以通过类似的方法解决。