非对称加密算法 RSA（三位作者的名字首字母）
区别于对称加密算法，非对称加密算法采用两种密钥，公钥和私钥，公钥加密，私钥解密，反之也可以。私钥保留，公钥可以公开发布。
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
RSA生成密钥的过程用到欧拉函数，模反元素等，十分复杂。
- 随机选择两个不相等的质数p和q
- 计算p和q的乘积n，上边说的密钥长度，就是n的长度
- 计算n的欧拉函数φ(n)
- 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
- 计算e对于φ(n)的模反元素d
过程虽然复杂，但是一般也不需要特别清楚，我们只需知道计算过程用到了p,q,n,e,d，这些值封装在一起就是私钥，其中n和e封装在一起就是公钥。对计算过程感兴趣的可以看看阮一峰的博客RSA算法原理（一）和RSA算法原理（二）。
我们的数据，经过公钥中的n和e进行计算。计算出来的值，可以通过私钥中的n和d反解出来。
密钥的形式
ASN.1
密钥中数据采用ASN.1结构。ASN.1本身只定义了表示信息的抽象句法，但是没有限定其编码的方法。ASN.1有各种编码规则，其中密钥采用唯一编码规则（DER，Distinguished Encoding Rules）。用ASN.1表示法，公私钥大概是如下形式。
PublicKey
1 | RSAPublicKey ::= SEQUENCE { |
PrivateKey
1 | RSAPrivateKey ::= SEQUENCE { |
DER 编码介绍
DER编码会将数据编码成二机制形式。DER使用一种TLV格式来描述数据
如果tag是容器类型，value就是另一组TLV了
tag编码
tag一般占一个字节。前两位表示class类型，第三位表示原子类型还是结构体类型。
具体类型编码如下
1 | 0x01 == BOOLEAN |
说明：所有的这些都是UNIVERSAl类型。因为前两位都是0。1E之前的都是primitive类型，因为第三位都是0。30和31是constructed类型，第三位是1。
长度的约定
长度字段标示value字段的长度。如果value字段小于128字节，长度字段占一字节。并且字节第一位是0。如果value字段多于128个字节。那这一字节的第一位设置为1，接下来的位数表示需要几个字节来表示长度字段。
说明：为什么以128为界。因为默认情况下以一个字节表达长度，而这个字节的第一位用来标志是否溢出。所以只剩下7位用来表达长度。7位可以表达的最大数字是2的7次方128。所以以128为界。如果不用第一位来标志溢出，虽然可以表达256的长度，但是超过256就无法表达了。
值的约定
每个值都有一些特殊说明，全部列举比较繁杂，密钥中主要是用INTEGER类型和SEQUENCE类型，下面我们对这两种值类型进行一些说明。
INTEGER
正常情况指定长度中的值就是编码后的值。
比如： 0x03，编码后为 0x02 0x01 0x03。类型，长度，值，很容易理解。
但是当一个正数，并且第一位是1的时候，需要做一些标示，来表明这个值是正值。标志很简单，就是在值前面加一个全0字节。
比如值 0x8F（10001111）首位是1
0x02表明类型是INTEGER，长度两个字节，0x00表示是正数。0x8F就是这个值。
SEQUENCE
SEQUENCE 包含一组有序的值。超过128位的情况，按照之前的长度约定走。例子如下
1 | 30 81 9f ; SEQUENCE (9f Bytes) |
外层SEQUENCE，81表示接下来1个字节表示长度，接下来的字节是9f，所以这个值占9f个字节。
内层SEQUENCE，0d，表示接下来d个字节是内容。
密钥的表现形式
接下来的分析，主要依据上边的编码介绍，可以对照着看。
密钥一般不是直接以der形式存在，大部分情况都会进行二次编码。比如下面这三个例子。
openssl生成的私钥
使用openssl生成一个私钥
1 | openssl genrsa -out private_rsa.pem 1024 |
使用base64解码，生成一个二机制文件
1 | openssl base64 -d -in private_rsa.pem -out private |
可以用vim查看，
1 | vi -b private |
在vim中，将展示改成16进制:%!xxd
1 | 00000000: 3082 025d 0201 0002 8181 00cc 9cd8 3a75 0..]..........:u |
接下来比较长，比较乏味，我将生成的私钥进行了简单的格式处理，我们看看是不是符合ASN.1中对私钥的描述
1 | # VERSION |
可以看到，私钥中的数据在这里面有完整的对应。
服务端给的公钥，待补充：这个公钥的类型是什么？
1 | -----BEGIN PUBLIC KEY----- |
格式化后
1 | 3081 9f //9f长度的SEQUENCE数据 |
头信息很长，首先是一个SEQUNENCE开头，里面有一个SEQUNENCE和一个Bit String。
内部的这个SEQUNENCE包装了两个数据，一个对象标识，一个空数据结尾，这个对象标识解出来是1.2.840.113549.1.1.1,对应的名字是szOID_RSA_RSA。这是加密算法标识符，有很多类型，这个类型表示，RSA既可以用于加密，也可以用于给数据签名。详细信息可以参考。
Bit String中放的数据就是我们的公钥了，下面看看这个公钥
1 | 30 81 89 |
以SEQUNENCE作为容器，里面有两个Integer，一个是129个字节的n，一个是e 65537。
sshkeygen生成的公钥
1 | 00000000: 0000 0007 7373 682d 7273 6100 0000 0301 ....ssh-rsa..... |
这个有点尴尬，好像不是der的编码格式。而且，第一行还显示出了ssh-rsa。这个格式没找到对应的编码介绍，网上有人翻译，看翻译过程，这个编码格式像是简化了的der。可能因为信息类型确定，长度也相对确定，所以省掉了tag，以及长度溢出的措施，这里应该是LV格式，即长度-值。长度占4个字节。我们用这个规则看一下上面的数据。
1 | 0000 0007 //长度 7 |
这个数据表达了三个信息，类型ssh-rsa，e 65537，n那一大串数。
ssh-keygen生成的公钥id_rsa.pub，可以通过命令ssh-keygen -f key.pub -e -m pem转成标准der格式。
比如上面那个公钥经过这个命令之后是这样的。
1 | 00000000: 3082 010a 0282 0101 00a0 f5d6 20a3 2ff7 0........... ./. |
这个就很熟悉了，标准的TLV格式。SEQUNENCE下两个INTEGER，n和e。
待补充
密钥的格式只见到过这几种，就对这几种进行了分析。还需要看看总共有多少种，如何分类，以及为什么这么分类。
参考