RSA

RSA 是一种公钥密码算法（非对称密码算法），由三位开发者的姓氏首字母进行命名。用于公钥密码和数字签名。

RSA 的加密

RSA 中，明文、密文、密钥都是数字，加密过程可用如下公式来表示：

​ $密文 = 明文^E \mod N$ (RSA 加密)

即明文的 E 次方求 N 的余数，这个余数就是密文。 所以直到 E 和 N 就可以进行加密，E 和 N 就是 RSA 加密的密钥，E 和 N 的组合就是 公钥 (E, N).E: Encryption, N: Number. E 和 N 是经过计算得来的，不是随意选取的。

RSA 的解密

RSA 的解密可以用如下公式来表示

​ $明文 = 密文^D \mod N$ (RSA 解密)

即密文的 D 次方求 N 的余数，这个余数就是明文，D 和 N 组合起来就是 RSA 的私钥 (D, N) . D: Decryption N:Number. D 是与 E 有着紧密的额联系的，否则是无法对 E 加密的密文通过 D 进行解密的。

RSA 的加密和解密使用相同的形式，并且可以用公式化进行表示。

生成密钥对

密钥对，即要生成加密使用的 (E, N) 和 解密的 (D, N), 需要生成三个数：E, D, N

(1) 求 N

准备两个很大的质数 p 和 q, p, q 太小使得破译变的容易，太长，会导致计算事件变成，所以需要均衡。假设 p 和 q 都是 521 比特。

如何生成质数？伪随机数算法 + 质数验证算法

如何判断质数？费马测试、米勒拉宾测试

$ N = p\times q$

(2) 求 L

L 在加密和解密过程中都不曾出现，只用于密钥对的生成过程。

​ $ L = lcm(p-1, q-1)$ L 是 p-1, q-1 的最小公倍数， lcm - least common multiple

(3) 求 E

​ $ 1 < E < L$ E 是一个比 1 大，比 L 小的数

​ $gcd(E, L) = 1$ E 和 L 的最大公约数必须为 1 (E 和 L 互质), gcd - greatest common divisor

求 E 可使用伪随机数生成器，生成 (1, L) 区间内的候选数，在判断是否满足 $gcd(E, L) = 1$ ，求最大公约数可使用欧几里得辗转相除法。

至此，已经求出了 E, N, 生成了密钥对中的公钥

(4) 求 D

D 由 E 计算而得， D, E , L 满足下列关系：

​ $1 < D <L$

​ $E\times D \mod L = 1$

只要数 D 满足上述条件，则通过 E 和 N 进行加密的密文，就可以通过 D 和 N 进行解密。要保证存在满足条件的 D, 就需要保证 E 和 L 的最大公约数为 1 $gcd(E, L) = 1$ , 时钟运算下的倒数，只有某个数和模数（如 12）的最大公约数为1，数学上称为和模数互质，才存在对应的倒数。

RSA 算法利用了求离散对数是困难的（通过密文求得明文进行破解），大整数的质因数分解是困难的（通过分解 N , 还原密钥生成的过程来进行破解）保证了机密性。

时钟运算的乘方，时钟运算的除法，时钟运算的离散对数，大整数的质因数分解

RSA 的攻击

  1. 通过密文求得明文进行破解

    $密文 = ?^E \mod N$ 密文可以通过窃取得到，E, N 都是公开的，求明文, 转化为离散对数问题

  1. 通过分解 N , 还原密钥生成的过程来进行破解

    已知公钥的 E N, 从密钥生成的过程破解，对 N 进行质因数分解，期望得到 p 和 q，从而求出 D, 转化为大整数的质因数分解问题

  1. 中间人攻击 (man-in-the-middle attack)

    针对于所有公钥密码算法，中间人拦截发送方和接收方之间的消息，拦截接收方发送给发送方的公钥，并将自己的公钥伪装成实际接收方的公钥发送给发送方，发送方使用中间人的公钥进行加密发送，被中间人进行拦截，并通过自己的私钥进行解密，截取消息。然后通过获取的接受方的公钥将篡改的消息进行加密发送给接收方。可以使用公钥证书解决该问题。

  1. 选择密文攻击 (Chosen Ciphertext Attack)

    通过将任意数据发送给解密服务，获得提示，利用解密提示，进行破译。解决方法：对密文进行认证，判断密文是否是由直到明文的人通过合法的方式生成的, RSA-OAEP 就是基于这种思路的一种 RSA 改良算法

实践

使用 openssl 生成密钥，进行加密和解密

密钥的生成与查看
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
# 生成私钥
$ openssl genrsa -out rsa_private.pem 2048

