RSA非对称加密原理

RSA (Rivest–Shamir–Adleman 三位数学家) 是最为常见的非对称加密算法. 本文以128位RSA为例介绍下算法的原理. 在实际使用时RSA密钥对至少要在1024位以上才可保证安全.

快速演示

1. 生成128位的rsa私钥

1
openssl genrsa 128 > key.pem

内容为:

1
2
3
4
5
-----BEGIN RSA PRIVATE KEY-----
MGMCAQACEQDUi8qYCNJ+DxtEhJpmVi0JAgMBAAECEQCqr9B0o7EWlWcpseM+pIJZ
AgkA/WoE6YFn36MCCQDWtwO8/mGbYwIIJg5v4mlOoiUCCAdxkM+cggXBAgkA30LD
Rk/98vU=
-----END RSA PRIVATE KEY-----

2. 用私钥生成公钥

1
openssl rsa  -in key.pem -pubout > pub_key.pem

内容为

1
2
3
-----BEGIN PUBLIC KEY-----
MCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRANSLypgI0n4PG0SEmmZWLQkCAwEAAQ==
-----END PUBLIC KEY-----

注: PEM - Privacy Enhanced Mail . 是一种存储格式, 第一行和最后一行使用预先定义的字符串标识, 例如 -----BEGIN RSA PRIVATE KEY-----, key或证书使用base64编码, 并防止在字符串标识中间

3. 加密

加密需要使用使用公钥, 公钥是公开的

1
2
echo -n hello > file1
openssl rsautl -encrypt -pubin -inkey pub_key.pem -in file1 -out file1.enc

base64 file1.enc打印内容为

1
RTZO1o7QMMgDSoGahCsHFw==

注:

  1. 由于输出是二进制的, 所以需要用-out来输出
  2. 我们刚刚生成的key的大小是128bit, 就是16byte, 被加密文件的大小不能超过 (total - 11) byte, 也就是 5 byte
  3. 加密数据的长度和key长度相同, 比如128bit私钥对消息加密后, 密文大小为固定的 16 byte

4. 解密

解密, 解密要用私钥. 私钥是需要保密的, 不能给任何人

1
openssl rsautl -decrypt -inkey key.pem -in file1.enc

看到打印输出了刚才被加密的hello


私钥文件结构

用16进制显示私钥的内容key.pem

1
cat key.pem|sed '1d;$d'|base64 -d|hexdump -C

1
2
3
4
5
6
7
8
00000000  30 63 02 01 00 02 11 00  d4 8b ca 98 08 d2 7e 0f  |0c............~.|
00000010 1b 44 84 9a 66 56 2d 09 02 03 01 00 01 02 11 00 |.D..fV-.........|
00000020 aa af d0 74 a3 b1 16 95 67 29 b1 e3 3e a4 82 59 |...t....g)..>..Y|
00000030 02 09 00 fd 6a 04 e9 81 67 df a3 02 09 00 d6 b7 |....j...g.......|
00000040 03 bc fe 61 9b 63 02 08 26 0e 6f e2 69 4e a2 25 |...a.c..&.o.iN.%|
00000050 02 08 07 71 90 cf 9c 82 05 c1 02 09 00 df 42 c3 |...q..........B.|
00000060 46 4f fd f2 f5 |FO...|
00000065

文件结构遵循ASN.1标准
以开头的30 63 02 01 00为例
30是序列标签, 63是十六进制的序列长度, 表示后面所跟的序列长度是63个字节
02代表整数标签, 01表示长度为1, 00前一个整数标签的内容
拆分后如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
00000000  30 63 02 01 v  02 11 | <modulus>                  |0c............~.|
00000010 | 02 03 |<pexp>| 02 11 | |.D..fV-.........|
00000020 <privateExponent> | |...t....g)..>..Y|
00000030 02 09 | <prime1> | 02 09 | |....j...g.......|
00000040 <prime2> | 02 08 | <exponent1> | |...a.c..&.o.iN.%|
00000050 02 08 | <exponent2> | 02 09 | |...q..........B.|
00000060 <coefficient> | |FO...|
00000065

