dive into RSA algorithm and public/private key RSA算法及密钥文件之由浅入深

缘起

在某个项目中的登录环节，使用了RSA和AES加密算法，后台的主要处理流程是：

使用RSA私钥解密加密的用户名和密码
将明文密码使用AES加密，然后去数据库查找

在某次更新中，我无意中修改了RSA私钥文件的某些字符，然后惊讶地发现仍然能够正确地解密密文！于是我在SO上发帖问了下，得知密钥文件和密钥不同：私钥文件中包含了公钥的内容。但是，打开密钥文件后，却没有发现相同的部分，于是就有了本文。

RSA算法

首先学习RSA算法，参考 RSA算法1&2，这里把算法中的一些参数说明下:

p: 质数
q: 质数，实际中 p 和 q 是两个很大的质数
n: p*q，即pq的乘积
𝞿(n): 欧拉函数，值为(p-1)*(q-1)
e: 1～𝞿(n)间的任意一个数，实际中取 65537
d: e对于𝞿(n)的模反元素，即满足 ed ≡ 1 (mod 𝞿(n))

取(n, e)作为RSA公钥，(n, d)作为RSA私钥–注意，这里指的是算法意义上的公钥和私钥组成。
假设明文为T，密文为C，那么加密的流程为已知n/e/T求解满足下式的C：

T^e ≡ C (mod n)

而解密流程为已知n/d/C求解满足下式的m：

C^d ≡ m (mod n)

简单的说，RSA算法是基于以下事实/数学原理：

大整数做因式分解，除了暴力列举，没有更好的方法；
已知n/e，无法求出 d
通过n/d，可以正确地求解T

创建RSA密钥对

可以使用openssl创建密钥对，我的环境是 OS X 10.14.4, LibreSSL 2.6.5 。在终端输入 openssl 进入 cli 模式，我们先创建一个私钥：

genrsa -out rsa_private_key.pem 1024

1024 是密钥的长度，越长越安全，rsa_private.pem就是生成的私钥文件，你可以用任一文本编辑器打开查看。接下来生成一个公钥：

    rsa -in rsa_private_key.pem -pubout -out rsa_public_key.pem

密钥文件格式有很多种，这里使用了 pem 格式。接下来，我们就以这种格式为例，探索下密钥文件的组成。

探索RSA密钥文件

在上面RSA算法的介绍中，我们明白了公/私钥的组成，但是密钥文件的格式却不单单只包含n/e或n/d，它需要遵循一定的规则来用于表示和交换。这有点类似字符编码中Unicode编码和UTF编码的关系。
为了方便地传输密钥文件，密钥文件有不同的格式，比如这里遇到的pem(privacy-enhanced mail)。下面是一个pem格式的公钥：

pem格式的私钥：

首尾两行是标签，表明当前文件是公钥还是私钥。中间的内容是密钥，该内容是对 der(distinguished encoding rules) 格式内容的base64编码。而der表示的就是符合ASN.1标准的密钥的二进制表达。

公钥文件探秘

接下来，我们以上面的公钥为例，结合ASN.1标准来查看下公钥的字节流内容。
因为公钥文件中的标签是 -----BEGIN PUBLIC KEY-----，所以这遵循的是PKCS#8中的 Subjec Public Key Info_{rfc7468#page-13}；中间的文本是对 der 格式的数据base64编码后的结果。 der数据的格式定义来自：

SubjectPublicKeyInfo ::= SEQUENCE 
{
   algorithm           AlgorithmIdentifier,
   subjectPublicKey    BITSTRING
}
AlgorithmIdentifier  ::=  SEQUENCE  {
    algorithm               OBJECT IDENTIFIER,
    parameters              ANY DEFINED BY algorithm OPTIONAL  }
RSAPublicKey ::= SEQUENCE {
     modulus            INTEGER,    -- n
     publicExponent     INTEGER  }  -- e

整个der是一个sequence，该sequence包含两个元素：

algorithm：一个sequence，格式见 AlgorithmIdentifier
subjectPublicKey：一个BITSTRING，它的值是符合RSAPublicKey定义的sequence

综上所述，该RSA公钥的der表达形如：