# 查看私钥
$ cat rsa_private.pem
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEA5kFKwnpv86aLqEoU2VQ1l9aYek/wRvWqE6k4k7kzxBLK9hJp
aOOPyd2bz41fsQqVE0ezw6v9IR1WoEDA1WOqwquPoHaN9zGCBCbhcMSftGlj2E9x
xMb2l0ViR/OHT/5PVFALOwKFB4GlUaruKvkpRWNN7IRd+tjH7WGyZPiGDvbRPlSz
jnyJj9Rjl0TQ1DQ3WJCnOrIjGbThK7re5ShxmHrCO/mlaLCGoe33k5G8XtUyuiFq
aXUtSHLIAOFJCrixQjYYWFcBRvuth8Fo6wW9t6dPxIBWplkeADN662lnEtzxuPK1
Kt/N1cwful7VsZSDN+Frhjkd1DF9kwERZHBDBQIDAQABAoIBAHdBA85cCZWhAZ4k
2E2DTsqYa5qVwnWOEQtjzpi8CDKaJSJzgMLBcZx0uZkyuIgCWhmFPnauoki/YDlZ
sEYU+8EdiCLspDSOIK+zz3lPbQPMvdivtNXc0qSgW/m2CLQGm+GoH1jtwiaUICJ/
LCF3sMduWlKQb/hWxJ2Oxw2CpjQi59QTB8z/gt+iCq+imv26qkpJLNhcvHrTMTpR
V7cmoX2ACAqPO+PWmKlC5RdH4j89F+yCkhE+hCGKzqEiqC1M8XsuyVn1mxL50GK5
/NHRBWsHc5ar5L0/pqiwx6ktSow7y2MXPttAEcX/MztpbiCgBCz4MVcF3AJ5F1qa
uY7+9WECgYEA9a7iGKc1BNVe8Zxg4jlgBxNvPJyxtN5iL2Roub9KLgzyYPEa6gK+
29b/wYUuYXNbJnPpOSe0dVqInp1gOmTMKAI7te+QKI1eiDxD0YgQsBhXIiBiEo0m
TNHBUEizWMO6wdqqdut3eHAVgmigkeQx+7AT2G/drHFp5D/GvqWGkDkCgYEA7+yO
L/T1U3w1EFfQVzIMt1N0+VLsdd4bDmnwOfH3/hTsJGxx+OFpTZLvIO34+HE5mZAH
pbrvJQCLRhYuSdDeFlK30l2P4TxTeN8y7a07jAq4eQP1g2ANnOPIqepoA0VoxLYt
IyzuGWwhv2mOWJpU5Rb8dhBaKwYE6Nu++L+eMS0CgYBqTsAats9kRgeNOINboEQD
C8/IRG1IvCl0JFiEd1db0dJXTDy/IW0Ap2mHjV9iX44Dd4hlaN7XINOY/rQS0Gbe
sQixUvXn9jP/c0RNODkwWXfqlmSZbmYyO1kQqkSgliELnNjCGGVbwfQst6UzO7C9
HZWYw98BrRmK4GXZPLqbUQKBgFLZhjQrS7gbkRtmp4wkvV1lFWSvbPY6z28HyCvK
Uc/Mm8rsI+NEu59NGQRvCOWJ+9D6epmRVtmZOX7nU+6rkLV2tQGQy4mE0nJP6P9I
LeLrJM6tPk+ykKDXy8hZKLfQdSBQpH+cGVBwFatKoRwZly1Q5bdDaE+pEXLzxxuQ
1+i1AoGBAOECFiG5hiv6NxNKndrZ/mbIcLqW/gbdd8Q0Ic/66jH9FmqIgZ68aN/v
J1u7M/NnNcyktgN2vrJhZ6gZyi1lzyZO9/XEjqsPYrSu371Yr8az4jJCwskBttux
whX63VoNZpJFldn1l6A9VI+kNkdZitjPKrOZ3F2dROtbuood5rjj
-----END RSA PRIVATE KEY-----

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

# 从私钥中提取公钥，并通过 -RSAPublicKey_out 指定为 PKCS1 格式
$ openssl rsa -in rsa_private.pem -out rsa_public.pem -RSAPublicKey_out

# 查看公钥，公钥只需要包含 D,N 所以长度会相对较小
$ cat rsa_public.pem
-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEA5kFKwnpv86aLqEoU2VQ1l9aYek/wRvWqE6k4k7kzxBLK9hJpaOOP
yd2bz41fsQqVE0ezw6v9IR1WoEDA1WOqwquPoHaN9zGCBCbhcMSftGlj2E9xxMb2
l0ViR/OHT/5PVFALOwKFB4GlUaruKvkpRWNN7IRd+tjH7WGyZPiGDvbRPlSzjnyJ
j9Rjl0TQ1DQ3WJCnOrIjGbThK7re5ShxmHrCO/mlaLCGoe33k5G8XtUyuiFqaXUt
SHLIAOFJCrixQjYYWFcBRvuth8Fo6wW9t6dPxIBWplkeADN662lnEtzxuPK1Kt/N
1cwful7VsZSDN+Frhjkd1DF9kwERZHBDBQIDAQAB
-----END RSA PUBLIC KEY-----

