RSA算法及密钥文件之由浅入深

缘起

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

  1. 使用RSA私钥解密加密的用户名和密码
  2. 将明文密码使用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算法是基于以下事实/数学原理:

  1. 大整数做因式分解,除了暴力列举,没有更好的方法;
  2. 已知n/e,无法求出 d
  3. 通过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格式的公钥:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCvke6mhqG9tgrlfQy76WTfC2jj
OBvaC0d4JGrg32ABUI2sSS8a58SaYfZMkVOVLYh6fk75oLUbUmZ7QONfGZPjKhxQ
JZwPiSFvO/fzkfay33TyeGdWDBHbgLmss3gA9OOKC7DQm1NkUrlQ59PddRPCr+Sx
QYLruugjXEVDhTwbXQIDAQAB
-----END PUBLIC KEY-----

pem格式的私钥:

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQCvke6mhqG9tgrlfQy76WTfC2jjOBvaC0d4JGrg32ABUI2sSS8a
58SaYfZMkVOVLYh6fk75oLUbUmZ7QONfGZPjKhxQJZwPiSFvO/fzkfay33TyeGdW
DBHbgLmss3gA9OOKC7DQm1NkUrlQ59PddRPCr+SxQYLruugjXEVDhTwbXQIDAQAB
AoGBAI/Cn7aNoRy1VkDJX0by+lzEe/Mp+2xUNgZDU5yka3lIG2mKV17hjpOXSVUy
3kzVht4+VK6EkCc6Fp4v6L3zNKq/jQjDNf03sgpj0wjMc0KhGOFAFY74UzuxikjW
yvEJFvh7nK2IMWzvftvReYXqAzAxAsvH6W3TE0JlOD2LKywBAkEA1/dTPaYN1jVG
3BnOl1kF6ecloWiDZTkO1jh0kV+XPCqrzWYIjQBqv25mI0m3iEDbRvMnuz5yFNWK
F3WDLVcUXQJBANAdnHgR3UhGxe+D8M0zSvYtKYfy7MkAtaFcG46059qQao49iHc0
O60Le2h3lY/jleBMCOmxiP44xl3vTfzIswECQQDSZaIT0j1yrY6uCPpKWjE3sbfo
arBvocnBi1iM8+qbdBrRzRCRhZF5k+0vfbauqDi4A1V2xpxPjcWtmw9D0a0FAkBc
lT+9fp0FgU6e7gBbGT145MB8FUrXZLRok1RDGSGn7uUoYCFsflUp91iwMbrcZy+O
t+SjKfK6vcEpmsMD+LkBAkBq1xbpN4vMrL+4bPdaXN62OxqwOnhLey54BTKjEGGY
XLq8m7phZ5qjhVPT89/MTnHm5V8VwvvH+ixDmhVEEN7X
-----END RSA PRIVATE KEY-----

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

公钥文件探秘

接下来,我们以上面的公钥为例,结合ASN.1标准来查看下公钥的字节流内容。
因为公钥文件中的标签是 -----BEGIN PUBLIC KEY-----,所以这遵循的是PKCS#8中的 Subjec Public Key Inforfc7468#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 IDENTIFIER09表示内容长度
 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表示 BITSTRING8d表示内容长度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. 将数字写成二进制形式;
  2. 将二进制序列填充进字节:每个字节的最高位空着;
  3. 在填充好的新字节中,最左边的最高位置1,最右边的最高位置0
  4. 再将字节转化成十六进制

以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

参考文档

RSA 密钥对格式-rfc8017
RSA算法1
RSA算法2
RSA Cryptography Specifications Version 2.1-rfc3447
rtf5208-pkcs#8
PEM
DER
Textual Encoding of Subject Public Key Info
非对称加密密钥格式
DER Encoding of ASN.1 Types
在线工具--ASN.1 decoder