Nevermoi

公开密钥加密简介

也称作非对称密钥加密，描述为用某用户公钥加密后所得的信息，只能用该用户的私钥才能解密。如果知道了其中一个，并不能计算出另外一个。

下面我们主要聊最常用的RSA加密算法。

数学基础

• 互质

两个正整数，如果出了1之外没有其他公因子，这两个数就互为质数，简称互质。

• 欧拉函数

任意正整数n，在小于等于n的正整数中，与n互质的数的个数可记为：

• 欧拉定理

如果a, n互质, 则有

• 欧拉定理的特例：费马小定理

当p是质数，, 则有

• 模反元素

由

可以写成：

这个b叫做a的模反元素

• 扩展欧几里德算法

用来求解二元一次方程的整数解

生成RSA密钥

RSA算法的可靠性基于一个事实：两个大质数的乘积易得，但对这个乘积因式分解很困难。

• 随机选两个质数

例如 p=13 和 q=23. 在实际情况中，这个质数特别大。

• 计算乘积

n = p x q = 13 x 23 = 299

• 计算欧拉函数

φ(n) = (p-1)(q-1) = 12 x 22 = 264

• 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质

e = 17

• 计算e对于φ(n)的模反元素d

ed ≡ 1 (mod φ(n)) 等价于 k倍的 φ(n) 加上 1 等于 ed，写作 ed = kφ(n) + 1
变形为 ed + φ(n)(-k) = 1， 代入 e 和 φ(n) 的值，也就是二元一次方程 17d + 264(-k) = 1
根据扩展欧几里德算法，可得 d = 233, k = 15.

• 至此，我们拥有了

p = 13, q = 23, n = 299, φ(n) = 264, e = 17. d = 233.
我们把n和e包装成公钥 (299, 17)，把n和d包装成私钥 (299, 233)

• 可靠性分析

在上面的6个数字中，我们只公布了n和e，而d是最重要的私钥，如果靠n和e计算d的话

1. ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
2. φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
3. 想要知道p和q，就需要对n进行因子分解。那就难咯。

加密和解密

• 加密：有明文m=20，使用公钥对儿(n, e)加密得到c的过程
  

根据 m^e ≡ c (mod n) 计算，20¹⁷ ≡ 76 (mode 299), c = 76 为密文。

• 解密：对于密文c=76, 有
  

c^d ≡ m (mod n) 计算， 76²³³ ≡ 20 (mode 299), 解密出m=20

提示：windows系统自带计算器可以帮助计算。

//