非对称加密算法及编程简介

虽然对称加密算法可以胜任很多加密场景,但还是有不少特殊情况。

从前有一个黑帮,老大和手下们之间的通信必须加密确保安全。于此同时,老大希望手下发给他的信息,不能被其他手下知晓。若采用对称加密算法,只能给每个手下都分配一个独立的密钥,但老大觉得太麻烦了。该怎么办呢?

黑帮老大希望他只维护一份密钥,就能达到这样的效果,有办法做大吗?

——且看本文介绍的主角——非对称加密算法。

概念

既然我们平时所熟知的加密被称为对称加密,那么与之对应,就有 非对称加密asymmetric encryption )。非对称加密,顾明思议,在加密和解密环节用的密钥是不同的。

如上图,非对称加密算法需要两把不同的密钥,这两把密钥组成一对:

  • 公钥public key ),公钥用来对数据进行 加密
  • 私钥private key ),也称为 密钥secret key ),用来对数据进行 解密
  • 公钥和私钥总是成对出现,用公钥加密后得到的密文,必须用对应的私钥才能解密;

这套加密机制完美解决了黑帮老大的难题,他只需要生成一对密钥:公钥分发给手下们,他们先用公钥加密信息,再发老大;老大接到密文,就用自己保管的私钥来解密;手下们就算拿到别人发的密文也解不开,因为私钥只有他们老大才有。

神奇的数学原理

您可能会觉得公钥和私钥的加密机制非常不可思议,这一切其实来一个神奇的数学原理。

我们来做一个数字游戏,您随便写下一个整数 m ( $1 \lt m \lt 7387$ ),然后计算 $m^3 \mod {7387}$ 并把结果告诉我,我就知道您写下的整数 m 是什么!不信我们来试试,假设您写下的整数是 123

1
2
3
# 用Python求123的3次方,再除以7387得到余数
>>> 123 ** 3 % 7387
6730

那么,我该如何通过结果 6730 还原出您写下的整数 123 呢?神奇的现象来了:

1
2
3
# 计算结果6730的4811次方,然后对7387取模
>>> 6730 ** 4811 % 7387
123

您还可以写下其他数字试试,同样的现象一样成立:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# 520
>>> 520 ** 3 % 7387
3842
>>> 3842 ** 4811 % 7387
520

# 1314
>>> 1314 ** 3 % 7387
7382
>>> 7382 ** 4811 % 7387
1314

哇,太神奇了!如果把整数 520 作为待加密的数据,那么 37387 就是公钥,数据和公钥一起计算得到的结果 3842 则是密文,而 48117387 则是私钥!这个数字游戏其实就是关于公钥加密,私钥解密的故事!

那么,公钥参数 37387 ,私钥参数 48117387 又是怎么生成的呢?

第一步,随机选择两个质数 pq

1
2
p = 83
q = 89

第二步,计算 pq 的乘积 n

1
n = p * q = 7387

第三步,计算 n 的欧拉函数 $\phi(n)$ ,记为 phi

1
phi = (p-1) * (q-1) = 7216

第四步,随机选择一个整数 e ,满足 $1 \lt e \lt \phi(n)$ ,且 e 和 $\phi(n)$ 互质:

我们随机选一个质数 e ,使得 $\phi(n)$ 不能被 e 整除即可。

1
2
# 我们选一个最简单的3作为例子
e = 3

第五步,计算 e 对 $\phi(n)$ 的模反元素 d ,即找到一个数 d 使得 ed 除以 $\phi(n)$ 的余数为 1

$ed \equiv 1 \pmod {\phi(n)}$ 等价于

$ed - 1 = k\phi(n)$

这个方程据说可以用扩展欧几里得算法来求解,但小菜没空去复习,就写了个函数暴力求解:

1
2
3
4
def findD(e, phi):
    for d in itertools.count(e+1):
        if (e*d-1) % phi == 0:
            return d

这几行代码对于给定的 e 和 $\phi(n)$ ,以 e+1 为起点,逐一尝试 d 的值。如果 ed-1 刚好能够被 $\phi(n)$ 整除,便意味着我们找到合适的 d 。这个例子合适的 d 值为:4811

