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

  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.

我们可以看到,私钥分为两个部分,第一部分是最基本的私钥参数,有了(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, 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).

我们之前对$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只有两个因数的情况):

  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$

对上面的过程进行证明:
因为有$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$,我们可以用搜索回溯的方法恢复密钥,方法如下

  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$与已知部分是否符合

上面的陈述的是搜索剪枝的思想,在搜索的时候我们采用广度优先搜索的方式进行搜索。
但是我们不能忽略一个重要的点,就是$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
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
#!/usr/bin/python3

import re
from itertools import product
from Crypto.Util.number import GCD, inverse


def solve_linear(a, b, mod):
if a & 1 == 0 or b & 1 == 0:
return None
return (b * inverse(a, mod)) & (mod - 1) # 计算b*a^(-1)%mod


def to_n(s):
s = re.sub(r"[^0-9a-f]", "", s)
return int(s, 16)


def msk(s):
cleaned = "".join(map(lambda x: x[-2:], s.split(":"))) #去掉冒号和多余字符和空格
return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)


def msk_ranges(s): # 求每一个半字节的取值范围
return [range(16) if c == " " else [int(c, 16)] for c in s]


def msk_mask(s):
return int("".join("0" if c == " " else "f" for c in s), 16)


def msk_val(s):
return int("".join("0" if c == " " else c for c in s), 16)


N = to_n("""\
00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
e8:6c:1d""")

p_ranges, pmask_msk, pmask_val = msk("""\
0: e: : : :c :c : : : :b : : : : :
:ab: e: 2: 8:c : : : 1:6 :6 : 6: f:d9: 0:
8 :5c:7 :06: : : :0 : 3:5 :4b: :6 : : :
2 : :6 : : : :2 :bc: c: :85:1 : 1:d : 3:
1:b4: : b: 1: 3: d:a : : :6e: 0:b :2 : :
:b : :9 :e : :82:8d: : :13: : : a: a:
: :4 : :c : f: : :7 :e :0a: : : b: 5:
: e:91:3 : :3c: 9: : 6: : :b5:7d: 1: :
: : :b :a1:99:6 :4 :3 :c :1a:02:4 : : 9:
9 :f : d:bd: :0 : : : :b3: : 4: :e9: 9:
: d: : :7 : :93: : e:dc: : 0: :e7: :
e : :2 : b: 2:5 : : : : : c:5f: : :e2:
: : 9: :2a: : e: : :2 : :9f: 7:3 : :
b : f:b : : 8: 7: : :f :6 :e :c : :3 : :
f7: 5: 8: 5: : : : : : 8: e: :03: c: :
33:76:e : 1:7 : c: : 0: :0b: : a: : 2: 9:
:c8:bf: : :06: 7:d5: :02: c:b :e2: 7:2 :
: """)

q_ranges, qmask_msk, qmask_val = msk("""\
0: f: :d0: 1:55: 4:31: : b:c4:8 : : e: d:
34: 3:f : : : : : 8:99:1 : : a:0 : :4 :
0 : :f : :a4:41:2 : :a : : 1: : a: c: :
: : 9: : : 2:f4: f: : : : :1 : 4:9 :
a : : :79:0 : : : : : 2: 8:b : :4 : 8:
:9b: 1: :d : :f :e4: :4 :c :e : :3 : :
7:2 : :d :8 :2 :7 : :d :67:fc:e : 0:f9: 7:
8 : : : :1 :2f: :51: : :2e:0a: e:3d: 6:
b : :dd: : 0:fb: :f4: : : :b4: 9:c : :
a: : : :d : : :6b: 2: :9b: a:60: :d6:
0:4f:16:d1: : :5 :fc: :f : :8 : : : :
1: 6:e1:9 : e:4 : 6: c: d:d :73: 3: : :7 :
:8 : 9: :3b:f : 2: : :f1: e: : :1e: :
8 : : : 6:0 : 4:99:e : : 5: : : 4: : :
: a:81:64: :7 :f : 9: d: :9 : : 7:93:f :
ac:8c: : 8: : 0: d: 8: :7 : :1d: :f : :
1 :a :6 :8 : :60: :b3: : : :89: : :14:
:5 """)


