解读RSA公钥私钥储存格式

（随手拍了一张雷阵雨前的深圳）

大家好，这里是 tiankonguse 的公众号(tiankonguse-code)。 
tiankonguse 曾是一名ACMer，现在是鹅厂视频部门的后台开发。 
这里主要记录算法，数学，计算机技术等好玩的东西。

这里一般一周更新两篇文章。
最近半个月来把 《大明王朝1566》看完了，结果文章就被拖延了。
今天来探索一下RSA公钥密钥的储存格式吧。

零、背景

之前在《最安全的加密算法RSA》的密钥生成小节中提到过公钥(yue)和私钥(yue)的数据都采用ASN.1格式表达。
然后我还贴上了我的公钥(yue),看起来很像《二进制上的明文算法》中介绍的base64编码后的样子。

对于生成过RSA密钥或者看到我贴的公钥时，不知道大家有没有想过那一串文本是什么?
我是一直有这个疑问的：RSA生成的公钥和私钥不是都是两个大整数吗？怎么变成一串文本了？他们之间有什么关系呢？我怎么得到这两个大整数呢？
是的，我有一连串的问题在头脑中自问自己。

这个问题在我头脑中已经很久了，我今天终于摆脱了拖延症，找到小程恢复我的VPS代理，打开GOOGLE一搜索，一切问题都找到了答案（这句话写于6月24日）。
今天我们就来聊聊SSH的RSA的公钥密钥储存格式吧。

一、生成公钥密钥

早在13年在腾讯微博实习的时候，我就写过对应的文章《ubuntu ssh无密码登录》。
这篇文章主要介绍怎么生成ssh的公钥，然后后续就不需要每次登陆都填写密码了。

先使用ssh-keygen -b 1024 -t rsa
命令生成密钥对。

然后私钥就会保存在id_rsa_test
中，公钥保存在id_rsa_test.pub
中。
内容如下：

看了上面的公钥和私钥内容，显然是base64编码的，那为什么使用base64储存呢？ 因为实际内容是使用ASN.1标准编码的二进制内容，二进制可读性太差，所以使用base64转化为文本内容。

一、ASN.1标准

在什么是协议文章中，我提到一类自描述应用协议，比如json、xml、protocol buffers、Apache Thrift。
没错，自描述应用协议是我自己自定义的一个词语，今天才知道，原来早在1984年就存在ASN.1标准了， 所以自描述应用协议的官方叫法是ASN.1标准。

由于ASN.1本身只是表示接口数据的通用语法，没有限定编码方法。
在这个标准下，接口数据可以序列化(encode、serialized)也可以反序列化(decode, deserialized)，通常在网络通信以及跨平台通信中使用。
由于ASN.1是个标准，到具体编码时，就分为多种实现方式了， 如BER，CER，DER，PER，XER等等。
而RSA生成的密钥就是使用ASN.1中的DER(Distinguished Encoding Rules)来编码的。

二、再看base64

背景中说了，RSA得到的密钥看起来很像base64，那我们就需要解码，得到原始的数据了。
可能有人会问为什么储存为base64呢? 答案是PER编码出来的数据是二进制，而在二进制上的明文算法中说过，文本中不能查看二进制。
所以这里就有了base64明文数据了。
刚好之前我自己写了一个base64加密解密函数，可以利用那两个函数来得到实际的二进制数据了。

使用base64解码，然后使用16进制打印出来是下面这个样子。 
下面我们一步一步来看这个十六进制数据吧。

三、分析公钥

根据上一小节得到的十六进制，我们现在来分析这个十六进制。

根据rfc3447可以了解到RSA公钥的格式：简单的LV格式(length-value)。
这种格式其实不具备可扩展性，数据的个数和位置约定死了。

第一部分如下： 
前四字节是字符串长度00 00 00 07
对应整数7，然后是长度为7的字符串”ssh-rsa”。

第二部分如下：
前四字节是字符串00 00 00 03
对应整数3，然后是三字节字符串01 00 01
。
这个数字是e，在《最安全的加密算法RSA》的密钥生成小节中提到过，目前的实现方法为了简单，固定为65537。

第三部分如下:
前四字节是字符串00 00 00 81
对应整数129，然后后面有129个字节，对应素数积n。

四、分析私钥

由于私钥也是base64编码，所以需要我们先转化为二进制数据，这里仍然使用十六进制打印出来。
对于私钥使用了ASN.1的TLV格式，虽然比公钥稍微好了一点，但是由于没有tag的概念，扩展性还是不好。

既然是有了一个标准，肯定有一些定义了，如下：

RSA密钥协议如下:

有了协议和标准，我们就可以分析这个二进制数据了。

第一部分0X3082代表是ASN.1 Sequence，0X025c为seq值。

第二部分0x02代表是一个整数，0x01代表长度为1，0x00为algorithm version的值。

第三部分0x02代表是一个整数，0x81代表长度为129字节代表大素数积n。
后面的0x81可以忽略，这个n以0x00开头的。

第四部分0x02代表是一个整数，0x03代表长度为3，代表公钥中的e，还是上面公钥小节中提到的固定数字。

第五部分0X0281代表后面是整数，长度为129字节，代表私钥中的d。

第六部分是0x0241代表第一个素数，长度为65字节。

第七部分是0x0241代表第二个素数，长度也是65字节。

第八部分0x0240代表d mod (p-1)
，长度是64字节。

第九部分0x0241代表d mod (q-1)
，长度为65字节。

第10部分是0x0240代表(inverse of q) mod p
，长度是64字节。

五、总结

好了，了解了上面的结构之后我们就可以得到公钥和私钥的大整数数了。
如果自己尝试破解素数积，也可以使用私钥中的两个素数来检查是否正确。
这里万万没想到的是两个素数竟然也保存了起来，理论不是只需要d和n就行了吗？

这两周看openssh和openssl源码的时候，发现代码中没有rsa的话默认使用ed25519加密，于是查了一下资料。
发现ed25519加密解密很快，生成时间短而且安全性更高，rsa则加密解密稍慢，生成时间长，安全性没有ed25519高，只是rsa以前都是默认，所以用的人更多。

参考资料如下

1. X.690: https://en.wikipedia.org/wiki/X.690

2. RSA Cryptography Specifications https://tools.ietf.org/html/rfc3447

3. Private-Key Information Syntax Specification https://tools.ietf.org/html/rfc5208

对了现在开通了公众号和小密圈。
博客记录所有内容。
技术含量最高的文章放在公众号发布。
比较好玩的算法放在小密圈发布。
小密圈这周接受免费加入，欢迎大家加入看各种算法的思路。

其他文章

每秒千万级系统架构篇  每秒千万级系统诞生篇  谈谈cache  排名算法 hash算法 Bloom Filter GDB CPU与内存 协议 JPEG

关于作者

曾是一名ACMer，现在是鹅厂视频部门的后台开发。

这里主要记录工作中的技术架构与经验、计算机相关的技术、数学、算法、生活上好玩的东西。

长按二维码支持作者，了解作者发布的最新好玩的东西。