如何深入浅出地讲解RSA密码？

一、对称加密与非对称加密

从前有个女孩叫做Alice，她想告诉Bob一个秘密。

然而有个叫Eve的人想要偷听。所以Alice需要想办法加密这条信息，防止Eve偷听。

古典的思路是：Alice和Bob提前准备了一个盒子，并配了两把钥匙。每次Alice把秘密装进盒子里，然后用钥匙锁起来寄给Bob。Bob接到盒子后用钥匙打开，便可以知道这个秘密了。

这种方式叫做对称加密。

其中，这个秘密本身叫做明文，用来加密的钥匙叫做密钥，锁好了的信息叫做密文。

Alice和Bob都有密钥，所以他们都可以随意地把明文翻译成密文，或是把密文翻译成明文。但Eve没有密钥，所以无法破解密文。

然而，在现代网络的实际应用中，这种对称加密却有很多很多的问题！

其中，最大的问题是：很多情况下，Alice和Bob可能没有机会提前商量，所以无法生成相同密钥！

比如，如果你想要发送一条秘密信息给我。如果采用对称加密的话，咱们的手机在商讨密码的时候，黑客可能已经在窃听了。那样的话，密钥就会被黑客窃取了。(⊙﹏⊙)

所以我们需要更好的办法，就是——非对称加密。RSA是就是非对称加密。

一般的钥匙都是既能上锁、也能开锁的。

但是，非对称加密中，密钥有两种：公有密钥、私有秘钥。

公有密钥用于上锁（加密）。

私有密钥用于解锁（解密）。

因为Alice只需要上锁，所以她只需要公有密匙就够了。私有密匙只有Bob拥有。

Alice会先通知Bob：我要告诉你一件事。然后Bob接着就会生成一把锁，并制作两种钥匙：公有密钥和私有秘钥。Bob会把公有密钥发给Alice，然后Alice会用公有密钥加密信息。Alice把上锁的密文发回来后，Bob再用自己的私有密钥解密，并得到明文。

整个过程中，只有Bob拥有私有密钥。

Bob的私有秘钥不会交给任何人的。

纵使Eve获得了明文和公开密钥，Eve也无法解密。因为只有私有密匙才可以解密。

非对称加密的基本原理就是这样。(－∀＝)

为了打造这两把钥匙，一把用于上锁，一把用于开锁，我们还需要利用一些计算机和数论方面的知识。(oﾟvﾟ)ノ

二、计算理论篇

1、时间复杂度

我们都知道计算机的计算速度非常快，计算几十位数的加减法都是秒出。

然而，虽然计算机很快，但再快也是有上限的。（╯＿╰）

比如我电脑的CPU主频是2.40GHz，也就是说我的电脑每秒可以进行2400000000次最基本的运行。

对于计算机来说，像加减乘除、比较大小、判断条件这样的运算都是需要消耗时间的。而计算机的计算能力是有限的，就算是超级计算机“天河二号”，每秒也只能算3.39亿亿次。

所以对于计算机算法来说，我们需要利用时间复杂度来衡量一个程序的算法有多耗时。

算法复杂度有各种各样的，有 的， 的, 的, 的, 的……

上述几个复杂度的算法一个比一个慢。通俗的讲，大O后面括号里面函数的增长速度越快，算法越耗时。

准确定义的话是这样的：存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) 。

举个通俗的例子，如果对于一个程序来说，输入规模 的话：

的算法大约只用1次运算，普通电脑 秒就能算完。

大约会用30次计算（log的底数是2），普通电脑 秒算完。

大约就是 次计算，普通电脑需要一秒左右。

大约是 次计算，普通电脑大概要30年。

的话，人类所有电脑加在一起，等太阳炸了都算不完。┑(￣Д ￣)┍

（这个例子其实非常的不严格，只是比较好理解而已，想要真正理解大O请认真读定义。）