_, dmask_msk, dmask_val = msk("""\
: : : f:8 :a5:d : 2: 0:b :7 : : 1: : 4:
1:0d: :3 : :6 : : : b: : : :e : : :
0e: 0:db: :1a:1c:c0: : e: : :99:bc:8 :a5:
7 :7 :7 : b: : : 8: 8: :7 :55: 2: : :f :
b2: : :b :f :4 : : 8: :b : : : : 0: :
0 : :6 :9 : : : : b: 4: : 0: a: 5:07:b :
9: c:9a: 9: : 7:9e: : b:60:f : : : :0 :
: 3:0 : : : : 1:b : : : b: 6:0 :f : :
: 2:18: 6: b:1 : : : : :d3:f3: :a : :
3: : : : : 3: d: 1: 2:7 : : d: : 2: d:
: : d:4 : :d : :6d: c:a :b6: : : : 1:
69: : 7: :89: :c :8 :61: d:25: 3:7 :1b: 4:
b : :8 :55: :49: 1:2 :3 : :1 :e9:a8: 3: :
9 : : 1:f8:d3: :e : :d : :9 :b6: : :71:
1 : :c1: : b: 1: : 6:e : :64: : :1a:c :
: b: :bf:c : : 0: : 8:a :4 : :26:a :5 :
6 : : : :eb: :e5: a: :3e:f9:10:0 : : :
6:0 : : 8: : 1:72: c:0 : f:5 : f:9c: 0: e:
7:b : : : : :d9: 4: : e:c :68: : : :
c: :3a: : :a0:ea: 3: 4: :72:a :d : 8: :
:0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
: :17:6 : : c: b: : f: :3 : 5:6 :3 :0e:
: 7:c :3e: 2: 9: 7: 6: f: e: f: 9: :f3: 9:
a :c1:6 : : 1:9 : :43: : f: 5: :0 :27: 4:
4 :a : :e9: : 8: 4:3 :8a: 6:16:d5:c : e: e:
:d : c:b :a8: : 7: : 9: :7 :7d: : : :
: : :4 :2 : : 3: 3: 6: : : :7b:0 : :
e: :0 : :a : : 5: : : : 5:1 :82:c :0d:
4 :2 :fd:36: 5:50:0 : : :d : f: 6: : :e :
0 : : :ce: :9e:8 : :0 :d :07:b3: : : :
0 :e4: : :68:b :c : : c:5 : : :3 : 7: 2:
c:e0: :5 : : :b4: :ef: 7: :1 :e : 0:f :
:6 : : : :e0:c :3 : : : 3: : d: : :
3: 3: c: a: :b : a:71: 3: 0:a : :4 :5d: :
0 :4 """)


_, dpmask_msk, dpmask_val = msk("""\
: 3:2a: : d: : : : :0 :1 : f: : : 6:
1 :2 :1b:07: a:e :b :c5:58:7 : :e8: 7: 1: c:
: 1:b :a0: 4:0f:5 :67: :3 :7 :6 :f9: : c:
:79: 0:1 :65: :8 : :99: d:d : :2 :9 :0 :
e: :0 : : : : d: :d :7 :6 :a9: a:8b: b:
: : 7: a:37: : :7 :1 :6 : :c2: 7:6 :b :
e: : : : : : :b :3a:5 : : : : : :
: : :cd:8 : : d: :7 : 3: : f:e : c: :
: a: :c : f:c : 7:b :5 : : :2 :8 :8 :6 :
0a: a: : :3 :db: : 4:00: : d: :b : 5: :
20: 2: 5: :82: : 0: 6: :8a: :7 : : 8: :
4: 1: : : : 8:46: : : : : : 0:f :c8:
2 : : c:7 : : 1: : :2 : 0: 5: : : 1:9b:
6:9 : 0:74: :c : :e : : :cb:b :3 :3 : :
2: : :47: :2 : 0:5 : : : d: 6:83: : :
:c7: : :0b: : : c: :3 :8 : :9 :4 : 7:
5 :c0:fe: :f9: 1: :0 : e: 8:02: : f: :c :
55:61""")

