非对称加密算法原理

玩个小游戏

你心中默念一个三位数，然后把它乘以23，把结果的后三位告诉我，我就能准确猜到你心中想的数字是几？

实验一下

假设你心中想的数字是231，那么 231*23=5313, 所以给应该给我数字就是 313

那我拿到313这个数字该怎么办呢？

我用313 乘以87 得到 313*87=27231 这个数； 它的后三位就是 231， 神奇不？

这里你是不是会有疑问：

• 23、87这两个数是干嘛的？
• 23、87这两个数出现的依据是什么？为什么是这两个数？ 别的数行不行？

结合我们的题目，以及演算过程， 聪明如你一定能发现，23，87 不就是非对称加密的密钥对吗？23对应公钥；87对应私钥

为什么是23， 87；他们是怎么出来的？且看下文…

原理

我们把这两个数相乘， 得到 23*87=2001

任何一个三位数乘以2001，末尾三位都是该数本身； 比如 231*2001=462 231

假设三位数是num； 2001 = p * q; 那么 num * 2001 的后三位 等于 num

所以 num * p * q 的后三位 等于 num

假设 num = (m1 * 1000) + m2; 那么

num * p = （(m1 * 1000) + m2) * p = m1 * 1000 * p + m2 * p

假如 m1 = 0（没有千位）；

num * p * q = m2 * p * q   得到的数(m2 * p * q)的后三位 等于 num

假如 m1>0 那么

num * p * q = (m1 * 1000 + m2) * p * q = m1 * 1000 * p * q + m2 * p * q 

由于 m1 * 1000 * p * q 得到的数都在千位以上； 它的结果根本不影响最终数的后三位 所以 m2 * p * q 的后三位值与 num * p * q 后三位值相等 都是 num

由此 我们可以认为 num 就是要加密的信息， p是公钥，q是私钥， m2 即是加密后的信息，其中模数为1000

一套完整的非对称加密逻辑就构建出来了

2001 的约数组合

我们这里只是取的 23，87 这对约数而已， 其实也可以使用29, 69这一对，或者其他组合

除了2001 其实1001、3001 … 都可以 其实都1+n*1000 然后反向求约数

我们只用构造一个数然后求它的约数就行了

公式：
p * q =1+n*(1ek) // 1ek 即10的k次方

如果我们想加密5位 就 100001 还可以更长 10000000001 = 27961 * 357641

还可以更长， 比如 10000000000000000000000000000000001 但是要求它的约数呢？ 是不是发现有点困难了？ 但是如果想尝试一下，其实也不是不可以求解

但是当你能求它的所有约数的时候， 其实就相当于能够穷举破解了；

我如果想要生成一组密钥对， 就得分解因式去求约数，求解困难不说，如果我求出来了， 意味着别人可以求出来， 直接把结果穷举出来就破解了， 好尴尬

所以 真实世界就不是使用乘法了，比如 RSA算法 使用的是指数和取模运算，但本质上就是上面这套思想。

RSA算法

公钥＝(E , N)
私钥＝(D, N)

我只是搬运工

RSA 算法原理（上）

RSA 算法原理（下）

只是个巧合？

当在阐述RSA算法的时候， 看到 E * D % φ(N) = 1 这一步 有种眼前一亮的感觉
结合文章开始的例子
2001 % 2000 不就等于 1 吗？ 试着反向碰瓷一下， 看看能不能发现点啥？
2001 = 23 * 87 那么 可以假设 E = 23； D = 87； φ(N) = 2000 = (P-1)(Q-1)
假设 P = 41; Q = 51; N = P * Q = 2091
至此 所有假设都符合 RSA的条件设定

那么 公钥＝(E , N) = (23, 2091)； 私钥 = (D, N) = (87, 2091) 设 明文 M = 231

计算密文 C = M^E mod N = 231²³%2091 = 1161

解密密文 M ＝C^D mod N = 1161⁸⁷%2091 = 231

如何计算 231²³%2091 具体请看 快速幂取模算法

成功完成了一次 加密，解密；

对比游戏算法 与 RSA算法 密钥变化
公钥：[23, 1000] => [23, 2091]
私钥：[87, 1000] => [87, 2091]
加解密算法不一样

通过生拉硬凑，得到的一组数据，通过不同的方式达到了同样的目的，过程竟然如此平顺，冥冥之中貌似有联系，可是怎么解释？也许只是是个巧合？

注意：P = 41; Q = 51; Q 不是质数;
φ(N) = φ(PQ) != 2000

模反元素特性

先了解下概念：模反元素