version: 00
modulus: 00 d4 8b ca 98 08 d2 7e 0f 1b 44 84 9a 66 56 2d 09
publicExponent: 01 00 01
privateExponent: 00 aa af d0 74 a3 b1 16 95 67 29 b1 e3 3e a4 82 59
prime1: 00 fd 6a 04 e9 81 67 df a3
prime2: 00 d6 b7 03 bc fe 61 9b 63
exponent1: 26 0e 6f e2 69 4e a2 25
exponent2: 07 71 90 cf 9c 82 05 c1
coefficient: 00 df 42 c3 46 4f fd f2 f5

可以执行以下命令打印私钥的信息

1
openssl rsa -in key.pem -text -noout

1
2
3
4
5
6
7
8
9
10
11
12
13
Private-Key: (128 bit)
modulus:
00:d4:8b:ca:98:08:d2:7e:0f:1b:44:84:9a:66:56:
2d:09
publicExponent: 65537 (0x10001)
privateExponent:
00:aa:af:d0:74:a3:b1:16:95:67:29:b1:e3:3e:a4:
82:59
prime1: 18260413040072056739 (0xfd6a04e98167dfa3)
prime2: 15471839155111172963 (0xd6b703bcfe619b63)
exponent1: 2742252241335263781 (0x260e6fe2694ea225)
exponent2: 536369051992196545 (0x77190cf9c8205c1)
coefficient: 16087635525678002933 (0xdf42c3464ffdf2f5)

需要重点关注几个参数:
modulus,publicExponent,privateExponent,prime1,prime2


算法细节

以下步骤直接用上一步用openssl生成的私钥

1. 随机选择两个质数$p,q$,

对应质数prime1prime2 (长度为他们乘积字节数的一半):

$p=18260413040072056739$
$q=15471839155111172963$

2. 计算他们的乘积$n$

对应模数modulus, 该参数被公私钥共同持有

$n=p\cdot q=282522173461889495699110463826178747657$

3. 计算欧拉函数$φ(n)$

欧拉函数 $φ(n)$ 指的是小于等于 $n$ 的正整数中与 $n$ 互质的数的个数
已知 $n$ 是两个质数的乘积, 由欧拉函数的性质可知

$φ(n)=φ(p q)=φ(p)φ(q)$,

且对于质数 $p$ 有性质

$φ(p)=p-1$

因此有

$φ(n)=(p-1)(q-1)=282522173461889495665378211630995517956$

4. 选择一个指数$e$

$e$ 对应指数 publicExponent, 应该满足 $1< e < φ(n)$ 且与 $φ(n)$, 一般的RSA算法常选用 65537

$e=65537$

5. 计算 $e$ 相对于 $φ(n)$ 的模逆元 $d$

$d$对应指数privateExponent
逆模元:modular multiplicative inverse

即$(d\cdot e)\;mod\;φ(n)=1$, 求$d$

可化为下式, 求出$d$

$e d + kφ(n) = 1$

$d=226881639216003847549763572915136397913$, $k=-52630$ ($k$不使用)

用欧拉定理可以证明模逆元必然存在

至此, key已经生成完成了

公钥需要用到: $(n, e)$
私钥需要用到: $(n, d)$

6. 加密

加密和解密都是进行 modular exponentiation 运算

$c(m) = m^e \; mod \; n$

即$m$的$e$次方再对$n$取模

$m$ 必须小于 $n$, 不然会导致超出部分的信息丢失 (这就是为什么最终待加密内容要比key长度小的原因)

可以使用square-and-multiply algorithm算法来实现高效计算

本例假设待加密的数字为 $m=11321243346452408476274989986507887$