SEQUENCE (2 elem)
  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.1 rsaEncryption (PKCS #1)
    NULL
  BIT STRING (1 elem)
    SEQUENCE (2 elem)
      INTEGER (1024 bit) 123289480296527093871276641095431691097585194601638956862227049483721…
      INTEGER 65537

接下来，我们把公钥中间的内容base64解码并用16进制表示(使用的是OS X自带的terminal)：

echo "MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCvke6mhqG9tgrlfQy76WTfC2jjOBvaC0d4JGrg32ABUI2sSS8a58SaYfZMkVOVLYh6fk75oLUbUmZ7QONfGZPjKhxQJZwPiSFvO/fzkfay33TyeGdWDBHbgLmss3gA9OOKC7DQm1NkUrlQ59PddRPCr+SxQYLruugjXEVDhTwbXQIDAQAB" | base64 -D | xxd  -g 1 -c 16

得到的内容：

00000000: 30 81 9f 30 0d 06 09 2a 86 48 86 f7 0d 01 01 01  
00000010: 05 00 03 81 8d 00 30 81 89 02 81 81 00 af 91 ee  
00000020: a6 86 a1 bd b6 0a e5 7d 0c bb e9 64 df 0b 68 e3  
00000030: 38 1b da 0b 47 78 24 6a e0 df 60 01 50 8d ac 49  
00000040: 2f 1a e7 c4 9a 61 f6 4c 91 53 95 2d 88 7a 7e 4e  
00000050: f9 a0 b5 1b 52 66 7b 40 e3 5f 19 93 e3 2a 1c 50  
00000060: 25 9c 0f 89 21 6f 3b f7 f3 91 f6 b2 df 74 f2 78  
00000070: 67 56 0c 11 db 80 b9 ac b3 78 00 f4 e3 8a 0b b0  
00000080: d0 9b 53 64 52 b9 50 e7 d3 dd 75 13 c2 af e4 b1  
00000090: 41 82 eb ba e8 23 5c 45 43 85 3c 1b 5d 02 03 01  
000000a0: 00 01

我们一段一段的进行解释：

 1:  30 81 9f // 30 表示sequnce， 9f表示接下来内容的长度，为159个字节
 2:     30 0d // sequence, od表内容长度13
 3:        06 09 //06表示OBJECT IDENTIFIER，09表示内容长度
 4:           2a 86 48 86 f7 0d 01 01 01 //1.2.840.113549.1.1.1 的编码
 5:        05 00 // 05表示null
 6:     03 81 8d // 03表示 BITSTRING，8d表示内容长度141
 7:        00
 8:        30 81 89
 9:           02 81 81 //02表示INTEGER
10:           00
11:           af 91 ... 1b 5d //INTEGER的内容，即RSA中的n
12:           02 03 // INTEGER
13:              01 00 01  //65537，即e

1.2.840.113549.1.1.1 转成上述字符的规则有些复杂，首先转换“1.2”：

1 * 40 + 2 = 42 = 0x2a

对于接下来的数字，如果小于127，就直接转成对应的十六进制；如果大于127，

将数字写成二进制形式；
将二进制序列填充进字节：每个字节的最高位空着；
在填充好的新字节中，最左边的最高位置1，最右边的最高位置0
再将字节转化成十六进制

以840为例，其十六进制为 0x0348，二进制表示为 11 0100 1000，先分组

7 6 5 4 3 2 1 0  |  7 6 5 4 3 2 1 0 
          1 1 0  |    1 0 0 1 0 0 0

然后再填充：

7 6 5 4 3 2 1 0  |  7 6 5 4 3 2 1 0 
1 0 0 0 0 1 1 0  |  0 1 0 0 1 0 0 0

因此转成 86 48。
113549的转化也是类似，这里就不演示了。

私钥文件探秘

ASN.1中对私钥的sequence表达：

 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
     }

其中， Version：

Version ::= INTEGER { two-prime(0), multi(1) }
           (CONSTRAINED BY
           {-- version must be multi if otherPrimeInfos present --})

如果Version的值不为0，那么必须填充OtherPrimeInfo：

OtherPrimeInfo ::= SEQUENCE {
            prime             INTEGER,  -- ri
            exponent          INTEGER,  -- di
            coefficient       INTEGER   -- ti
        }

由上可知，如果修改的某几位不是n或e，在解密的过程中是不会受到影响的。那么，问题来了：为什么要在私钥的sequence中添加这么多元素呢？根据 rtf5208 中的说明：

The intention of including a set of attributes is to provide a simple
way for a user to establish trust in information such as a
distinguished name or a top-level certification authority’s public
key. While such trust could also be established with a digital
signature, encryption with a secret key known only to the user is
just as effective and possibly easier to implement.

所以，目的是提供了一种简易的方式来确认密钥文件信息。

Q&&A

如果pem文件的标签是 -----BEGIN RSA PUBLIC KEY-----，那么遵循的是 pkcs#1，一个专门为RSA算法量身打造的密钥文件标准。如果标签是 -----BEGIN PUBLIC KEY-----，那么遵循的是 pkcs#8，这是面向更通用的密钥文件标准。

openssl 提供的命令

可想而知，如果自己根据协议自己来生成密钥或者读取密钥，会很容易出错，所以平时管理/使用的时候，我们应该借助openssl的力量。下面列举一些有用的命令：

openssl genrsa -out rsa_private_key.pem   1024  //生成私钥,1024是密钥长度
openssl  pkcs8 -topk8 -inform PEM -in rsa_private_key.pem -outform PEM -nocrypt -out rsa_private_key_pkcs8.pem //将私钥转换成PKCS8格式
openssl rsa -in rsa_private_key.pem -pubout -out rsa_public_key.pem 
openssl rsa -in rsa_private_key.pem -text -inform PEM -noout //查看私钥内容
openssl rsa -inform PEM -pubin -in pub.key -text -noout  //查看公钥内容
openssl pkey -inform PEM -pubin -in pub.key -text -noout //查看公钥内容
openssl x509 -in cert.crt -outform der -out cert.der //PEM to DER
openssl x509 -in cert.crt -inform der -outform pem -out cert.pem //DER to PEM