我们可以发现， 时间复杂度直接影响了程序完成的速度。从下图可知，当n增大的时候，不同时间复杂度的耗时差距立竿见影。

算法复杂度各种各样的都有，有时分析起来比较大下会特别困难，不过下面两件事是肯定的，而且非常重要：

对数时间复杂度比多项式时间复杂度快得多。

多项式时间复杂度比指数时间复杂度快得多。

事实上，在密码学中，很多时候密码不是不可以破解的，只不过破解密码需要大量的时间。

比如RSA最关键的一步，是Bob生成两个质数p1和p2，然后计算它们的积n，用乘法n=p1*p2，随后告诉Alice这个n的值。然而如果Eve想要破解密码，他必须在已知n的情况下求出p1和p2，他需要将n因数分解分解为n=p1*p2。

如果对于输入规模来说，乘法的时间复杂度是多项式级的，而分解质因数的时间复杂度是指数级的。

所以，分解质因数要比乘法慢得多。所以只要Bob生成的p1和p2足够大，等到Eve分解完n的时候，地球恐怕已经都不存在了。

密码本质上就是拉开了时间复杂度的差距，使得破解密码的时间复杂度高于加密的时间复杂度，以达成保密的目的。

2、RSA用到的几个算法以及它们的复杂度（这里就不解释这几个算法的实现步骤了……）

a. 乘法

作用：计算两个数的积。

时间复杂度：多项式级（相对于输入规模）

b. 随机数生成算法

作用：生成随机数（其实是伪随机数）

时间复杂度：多项式级（相对于输出规模）

c. Miller-Rabin测试

作用：测试一个数是否是质数。（有概率误判，伪素数可能蒙混过关。单次测试的可信度还不是非常高。需要用不同的参数进行多次独立测试，让误概率小到可以忽略不计。）

时间复杂度：多项式级（相对于输入规模）

d. 快速幂

作用：快速计算 mod n的值

时间复杂度：多项式级（相对于输入规模）

e. 扩展欧几里得算法

作用：快速求出ax+by=1的一组解。（a和b是常数且互质。解不唯一，这里只是算出来一组。）

时间复杂度：多项式级（相对于输入规模）

3、破解RSA无法绕开的一个步骤

分解质因数

时间复杂度：指数级（相对于输入规模）

这就是为什么RSA理论上非常安全，因为破解RSA所要付出地计算成本远远高于使用RSA进行加密的计算成本。

至于如何利用Miller-Rabin测试、快速幂、扩展欧几里得等算法进行RSA，我们需要先再介绍一些数论。

三、数论篇

_( ﾟДﾟ)ﾉ先膜拜一位巨神。

1、欧拉函数——φ()

φ(n)表示：小于n的正整数中与n互质的数的数目。（互质表示公因数为1）

比如想要知道φ(10)的话，我们就可以看[1, 10)中和10互质的整数，也就是1、3、7、9这四个数。（2、4、6、8和10有公因数2，而5和10有公因数10）。所以φ(10)=4。

比如想要知道φ(21)的话，我们就可以看[1, 21)中和21互质的整数，也就是1、2、4、5、8、10、11、13、16、17、19、20这12个数。（3、6、9、12、15、18和21有公因数3，而7、14和21有公因数7）。所以φ(21)=12。

我们惊喜地发现╰(*°‿°*)╯：

如果n能写作两个不同质数 与 的乘积，那么

(这个大家自己证明吧(￣▽￣))

比如10=2*5，2和5是两个质数，所以φ(10)=(2-1)*(5-1)=4。

比如21=3*7，3和7是两个质数，所以φ(21)=(3-1)*(7-1)=12。

2、同余式

相信各位同学都知道余数是什么。

比如说，23÷7=3……2

再比如，65÷7=9……2

我们发现，这两个数除以7都余2，于是我们就可以这样写：

23 ≡ 65（mod 7）

当然也可以这样：

23 ≡ 2（mod 7）

65 ≡ 2（mod 7）

