蓝帽杯2022 crypto复现

2022-09-23
Tags: Crypto wp.
Categories: write up.

pem文件解析

corrupted_key

上来拿到题目先看题目名字：损坏的密钥。告诉我们要修复附件中的pem文件

由于pem文件缺失部分数据，无法用openssl进行读取，只能解析内容提取数据（参考(PKCS1) RSA 公私钥 pem 文件解析 - 知乎 (zhihu.com)）

我们可以提取到四组数据：

n=0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641

e=0x10001

part_dq=0xc90bcecf1cbab3358585e8a041d1b1

inv_q=0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598

由于知道部分dq，所以这题才考察dq泄露的攻击方式。但是dq缺失了一部分，很容易想到利用一元的coppersmith来解决这个问题

很显然这个式子存在两个未知数，无法使用coppersmith，使所以这里把inv_q利用起来

因为

所以 两边同时乘上q，可得 将与上式联立，可得 这样就可以使用coppersmith了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
_dq = 0xc90bcecf1cbab3358585e8a041d1b1
inv_q = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
PR.<x> = PolynomialRing(Zmod(n))
dq = (2 ** 120 * x) + _dq
for k in range(65537,0,-1):
    f = inv_q * (e * dq - 1) ** 2 + k * (2 * inv_q - 1) * (e * dq - 1) + inv_q * k^2 - k^2
    f = f.monic()
    root = f.small_roots(X=2^392,beta=0.4)
    if len(root) > 0:
        print(int(root[0]) * 2 ** 120 + _dq)
        print(k)
        break
#dq = 11263269100321843418340309033584057768246046953115325020896491943793759194249558697334095131684279304657225064156696057310019203890620314290203835007881649
#k = 59199

之后代入k算出q，再用常规的RSA解出key，注意在原代码中是用PKCS1_OAEP加密的，所以要用这个算法还原回去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import gmpy2
with open("D:\\技术之路\\Crypto\\题目\\蓝帽杯2022\\corrupted_key\\flag.enc","rb")as f:
    c = f.read()
c1 = bytes_to_long(c)
dq = 11263269100321843418340309033584057768246046953115325020896491943793759194249558697334095131684279304657225064156696057310019203890620314290203835007881649
k = 59199
n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
q = int((e * dq - 1) // k + 1)
assert n % q == 0
p = int(n // q)
phi = (p - 1) * (q - 1)
d = int(inverse(e,phi))
key = RSA.construct((n,e,d,p,q))  #把数据变成公钥
flag = PKCS1_OAEP.new(key)
flag = flag.decrypt(c)
print(flag)
#flag = b'flag{f1bf5c44-e2b4-424f-baff-b38b73a82e72}'