_, dqmask_msk, dqmask_val = msk("""\
:0b:7 :4 :0 : 0:6 : 7:7e: : 5: : 7: : a:
a :d : 0: 6: 4:86: : :8 : : : : :e :8f:
9: : : : 1: :2 : : 7: b:1 :5 : f: :8 :
:d :21: :e : d: :c9:e : b: : :1 : : :
:d :a2:b7: : : :f3: :42: :e : c: :f :
: 0:f :7 : 4: 5:34: :4 : c: : :8 :d : 8:
5 :af: 3:1d: 5:4 : :2 : :6 :c : 6:a :1 :5 :
a:9 : :d : : :0a:a1: :f :7 :9 :b : : :
f:2 :27: f: :0 :f6:4d: : : : : :5 : :
4:08: : 5: : 8: 5: : : :18: 4: 8:57: 2:
f: a: : :a8: f: c:f : e: 1:9 :c : 4:9 : :
: : : : : 1: :2 : :d1: : 6:e : d: :
: f:04:2 :8d: : 3: : :b : 8: :d6: : 2:
: : :6 : : f: : : 0:6 : :51: :48:19:
: : :69:4 : c: :c : : f: :f4:d : : f:
d:0 :0d:b :3 : 3:2 : : :6 : b:5 :2 : : c:
1:5a: f:f : : :7e:3e: :d :f :0 : d: c: 6:
1""")


E = 0x10001

def search(K, Kp, Kq, check_level, break_step):
max_step = 0
cands = [0] # 广搜队列
for step in range(1, break_step + 1):
# step代表复原倒数第step步
max_step = max(step, max_step)

mod = 1 << (4 * step)
mask = mod - 1

cands_next = []
for p, new_digit in product(cands, p_ranges[-step]):
pval = (new_digit << ((step - 1) * 4)) | p

# 四个剪枝
if check_level >= 1:
qval = solve_linear(pval, N & mask, mod)
if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
continue

if check_level >= 2:
val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
if val is None or not check_val(val, mask, dmask_msk, dmask_val):
continue

if check_level >= 3:
val = solve_linear(E, 1 + Kp * (pval - 1), mod)
if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
continue

if check_level >= 4:
val = solve_linear(E, 1 + Kq * (qval - 1), mod)
if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
continue

if pval * qval == N: #得到答案
print("Kq =", Kq)
print("pwned")
print("p =", pval)
print("q =", qval)
p = pval
q = qval
d = inverse(E, (p - 1) * (q - 1))
print("d =", d)
coef = inverse(p, q)

from Crypto.PublicKey import RSA
print(RSA.construct((N, E, d, p, q, coef)).exportKey().decode())
quit()

cands_next.append(pval)

if not cands_next:
return False
cands = cands_next
return True


def check_val(val, mask, mask_msk, mask_val):
test_mask = mask_msk & mask
test_val = mask_val & mask
return val & test_mask == test_val



for K in range(1, E):
if K % 100 == 0:
print("checking", K)
if search(K, 0, 0, check_level=2, break_step=20):
print("K =", K)
break

for Kp in range(1, E):
if Kp % 1000 == 0:
print("checking", Kp)
if search(K, Kp, 0, check_level=3, break_step=30):
print("Kp =", Kp)
break

for Kq in range(1, E):
if Kq % 100 == 0:
print("checking", Kq)
if search(K, Kp, Kq, check_level=4, break_step=9999):
print("Kq =", Kq)
break

当然最后还有一个坑,不像前几个RSA用的是PKCS padding,这个加密之后的文件用的是OAEP padding方式,要用
openssl rsautl -decrypt -inkey private.pem -keyform PEM -in flag.enc -oaep
指定OAEP填充方式,巨坑

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。