准确地说，如果a=b+km的话，a ≡ b（mod m）

同余式有这样两个性质：

同余式可以互相加：若a ≡ b（mod m）、c ≡ d（mod m），则a+c ≡ b+d（mod m）

同余式可以互相乘：若a ≡ b（mod m）、c ≡ d（mod m），则a*c ≡ b*d（mod m）

举个例子，既然我们知道23×(23+65)≡ 2×(2+2) ≡ 8 ≡ 1（mod 7）

因为23×(23+65) =2024，也就是说2024÷7余数是1。（不信自己动手算算看(^▽^ )）

3、欧拉公式

(mod n)

(自学了拉格朗日定理的高中生请自己证明^_~)

4、乘法逆元

如果ab ≡ 1（mod m），则称a和b为关于m互为乘法逆元。

已知a求b的方法：

因为ab ≡ 1（mod m），所以不妨设ab+mk=1，其中a和m为已知数。

可以利用扩展欧几里得算法，可以在多项式时间内，计算出来一个乘法逆元b。

(事实上，b的解不唯一，这里只是求出了一个b。)

四、两把钥匙

我们终于开始构造咱们需要的两把钥匙了。ヾ(≧▽≦*)o

第一把：公钥，用于加密，送给Alice。

第二把：密钥，用于解密，Bob自己留好。

1、Bob随机生成了一些非常非常大的整数，并用Miller-Rabin算法检测它们是不是质数，直到找到两个大质数—— 和 。（随机数生成：多项式时间；Miller-Rabin: 多项式时间）

2、Bob计算两个质数的乘积 （乘法: 多项式时间）

3、Bob计算 （乘法: 多项式时间）

请注意！因为n太大了，而分解质因数需要指数时间，所以没有人能够将n质因数分解。

因此，任何人都无法利用n推出φ(n)。（理论上在太阳爆炸之前可能性极小）

φ(n)的值只有Bob自己知道。

4、Bob构造了一个比1大、比φ(n)小、不等于 或 的整数e。（随机数：多项式时间）

5、Bob求出了e对于φ(n)的乘法逆元d，也就是说ed ≡ 1（mod φ(n)），也就是说ed=kφ(n)+1 (扩展欧几里得，多项式时间)

请注意！现在神奇的事情发生了！对于一个与n互质的数a：

因为 (mod n)

所以 (mod n)

所以 (mod n)

所以 (mod n)

所以，若 (mod n), 则（mod n）

到这里，两把钥匙构造完成！ㄟ(≧◇≦)ㄏ

公钥：（n, e）

密钥：（n, d）

于是，对于明文a，Alice利用公钥（n, e）就可以加密为密文c了。

她只用计算 (mod n) (快速幂算法，多项式时间)

而Bob利用只有自己知道的密钥（n, d），可以计算（mod n）

除了Bob，没有任何人可以知道φ(n)，所以没有人可以求出e关于φ(n)的乘法逆元d。也就是说d的值从头到尾只有Bob自己知道，不可能泄露。

现在，Bob需要做的，仅仅是把公钥(n, e)交给Alice，让Alice把密文a加密成c，得到密文c后再用自己的密钥解密。

Eve就不可能窃听了。<(￣ˇ￣)/

---

大功告成了！(/≧▽≦)/

不过事情还没有结束，接下来还有很多问题。

比方说在RSA中，显然a不能太大，因为n需要比a还要大的。而且如果a太大的话，RSA速度捉急。

所以如果加密长信息的时候，通常是用RSA来传递种子，然后用伪随机数算法展开，然后再利用AES等对称密码进行一次一密的加密。不过那就是另外一个故事了……

而且RSA只是理论上不可破而已，实践中因为操作不当，可能会有各种各样的问题。比如如果两个质数p1和p2如果太过接近的话，分解质因数也是很容易的……RSA在实际应用中的攻防还是可以继续讨论的。( ￣ ￣)