RSA非对称加密算法

本文作者：梁开权，叩丁狼高级讲师。原创文章，转载请注明出处。

由于计算机软件的非法复制，通信的泄密、数据安全受到威胁，解密及盗版问题日益严重，甚至引发国际争端，所以在信息安全技术中，加密技术占有不可替代的位置，因此对信息加密技术和加密手段的研究与开发，受到各球计算机界的重视，发展日新月异。现在我们就RSA的加密算法给大家介绍一下。

RSA是目前最有影响力的非对称加密算法，该算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加***，即公钥，而两个大质数组合成私钥。公钥是可发布的供任何人使用，私钥则为自己所有，供解密之用。

算法实现过程

1. 随意选择两个大的质数p和q，p不等于q，计算N=pq(一般都是超过10万以上的质数)
2. 根据欧拉函数，不大于N且与N互质的整数個数為φ(n)=(p-1)(q-1)
3. 选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1)
4. 用以下这个公式计算d：(d × e) % (φ(n)) = 1
5. 将p和q的记录销毁(p和q的值是绝密的,只在钥匙设计者的脑子中)

以上内容中，e是公钥，d是私钥。

RSA算法的过程

场景:用户A希望把一个数据3传递给用户B,但是直接明文传递的话很有肯能导致隐私的泄露,所有采用RSA非对称加密的方式传输,那么他们会怎么做呢?
1:用户B任意选择两个大的质数,这里使用两个比较小的质数来做模拟即可
质数p = 3, 质数q = 11 根据上面的公式计算出N = 3 11 = 33
2:根据欧拉函数(如果不懂什么是欧拉函数可以先百度下)算出不大于35,并且和35互质的数的个数: φ(35) = (p - 1) (q - 1) = 2 10 = 20
3:随意选取一个整数e = 3作为公钥,该数和20互质,并且小于20,符合公钥的要求
4:根据公式计算数据d作为私钥: (d 3) % 20 = 1 解出d的值为7, 也就是私钥d = 7;
5:用户B算出了公钥和私钥后,把公钥3直接发给用户A,私钥7是绝密的,只有自己知道,用户A拿到公钥后直接使用公式把明文3进行加密处理,得到密文C = 明文^公钥 % N = 3³ % 33 = 27,然后用户A就能放心的把密文C = 27就传递给用户B
6:用户B拿到密文C = 27后,就要进行解密的操作,使用公式:明文M = 密文^私钥 % N = 27⁷ % 33 = 3

在以上场景中我们使用了比较小的数来模拟计算,发现就算外界窃取到了密文是27,由于没有私钥,也无法真正的**出明文3,在真实的计算机环境中,要**位数比较少的RSA加密还是比较容易的,但是在真实的网络场景中,使用的质数往往都超过了10万,需要**出来则至少需要好几年,而一般网络应用会定期更换**,所以通过暴力**的方式,几乎是不可能实现的,可以认为RSA加密算法是安全的.