Harry's Blog

温故知新

0%

RSA私钥文件学习（2022蓝帽杯复现）

发表于 更新于   阅读次数： Valine：
本文字数： 22k 阅读时长 ≈ 20 分钟
蓝帽杯复现，主要为RSA私钥pem文件填充原理学习。

2022蓝帽杯·Crypto复现

没报上名，赛后复现。

corrupted_key（复现）

  • corrupted_key.py
1
2
3
4
5
6
7
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag

key = RSA.generate(1024)
open("flag.enc",'wb').write(PKCS1_OAEP.new(key.publickey()).encrypt(flag))
open('priv.pem','wb').write(key.exportKey('PEM'))

  • flag.enc

  • priv.pem

    改后缀为txt

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    -----BEGIN RSA PRIVATE KEY-----
    MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
    UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
    dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB








    yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
    zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==
    -----END RSA PRIVATE KEY-----

pem·hex下结构：

1
2
3
4
5
6
7
8
9
10
11
12
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}

不会这种残缺的pem读取，没有好使的工具

于是，比赛时，参考外国友人在其他比赛的wp

get到他的思路，找规律来人工肉眼读取pem

首先是结构，现我总结如下：

也即：

1
[30]len(总文件) + 02 01 00 + [02][len(n)]n + [02][len(e)]e + [02][len(d)]d + [02][len(p)]p + [02][len(q)]q + [02][len(dp)]dp + [02][len(dq)]dq + [02][len(qi)]qi

题目附件里的pem只有前后一点，怼着看，容易知道上面只给了n、e， 下面给了部分的dq以及完整的qi（$q^{-1} \mod p$）

n

1
2
3
4
5
6
7
8
9
10
11
12
13
(base) wenhui@Harrys-MacBook-Pro corrupted_key % echo -n 'MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB' | base64 -d | hexdump
0000000 30 82 02 5e 02 01 00 02 81 81 00 d7 15 25 06 aa
0000010 9c ec 05 e5 33 5d 6b 46 f5 49 14 07 c3 19 9f d5
0000020 10 91 f1 f6 03 0d 37 62 b9 e0 3f 49 c9 dc dc 07
0000030 50 54 e0 cc 14 8b 97 4b 41 85 4b d9 3b 4e e1 6a
0000040 2a 87 6e e6 20 05 e8 0e f8 06 b7 aa 3b 64 b1 bf
0000050 9b 1f a7 73 e3 53 d0 cd b9 ff 97 83 dd d5 f5 e6
0000060 74 99 ad 10 f3 61 e9 38 d0 0b 82 a6 a4 c4 2a 05
0000070 35 c5 e7 67 21 79 8e 86 b4 5c d4 b8 d0 3b 0d 7e
0000080 75 c2 be 87 66 a1 e8 43 bd c6 41 02 03 01 00 01
0000090

81 81 为其长度标识

1
2
3
4
5
6
7
8
9
00 d7 15 25 06 aa
9c ec 05 e5 33 5d 6b 46 f5 49 14 07 c3 19 9f d5
10 91 f1 f6 03 0d 37 62 b9 e0 3f 49 c9 dc dc 07
50 54 e0 cc 14 8b 97 4b 41 85 4b d9 3b 4e e1 6a
2a 87 6e e6 20 05 e8 0e f8 06 b7 aa 3b 64 b1 bf
9b 1f a7 73 e3 53 d0 cd b9 ff 97 83 dd d5 f5 e6
74 99 ad 10 f3 61 e9 38 d0 0b 82 a6 a4 c4 2a 05
35 c5 e7 67 21 79 8e 86 b4 5c d4 b8 d0 3b 0d 7e
75 c2 be 87 66 a1 e8 43 bd c6 41
1
2
3
4
5
6
7
8
9
10
11
txt = '''00 d7 15 25 06 aa
 9c ec 05 e5 33 5d 6b 46 f5 49 14 07 c3 19 9f d5
 10 91 f1 f6 03 0d 37 62 b9 e0 3f 49 c9 dc dc 07
 50 54 e0 cc 14 8b 97 4b 41 85 4b d9 3b 4e e1 6a
 2a 87 6e e6 20 05 e8 0e f8 06 b7 aa 3b 64 b1 bf
 9b 1f a7 73 e3 53 d0 cd b9 ff 97 83 dd d5 f5 e6
 74 99 ad 10 f3 61 e9 38 d0 0b 82 a6 a4 c4 2a 05
 35 c5 e7 67 21 79 8e 86 b4 5c d4 b8 d0 3b 0d 7e
 75 c2 be 87 66 a1 e8 43 bd c6 41'''.replace(' ', '').replace('\n', '')
