概述
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。在了解RSA算法之前，先熟悉下几个术语根据密钥的使用方法，可以将密码分为对称密码和公钥密码
对称加密：加密和解密使用同一种密钥的方式
非对称加密：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
好多人都知道RSA加密的数学公式，但是不知道其的内部运作，那么我们以下就详细分析一波！
离散对数问题
图1
图2
图1，mod就是取余的意思，上面公式的意思是3的多少次方除以17余数为12。由图2可知道3的13次方的时候就满足图1的公式。由图2的可知，公式后面的余数都是不一样的，而且是1-16。当我们好奇试试3^17%17时候，结果就是3，好明显等于了3^1%17的结果，那么我们称3为17的原根。
欧拉函数
思考：任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示
计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8 所以 φ(8) = 4
计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7 所以 φ(7) = 6
计算56的欧拉函数：φ(56) = φ(8)* φ(7) = 4 * 6 = 24
关于互质关系
如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系（coprime）。
欧拉函数特点
一、当n是质数的时候，φ(n)=n-1。
二、如果n可以分解成两个互质的整数之积，如n=A*B则： φ(A*B)=φ(A)*φ(B)
根据以上两点得到：如果N是两个质数P1 和 P2的乘积则：φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
欧拉定理
如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。如图3所示：
图3
我们可以设置互质的数如m=5和n=3，那么φ(3) = 3-1=2，5^2%3=1。所以上面的公式是成立的。（有兴趣的可以试多一点数字，注意是互质的两个数）
费马小定理
欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。如图4所示：
图4
公式转换
图5
注意：满足第3步的时候，m必须要小于n。
模反元素
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。那么d就是e对于x的“模反元素”。如图6所示：
图6
迪菲赫尔曼密钥交换
图7
图8
图9
公钥： n和e
私钥： n和d
明文: m
密文: c
说明：
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因数分解才能算出。
网友评论