-- TOC --
本文介绍非对称加密算法RSA的原理，参考很多不同的资料。
对称加密（Symmetric-key algorithm），又称私钥加密，即信息的发送方和接收方使用同一个密钥来进行加密和解密数据。使用对称算法最大的问题是要找到安全的密钥分发方法，确保其他人无法得到密钥。它的最大优势是加/解密速度快，适合于数据量大的场景，但密钥管理困难。DES，3DES，AES都是对称算法。（DES使用56位密钥，已不再是安全的，1999年使用枚举密钥搜索法，24小时就能破解）
非对称加密，又称公钥密钥加密。它需要使用一对密钥来分别完成加密和解密操作，一个公开发布，即公钥，另一个由用户自己秘密保存，即私钥。信息发送者用接收者公开密钥去加密，而信息接收者则用自己的私钥解密（用公钥加密，只能用私钥来解）。公钥机制灵活，但加密和解密速度却比对称密钥加密慢得多。非对称加密算法解决了对称算法中密钥分发的问题！但是，它的加密速度比对称加密钥慢很多。著名的RSA算法就是非对称的加密算法。
因此，对称算法和非对称算法各自都有应用场景，相互配合，完成安全通信的需求。而由于分发秘钥的安全性得到了非对称算法的解决，因此人们称非对称算法才是计算机通信安全的基石。
在1976年之前，世界上只有对称加密算法。
1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为"非对称加密算法"。如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
1977年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。（我现在随手创建的秘钥，都是4096位的）
这部分不是很难，中学数学就可以理解，因为我们不需要证明，只是去理解。
Alice和Bob要进行加密通信，Alice应该如何选择秘钥呢？
假设Alice选择了63和53。
实际应用中，这两个质数越大越好，越大就越难以破解。
\(n=p\times q=61\times 53=3233\)
n的二进制长度，就是秘钥长度。
>>> bin(3233)
'0b110010100001'
>>> len(bin(3233)[2:])
12
Alice选择的n=3233，一共12位，这个秘钥的长度就是12位的。（实际应用，不可能使用这么短的秘钥，至少1024位，我随手创建的秘钥，都是4096位的）
n的欧拉函数值，就是小于等于n，同时与n互质的数的个数。根据前面提到的数学知识，这里的n的欧拉函数计算，可以使用如下等式：
$$\psi(n)=(p-1)(q-1)$$
因为p和q都是质数。
Alice算出 \(\psi(3323)=60\times 52=3120\)
Alice要在1到3120之间，随机选择一个数e，这个数要与3120互质。假设Alice选择 e=17。
实际应用一般e=65537，请参考：OpenSSL使用总结
参考前面的数学知识，由于模反元素解不唯一，Alice得到一个解d=2753。
Alice的公钥为 (n,e)， 即（3233,17）；私钥为 (n,d) （3233,2753）
RSA算法的可靠性来自于对大整数的质因数分解极其困难！根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
上面的计算，一共出现6个数字，pqned和\(\psi(n)\)，着6个数字中，公钥用到两个（n,e），其它都是不公开的秘密。
攻击者只有得到私钥，即得到d，才能破解RSA，那么在知道公钥（n,e）的情况下，是否可以推到出d呢？
因为： \(e \times d \equiv 1 (\bmod \psi(n))\)， 要得到 \(\psi(n)\)，就需要知道p和q，\(n=pq\)，n公开了，因此如果能够将n进行质因数分解得到p和q，就破解了RSA算法。但是，对一个很大的数的质因数分解，现在在数学上除了暴力计算，是无解的。
“对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。”
现在Bob拿到了Alice的公钥（n,e），Bob要向Alice发送消息m，就要使用Alice的公钥进行加密。
m必须是整数，如果不是，需要将其转换成整数，比如取二进制值，而且m在数量上必须小于n，如果大于，计算结果将不正确，此时可采取分段加密的方式。
Bob的加密，就是按下式计算c：
$$m^e \equiv c \pmod n$$
就是计算m的e次方，然后除n，取余数。
假设m=65，计算结果为：
>>> 65**17 % 3233
2790 # c when m=65
Bob将2790发给Alice。
Alice用下面这个式子来解密：
$$c^d \equiv m \pmod n$$
就是计算c的d次方，然后除n，取余数。
>>> 2790**2753 % 3233
65
Alice解出Bob发给她的消息是65。
所以，RSA算法加密解密的过程，就是做乘法和模运算！
我们再来看看反过来的情况，Alice用私钥加密，Bob用公钥解密。假设Alice的m=99：
>>> 99**2753 % 3233
89
>>> 89**17 % 3233
99
用公钥解密私钥，常用来做数字签名，有这样的签名的信息，具有不可抵赖性和不可篡改性。
另外，不管是用公钥还是私钥，加密解密的计算过程都一样，不一样的只是，一方使用e，另一方使用d。
我们要证明的是： \(c^d\equiv m \pmod n\)
因为： \(m^e\equiv c\pmod n\)
因此c可以写成：\(c=m^e - kn\)， k是整数
将c代入我们要证明的式子，得到：
\((m^e - kn)^d \equiv m \pmod n\)，这个式子等价如下面这个：
$$(m^{ed})\equiv m\pmod n \tag 1$$
因为：\(ed \equiv 1 (\bmod \psi(n))\)
所以：\(ed=h\psi(n) + 1\)，将这个式子代入（1），得：
$$m^{h\psi(n)+1}\equiv m \pmod n \tag 2$$
式子（1）和（2），就是我们要证明的式子，这两个式子等价。
根据欧拉定理，\(m^{\psi(n)}\equiv 1 \pmod n\)
将上式左边做h此方计算，再乘以一个m，得：
\((m^{\psi(n)})^h\times m \equiv m \pmod n\)
这个式子与式子（2）是一样的，得证。
不互质，就意味着m和n除了1之外，还有别的公因子。由于 \(n=p\times q\)，那么，m必然等于p或者q的倍数。
取 \(m=ap\)，因q是质数，m与q一定互质，根据欧拉定理：
\(m^{q-1}\equiv 1 \pmod q\)，(q-1)是q的欧拉函数值。
对上式进行处理：
\((m^{q-1})^{h(p-1)} \equiv 1 \pmod q\)
\((p-1)(q-1)=\psi(n)\)
\(ed=h\psi(n) + 1\)
得：\(m^{ed-1} \equiv 1 \pmod q\)
\(m^{ed-1} = 1 + tq\)
\(m^{ed}=m + tqm\)， 因 m=ap，得：
\(m^{ed}=m+tapq=m+tan\)，n=pq，得：
\(m^{ed} \equiv m \pmod n\)，这与上面式子（1）一样，得证。
有点烧脑...
本文链接：https://cs.pynote.net/se/jjm/202110055/
-- EOF --
-- MORE --