print(txt)
# 00d7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641

e

1
02 03 01 00 01

e = 0x010001

$q^{-1} mod p$

1
2
3
4
5
6
7
8
9
(base) wenhui@Harrys-MacBook-Pro corrupted_key % echo -n 'yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==' | base64 -d | hexdump
0000000 c9 0b ce cf 1c ba b3 35 85 85 e8 a0 41 d1 b1 02
0000010 41 00 e3 01 6c b3 60 9c 1d 64 3c 16 74 39 c3 b9
0000020 38 b8 81 f4 23 7f 24 86 0d 3b 1c b8 5a 62 6d 5c
0000030 cd 47 26 96 4e 0f 82 70 d6 c4 df 9e bf eb cc 53
0000040 8e 4e e5 e1 a7 b7 36 8e de 51 ec 6a e9 17 f7 8e
0000050 b5 98                                          
0000052

02 后面的len是十六进制下有几组，两个为一组

1
2
3
4
5
6
7
txt = '''00 e3 01 6c b3 60 9c 1d 64 3c 16 74 39 c3 b9
38 b8 81 f4 23 7f 24 86 0d 3b 1c b8 5a 62 6d 5c
cd 47 26 96 4e 0f 82 70 d6 c4 df 9e bf eb cc 53
8e 4e e5 e1 a7 b7 36 8e de 51 ec 6a e9 17 f7 8e
b5 98 '''.replace(' ', '').replace('\n', '')
print(txt)
# 00e3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598

dq

dq = 0x........c90bcecf1cbab3358585e8a041d1b1

总

1
2
3
4
5
6
import gmpy2
# dq = 0x........c90bcecf1cbab3358585e8a041d1b1
# qi = inv(q, p)
qi = 0x00e3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
n = 0x00d7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x010001

复原私钥后解密操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

#测试密钥解密
with open('priv.pem', 'rb') as f:
    private_key = f.read()
    print(private_key)
with open('flag.enc', 'rb') as f:
    encrypt_text = f.read()
    print(encrypt_text)
private_key = RSA.importKey(private_key)
pk = PKCS1_OAEP.new(private_key)
msg = pk.decrypt(encrypt_text)
print(msg)

若破解成功后，生成完整的私钥，再执行以上代码即可解

于是，我们的目的明确：恢复私钥（分解n、求phi、求d）

Part1 - dq_h

  • 已知dq的低位(dq_l)，即：dq = d mod (q-1)
  • n
  • e

涉及给了高位或低位，无外乎CopperSmith来解

求出高位(dq_h)后，即退化为dq已知的问题

难点在于如何合理构造f函数，利用CopperSmith方法求解出dq_h

拜读官方给的选手wp，有以下思路

$q_i ≡ q^{-1} \mod p$

所以$q•q_i ≡ 1 \mod p$，即：$q•q_i -1 = k•p$

两边同乘q，得：$q^2 • q_i - q = k•n$

也就是：

1⃣️
$$
q^2 • q_i - q ≡ 0 \mod n
$$
f构造出来了，想办法把dq填入即可（好丝滑的思路👍）

聚焦dq，有：$d_q ≡ d \mod q-1$

于是有，$e•d_q ≡ e•d ≡ k’•phi +1 \mod q-1$

即：$e•d_q -1 ≡k’•(p-1)(q-1) ≡ 0 \mod q-1 $

所以有$e•d_q-1=k(q-1)$，则：

2⃣️
$$
e•d_q+k-1=kq
$$
为方便讨论，记 $t = e•d_q+k-1=kq$

为好代入1⃣️式，对1⃣️两边同乘$k^2$，得：

$(kq)^2 •q_i-k•(kq) ≡ 0 ≡ t^2•q_i-k•t\mod n$

到此，只要有正确的k就就可以使用CopperSmith了

对式2⃣️分析可知，k与e在一个数量级，于是，可以采用最为原始的遍历k来用CopperSmith解f函数

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
n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
qi = 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
e = 0x10001
dq_l = 1043891160170747082120115133012365745

