很有意思的一道题,涉及私钥文件的结构
题目 给了一个 priv.pem
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-----
和一个加密的脚本
1 2 3 4 5 6 7 from Crypto.PublicKey import RSAfrom Crypto.Cipher import PKCS1_OAEPfrom secret import flagkey = 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
的源码,发现私钥文件的结构是:
1 2 3 4 5 6 7 8 0 (注意!!!!) n e p q d mod (p-1) d mod (q-1) (inverse of q) mod p
完整来说是
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 }
一通操作后发现可以拿到 ,,CRT 系数(即 )和 低位,至于怎么拿到的等下再说,这里可以构造等式如下: 然后 代入得 显然 和 数量级是相当的, 的未知高位有512-120=392位,就可以通过 coppersmith 爆破 。
参数提取 然后就是有意思的部分了,如何从残损的私钥文件中提取参数呢? 对着源码一顿调试了几个钟(太菜了呜呜),发现是先将各个参数塞进一个首位为 0 的数组,然后各个参数前面补上长度,后面 long_to_bytes
转换成 bytes ,最后拼接起来。 我的提取脚本如下:
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 from binascii import a2b_base64from Crypto.Util.asn1 import DerIntegerfrom 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 :] der_int = DerInteger() n = decode_b64[3 :135 ] der_int.decode(n) print ('[+] n =' ,n:=der_int.value)e = decode_b64[135 :140 ] der_int.decode(e) print ('[+] e =' ,e:=der_int.value)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 : break dp_l = decode_b64[-82 :-67 ] print ('[+] dp_l =' ,bytes_to_long(dp_l))
可以看到我一开始直接把前 4 个字节丢了,然后在新 List 里用库函数解析 3 - 134 号位的数据,这部分就是属于 的,然而实际上 bytes_to_long
解析 7 - 134 号位的数据得到的也是 ,那么问题来了, 3 - 6 号位这 4 个字节里放了啥?
以下是新List:
1 \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
解析出来的数据,也是 那么现在你应该也可以尝试写出 的编码:
细心的你还发现我开头扔了 4 个字节,猜猜是啥呢? 答案是整个私钥文件编码后作为值域前面补的标签域和长度域,最前面再补一个 0 ,也就是
后两个字节 bytes_to_long
解码后是 606 ,恰为后面跟的完整数据的长度
后来偶然间发现竟然有类似的题目()0CTF 2016 Quals equation
参考 https://mp.weixin.qq.com/s/A9OmgHAmGLJPEL4cQBU8zQ https://www.likecs.com/show-40060.html