[RSA]私钥重构
Openssl中私钥的构成
在传统的RSA中，通常我们认为(n,e)是公钥，(n,d)是私钥，加密解密使用
$c\equiv m^e\pmod n, \ m\equiv c^d\pmod n$
这固然是没有问题的，但是考虑到我们一般取$e=\text{0x10001}$，这个时候d一般是一个很大的数字，加密起来速度很慢。
在私钥中不仅存在我们熟知的n, e, d,我们在查看私钥openssl rsa -in private.pem -text时发现私钥中存在以下值：
| 参数 | 含义 |
|---|---|
| modulus | $n$ |
| publicExponent | $e$ |
| privateExponent | $d$ |
| prime1 | $p$ |
| prime2 | $q$ |
| exponent1 | $d_p=d \bmod {(p-1)}$ |
| exponent2 | $d_q=d\bmod {(q-1)}$ |
| coefficient | $q_p=q^{-1}\bmod p$ |
在RSA加密标准PKCS #1 v2.2中我们可以看到这样的描述：
For the purposes of this document, an RSA private key may have either
of two representations.
The first representation consists of the pair (n, d), where the
components have the following meanings:n the RSA modulus, a positive integer d the RSA private exponent, a positive integerThe second representation consists of a quintuple (p, q, dP, dQ,
qInv) and a (possibly empty) sequence of triplets (r_i, d_i,
t_i), i = 3, …, u, one for each prime not in the quintuple,
where the components have the following meanings:p the first factor, a positive integer q the second factor, a positive integer dP the first factor's CRT exponent, a positive integer dQ the second factor's CRT exponent, a positive integer qInv the (first) CRT coefficient, a positive integer r_i the i-th factor, a positive integer d_i the i-th factor's CRT exponent, a positive integer t_i the i-th factor's CRT coefficient, a positive integerIn a valid RSA private key with the first representation, the RSA
modulus n is the same as in the corresponding RSA public key and is
the product of u distinct odd primes r_i, i = 1, 2, …, u, where u
>= 2. The RSA private exponent d is a positive integer less than n
satisfyinge * d == 1 (mod \lambda(n)),
where e is the corresponding RSA public exponent and \lambda(n) is
defined as in Section 3.1.
我们可以看到，私钥分为两个部分，第一部分是最基本的私钥参数，有了(n,d)才能完成解密过程；另一部分参数是为了加速解密速度。
In a valid RSA private key with the second representation, the two
factors p and q are the first two prime factors of the RSA modulus n
(i.e., r_1 and r_2); the CRT exponents dP and dQ are positive
integers less than p and q, respectively, satisfyinge * dP == 1 (mod (p-1)) e * dQ == 1 (mod (q-1)) ,and the CRT coefficient qInv is a positive integer less than p
satisfyingq * qInv == 1 (mod p).
我们之前对$d_p$的定义是$d_p=d\pmod{(p-1)}$，在这里我们做以下推导
$$
\begin{aligned}
d_p&\equiv d&\pmod {p-1}\\
ed_p&\equiv ed&\pmod {p-1}\\
ed_p&\equiv k\varphi(n)+1&\pmod{p-1}\\
ed_p&\equiv k(p-1)(q-1)+1&\pmod{p-1}\\
ed_p&\equiv 1&\pmod{p-1}
\end{aligned}
$$
同理可得$ed_q\equiv 1\pmod {q-1}$
RSA的解密过程
我们先参考一下原文
a. If the first form (n, d) of K is used, let m = c^d mod n. b. If the second form (p, q, dP, dQ, qInv) and (r_i, d_i, t_i) of K is used, proceed as follows: i. Let m_1 = c^dP mod p and m_2 = c^dQ mod q. ii. If u > 2, let m_i = c^(d_i) mod r_i, i = 3, ..., u. iii. Let h = (m_1 - m_2) * qInv mod p. iv. Let m = m_2 + q * h. v. If u > 2, let R = r_1 and for i = 3 to u do 1. Let R = R * r_(i-1). 2. Let h = (m_i - m) * t_i mod r_i. 3. Let m = m + R * h.
我们可以看到如果只有(n,d)就直接按原始的解密公式解密就行。如果给出了第二部分的参数，就按如下的步骤进行（只考虑n只有两个因数的情况）：
- $m_1=c^{d_p}\bmod p,\ m_2=c^{d_q}\bmod q$
- $h=(m_1-m_2)*q_p \bmod p$
- $m=m_2+qh$
对上面的过程进行证明：
因为有$ed_p\equiv 1\pmod {p-1}$，所以$m_1=m^{ed_p}\bmod p=m^{k(p-1)+1}\bmod p$
由于p是质数，所以由费马小定理$m^{(p-1)}\equiv 1\pmod p$可得到$m_1=m\bmod p$，同理$m_2=m\bmod q$
现在我们得到了$m_1,m_2$，需要用中国剩余定理求取$m$。
我们不妨令$m_1=m-k_1p,\ m_2=m-k_2q$，所以就有：
$$
\begin{aligned}
h&=(m_1-m_2)q_p\bmod p\\
&=(k_2q-k_1p)q_p\bmod p\\
&=k_2q(q^{-1}\bmod p)\bmod p\ -k_1pq_p\bmod p\\
&=k_2
\end{aligned}
$$
$$
\begin{aligned}
m&=m_2+qh\\
&=(m-k_2q)+k_2q\\
&=m
\end{aligned}
$$
如何尝试恢复私钥
首先我们因为得到了一个残缺不全的私钥，我们得到了一部分的私钥，私钥中有以下关系：
$$
\begin{aligned}
\varphi(n) &= n-p-q+1\\
ed&\equiv1\pmod{\varphi(n)}\\
ed_p&\equiv 1 \pmod{(p-1)}\\
ed_q&\equiv 1\pmod{(q-1)}\\
n &= pq
\end{aligned}
$$
在对其简易变形一下，我们在引入三个变量$k. k_p, k_q$，对上面的公式进行变形：
$$
\begin{aligned}
ed& = k\varphi(n) + 1\\
ed_p& = k_p(p-1) + 1\\
ed_q&=k_q(q-1)+1
\end{aligned}
$$
如果$a=b$，那么显然$a\equiv b\pmod n$
更进一步，如果我们只考虑最低的t个半字节(4bit)，既，把等式变换成$\pmod {16^t}$的同余式。
$$
\begin{aligned}
\varphi(n)&\equiv n-p-q+1&\pmod {16^t}\\
ed&\equiv k\varphi(n)+1&\pmod {16^t}\\
ed_p&\equiv k_p(p-1)+1&\pmod {16^t}\\
ed_q&\equiv k_q(q-1)+1&\pmod {16^t}\\
n&\equiv pq&\pmod {16^t}
\end{aligned}
$$
我们现在知道完整的$n,e$，部分的$d,p,q,d_p,d_q$，完全不知道$k,k_p,k_q$，我们可以用搜索回溯的方法恢复密钥，方法如下
- 枚举第t位p可能的取值
- 因为$n\equiv pq\pmod{16^t}$，所以计算$p=n\times q^{-1}\bmod {16^t}$，检查q的已知值
- 计算$d=(1+k(n-p-q+1))\times e^{-1}\bmod {16^t}$，检查d与已知部分是否符合
- 计算$d_p = (1+d_p(p-1)) \times e^{-1}\bmod {16^t}$，检查$d_p$与已知部分是否符合
- 计算$d_q=(1+d_q(q-1))\times e^{-1}\bmod{16^t}$，检查$d_q$与已知部分是否符合
上面的陈述的是搜索和剪枝的思想，在搜索的时候我们采用广度优先搜索的方式进行搜索。
但是我们不能忽略一个重要的点，就是$d,d_p,d_q$的确定，在上面的表述中我们可以发现，如果要使用3,4,5步剪枝，就分别必须知道$d,d_p,d_q$的取值，在这之前我们先确定这三个值的范围。因为$ed=k\varphi(n)+1$，并且$d<\varphi(n)$，所以必然有$k < e$；同理，$k_p < e, k_q < e$。
那么我们就可以使用这样的搜索方法，先枚举$k$的取值，对每个$k$尝试搜索答案（仅用步骤1,2,3），如果可以搜索到达一定层数（代码中是20层），我们就确定当前$k$为正确值；然后我们枚举$k_p$的取值，用1,2,3,4步进行搜索，如果可以达到一定层数（代码中是30层），我们就确定$k_p$的值；最后我们枚举$k_q$的取值，尝试搜索出结果。
Jarvis OJ GodLike RSA
这道题目给出了一个4096位的RSA公钥，标准e，同时给出了部分私钥，参考国外类似题目wp，我们编写脚本完成解密
1 | #!/usr/bin/python3 |
当然最后还有一个坑，不像前几个RSA用的是PKCS padding，这个加密之后的文件用的是OAEP padding方式，要用openssl rsautl -decrypt -inkey private.pem -keyform PEM -in flag.enc -oaep
指定OAEP填充方式，巨坑