Two Easy Ways to Factor RSA

Introduction

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

https://id0-rsa.pub/problem/15/

https://id0-rsa.pub/problem/45/

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出现呢?

  1. 某些任意精度的整数库出问题了。
  2. 在读写数据时有条件竞争
  3. CPU的运算单元出问题了(CPU本身问题或者外部环境影响)。
  4. 私钥$(p, q, d_p, d_q, q_{inv})$中某部分变了。
  5. 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之类的,因此问题不会太大。

Load Comments?