最安全的加密算法RSA

大家好，这里是tiankonguse的公众号(tiankonguse-code)。
tiankonguse曾是一名ACMer，现在是鹅厂视频部门的后台开发。
这里主要记录算法，数学，计算机技术等好玩的东西。

这篇文章从公众号tiankonguse-code自动同步过来。
如果转载请加上署名：公众号tiankonguse-code，并附上公众号二维码，谢谢。

零、背景

之前介绍了AES加密算法，这个算法的缺点是加密钥匙和解密钥匙一样，缺少安全性。
今天来介绍一下目前世上最安全的加密算法之一RSA加密算法。

注：密钥的第二个字拼音是yue，即密钥（yue）。

一、历史

以前的加密都是对称性加密（Symmetric-key algorithm），即加密规则和解密规则相同。
这种加密最大的缺点就是对应的规则需要告诉其他人，否则无法解密。
保存和传递这个规则是个难题。

1974年瑞夫·墨克（Ralph C. Merkle）提出了一种新的构想：可以公开加密规则，然后可以在不传递解密规则的情况下完成解密。
1976年惠特菲尔德·迪菲（Bailey Whitfield Diffie）和马丁·赫尔曼（Martin Edward Hellman）找到一种算法实现了这种构思。
这个方法称为Diffie–Hellman–Merkle密钥交换。
后续又有很多方法类提出来，比如RSA、ElGamal、背包算法、Rabin，椭圆曲线加密算法。
其中RSA加密算法使用最为广泛。

这种加密算法称为不对称加密算法。
使用规则如下：

1. 乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
2. 甲方获取乙方的公钥，然后用它对信息加密。
3. 乙方得到加密后的信息，用私钥解密。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
下面就一步步讲解这个RSA算法吧。

PS：如果你不是程序员或者数学专业的，请直接跳到结论小节吧，下面的都是数学知识。

二、基础数学知识

互质：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。

欧拉函数：任意给定正整数n，求小于等于n的正整数之中与n互质的个数的方法，以φ(n)表示。

φ(n) 的计算方法如下：

1. 如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
2. 如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。
3. 如果n是质数的某一个次方，即 n = p^k，则φ(p^k) = p^k - p^(k-1) = p^k (1 - 1/p)。
   这是因为只有当一个数不包含质数p，才可能与n互质。
   而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
4. 如果n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)。
   即积的欧拉函数等于各个因子的欧拉函数之积。
   这一条的证明要用到”中国剩余定理”，这里就不展开了。
5. 因为任意一个大于1的正整数，都可以写成一系列质数的积。
   根据上面的四条,可以计算出φ(n) = n(1 - 1/p1)(1 - 1/p2)...(1 - 1/pr)，其中p1、p2、...、pr是n的所有质数因子。

欧拉定理：如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：a^φ(n) % n = 1。
欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。

欧拉定理有一个特殊情况。
假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成a^(p-1) % p = 1。
这就是著名的费马小定理。它是欧拉定理的特例。
欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。

模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得ab被n除的余数是1，即ab % n = 1。
这时，b就叫做a的”模反元素”。

好了，了解了互质、欧拉函数、欧拉定理、模反元素之后，就可以来看看RSA加密算法了。

三、密钥生成

假设Alice和Bob进行加密通信，她该怎么生成公钥和私钥呢？
PS：看到Alice和Bob，Acmer是不是想到了比赛时候的博弈题了，而且大部分时候还做不出来，哈哈。

第一步，Alice随机选择两个不相等的质数p和q。
如61和53（实际应用中，这两个质数越大，就越难破解）。

第二步，计算p和q的乘积n = 61×53 = 3233。
n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。
实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

第三步，计算n的欧拉函数φ(n)。
根据公式：φ(n) = (p-1)(q-1)，Alice算出φ(3233)等于60×52，即3120。

第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
Alice就在1到3120之间，随机选择了17（实际应用中，常常选择65537）。

第五步，计算e对于φ(n)的模反元素d。
根据上面介绍的模反函数可以知道需要满足公式ed % φ(n) = 1，即ed - 1 = kφ(n)。
代入对应的数据可以转化为17d - 3120k = 1，根据扩展欧几里得算法可求解。
比如(2753,15)是一组解,即d=2753。

第六步，将n和e封装成公钥，n和d封装成私钥。
在Alice的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
实际应用中，公钥和私钥的数据都采用ASN.1格式表达。

比如我的公钥是下面这样：

