2022 蓝帽杯 - corrupted_key

题目

给了一个 priv.pem

和一个加密的脚本

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

分析

数理部分

题目名为 corrupted_key ，意为残损的私钥文件，既然是残损的，那么剩下的部分就是解题的关键了。通过查看 Crypto.PublicKey.RSA 的源码，发现私钥文件的结构是：

0 （注意！！！！）
n
e
p
q
d mod (p-1)
d mod (q-1)
(inverse of q) mod p

完整来说是

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
}

一通操作后发现可以拿到 ,,CRT 系数（即）和低位，至于怎么拿到的等下再说，这里可以构造等式如下：

然后

代入得

显然和数量级是相当的，的未知高位有512-120=392位，就可以通过 coppersmith 爆破。

参数提取

然后就是有意思的部分了，如何从残损的私钥文件中提取参数呢？对着源码一顿调试了几个钟（太菜了呜呜），发现是先将各个参数塞进一个首位为 0 的数组，然后各个参数前面补上长度，后面 long_to_bytes 转换成 bytes ，最后拼接起来。我的提取脚本如下：

from binascii import a2b_base64
from Crypto.Util.asn1 import DerInteger
from Crypto.Util.number import *
pem = '''-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB

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

pemlist = pem.split('\n')
decode_b64 = b''
for i in pemlist[1:-1]:
    decode_b64+=a2b_base64(i)
decode_b64 = decode_b64[4:] # 丢弃前4个字节

der_int = DerInteger()

# 提取n
n = decode_b64[3:135]
der_int.decode(n)
print('[+] n =',n:=der_int.value)

# 提取e
e = decode_b64[135:140]
der_int.decode(e)
print('[+] e =',e:=der_int.value)

# 提取CRT系数
for len in range(1,300):
    try:
        q_inv_p = decode_b64[-len:]
        der_int.decode(q_inv_p)
        print('[+] q_inv_p =',q_inv_p:=der_int.value)
    except:
        len+=1
    else:
        # print(len)    # 67
        break
# print(q_inv_p.bit_length())   # 512

# 提取dp低位
dp_l = decode_b64[-82:-67]
# print(dp_l)
print('[+] dp_l =',bytes_to_long(dp_l))

可以看到我一开始直接把前 4 个字节丢了，然后在新 List 里用库函数解析 3 - 134 号位的数据，这部分就是属于的，然而实际上 bytes_to_long 解析 7 - 134 号位的数据得到的也是，那么问题来了， 3 - 6 号位这 4 个字节里放了啥？

以下是新List：

\x02\x01\x00\x02\x81\x81\x00\xd7\x15%\x06\xaa\x9c...

这里涉及一个ASN.1（Abstract Syntax Notation dot one，即抽象记法1）的问题，简单来说就是将数据编码成 3 个部分：标志域、长度域、值域 标志域中，约定 02 表示整数长度域稍微复杂些，记录的是值域的长度，分为定长和不定长两种情况定长时，若值域长度不超过 127 ，则用短格式表示，也就是直接用 16 进制表示，比如长度为 31 就是 0x1F ，即 0001 1111 ；若长度超过 127 ，则用长格式表示，首字节的首位置 1 表示长格式，后面7位则表示后面再跟多少个表示长度的字节，比如 1000 0001 表示后面 1 个字节表示长度，后面的长度也是直接用 16 进制表示。现在可以看到新 List 中， 0 号位为 02 表示整数， 1 号位 01 表示长度为 1 ， 2 号位 00 表示数据为 0 ，这就是上面提到的私钥文件结构中的那个 0 。再继续分析， 3 号位 02 表示数据为整数， 4 号位中的首比特为1表示使用长格式，后面 7 个比特为 000 0001 意为数据长度用 1 个字节表示，没错就是后面紧跟的 5 号位，表示数据长度为 0x81 ，转换成 10 进制就是 129 ，试了一下 6 - 134 号位用 bytes_to_long 解析出来的数据，也是那么现在你应该也可以尝试写出的编码：