关于rsa:RSA-算法基础之案例篇

计算秘钥

1、随机抉择两个不相等的质数 p 和 q（例如抉择 3 和 11）

2、计算 p 和 q 的乘积 n=p×q=3×11=33

3、依据“欧拉函数”介绍过的公式代入计算 n 的欧拉函数值

φ(n)=(p-1)(q-1)
φ(33)=(3-1)×(11-1)=2×10=20

4、随机抉择一个整数 e，条件是 1 <e<φ(n)，且 e 与 φ(n)互质。在 1 到 20 之间，随机抉择 7，即 e =7

5、因为 e 与 φ(n)互质，依据求模反元素的公式模反元素 d 为：

ed≡1(mod φ(n))
7d≡1(mod 20)
7d≡21
d=3

6、将 n 和 e 封装成公钥，n 和 d 封装成私钥

n=33，e=7，d=3
所以公钥就是(33,7)，私钥就是(33,3)
其中，n 的长度就是密钥长度，33 写成二进制是 100001

一共有 6 位，所以这个密钥就是 6 位。

加密过程

假如甲要发送一串机密数字 m = 5 给乙，乙发送了一个公钥 (n,e)=(33,7) 给甲。甲依据以下公式及公钥对密文 m 加密成 c：

m^e ≡ c(mod n)

代入相干的值后为：

c = m^e mod n = 5⁷ mod 33 = 78125 mod 33 = 14

甲将应用公钥加密的密文 c =14 发送给乙。

解密过程

乙收到密文后，应用私钥 (n,d)=(33,3) 依据以下公式进行解密：

c^d = m(mod n)

代入相干的值后为：

m = c^d mod n = 14³ mod 33 = 78125 mod 33 = 5

乙应用私钥胜利计算出密文 m。

安全性

从始至终，用来解密的私钥 (n,d)=(33,3) 始终都在乙处，从未泄露。乙给甲的仅仅是用来加密的公钥(33,7)，这个公钥并不能用来解密，即便被别人截获，也没有任何泄密的危险。

密钥组成与加解密公式