Two Easy Ways to Factor RSA

Introduction

在id0-rsa.pub上做题，记录下自己的理解。

Factor n with fault attack

RSA-CRT optimization

paper：https://people.redhat.com/~fweimer/rsa-crt-leaks.pdf

在RSA中，如果我们知道了$n$的分解$p, q$，那么在解密（签名）的时候我们可以利用环同构 $$ \mathbb{Z}/n\mathbb{Z} \longleftrightarrow \mathbb{Z}/p\mathbb{Z} \oplus \mathbb{Z}/q\mathbb{Z} $$ 来把在$\bmod{n}$上的解密（签名）运算 $$ m \equiv c^d \pmod{n} $$ 转化为分别在$\bmod{p}$和$\bmod{q}$上的运算： $$ \begin{cases} m_p & \equiv c_p^{d_p} \pmod{p}\newline m_q & \equiv c_q^{d_q} \pmod{q} \end{cases} $$ 再利用CRT（Chinese Remainder Theorem，中国剩余定理）来得到在$\bmod{n}$下的解。

这样大概能使解密运算快上4倍。

这种优化就被称作为RSA-CRT optimization。

在实际操作中，一般是先预先计算好 $$ \begin{cases} d_p & \equiv e^{-1} \pmod{p-1}\newline d_q & \equiv e^{-1} \pmod{q-1}\newline q_{inv} & \equiv q^{-1} \pmod{p} \end{cases} $$ 然后，在解密的时候，只需要 $$ \begin{cases} m_p & \equiv c_p^{d_p} \pmod{p}\newline m_q & \equiv c_q^{d_q} \pmod{q}\newline h & \equiv q_{inv} \cdot (m_p - m_q) \pmod{p} \end{cases} \Longrightarrow m = m_q + h \cdot q $$

里面这个$h$，实际上就跟Hensel’s lifting 里从$\bmod{p}$到$\bmod{p^2}$中$r_2 = r_1 + tp$里的这个$t$差不多的东西。

虽然可能一下子想出这个$h$不太容易，但是可以反向验证一下正确性：

$\bmod{q}$：显然，$m \equiv m_q\pmod{q}$

$\bmod{p}$：代入一下$h, q_{inv}$，$m\equiv m_q + q^{-1} \cdot (m_p - m_q) \cdot q \equiv m_o \pmod{p}$

这样就能感觉到为什么会那个样子构造$h$了，实际上这边就是一种CRT的构造解法。

Arjen Lenstra’s CRT attack

如果我没有看错的话，这个Lenstra应该就是提出LLL算法（Lenstra–Lenstra–Lovász lattice basis reduction algorithm ）中的某个L。

感觉paper讲的很清晰了，直接上图：

Screen Shot 2020-05-01 at 1.58.00 PM

那么，会有哪些可能会导致这种Fault出现呢？

某些任意精度的整数库出问题了。
在读写数据时有条件竞争
CPU的运算单元出问题了（CPU本身问题或者外部环境影响）。
私钥$(p, q, d_p, d_q, q_{inv})$中某部分变了。
CPU缓存或者内存受影响导致bit errors。

如何避免这种情况？

很简单，只要在签名（解密）完后，再验证一遍即可：$y^e \equiv x \pmod{n}$

实际上之前CNSS 2019 Recruit的时候也有一道Fault Attack的题目：坤坤的帅气签名

Factor n given public exponent && private exponent

给定$(n, e, d)$，我们也能分解出$p, q$。

1571317572853

可以自己测试一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


In [1]: from Crypto.Util.number import *

In [2]: p = getPrime(50)

In [3]: q = getPrime(50)

In [4]: n = p*q

In [5]: e = 0x10001

In [6]: d = inverse(e, (p-1)*(q-1))

In [7]: p, q, n, e, d
Out[7]:
(595736391353269,
 1115779042489183,
 664710180320111683519664189227,
 65537,
 537877996898485924520932355009)

In [8]: kphi = e*d - 1

In [9]: kphi
Out[9]: 35250910282736072035328343750224832

In [10]: pow(2, kphi, n)
Out[10]: 1

