Partial Key Exposure Attack On Low-Exponent RSA

前置知识

RSA加密算法是一种非对称加密算法,RSA算法的可靠性基于对极大整数做因数分解的难度。
我们先来看下如何进行RSA加/解密:

公钥与私钥的产生

1)选取两个大素数 $p$ 和 $q$ ,$p ≠ q$, 计算 $N = pq$
2)根据欧拉函数 ,求 $r = \varphi \left( N\right) = \varphi ( p) \varphi( q) = (p-1)(q-1)$
3)选取一个小于 $r$ 的整数 $e$ ,使 $e$ 和 $r$ 互素。求 $e$ 和 $r$ 的模返元素命名为 $d$ ($ed\equiv 1\pmod r$)
$\left( N,e\right)$ 就是公钥,$\left( N,d\right)$ 就是私钥

加/解密

假设 $m$ 为明文 $c$ 为密文,加密过程即
$$c\equiv m^{e} \pmod N$$
解密过程:
$$c^{d}=m\pmod N $$

原理

$$c^{d}\equiv m^{ed} \pmod N$$
我们知道 $ed=1 \pmod r $, 即 $ed=1+h\varphi \left( N\right)$。所以我们就可以得到:
$$n^{ed}=n^{1+h\varphi \left( N\right)}=n\left(n^{\varphi (N)}\right)^{h}\equiv n(1)^{h} \pmod N\equiv n \pmod N$$

如何进行攻击

前提条件

要完成攻击需要私钥泄露的最低位位数超过 $n/4$ (n为N的比特数)

经典做法

首先我们先设 $d_0$ 为泄露的私钥 $n$ 为N的比特数 $s = (p + q)$
1)我们先列出这个等式:$ed_0 \equiv 1 + k(N - s + 1) \pmod 2^{n/4}$
2)通过不断的对 $k$ 取值我们可以计算出 $s$ 的值
3)然后我们再运用这个等式:$p^{2} - sp + N \equiv 0 \pmod 2^{n/4}$
4)计算出 $p_0$ $q_0$ 的值 ($p_0$ $q_0$一定是整数 同时$p_0q_0 = N \mod 8$ 不是可以排除)
5)接下来把得到的 $p_0$ $q_0$ 代入 $f\left( x,y\right) = (rx + p_0)(ry + q_0) - N$ ($r = n/4$)
6)我们解出 $xy$,$p = rx + p_0$、$q = ry + q_0$
7)通过 $ed - k\varphi(N) = 1$ 计算出 $d$ 在和泄露出来的最低位比较来确认 $d$ 是否正确

快速做法

快速做法的核心就是下面这个公式
$$d = (kN + 1) / e$$
这里的 $d$ 只是真正的 $d$ 的近似值,求出来之后我们需要拿泄露的最低位替换近似值的最低位
同时也带来了一个问题 如果泄露的位数不够就无法完成攻击

未完待续