# [RSA]私钥重构

## Openssl中私钥的构成

$c\equiv m^e\pmod n, \ m\equiv c^d\pmod n$

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$

For the purposes of this document, an RSA private key may have either
of two representations.

1. 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 integer
2. The 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 integer

In 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
satisfying

e * d == 1 (mod \lambda(n)),

where e is the corresponding RSA public exponent and \lambda(n) is
defined as in Section 3.1.

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, satisfying

e * dP == 1 (mod (p-1))

e * dQ == 1 (mod (q-1)) ,

and the CRT coefficient qInv is a positive integer less than p
satisfying

q * qInv == 1 (mod p).

\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}

## 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.

1. $m_1=c^{d_p}\bmod p,\ m_2=c^{d_q}\bmod q$
2. $h=(m_1-m_2)*q_p \bmod p$
3. $m=m_2+qh$

\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}

\begin{aligned} ed& = k\varphi(n) + 1\\ ed_p& = k_p(p-1) + 1\\ ed_q&=k_q(q-1)+1 \end{aligned}

\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}

1. 枚举第t位p可能的取值
2. 因为$n\equiv pq\pmod{16^t}$，所以计算$p=n\times q^{-1}\bmod {16^t}$，检查q的已知值
3. 计算$d=(1+k(n-p-q+1))\times e^{-1}\bmod {16^t}$，检查d与已知部分是否符合
4. 计算$d_p = (1+d_p(p-1)) \times e^{-1}\bmod {16^t}$，检查$d_p$与已知部分是否符合
5. 计算$d_q=(1+d_q(q-1))\times e^{-1}\bmod{16^t}$，检查$d_q$与已知部分是否符合

## Jarvis OJ GodLike RSA

openssl rsautl -decrypt -inkey private.pem -keyform PEM -in flag.enc -oaep