记 Cryptohack 中的一道题: Privacy-Enhanced Mail?

1 总述

CryptoHack是一家密码学学习与练习的CTF平台,题目质量很好。

在刷题的时候遇到一道题触及到了自己知识盲区,经过痛苦的研究终于过关。分享一下经验。

–— BEGIN BLOG ARTICLE –—

2 题目

PEM is a popular format for sending and receiving keys, certificates, and other cryptographic material. It looks like:

-----BEGIN RSA PUBLIC KEY-----
MIIBCgKC... (a whole bunch of base64)
-----END RSA PUBLIC KEY-----

It wraps base64-encoded data by a one-line header and footer to indicate how to parse the data within. Perhaps unexpectedly, it's important for there to be the correct number of hyphens in the header and footer, otherwise cryptographic tools won't be able to recognise the file.

The data that gets base64-encoded is DER-encoded ASN.1 values. Confused? Here is more information about what these acronyms mean but the complexity is there for historical reasons and going too deep into the details may drive you insane.

Extract the private key d as a decimal integer from this PEM-formatted RSA key.

底下有一个PEM的RSA私钥的文件链接,这里就不放了。

题目很清晰,要求将用DER编码的RSA私钥解码,然后提取出其中的 d ,这个 d 在RSA算法里面满足以下条件: \[ ed \equiv 1\:(\!\!\!\!\mod\:\phi(N)\,) \]

刚开始时间花费在怎样将这个PEM解码,然后分析ASN.1。在网上找了n多解码工具、代码和库。

大整数是解码出来了,但是没搜到RSA密钥的封装方式,所以也没搞懂到底哪个整数是 d

于是开始互联网的漫游。

最终在openssl中找到了解决办法,那就是 openssl rsa .

终端输入 openssl rsa -help 可以看到以下提示:

Usage: rsa [options]
Valid options are:
 -help              Display this summary
 -inform format     Input format, one of DER PEM
 -outform format    Output format, one of DER PEM PVK
 -in val            Input file
 -out outfile       Output file
 -pubin             Expect a public key in input file
 -pubout            Output a public key
 -passout val       Output file pass phrase source
 -passin val        Input file pass phrase source
 -RSAPublicKey_in   Input is an RSAPublicKey
 -RSAPublicKey_out  Output is an RSAPublicKey
 -noout             Don't print key out
 -text              Print the key in text
 -modulus           Print the RSA key modulus
 -check             Verify key consistency
 -*                 Any supported cipher
 -pvk-strong        Enable 'Strong' PVK encoding level (default)
 -pvk-weak          Enable 'Weak' PVK encoding level
 -pvk-none          Don't enforce PVK encoding
 -engine val        Use engine, possibly a hardware device

其中的 -text 代表以文本形式输出密钥, 一般可以带上 -noout 取消密钥的输出,因为我们已经有了密钥了。

所以通过管道将密钥的文本输入进去:

cat ./privacy_enhanced_mail.pem | openssl rsa -modulus -noout

得到以下输出:

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

获得了16进制的各密钥构造。 鉴于 eN 在一起封装成公钥, 在里面是 publicExponent , 所以 privateExponent 就是 d

privateExponent:
    7c:3b:1d:53:4f:29:9b:43:c1:26:08:76:30:3c:0a:
    95:be:17:bf:91:a5:df:2f:1c:ac:da:7c:75:a0:23:
    6e:4f:81:e1:21:0d:27:c0:12:6f:b3:4d:80:f2:7a:
    41:a4:d7:e4:8c:a7:c5:b0:e7:88:78:b1:9f:d0:d6:
    c0:bf:68:30:fb:8a:44:01:b1:6d:93:8a:d5:4c:4d:
    0b:35:68:62:05:6c:b0:55:4e:b2:ab:83:90:ad:18:
    25:b3:1d:af:bf:2f:c0:5d:19:4f:38:c2:f2:24:20:
    d3:21:0a:da:02:30:24:26:40:ca:e0:05:eb:85:cb:
    c8:dc:ca:18:25:ea:74:96:d9:b1:70:c5:cb:fe:35:
    4f:e1:9a:63:10:2b:82:f3:8d:5d:7c:25:17:35:20:
    8b:83:a5:42:40:92:7f:89:98:48:c1:6a:5f:e7:0c:
    e9:50:da:ff:7b:f9:f4:b7:1b:59:81:01:a5:20:48:
    cd:30:c1:6c:b9:94:33:0b:10:59:2d:2c:95:d4:d0:
    e5:79:f5:28:7f:f7:4a:88:26:8d:03:89:69:8c:8f:
    7b:9a:e8:13:f3:92:46:89:3d:02:66:1c:f0:8d:9c:
    bc:ec:9f:72:2c:f7:6d:0e:96:f1:e1:77:37:e2:9e:
    ce:86:76:76:7c:b6:e1:df:0d:bd:2d:73:1e:d8:48:
    b1

将这个字符串处理一下,就可以获得大整数 d 了。

3 代码

  1. 大概分析一下整个流程,首先需要将 openssl-rsa 的输出结果做个处理,将 privateExponent 的部分挑出来。
  2. 将得出的字符串进行二次整理,将 privateExponent 部分去掉,去掉空格, \n: 等不需要的字符。
  3. 将字符串转换为十六进制整数,然后输出。

实现

针对第一步,因为我不会用 sed ,所以只好用 awk 。 但是后来用 awk 整理了半天也没搞好怎么优雅地用正则表达式分段然后pattern识别。 所以就直接用三次 awk 解决。 Hacky trick.

cat ./rsa_private_key.pem | openssl rsa -text -noout | awk '/privateExponent/' RS='prime1' | awk '/privateExponent/' RS=')'

针对第二步,一个简单的 replace() 即可解决。

astr.replace("privateExponent:","").\
    replace("\n","").replace(":","").replace(" ","")

针对第三步,直接用 ast.literal_eval .

anum = ast.literal_eval('0x'+astr)

所以将整个流程整理一下,加上 argparser 处理命令行参数,然后拼在一起。

就得出来了一个python程序。

from os import popen        
from ast import literal_eval
import Crypto.Util.number   
import argparse             

def str_proc(astr):
    anum = literal_eval('0x'+\
                        astr.replace("privateExponent:","").\
                        replace("\n","").replace(":","").replace(" ",""))
    return anum


def main():
    parser = argparse.ArgumentParser()
    parser.add_argument('-f','--filename',help="Specify the PEM Private Key file.")
    arg = parser.parse_args()
    pem_filename = arg.filename

    system_obj = popen("cat " + pem_filename +\
                       " | openssl rsa -text -noout | awk '/privateExponent/'"+\
                       " RS='prime1' | awk '/privateExponent/' RS=')' ")
    astr = system_obj.read()
    print(str_proc(astr))

if __name__=="__main__":
    main()

运行,加上参数:

~/ $ python ./test.py -f ~/Downloads/rsa_private_key.pem

就得到了大整数。

–— END BLOG ARTICLE –—