其实文初的游戏就是应用了模反元素的特性

p=23 m=1000 p和m互为质数， 找到q=87
(p * q) % m = 2001 % 1000 = 1
符合模反元素的特性

归纳成公式：

设p，m互为质数，根据(p * q) % m = 1 求出 q 
设  p * q = m * k +1
设  明文为 M  且 M < m 
则 (M * p * q ) % m = (M * (m * k +1)) % m =  (M * m * k + M) % m = M % m = M
则 (M * p * q ) % m = (((M * p) % m) * (q % m) ) % m = M
加密密文： C = (M * p ) % m 
解密密文： (C * q) % m = (((M * p ) % m) * q) % m = ((((M * p ) % m) % m) * (q % m) ) % m
          = (((M * p) % m) * (q % m) ) % m = M

所以 我们不一定非要以1000为模

还是以231 为明文； 那么取 m > 231 找一个最小的质数 m = 233 那么由于 p * q % m = 1
所以 p * q = 234 设 p = 3， 3 与 231 互质 所以可以求的 q = 234 / 3 = 78

公钥：[3, 233]   
私钥：[78, 233]   
加密: 231 * 3 % 233 = 227
解密：227 * 78 % 233 = 17706 % 233 = 231   // 成功反解

上例为了方便理解做的阐述，采用了逆向推导
实际上如果我们要产生一组密钥对， 只用找两个质数p，q 相乘，则 m = (p * q -1)/k 即可产生一套密钥对

p，q 为质数  
模数：m =  (p * q -1)/k
公钥：[p, m]   
私钥：[q, m]   
加密：C = M * p % m
解密：M = C * q % m

这样一个简单的非对称加密算法就构造成功了

不过，再深入思考下， 如果已知 公钥 [p, m] 根据公式 p * q % m = 1 其实很容易求出 q，并且可以得到不止一个 q；
这样的加密算法，就没什么意义了；

RSA就很好的解决了这个问题 他的模与公钥私钥之间没有构成直接的联系，通过两个质数 很容易求出模 N；以及公钥 E 和私钥D； 但是已知模N 和公钥E 却很难反推出 私钥D

RSA算法原理与证明

本文中的简单例子是通过模反元素性质进一步推导出如下数学特性，实现了一套简单的非对称加密算法

前置条件：
1、设p，m互为质数
2、M < m
如果 (p * q) % m = 1 成立 则 (M * p * q ) % m = M 成立

RSA算法中在模反元素基础上引入了欧拉定理：

a^φ(N) % N =1

下列是RSA算法中的关键元素

质数：P    
质数：Q
模数：N = P * Q
欧拉函数： φ(N) = (P-1)*(Q-1)
公钥：E 小于φ(N)，并与 φ(N)互质
私钥：D
ED关系：E * D % φ(N) = 1
明文：M  条件M < N 
密文：C

在推导前，先引入一个取模运算法则，在前文中的推导中也都用到该法则：

(a * b) % p = (a % p )*(b % p) % p

通过这个可以推导出

a ^b % p = ((a % p)^b) % p

RSA 算法中关于公钥E，与私钥D的计算其实就是使用了模反元素特性

E * D % φ(N) = 1

由此可以得出：

E * D % φ(N) = 1
进一步, K 为正整数 E * D = φ(N) * K +1

根据欧拉定理可以得到：

M^φ(N) % N = 1
M^{E * D} % N = M ^{φ(N) * K +1} % N
M^{E * D} % N = (M * M^{φ(N) * K}) % N
M^{E * D} % N = ((M % N) * (M^{φ(N) * K}) % N)) % N
因为 M < N 所以 M % N = M
(M^{φ(N) * K}) % N = ((M^φ(N))^k) % N
(M^{φ(N) * K}) % N = ((M^φ(N)%N)^k) % N = 1^k % N = 1
所以 M^{E * D} % N = (M * 1) % N = M

RSA算法中其实就是使用了这个数学特性

M^{E * D} % N = M

对RSA进行证明：

加密： C ＝ M^E % N
最终需要要证明的是： C^D % N = M

代如 C ＝ M^E % N

C^D % N = (M^E % N )^D % N = (M^E)^D % N = M^{E * D} % N = M

完美验证！

结语

本文中的论述都是本人在研究非对称加密算法及RSA算法原理时的心路历程，通过不断的联想和深入剖析, 正向和反向推算相结合，不断的从懵懂到豁然开朗， 也许有些反复和混乱，但是也是反映的是一种遇到问题，不断思考，探究，归纳，总结，证明的学习方法，希望能对小白或者初学者提供有效的帮助