复现蓝帽杯2022一道Crypto题-corrupted_key
潜心 2022-7-11 CryptoRSAbluehat2022
# corruptd_key
hint: 利用rsa各参量之间的关系构造方程，并用coppersmith方法恢复完整私钥
官方Writeup：【官方WP】第六届“蓝帽杯”初赛CTF题目解析 (qq.com) (opens new window)
题目给出了密文以及一个损坏的私钥，私钥如下
-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB
yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==
-----END RSA PRIVATE KEY-----
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
根据私钥的组成，从现有的私钥中提取信息
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
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
import base64
data1 = '''MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB'''
data2 = '''yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA=='''
def fun(data):
data = base64.b64decode(data.replace("\n", ""))
tmp = ""
for i in data:
tmp += hex(i).replace("0x", "").zfill(2)
return tmp
data1 = fun(data1)
data2 = fun(data2)
n_len = int(data1[18:20], 16) * 2 # 258
n = data1[20:20+n_len]
e_len = int(data1[20+n_len+2:20+n_len+4], 16) * 2 # 6
e = data1[20+n_len+4:20+n_len+4+e_len]
dp_low = data2[:-134]
coeff = data2[-130:] # coeff = pow(q, -1, p)
print(f"n = {int(n, 16)}")
print(f"e = {int(e, 16)}")
print(f"dp_low = {int(dp_low, 16)}")
print(f"coeff = {int(coeff, 16)}")
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
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
n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
e = 65537
dp_low = 1043891160170747082120115133012365745
coeff = 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
1
2
3
4
2
3
4
现在已知n、e、dp的低位和CRT系数，使用赛后别的师傅提供的脚本恢复p和q：Sage Cell Server (sagemath.org) (opens new window)
import gmpy2
n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
e = 65537
dp_low = 1043891160170747082120115133012365745
coeff = 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
s = []
for i in range(e):
try:
tt = gmpy2.invert(i,2**120)*(e*dp_low+(i-1))%2**120
s.append(tt)
except:
continue
print(len(s))
PR.<x>=PolynomialRing(Zmod(n))
for i in range(len(s)):
f = coeff*(2^120*x+int(s[i]))^2-(2^120*x+int(s[i]))
f = f.monic()
root = f.small_roots(X=2^392, beta=1, epsilon=0.1)
if root:
print(i)
x = int(root[0])
s = int(s[i])
q = 2^120*x+s
print(f"q = {q}")
print(f"p = {n//q}")
break
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
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
32768
29599
q = 12469144192094336933187534132907623337514842804208163244218540727384104398951558782195384932941310035462094951428865175221316720981428462265191789302379089
p = 12112790828812363063315417237469719611888243756064158121348026938824270601623590308149025542977097905953795136774300936003505715307199422663647014200158449
1
2
3
4
2
3
4
解出m，即为flag
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
e = 65537
q = 12469144192094336933187534132907623337514842804208163244218540727384104398951558782195384932941310035462094951428865175221316720981428462265191789302379089
p = 12112790828812363063315417237469719611888243756064158121348026938824270601623590308149025542977097905953795136774300936003505715307199422663647014200158449
d = inverse(e, (p-1)*(q-1))
privatekey = RSA.construct((n,e,d,p,q))
rsa = PKCS1_OAEP.new(privatekey)
m = rsa.decrypt(open('flag.enc','rb').read())
print(m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
b'flag{f1bf5c44-e2b4-424f-baff-b38b73a82e72}'
1