如何深入浅出地讲解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(1) 的， O(logn)的,  O(n)的, O(n^2)的, O(2^n)的…… 上述几个复杂度的算法一个比一个慢。通俗的讲，大O后面括号里面函数的增长速度越快，算法越耗时。 准确定义的话是这样的：存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) 。  举个通俗的例子，如果对于一个程序来说，输入规模 n=10^9 的话： O(1)的算法大约只用1次运算，普通电脑 10^{-9} 秒就能算完。 O(logn) 大约会用30次计算（log的底数是2），普通电脑 10^{-8} 秒算完。 O(n)大约就是 10^9 次计算，普通电脑需要一秒左右。 O(n^2) 大约是 10^{18} 次计算，普通电脑大概要30年。 O(n!) 的话，人类所有电脑加在一起，等太阳炸了都算不完。┑(￣Д ￣)┍ （这个例子其实非常的不严格，只是比较好理解而已，想要真正理解大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. 快速幂 作用：快速计算 a^x 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能写作两个不同质数 p_1  与 p_2 的乘积，那么 φ(n)=(p_1-1)(p_2-1) (这个大家自己证明吧(￣▽￣)) 比如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、欧拉公式 若a与n互质，则a^{φ(n)}≡1  (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算法检测它们是不是质数，直到找到两个大质数——p_1 和 p_2 。（随机数生成：多项式时间；Miller-Rabin: 多项式时间） 2、Bob计算两个质数的乘积 n=p_1p_2 （乘法: 多项式时间） 3、Bob计算 φ(n)=(p_1-1)(p_2-1) （乘法: 多项式时间） 请注意！因为n太大了，而分解质因数需要指数时间，所以没有人能够将n质因数分解。 因此，任何人都无法利用n推出φ(n)。（理论上在太阳爆炸之前可能性极小） φ(n)的值只有Bob自己知道。 4、Bob构造了一个比1大、比φ(n)小、不等于 p_1 或 p_2 的整数e。（随机数：多项式时间） 5、Bob求出了e对于φ(n)的乘法逆元d，也就是说ed ≡ 1（mod φ(n)），也就是说ed=kφ(n)+1 (扩展欧几里得，多项式时间) 请注意！现在神奇的事情发生了！对于一个与n互质的数a： 因为 a^{φ(n)}≡1  (mod n) 所以 a^{kφ(n)}≡1  (mod n) 所以 a^{kφ(n)+1}≡a (mod n) 所以 a^{ed}≡a (mod n) 所以，若 c\equiv a^e (mod n), 则c^d\equiv a^{ed} \equiv a（mod n） 到这里，两把钥匙构造完成！ㄟ(≧◇≦)ㄏ 公钥：（n, e） 密钥：（n, d） 于是，对于明文a，Alice利用公钥（n, e）就可以加密为密文c了。 她只用计算c\equiv a^e (mod n)  (快速幂算法，多项式时间) 而Bob利用只有自己知道的密钥（n, d），可以计算a\equiv  c^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在实际应用中的攻防还是可以继续讨论的。( ￣ ￣) ~画图好累啊(＞﹏＜) 感谢评论区大佬ヾ(＾。^*) 欢迎大家指正。 大佬们要觉得没问题就给个赞吧( •̥́ ˍ •̀ ) 谢谢≥﹏≤