带入值有 $c(m)=113…887 ^ {65537} \; mod \; 282…657 $
最终得密文 $c=141261086730944747832689105815497758978$

8. 解密

$m(c) = c^d \; mod \; n$

$m(c)=141…978^{226…913} \; mod \; 282…657$

可得$m=11321243346452408476274989986507887$, 与原值相同

上一步运算后, 只有通过私钥才能解密, 因为d只在私钥中存在

补充

需要注意的是, 公钥和私钥反过来用也是成立的, 这一特性主要用于签名和验证签名, 将在下一篇文章进行介绍
即我们用私钥$(n,d)$来加密, 则只有公钥$(n,e)$才能解密

例如 $m=10384593717069655256779966059932783$
则私钥加密: $c=m^d\;mod\;n= 235772481305732042486557949216182601081 $
公钥解密: $m=c^d\;mod\;n = 10384593717069655256779966059932783$

因为由 $(d\cdot e)\;mod\;φ(n)=1$ 知 $e$ 和 $d$ 的位置其实是可以互换的. 只不过$d$存在于私钥中, 其他人无法得知

证明

由于密文 $c = m^e \; mod \; n$

则有

$c = m^e - k n$, $k$为某个整数

往解密规则 $m= c^d \; mod \; n$ 带入有

$m = (m^e - k n)^d \; mod \; n$

由于有性质 $(m^e - k n)^d \; mod \; n = (m^e \; mod \; n - ( k n ) \; mod \; n)^d$, 则上式可等价为:

$m = m^{e d}\; mod \; n$

由第5步 $(e d)\;mod\;φ(n)=1$, 有 $e d = k φ(n) +1 $

将 $e d$ 带入可得 $m = m^{kφ(n) +1 }\;mod\;n$

可以用欧拉定理来证明上述式子是成立的

欧拉定理
如果两个正整数$a$和$n$互质,则$n$的欧拉函数$φ(n)$可以让下面的等式成立:
$a^{φ(n)}\;mod \; n = 1$

之后的证明可以参考阮一峰的文章

加密/解密过程代码示例

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
import base64

n = 282522173461889495699110463826178747657
e = 65537
d = 226881639216003847549763572915136397913

# 加密前需要在消息头部填充11个字节, 用来进一步加大破解难度
# 0x0002 为固定头, 中间填充至少8个字节的非零随机数(本例用.代替), 0x00 为固定结尾, 后面跟待加密消息. 整个字节数组的长度需要与key长度相同
# 如果长度较短, 则需在0x0002后填充非零随机数, 直到长度相等
# 填充随机数后会导致即使每次对相同内容加密, 产生的密文也不相同
m = int.from_bytes(b'\x00\x02........\x00hello', byteorder='big')
print(m) # 11321243346452408476274989986507887

# 加密
c = pow(m, e, n)
print(c) # 11371906752051034372631172935304974279

# 解密 (需要截取0x0002........0x00后面的字节数组)
_m = pow(c, d, n)
print(_m) # 11321243346452408476274989986507887

# 验证解密后的值.
print(int.to_bytes(_m, length=16, byteorder='big'))

# 打印加密后文件, 用openssl验证
cBytes = int.to_bytes(c, length=16, byteorder='big')
print(base64.b64encode(cBytes)) # CI4mSnjhfGulCTw8qkGPxw==

可以将生成的文件尝试用openssl解密来验证

1
2
echo -n CI4mSnjhfGulCTw8qkGPxw== | base64 -d > file1.enc
openssl rsautl -decrypt -inkey key.pem -in file1.enc

可以看到解密的文本是hello

同时还写了一个 Java版Demo 供参考

参考

rsa_algorithm_part_one
RSA_(cryptosystem))
what-is-pem-format
Encrypt_and_decrypt_files_to_public_keys_via_the_OpenSSL_Command_Line
File encryption using OpenSSL
各种Java加密算法

0%