k = 1
while True:
    F.<x> = PolynomialRing(Zmod(n))
    if k%100 == 0:
        print("%d times"%k)
    dq = (x * 2**120 + dq_l)
    t = dq * e - 1   + k  # 在一元copper下 变成模p爆破k
  # t = k * q  
    f = qi*t*t-k*t
    # small_roots(TT,[2**(512-120),e],m=3,d=6)
    f = f.monic()
    dq_h = f.small_roots(X = 2**(512-120),beta=0.4)
    if (len(dq_h)) != 0 :
        print(k)
        print(dq_h)
        break
    k += 1
# M1 MBP上十几、二十分钟
# 59100 times
# 59199
# [8473541887500515583954330543610580482352988466308294038598683460069270949695742839059962985745363324600134512811492604]

所以，得到：

  • k = 59199
  • dq_h = 8473541887500515583954330543610580482352988466308294038598683460069270949695742839059962985745363324600134512811492604

part2 - recover PRIVATE KEY

dq高低位都有了，即可得到dq

又有k，根据式2⃣️$e•d_q+k-1=kq$可得q

于是n分解成功，所有参数可求

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
import gmpy2

n = 0x00d7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x010001
# qi = inv(q, p)
qi = 0x00e3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
# dq = d mod (q-1) = 0x........c90bcecf1cbab3358585e8a041d1b1
dq_l = 0xc90bcecf1cbab3358585e8a041d1b1
dq_h = 8473541887500515583954330543610580482352988466308294038598683460069270949695742839059962985745363324600134512811492604
dq = (dq_h * 2**120+dq_l)
k = 59199
q = (dq*e-1+k)//k
p = n//q
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))
dp = d % (p-1)
print(n)
print(e)
print(d)
print(p)
print(q)
print(dp)
print(dq)
print(qi)
"""
151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
65537
66980701583036734736960294391078312622827897052791813876359026247918495979594634282982071853820451331222681673373427663666376575651344098661059603483956134335089509308267535247063609325195212704938058730366660923446510585605669518343968880619319880983999690229384618652977238799179660803464509489433199564801
12112790828812363063315417237469719611888243756064158121348026938824270601623590308149025542977097905953795136774300936003505715307199422663647014200158449
12469144192094336933187534132907623337514842804208163244218540727384104398951558782195384932941310035462094951428865175221316720981428462265191789302379089
11498252026215339897996227126317442002148273807959830401838708697653776075624560175939807697631738024706616156507054180549156927547667584459935731684701121
11263269100321843418340309033584057768246046953115325020896491943793759194249558697334095131684279304657225064156696057310019203890620314290203835007881649
11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
"""

其后，参考的wp用之，生成私钥，解得flag

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
#解密
n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
t = 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
e = 0x10001
dq_l = 1043891160170747082120115133012365745
        
k = 59199 
dq_h = 8473541887500515583954330543610580482352988466308294038598683460069270949695742839059962985745363324600134512811492604
from Crypto.Util.number import*
dq = (dq_h * 2**120 + dq_l)
q = (GCD((dq * e - 1 ) * t - k*(1-t) ,n))
p = n//q
d = inverse(e,(p-1)*(q-1))

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import gmpy2
e=65537

n=p*q
d=d
privkey=RSA.construct((int(n),e,int(d)))  # 只需要传n、e、d
f = open('privkey2.pem','wb')
f.write(privkey.export_key('PEM'))
f.close()

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
cipher_text=open(r"flag.enc","rb").read()
ciphertxt=cipher_text
key=RSA.importKey(open(r"privkey2.pem").read())
cipher=PKCS1_OAEP.new(key)
message=cipher.decrypt(ciphertxt)
print(message)

flag{f1bf5c44-e2b4-424f-baff-b38b73a82e72}

本题按理来说，已结束。

但接下来，出于对pem私钥结构的好奇，我进行了如下研究。

更多

