关于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)，这个公钥并不能用来解密，即便被别人截获，也没有任何泄密的危险。

密钥组成与加解密公式