RAS加密原理

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以外，没有其他公因数，我们就称这两个数是互质关系(https://links.jianshu.com/go?to=http%3A%2F%2Fzh.wikipedia.org%2Fzh-

cn%2F%E4%BA%92%E7%B4%A0)（coprime）。

欧拉函数特点

一、当n是质数的时候，φ(n)=n-1。

二、如果n可以分解成两个互质的整数之积，如n=AB则： φ(AB)=φ(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 。由于ed = φ(n)k + 1。要知道e和φ(n);

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

3、由于 n=p1*p2。只有将n因数分解才能算出。