点开exp所生成的私钥文件，可见

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB
AoGAX2I5MWOog+N5afYcBTPyXLe0hkCjtN2EeJ2R1uYpmJF4n9UanwO5IJhg5CcM
cNo0cPokWUND6Rv9YmY8K6dDEpB+BTULPEoeOJa0l8M0KljcmeBuPSc0YWCYd8Zg
Tc68gtOyT9adcne7/IKdh1hO2iAFraAj3bwzuHg97GvM2AECQQDuE+g/vilcoaQx
Sa7jiJcVfKqs7FrfY8rdYIi6iGLRiZxs9dLAtQ52X0l/hxN0nq8Mt9vQFLzhVd7a
Mq69r/JRAkEA50YWmJ3dhsC7SaKP6apHECpoh1GU+ixvptah8qbyjhZ7B+o2xmTf
j6BK/Ph+it/g6HxP99nH0YqU2pgxwd4o8QJBANcNtmn13SjmfgljlI3FsSvgm89u
BLvrSbFk5L0SO6kpE9q8xu353qGAe0SuAB4ExPzJC87PHLqzNYWF6KBB0bECQQDb
ikkA7zrPJD2llM+QPLfgvKElc2g8Y9pJQg3RznEKOITp6oe8pR0jtkH5Cdr18bgK
eZdf7DgmzaqoJzl0k3PBAkAEZM8zEVu9kvF83t3Iebxw2oYMAVfyrNHSY/0fZFgf
kVvwlMXuHRs2vp4ro26TSrqpFT1VCXbaw64xspA5FYPK
-----END RSA PRIVATE KEY-----

而我们最初想要恢复的私钥文件，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB








yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==
-----END RSA PRIVATE KEY-----

它们是不同的！

但为什么可以解出flag呢？

原因是，exp里所生成私钥文件里p、q数据和欲恢复的私钥文件里p、q相反

即：

  • $p_{exp} = q_{want}$
  • $q_{exp} = p_{want}$

这就导致了其他参数不同（例如dp、dq也反了，qi也不同），因此base后所生成的私钥文件必然是不完全相同的

但d是一致的，这就让它可以正常解密出flag

但我渴求完全恢复出来，如果做到了这会让我感到开心😺

但简单试了下相关的库，没找到好使的（p、q都反了）

心血来潮，便打算自己完整的写个生成私钥的脚本出来，这虽重复造轮，但对我而言意义非凡

但现实挺骨感的，通宵写了一夜的bug，就是读取不了，解不出flag🤧

睡醒后，找了些资料，完善了对私钥数据的认知，总算根据原理成功写出