我还写了一个 Python 脚本来生成公钥和私钥参数,有兴趣的话可以自己玩一玩:

 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
import bitmap
import itertools
import random

def getPrimes(limit=2**16-1):
    size = limit + 1

    m = bitmap.BitMap(size)
    for i in range(2, size//2+1):
        for j in itertools.count(2):
            pos = i*j
            if pos < size:
                m.set(pos)
            else:
                break

    primes = []
    for i in range(2, size):
        if not m.test(i):
            primes.append(i)

    return primes

def findD(e, phi):
    for d in itertools.count(e+1):
        if (e*d-1) % phi == 0:
            return d

# 生成质数
primes = getPrimes(2**16-1)

# ①随机选两个质数p和q
p = random.choice([i for i in primes if i < 100])
print('p:', p)

q = random.choice([i for i in primes if i < 100 and i != p])
print('q:', q)

# ②计算p和q的乘积n
n = p * q
print('n:', n)

# ③计算n的欧拉函数phi
phi = (p-1) * (q-1)
print('phi:', phi)

# ④找到一个比phi小的数e,使得e和phi互质
# 我们找一个质数e,使得phi不能被e整除
e = [p for p in primes if phi%p][0]
print('e:', e)

d = findD(e, phi)
print('d:', d)

# 验证
for m in range(2, n):
    c = m**e % n
    m2 = c**d % n
    if m!=m2:
        print('FAILED:', m, c, m2, m==m2)

安全性

至此,游戏中的公钥 en ,私钥 dn 便全部备齐!至于原理和数学证明,需要数论的一些知识,本文就不再赘述了。有兴趣的读者,可以自行查阅一些资料。

您可能对安全性还有疑问,私钥中的关键参数 d 是否有可能被破解出来呢?想要计算 d ,必须知道 $\phi(n)$ ;而想要得到 $\phi(n)$ 必须知道 pq ;而想要知道 pq ,必须对 n 进行因式分解。

而对极大整数 n 做因素分解是非常困难的,这决定的 RSA 算法的可靠性。我们玩的数字游戏数值都不大,很容易被破解。但只要 n 的位数足够长,被破解的可能性就非常小。同理,第三方知道加密后的密文 c 以及 密钥 en ,也很难破解出原文 m

这里提到的位是指二进制位,即 n 的二进制形式所占的比特位个数。

目前,能够被破解的 n 最大位数是 768 位,因此有人开始质疑 1024 位密钥的安全性。现在推荐的密钥长度至少要 2048 位,只要长度足够,安全性完全不用担心。

应用场景

加密

公钥加密私钥解密是非对称加密算法最典型的应用场景,特别适用于密钥需要公开的场景,比如 传输层安全协议 TLS ,它为通讯双方提供可靠的加密连接。

如果没有非对称加密算法,TLS 将无法实现。因为对称加密算法要求双方使用同一密钥,加密连接建立之前,只能明文协商密钥。试想浏览器想跟服务器建立安全连接,无论是它选定密钥然后发给服务器,还是服务器选定密钥发给它,只要密钥经过明文传输,加密就失去意义。

有了非对称加密算法,服务器可以生成一对密钥,私钥自己保管,公钥可以公开。当浏览器请求建立加密连接时,服务器可以将公钥发给浏览器,因为公钥是可以公开的。浏览器将敏感信息用公钥加密后再发给浏览器,只有掌握私钥的服务器才能解密,他人便无法知晓。

同理,服务器想发敏感信息给客户端,必须由客户端生成的公钥加密。换句话讲,每对密钥解决一个方向的加密问题,通讯双方都需要生成自己的密钥对,负责加密对方发来的数据。

由于非对称加密算法运算复杂,加密效率不高,通常只是用来加密少量的关键信息,比如协商密钥。回到 TLS 这个例子,其实可以借助非对称加密算法协商密钥,从而直接使用更高效的对称加密算法来加密数据:

  1. 服务器生成公钥(紫色)和私钥(红色)对;
  2. 客户端(浏览器)连接上来后,服务器将公钥发给客户端;
  3. 客户端随机生成一个用于对称加密( AES )的密钥(黄色);
  4. 客户端用公钥对生成的密钥进行加密,然后后发给服务器;
  5. 服务器收到客户端用公钥加密的密钥后,用自己的私钥解密,至此密钥协商完毕;
  6. 由于私钥只有服务器才有,因此第三方无法知晓客户端选定的密钥是啥;
  7. 此后通信双方采用对称加密,以该密钥加密数据;

签名

实际上,私钥也可以用来加密数据,加密后的密文只有公钥才能解密。尽管如此,由于公钥是公开的,因此这个机制不能来加密数据,但可以对用来对数据进行签名防伪。

回到黑帮的场景,老大会给手下们发指令。虽然指令内容可以公开,但是必须有一个机制来甄别指令是否老大发出的。这时应该怎么做呢?

  1. 黑帮老大对指令 m 的内容计算 SHA 数据指纹,结果为 h
  2. 黑帮老大使用私钥对数据指纹 h 进行加密,结果作为指令的签名 s
  3. 黑帮老大将指令 m 和签名 s 一起发给手下;
  4. 手下重新计算指令 m 的数据指纹,与 s 解密后的结果进行对照,即可判断真伪;
    • 如果两者一致,说明指令是真实的;
    • 否则两者不一致,说明指令是伪造的;
    • 由于签名需要私钥参与,因此第三方无法伪造签名;

代码实现

最后,我们以 Go 语言为例,演示如何编程实现非对称加密、解密、签名以及验签:

密钥生成

 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
// 随机生成一对密钥
key, err := rsa.GenerateKey(rand.Reader, 2048)
if err != nil {
	panic(err)
}

// 序列化公钥
publicBytes, err := x509.MarshalPKIXPublicKey(&key.PublicKey)
if err != nil {
	panic(err)
}

// 编码公钥
publicKey := pem.EncodeToMemory(&pem.Block{
	Type:  "RSA PUBLIC KEY",
	Bytes: publicBytes,
})
fmt.Println(publicKey)

// 编码私钥
privateKey := pem.EncodeToMemory(&pem.Block{
	Type:  "RSA PRIVATE KEY",
	Bytes: x509.MarshalPKCS1PrivateKey(key), // 序列化私钥
})
fmt.Println(privateKey)

加密解密

 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

// 例子直接生成一对新的密钥进行实验
key, err := rsa.GenerateKey(rand.Reader, 2048)
if err != nil {
	panic(err)
}

// 待加密明文
plaintext := []byte("fasionchan.com")

// 用公钥加密,得到密文
ciphertext, err := rsa.EncryptPKCS1v15(rand.Reader, &key.PublicKey, plaintext)
if err != nil {
	panic(err)
}

// 用私钥解密,得到原来的明文
text, err := rsa.DecryptPKCS1v15(rand.Reader, key, ciphertext)
if err != nil {
	panic(err)
}

if bytes.Compare(text, plaintext) != 0 {
	panic("error")
}

签名验签

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 例子直接生成一对新的密钥进行实验
key, err := rsa.GenerateKey(rand.Reader, 2048)
if err != nil {
	panic(err)
}

// 待签名数据
data := []byte("fasionchan.com")

// 对数据求哈希
dataHash := sha256.Sum256(data)

// 使用私钥对哈希值进行加密,结果作为数据签名
signature, err := rsa.SignPKCS1v15(rand.Reader, key, crypto.SHA256, dataHash[:])
if err != nil {
	panic(err)
}

// 使用公钥对签名进行解密,与哈希值对比,验证签名是否真实
if err := rsa.VerifyPKCS1v15(&key.PublicKey, crypto.SHA256, dataHash[:], signature); err != nil {
	panic(err)
}

小菜学网络】系列文章首发于公众号【小菜学编程】,敬请关注:

【小菜学网络】系列文章首发于公众号【小菜学编程】,敬请关注: