RSA a little bit of thought

作者

1976年，美国计算机学家W.Diffie 和 M.Hellman提出“在不传递密钥的前提下交换密钥”¹。
1977年，三位麻省理工的数学家实现了这种算法，RSA is short for author’s lastname，Ron Rivest、Adi Shamir，Leonard Adleman.

时间

It’s invented in 1977.

场景

数字签名的三个作用，防伪造，防篡改，访抵赖。

任何人都可以通过小明的公钥对这个签名进行验证，如果验证通过，可以肯定，该消息是小明发出的。

数字签名算法在电子商务、在线支付这些领域有非常重要的作用：

首先，签名不可伪造，因为私钥只有签名人自己知道，所以其他人无法伪造签名。

其次，消息不可篡改，如果原始消息被人篡改了，那么对签名进行验证将失败。

最后，签名不可抵赖。如果对签名进行验证通过了，那么，该消息肯定是由签名人自己发出的，他不能抵赖自己曾经发过这

逻辑

基于“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。公钥PublicKey,私钥PrivateKey或者Secret Key，其中公钥加密，私钥解密；私钥加密，公钥解密。
RSA通过离散对数，欧拉函数、欧拉定理、模反元素，以及交换密钥规则的知识背景下被研发问世。
SK：Secret Key/Private Key — （保密）
PK: Public Key — (公开)

方案

离散对数

m^k mod n = 1~ n-1. m是n的原根。

欧拉函数

φ（m）= {与m互质数}的集合中元素的个数。
当m本身是质数时φ(m) = m-1; 如 φ(5)= 5-1=4。

当m可以被分解成两个互质的整数之积，如m = A*B，AB互质，
那么 **φ(n)=φ(A*B) = φ(A)*φ(B)=(A-1)*(B-1)**

例如

φ(35) = φ(57) = φ(5)φ(7)=(5-1)(7-1) = 46=24.

1---2---3---4---6---8---9---11                        8
12--13--16--17--18--19--22--23                        8
24--26--27--29--31--32--33--34                        8
\--------------------------------------------------------------/
                                                    **24**

φ(56)=φ(7*8)=φ(7)*φ(8)=(7-1)φ(8)= 64=24.
φ(8)= {1—3—5—7} = 4.

1---3---5---9---11---13---15---17                      8
19--23--25--27--29---31---33---37                      8
39--41--43--45--47---51---53---55                      8
\--------------------------------------------------------------/
                                                    **24**

*因为24=(5-1)*(7-1)=(7-1)φ(8) =φ(56)=φ(35) ，所以，通过反推24的因子是不能成立的。

欧拉定理

如果正整数m,n 互质， m ^φ(n) mod n = 1.
根据欧拉函数，当n 为质数时，m^(n-1) mod n = 1.

m ^φ(n)  mod n  = 1
[m ^φ(n) mod n]^k = 1^k
m ^k*φ(n)  mod n = 1
[m ^k*φ(n) mod n]*m = 1*m
m ^k*φ(n)+1  mod n = m

模反元素

如果正整数m,n 互质，那么 m*d mod n = 1 , d就是m 对n的模反元素。
例如：
m = 3,n=5;
3*d mon 5 = 1，那么d = 12.

假设k是mon过程的商，那么 kn+1 = md.
例如5k +1 = 3d
当k =1, d=2
k=4, d=7
k=10, d=17
…

RSA

m^e mod n = c 加密

c^d mod n = m 解密

公鑰： n和e 私鑰： n和d 明文: m 密文: c
還記得條件嗎？m < n；d 是 e 相對於φ(n) 的模反元素。

說明：

1、n會非常大，長度一般為1024個二進制位。（目前人類已經分解的最大整數，232個十進制位，768個二進制位）；

2、由於需要求出φ(n)，所以根據歐函數特點，最簡單的方式n 由兩個質數相乘得到: 質數：p1、p2，Φ(n) = (p1 -1) * (p2 - 1)；

3、最終由φ(n)得到e 和 d 。

總共生成6個數字：p1、p2、n、φ(n)、e、d。

關於RSA的安全：

除了公鑰用到了n和e 其餘的4個數字是不公開的。

目前破解RSA得到d的方式如下：

1、要想求出私鑰 d 。由於e*d = φ(n)*k + 1。要知道e和φ(n);

2、e是知道的，但是要得到 φ(n)，必須知道p1 和 p2。

3、由於 n=p1*p2。只有將n因數分解才能算出

一个具有注脚的文本。¹

---

1. RSA的數學原理 https://kknews.cc/history/z84oz43.html ︎︎