先看一个测试性质的私钥文件(十六进制下)内容

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
Last login: Sat Jul 16 18:45:25 on ttys003
(base) wenhui@Harrys-MacBook-Pro ~ % echo -n 'MIICWgIBAAKBgQCcSnm2TgLST457G9sUfy9qyITaX1gGHTYzpe364ho1ayOF0f2U
EDJVO7eUxKHm8qQIoFU6xjdjMZGxaODrVQMqkbBn3EWzCdW2R4B0Kp/YUFlGQoWS
KFUin0D7uWn2DM4jPcpTTOX0Og2VSe0SGQ0spn++rF7buHqxv3c12DTVowIDAQAB
An8FUfFk+h5DCnI84yOR/MJXTenKF3TDCak8YfvcadXoRL1eh6LQ+bwqmEuC6Xe9
9xbC60SNu59LnIjrXIICXCuazAW8JEpQqYoijyAsX7LiFctvKwDh7DP+9g3/4+vN
08C1o+38/Yl/aAZmUHiyZxj1/TPu25fXiHPWEeTXOo3xAkEAx2j4EbnWZuARrtAi
i7T5j2IuhT4UsD+U0YWjFnwQiWpwJ5F67uISFqA6MHn2v0LfVE5eADX9kPYa2FcZ
s0T1SQJBAMik7REmT1d9snwMHS0qqlkeZGCu7MEcJEHAsmIcpZBo6q+CtPJBFikO
VVPK6H01IM97ApActK2OuerbZBUhb4sCQFJfShoIakiUxrkvwRV07KIOLKldu64S
lab3TSc8mJgrH6k4r09+k3pFNcRQnVzkgtyQgsQTiWsYPn6ffD5RfgECQQCrtOCg
PY3GzO4y1FcfsRSJIcY7K1e3RzMMBjFiXyuc8vxsaMobS3IAfqCtDcd6Zz4F8TpX
RAmnQa5/e3Mh1jRTAkApRCqIkHmCu4MA3bNSImZ6Ll7gdB8Ppcu1aYqmLP0XpEvL
VmTRs4AtlHEOi1ZdGuNcoAzIcrK9h4sVnXRo+JTJ' | base64 -d | hexdump
0000000 30 82 02 5a 02 01 00 02 81 81 00 9c 4a 79 b6 4e
0000010 02 d2 4f 8e 7b 1b db 14 7f 2f 6a c8 84 da 5f 58
0000020 06 1d 36 33 a5 ed fa e2 1a 35 6b 23 85 d1 fd 94
0000030 10 32 55 3b b7 94 c4 a1 e6 f2 a4 08 a0 55 3a c6
0000040 37 63 31 91 b1 68 e0 eb 55 03 2a 91 b0 67 dc 45
0000050 b3 09 d5 b6 47 80 74 2a 9f d8 50 59 46 42 85 92
0000060 28 55 22 9f 40 fb b9 69 f6 0c ce 23 3d ca 53 4c
0000070 e5 f4 3a 0d 95 49 ed 12 19 0d 2c a6 7f be ac 5e
0000080 db b8 7a b1 bf 77 35 d8 34 d5 a3 02 03 01 00 01
0000090 02 7f 05 51 f1 64 fa 1e 43 0a 72 3c e3 23 91 fc
00000a0 c2 57 4d e9 ca 17 74 c3 09 a9 3c 61 fb dc 69 d5
00000b0 e8 44 bd 5e 87 a2 d0 f9 bc 2a 98 4b 82 e9 77 bd
00000c0 f7 16 c2 eb 44 8d bb 9f 4b 9c 88 eb 5c 82 02 5c
00000d0 2b 9a cc 05 bc 24 4a 50 a9 8a 22 8f 20 2c 5f b2
00000e0 e2 15 cb 6f 2b 00 e1 ec 33 fe f6 0d ff e3 eb cd
00000f0 d3 c0 b5 a3 ed fc fd 89 7f 68 06 66 50 78 b2 67
0000100 18 f5 fd 33 ee db 97 d7 88 73 d6 11 e4 d7 3a 8d
0000110 f1 02 41 00 c7 68 f8 11 b9 d6 66 e0 11 ae d0 22
0000120 8b b4 f9 8f 62 2e 85 3e 14 b0 3f 94 d1 85 a3 16
0000130 7c 10 89 6a 70 27 91 7a ee e2 12 16 a0 3a 30 79
0000140 f6 bf 42 df 54 4e 5e 00 35 fd 90 f6 1a d8 57 19
0000150 b3 44 f5 49 02 41 00 c8 a4 ed 11 26 4f 57 7d b2
0000160 7c 0c 1d 2d 2a aa 59 1e 64 60 ae ec c1 1c 24 41
0000170 c0 b2 62 1c a5 90 68 ea af 82 b4 f2 41 16 29 0e
0000180 55 53 ca e8 7d 35 20 cf 7b 02 90 1c b4 ad 8e b9
0000190 ea db 64 15 21 6f 8b 02 40 52 5f 4a 1a 08 6a 48
00001a0 94 c6 b9 2f c1 15 74 ec a2 0e 2c a9 5d bb ae 12
00001b0 95 a6 f7 4d 27 3c 98 98 2b 1f a9 38 af 4f 7e 93
00001c0 7a 45 35 c4 50 9d 5c e4 82 dc 90 82 c4 13 89 6b
00001d0 18 3e 7e 9f 7c 3e 51 7e 01 02 41 00 ab b4 e0 a0
00001e0 3d 8d c6 cc ee 32 d4 57 1f b1 14 89 21 c6 3b 2b
00001f0 57 b7 47 33 0c 06 31 62 5f 2b 9c f2 fc 6c 68 ca
0000200 1b 4b 72 00 7e a0 ad 0d c7 7a 67 3e 05 f1 3a 57
0000210 44 09 a7 41 ae 7f 7b 73 21 d6 34 53 02 40 29 44
0000220 2a 88 90 79 82 bb 83 00 dd b3 52 22 66 7a 2e 5e
0000230 e0 74 1f 0f a5 cb b5 69 8a a6 2c fd 17 a4 4b cb
0000240 56 64 d1 b3 80 2d 94 71 0e 8b 56 5d 1a e3 5c a0
0000250 0c c8 72 b2 bd 87 8b 15 9d 74 68 f8 94 c9      
000025e

先声明一下填充的格式参数吧

  • 前缀，例如02、30，一定存在
  • 辅助参数，例如81、82,可能存在
  • 长度，数据十六进制下字节数的十六进制，一定存在

具体的，当我们有n、e、d…等数据等时候，要如何填充呢？

1
2
3
4
5
6
7
8
9
10
11
12
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}

按照以上结构，我们先不管version Version,看看第一个参数n怎么填充吧（所有数据都是十六进制）

上面私钥里

1
n = 0x9c4a79b64e02d24f8e7b1bdb147f2f6ac884da5f58061d3633a5edfae21a356b2385d1fd941032553bb794c4a1e6f2a408a0553ac637633191b168e0eb55032a91b067dc45b309d5b64780742a9fd85059464285922855229f40fbb969f60cce233dca534ce5f43a0d9549ed12190d2ca67fbeac5edbb87ab1bf7735d834d5a3