# 查看 RSA 公钥的组成要素 D,N
$ openssl rsa -in rsa_public.pem -RSAPublicKey_in -text -noout
RSA Public-Key: (2048 bit)
Modulus:
    00:e6:41:4a:c2:7a:6f:f3:a6:8b:a8:4a:14:d9:54:
    35:97:d6:98:7a:4f:f0:46:f5:aa:13:a9:38:93:b9:
    33:c4:12:ca:f6:12:69:68:e3:8f:c9:dd:9b:cf:8d:
    5f:b1:0a:95:13:47:b3:c3:ab:fd:21:1d:56:a0:40:
    c0:d5:63:aa:c2:ab:8f:a0:76:8d:f7:31:82:04:26:
    e1:70:c4:9f:b4:69:63:d8:4f:71:c4:c6:f6:97:45:
    62:47:f3:87:4f:fe:4f:54:50:0b:3b:02:85:07:81:
    a5:51:aa:ee:2a:f9:29:45:63:4d:ec:84:5d:fa:d8:
    c7:ed:61:b2:64:f8:86:0e:f6:d1:3e:54:b3:8e:7c:
    89:8f:d4:63:97:44:d0:d4:34:37:58:90:a7:3a:b2:
    23:19:b4:e1:2b:ba:de:e5:28:71:98:7a:c2:3b:f9:
    a5:68:b0:86:a1:ed:f7:93:91:bc:5e:d5:32:ba:21:
    6a:69:75:2d:48:72:c8:00:e1:49:0a:b8:b1:42:36:
    18:58:57:01:46:fb:ad:87:c1:68:eb:05:bd:b7:a7:
    4f:c4:80:56:a6:59:1e:00:33:7a:eb:69:67:12:dc:
    f1:b8:f2:b5:2a:df:cd:d5:cc:1f:ba:5e:d5:b1:94:
    83:37:e1:6b:86:39:1d:d4:31:7d:93:01:11:64:70:
    43:05
Exponent: 65537 (0x10001)
加密与解密
1
2
3
4
5
6
7
8
9
# 从私钥中提取 pkcs8 格式的公钥
$ openssl rsa -in rsa_private.pem -out rsa_public_pkcs8.pem -pubout

# 加密
$ echo -n 'hello' | openssl rsautl -pubin -inkey rsa_public_pkcs8.pem -keyform PEM -encrypt -out cipher_text

# 解密
$ cat cipher_text | openssl rsautl -inkey rsa_private.pem -keyform PEM -decrypt
hello

使用 JCA 进行解密验证

使用这里的私钥进行解密前，需要将 PKCS1 格式的私钥转换成 PKCS8 格式的私钥：

1
2
3
4
# pkcs8 命令用来处理 PKCS#8 格式的密钥
# -outform DER 指定输出为 ASN.1 的 DER 编码格式
# -nocrypt 不对输出的私钥进行加密（私钥属于私密信息，需要保证安全存储，这里为了在 Java 中使用，不进行加密，加密可使用 KeyStore 存储）
openssl pkcs8 -in rsa_private.pem -outform DER -topk8 -out rsa_private_pkcs8.der -nocrypt

Java 中进行解密验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class RSACryptTest {

    @SneakyThrows
    public static void main(String[] args) {

        String pkcs8PrivateKeyPath = "E:\\learning-dir\\shell-learning\\rsa\\rsa_private_pkcs8.der";
        String cipherTextPath = "E:\\learning-dir\\shell-learning\\rsa\\cipher_text";

        byte[] privateKeyBytes = Files.readAllBytes(Paths.get(pkcs8PrivateKeyPath));
        byte[] cipherText = Files.readAllBytes(Paths.get(cipherTextPath));

        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(privateKeyBytes);
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        PrivateKey privateKey = keyFactory.generatePrivate(keySpec);

        Cipher cipher = Cipher.getInstance("RSA");
        cipher.init(Cipher.DECRYPT_MODE, privateKey);

        byte[] clearText = cipher.doFinal(cipherText);
        System.out.println(new String(clearText));
    }
}

最终打印出解密的结果：

1
hello

附录

PKCS#1 公钥 ASN.1 格式

1
2
3
4
RSAPublicKey ::= SEQUENCE {
    modulus INTEGER , -- n
    publicExponent INTEGER -- e
}

PKCS#1 私钥 ASN.1 格式

1
2
3
4
5
6
7
8
9
10
11
12
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
}

参考阅读

[1] 图解密码技术

[2] 深入剖析 RSA 密钥原理及实践 - [vivo互联网技术]

[3] how to load the private key from a .der file into java private key object - Stack Overflow

[4] openssl rsa command

[5] openssl pkcs8 command