In [11]: pow(2, kphi // 2, n)
Out[11]: 1

In [12]: pow(2, kphi // 4, n)
Out[12]: 1

In [13]: pow(2, kphi // 8, n)
Out[13]: 1

In [14]: pow(2, kphi // 16, n)
Out[14]: 1

In [15]: pow(2, kphi // 32, n)
Out[15]: 78760480679820634213819949631

In [16]: pow(2, kphi // 16, p)
Out[16]: 1

In [17]: pow(2, kphi // 16, q)
Out[17]: 1

In [18]: pow(2, kphi // 32, q)
Out[18]: 1

In [19]: pow(2, kphi // 32, p)
Out[19]: 595736391353268

In [20]: p - 1
Out[20]: 595736391353268

可以发现，pow(2, kphi // 32, n) != 1的原因就是由于pow(2, kphi // 32, p) != 1。

而此时却有pow(2, kphi // 32, q) == 1，就这说明x = pow(2, kphi // 32, n) - 1会是$p$的倍数，而不会是$q$的倍数（因此，不是$n$的倍数），这样再取GCD(x, n)，就可以得到$n$的一个分解：$p$。

当然，也有可能，pow(2, kphi // 32)模$p$和模$q$都不为1。这个时候就要把2换成另外一个素数，然后继续这个操作。

上面那个算法的指数是从小到大的顺序，我这边测试的时候是从大到小的顺序。

不难理解，这个分解方法，实际上就是利用环同构 $$ \mathbb{Z}/n\mathbb{Z} \longleftrightarrow \mathbb{Z}/p\mathbb{Z} \oplus \mathbb{Z}/q\mathbb{Z} $$ 不断地对1这个数开平方根。

我们知道，在模（素数）运算下，1的平方根只有两个：1, -1。

在$\mathbb{Z}/n\mathbb{Z}$里等于1，实际上就相当于分别在$\mathbb{Z}/p\mathbb{Z}$和$\mathbb{Z}/q\mathbb{Z}$里等于1。

我们在$\mathbb{Z}/n\mathbb{Z}$里不断地对1开根（即把指数$k \cdot (p-1)\cdot(q-1)$除以2），也就是相当于分别在$\mathbb{Z}/p\mathbb{Z}$和$\mathbb{Z}/q\mathbb{Z}$里不断地对1开根。

由于$p-1, q-1$一开始都是偶数（$k$一开始也可能有一些2），所以一开始都还是会在$\mathbb{Z}/p\mathbb{Z}$和$\mathbb{Z}/q\mathbb{Z}$里等于1的。

当我们把指数里的$k\cdot (p-1) \cdot (q-1)$中$k\cdot (p-1)$里的2全都除完了，由费马小定理知 $$ 2^{k\cdot(q-1) / 2^s \cdot (p-1)} \equiv 1 \pmod{p} $$ 但是，如果我们再除一次2，就有可能会（取决于底数2在$\mathbb{Z}/p\mathbb{Z}$里的阶数） $$ 2^{k\cdot(q-1) / 2^s \cdot (p-1) / 2} \equiv -1 \pmod{p} $$

如果不是-1的话，就继续不断地除以2。

其实这边的底数，最好选一个$\mathbb{Z}/p\mathbb{Z}$里的原根，这样的话这里必定是-1。

但此时另一边则可能还是 $$ 2^{k\cdot(p-1) / 2^s \cdot (q-1) / 2} \equiv 1 \pmod{q} $$ 这样就会使得这个底数在$\mathbb{Z}/n\mathbb{Z}$下会从1变为非1。

贴的图片里的算法实际上就是在寻找从非1变为1的那一步。

然后我们就可以利用上面的方法，分解出$p$。

事实上，基于我之前的某个观察，如果没有这个$n$，只给出$e, d$，我们也是可以用另外一个方法分解出$p, q$的:

NCTF 2019 babyRSA

里面的那个方法的时间复杂度是取决于公钥指数$e$的，不过RSA为了加密的效率，经常会取一些比较小的e，例如65537、3之类的，因此问题不会太大。