这里规定，参数第一个字节（这里是9c）超过0x80就需要高位补充00

即：

1
009c4a79b64e02d24f8e7b1bdb147f2f6ac884da5f58061d3633a5edfae21a356b2385d1fd941032553bb794c4a1e6f2a408a0553ac637633191b168e0eb55032a91b067dc45b309d5b64780742a9fd85059464285922855229f40fbb969f60cce233dca534ce5f43a0d9549ed12190d2ca67fbeac5edbb87ab1bf7735d834d5a3

然后计算其「长度」，即：有几个字节（以上一个数字或字母算半个字节，故就是计算 len // 2）

用十六进制表示

1
2
n = '009c4a79b64e02d24f8e7b1bdb147f2f6ac884da5f58061d3633a5edfae21a356b2385d1fd941032553bb794c4a1e6f2a408a0553ac637633191b168e0eb55032a91b067dc45b309d5b64780742a9fd85059464285922855229f40fbb969f60cce233dca534ce5f43a0d9549ed12190d2ca67fbeac5edbb87ab1bf7735d834d5a3'
print(hex(len(n)//2))  # 0x81

若长度大于80则辅助参数存在

  • 若长度需要一个字节表示，则辅助参数为81

    例如：长度为81,则表示为81 81 具体数据

  • 若长度需要两个字节表示，则辅助参数为82

    例如：长度为025a，则表示为82 02 5a 具体数据

回到测试私钥，n长度为81,则表示为

1
81 81 00 9c 4a 79 b6 4e 02 d2 4f 8e 7b 1b db 14 7f 2f 6a c8 84 da 5f 58 06 1d 36 33 a5 ed fa e2 1a 35 6b 23 85 d1 fd 94 10 32 55 3b b7 94 c4 a1 e6 f2 a4 08 a0 55 3a c6 37 63 31 91 b1 68 e0 eb 55 03 2a 91 b0 67 dc 45 b3 09 d5 b6 47 80 74 2a 9f d8 50 59 46 42 85 92 28 55 22 9f 40 fb b9 69 f6 0c ce 23 3d ca 53 4c e5 f4 3a 0d 95 49 ed 12 19 0d 2c a6 7f be ac 5e db b8 7a b1 bf 77 35 d8 34 d5 a3

最后，加前缀（除version前缀是30外，其余数据前缀都是02)

即：

1
02 81 81 00 9c 4a 79 b6 4e 02 d2 4f 8e 7b 1b db 14 7f 2f 6a c8 84 da 5f 58 06 1d 36 33 a5 ed fa e2 1a 35 6b 23 85 d1 fd 94 10 32 55 3b b7 94 c4 a1 e6 f2 a4 08 a0 55 3a c6 37 63 31 91 b1 68 e0 eb 55 03 2a 91 b0 67 dc 45 b3 09 d5 b6 47 80 74 2a 9f d8 50 59 46 42 85 92 28 55 22 9f 40 fb b9 69 f6 0c ce 23 3d ca 53 4c e5 f4 3a 0d 95 49 ed 12 19 0d 2c a6 7f be ac 5e db b8 7a b1 bf 77 35 d8 34 d5 a3

同理依次处理好e、d、p、q、dp、dq、qi后，拼接即可

而至于version则分为两部分

  • 文件总长数据 + 私钥判断数据

由资料，n前数据为私钥判断数据，只有以下两种形式

  • 020103 公钥
  • 020100 私钥

这里生成私钥文件，故：

1
02 01 00 02 81 81 00 9c 4a 79 b6 4e 02 d2 4f 8e 7b 1b db 14 7f 2f 6a c8 84 da 5f 58 06 1d 36 33 a5 ed fa e2 1a 35 6b 23 85 d1 fd 94 10 32 55 3b b7 94 c4 a1 e6 f2 a4 08 a0 55 3a c6 37 63 31 91 b1 68 e0 eb 55 03 2a 91 b0 67 dc 45 b3 09 d5 b6 47 80 74 2a 9f d8 50 59 46 42 85 92 28 55 22 9f 40 fb b9 69 f6 0c ce 23 3d ca 53 4c e5 f4 3a 0d 95 49 ed 12 19 0d 2c a6 7f be ac 5e db b8 7a b1 bf 77 35 d8 34 d5 a3 02 03 10 00 01 ...

而私钥判断数据前的文件总长数据结构如下

专属前缀03 + len（总文件）

同样的这里的len计算、填充方式同上

（长度大于80要辅助参数，因为其后数据为私钥判断数据+其他参数，第一字节固定为02，所以不可能补00）

于是，最终测试数据产生的（十六进制）私钥文件为：

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
30 82 02 5a 02 01 00 02 81 81 00 9c 4a 79 b6 4e
02 d2 4f 8e 7b 1b db 14 7f 2f 6a c8 84 da 5f 58
06 1d 36 33 a5 ed fa e2 1a 35 6b 23 85 d1 fd 94
10 32 55 3b b7 94 c4 a1 e6 f2 a4 08 a0 55 3a c6
37 63 31 91 b1 68 e0 eb 55 03 2a 91 b0 67 dc 45
b3 09 d5 b6 47 80 74 2a 9f d8 50 59 46 42 85 92
28 55 22 9f 40 fb b9 69 f6 0c ce 23 3d ca 53 4c
e5 f4 3a 0d 95 49 ed 12 19 0d 2c a6 7f be ac 5e
db b8 7a b1 bf 77 35 d8 34 d5 a3 02 03 01 00 01
02 7f 05 51 f1 64 fa 1e 43 0a 72 3c e3 23 91 fc
c2 57 4d e9 ca 17 74 c3 09 a9 3c 61 fb dc 69 d5
e8 44 bd 5e 87 a2 d0 f9 bc 2a 98 4b 82 e9 77 bd
f7 16 c2 eb 44 8d bb 9f 4b 9c 88 eb 5c 82 02 5c
2b 9a cc 05 bc 24 4a 50 a9 8a 22 8f 20 2c 5f b2
e2 15 cb 6f 2b 00 e1 ec 33 fe f6 0d ff e3 eb cd
d3 c0 b5 a3 ed fc fd 89 7f 68 06 66 50 78 b2 67
18 f5 fd 33 ee db 97 d7 88 73 d6 11 e4 d7 3a 8d
f1 02 41 00 c7 68 f8 11 b9 d6 66 e0 11 ae d0 22
8b b4 f9 8f 62 2e 85 3e 14 b0 3f 94 d1 85 a3 16
7c 10 89 6a 70 27 91 7a ee e2 12 16 a0 3a 30 79
f6 bf 42 df 54 4e 5e 00 35 fd 90 f6 1a d8 57 19
b3 44 f5 49 02 41 00 c8 a4 ed 11 26 4f 57 7d b2
7c 0c 1d 2d 2a aa 59 1e 64 60 ae ec c1 1c 24 41
c0 b2 62 1c a5 90 68 ea af 82 b4 f2 41 16 29 0e
55 53 ca e8 7d 35 20 cf 7b 02 90 1c b4 ad 8e b9
ea db 64 15 21 6f 8b 02 40 52 5f 4a 1a 08 6a 48
94 c6 b9 2f c1 15 74 ec a2 0e 2c a9 5d bb ae 12
95 a6 f7 4d 27 3c 98 98 2b 1f a9 38 af 4f 7e 93
7a 45 35 c4 50 9d 5c e4 82 dc 90 82 c4 13 89 6b
18 3e 7e 9f 7c 3e 51 7e 01 02 41 00 ab b4 e0 a0
3d 8d c6 cc ee 32 d4 57 1f b1 14 89 21 c6 3b 2b
57 b7 47 33 0c 06 31 62 5f 2b 9c f2 fc 6c 68 ca
1b 4b 72 00 7e a0 ad 0d c7 7a 67 3e 05 f1 3a 57
44 09 a7 41 ae 7f 7b 73 21 d6 34 53 02 40 29 44
2a 88 90 79 82 bb 83 00 dd b3 52 22 66 7a 2e 5e
e0 74 1f 0f a5 cb b5 69 8a a6 2c fd 17 a4 4b cb
56 64 d1 b3 80 2d 94 71 0e 8b 56 5d 1a e3 5c a0
0c c8 72 b2 bd 87 8b 15 9d 74 68 f8 94 c9

最后base64加密之，每64个字符为一行，前加-----BEGIN RSA PRIVATE KEY-----,后加-----END RSA PRIVATE KEY-----即可

总代码如下

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
# private key
import base64


def shex(num):
    tmp = str(hex(num))[2:]
    if len(tmp) % 2 == 1:
        tmp = '0' + tmp
    return tmp


def hlen(hstring):
    tmp = shex(len(hstring) // 2)
    if len(tmp) == 1:
        tmp = '0' + tmp
    return tmp


def construct(num, T=0):
    if T == 0:
        num = shex(num)
    if int(num[:2], 16) >= 0x80:
        num = '00' + num
    LEN = hlen(num)
    if int(LEN, 16) >= 0x80:
        if int(hlen(LEN), 16) == 1:
            return '81' + LEN + num
        if int(hlen(LEN), 16) == 2:
            return '82' + LEN + num
    return hlen(num) + num


def hpad(data, T=0):  # 默认不是文件头, 是就T=1
    return '02' + construct(data, T) if T == 0 else '30' + construct(data, T)



n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
e = 65537
d = 66980701583036734736960294391078312622827897052791813876359026247918495979594634282982071853820451331222681673373427663666376575651344098661059603483956134335089509308267535247063609325195212704938058730366660923446510585605669518343968880619319880983999690229384618652977238799179660803464509489433199564801
q = 12112790828812363063315417237469719611888243756064158121348026938824270601623590308149025542977097905953795136774300936003505715307199422663647014200158449
p = 12469144192094336933187534132907623337514842804208163244218540727384104398951558782195384932941310035462094951428865175221316720981428462265191789302379089
dq = 11498252026215339897996227126317442002148273807959830401838708697653776075624560175939807697631738024706616156507054180549156927547667584459935731684701121
dp = 11263269100321843418340309033584057768246046953115325020896491943793759194249558697334095131684279304657225064156696057310019203890620314290203835007881649
qi = 230121277324731969722527349653498610340545443290131539298194061889386294775484298329444143510348368415044353961014184478364151608769305026976078967964618

pk = '020100' + hpad(n) + hpad(e) + hpad(d) + hpad(p) + hpad(q) + hpad(dp) + hpad(dq) + hpad(qi)
pk = hpad(pk, T=1)  # 文件头
print(pk)
pk = str(base64.b64encode(bytes.fromhex(pk)))[2:-1]
f = open('privacy.pem', 'w')
f.write('-----BEGIN RSA PRIVATE KEY-----\n')
for i in range(len(pk) // 64):
    f.write((pk[i * 64: i * 64 + 64] + '\n'))
if len(pk) % 64 != 0:
    f.write((pk[(len(pk) // 64) * 64:] + '\n'))
f.write('-----END RSA PRIVATE KEY-----')
f.close()

效果图

如上图，复原成功，试着拿来解密

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP


#测试密钥解密
with open('privacy.pem', 'rb') as f:
    private_key = f.read()
with open('flag.enc', 'rb') as f:
    encrypt_text = f.read()
private_key = RSA.importKey(private_key)
pk = PKCS1_OAEP.new(private_key)
msg = pk.decrypt(encrypt_text)
print(msg)  # b'flag{f1bf5c44-e2b4-424f-baff-b38b73a82e72}'

成功！

值得一提，以上私钥文件填充的 前缀+辅助参数+长度+00 的方法叫做TLV

说明：
02 - tag T
01 - length L
03 - 00000003 在公钥组装中，舍弃0x00；私钥组装中，保留0x00 V

打个小结

RSA PEM 私钥文件

  1. 对RSA各参数使用TLV方法

    • 参数第一个字节（这里是9c）超过0x80就需要高位补充00

    • 计算其「长度」

      若长度大于80则辅助参数存在

      • 若长度需要一个字节表示，则辅助参数为81

        例如：长度为81,则表示为81 81 具体数据

      • 若长度需要两个字节表示，则辅助参数为82

        例如：长度为0251，则表示为82 02 51 具体数据

    • 加前缀（除version前缀是30外，其余数据前缀都是02)

  2. 加私钥判断数据，02 01 00 +各参数TLV后的数据拼接

  3. 加文件总长数据，将第2步的结果用TLV方法（前缀为30）

  4. 将第3步结果base64编码，每64位字符为一行

  5. 前加-----BEGIN RSA PRIVATE KEY-----

    后加-----END RSA PRIVATE KEY-----

总结

  • 私钥、公钥文件的人工读取

  • 十六进制泄漏低位不影响计算

    十进制砍掉高位，我接受的来，十六进制当时确实是迷茫

  • CopperSmith思路寻找、转换思路爆破参数k的方式

  • PEM私钥文件生成原理学习与实现

  • 16进制转byte

    直接.encode()不行🤔