$ cat id_rsa.pub
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAgQC9E4ol/zo2imljzR47bEc68voiwOYjlkRxrO0wC6iZno78AVDKVWv7T6bHGgbbE+FgjyV1vjn6OMfylMUiqiVZZ9kZlpal6S+vr8TkHxtGAeBZSDbVNlnswiuRw7xu3LpHKBkctofCg+tvUh8cAFbIVbtBw4VxyX8JP3L/YANeyw== tiankonguse@tiankonguse-PC

第七步，看看RSA算法的可靠性。
回顾上面的密钥生成步骤，一共出现六个数字：p、q、n、φ(n)、e、d。
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。
其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。

那么，有无可能在已知n和e的情况下，推导出d？

1. ed % φ(n) = 1只有知道e和φ(n)，才能算出d。
2. φ(n)=(p-1)(q-1)只有知道p和q，才能算出φ(n)。
3. n=pq只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。
目前，除了暴力破解，还没有发现别的有效方法。

维基百科这样写道：

对极大整数做因数分解的难度决定了RSA算法的可靠性。
换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。

假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。
但找到这样的算法的可能性是非常小的。
今天只有短的RSA钥匙才可能被强力方式解破。
到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。

只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。

1983年麻省理工学院在美国为RSA算法申请了专利。
这个专利2000年9月21日失效。

这个专利现在已经失效了，所以现在可以大胆的使用了。

四、加密与解密

有了公钥和密钥，就能进行加密和解密了。

假设Bob要向Alice发送加密信息m（小于n的一个整数），他就要用Alice的公钥 (n,e) 对m进行加密。
所谓”加密”，就是算出下式的c：m^e % n = c。
Alice的公钥是 (3233, 17)，Bob的m假设是65，那么可以算出下面的等式：65^17 % 3233 = 2790。
于是，c等于2790，Bob就把2790发给了Alice。

Alice拿到Bob发来的2790以后，就用自己的私钥(3233, 2753) 进行解密。
上面提到这个等式：c^d % n = m。

也就是说，c的d次方除以n的余数为m。
现在，c等于2790，私钥是(3233, 2753)，那么，Alice算出2790^2753 % 3233 = 65。
因此，Alice知道了Bob加密前的原文就是65。

至此，加密解密的整个过程全部完成。

我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。

你可能会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数或者字符串，该怎么办？
这里需要普及一个知识：在计算机世界里，一切数据都可以表示成二进制的形式，而二进制可以当做整数来使用即可。
对于整数过大问题，这个实际就是我们拆分二进制时拆分的问题，拆分的小一点就行了。
比如n大于1024，我们可以每次选择10位二进制进行加密，这样组成的数字肯定小于1024了。

三、结论

好了，看到这里就看完了RSA的整个加密解密原理,以及为什么这个算法是安全的。
实际使用中由于RSA加密算法的计算量比较大，大家都是先使用对称加密算法对数据进行加密，之后再使用RSA加密算法对对称加密的密钥进行加密，这两个算法组合起来，就可以快速高效的加密数据了。

这里再重复一下这个加密算法安全的原因：
根据目前的数学理论，只能对大整数进行质因数分解才能破解这个算法，但是这个复杂度太高，现有的计算能力还不能计算出来。

有人可能会问假设我找到一个方法，不进行因数分解，也可以得到私钥是不是就行了？
如果能够发现这样的一个公式或者理论，那恭喜你，你已经超越了世界上99.99%的人了，可以得数学界的若贝尔奖了。

有人可能会问假设我找到一个很牛逼的算法，可以快速的进行因数分解，是不是就可以破解这个算法了呢？
回答和上面的一样，你也可以得奖了，这个算法之所以安全就是依赖大整数质因数分解比较困难。

随着计算机的计算能力越来越强，后续的计算机有可能使用暴力的方法解除质因子，所以后续这个算法的密钥长度也应该对应的加长的。

忘记说了，前段时间的WannaCry病毒就是使用这个算法加密数据的，然后私钥找不到，所以数据没办法找回来了。
后续大家还是定时备份数据比较好，不放心网盘的话可以买两个移动硬盘，花这个钱还是值得的。

对了现在开通了公众号和小密圈。
博客记录所有内容。
技术含量最高的文章放在公众号发布。
比较好玩的算法放在小密圈发布。
小密圈这周接受免费加入，欢迎大家加入看各种算法的思路。

长按图片关注公众号，接受最新文章消息。