RSA的诞生
在人类熟练使用文字，飞鸽传书时代就已经有密码学的影子，古代为了防止一些政治军事等重要信件被敌人截取发明了古典密码学。古典密码学基本上没有任何信息理论，只是人们根据经验对文字的一种简单混淆。常用的古典密码学基本包含以下几种：
- 单表替换加密（MonoalPhabetic CiPher）
- 多表替换加密（PolyalPhabetic CiPher）
- 其他奇奇怪怪的加密方式
现代密码学起源于二十世纪中期，1949年香农（C.E.Shannon）发表了题为《保密系统的通信理论》的经典论文正式标志着现代密码学的开始。早期的现代密码学的加密方式是：甲方用一个密钥进行加密，乙方收到密文后用相同的密钥进行解密。这就是我们熟悉的对称加密。然而对称加密有一个巨大的问题：甲乙双方如何通过网络协商出一个完全一致的对称密钥？
直到1976年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman提出了非对称加密的思想，被称为“Diffie-Hellman密钥交换算法”。这种算法提出：我们可以不使用直接传输对称密钥的方式来协商加解密的密钥。
受此想法的启发，1977年三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。此方法以这三位数学家的名字首字母命名，这就是大名鼎鼎的RSA算法！
RSA为何如此重要？
非对称密钥是现代密码学的基石，被应用于各个领域。可以毫不夸张的说，没有非对称加密现代互联网的发展将大大受限，其规模将远远不及现在，我们常用户网络支付，在线银行，甚至在线聊天等都不会存在。而RSA做为早期出现的非对称加密在网络安全中扮演着无可替代的角色，是信息安全的半壁江山！
RSA工作方式
公私钥初始化
- 随机生成两个大素数\(P\)和\(Q\),并计算$$N = P \times Q$$
- 计算$$r = φ(N) =φ(PQ)= φ(P)φ(Q) = (P-1)(Q-1)$$
- 选择一个小于\(r\)的整数\(e\)，使\(e\)和\(r\)互质。并求的\(e\)关于\(r\)的模反元素，命名为\(d\)，有$$ed≡1(mod \ r)$$
- 将\(P\)和\(Q\)销毁
此时，\((N,e)\)是公钥，\((N,d)\)是私钥。
消息加密
首先将消息\(m\)以双方约定的格式（有标准的填充格式）转换为一个小于\(N\)，且于\(N\)互质的整数\(n\)。如果消息过长，可以将消息分成几段进行加密（使用RSA_PKCS1_PADDING填充格式时RSA密文块有11bytes的填充长度，对于1024bit长的密钥所能加密的最长明文为:\(1024/8-11=117bytes\))。由于性能原因一般我们不会使用RSA加密长度大于一块数据，只用RSA加密一些关键数据。
RSA加密公式如下：$$m^e≡c(mod \ N)$$
消息解密
利用密钥\(d\)进行解密：$$c^d≡m(mod \ N)$$
RSA加解密就是如此简单，任何会编程的人都可以用Python语言快速实现一个RSA加密算法，但是它又是如此强大！
RSA原理证明
一点数论知识
数论数最纯粹的数学之一，主要研究整数的性质。被誉为“最纯”数学。
正所谓大道致简，数论研究的很多问题看似简单质朴却又深刻而丰富。如著名的“哥德巴赫猜想”，极其精简却是数学难题的皇冠，三百多年耗尽无数巨人的心血，至今无人摘得。
这篇文章中我只简单的介绍一下证明RSA算法所用到的一点基本的数论概念。
互质关系
因数，最大公因数等概念初中就学过。互质关系定义很简单：如果两个正整数\(a\),\(n\)，除了1以外，没有其他的公因子，我们就称这两个数为互质关系，可以表示为:\(gcd(a,n)=1\)。注意，两个数互质和他们是否是质数没有关系，两个非质数也可能互质,如：9和10互质，但都不是质数。
由两个数互质我们可以得到如下结论：
- 任意两个质数构成互质关系，比如13和61。
- 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
- 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
- 1和任意一个自然数是都是互质关系，比如1和99。
- P是大于1的整数，则P和P-1构成互质关系，比如57和56。
- P是大于1的奇数，则P和P-2构成互质关系，比如17和15。
同余式
如果整数\(a\)和整数\(b\)除以整数\(n\)余数相同，我们说整数\(a\)和\(b\)关于\(n\)同余，可以表示为：$$a≡b(mod \ n)$$
例如\(13\)除以\(3\)和\(2\)的余数都为\(1\)，我们可以写成$$3≡2(mod \ 13)$$
模反元素
当整数\(a\),\(b\)和\(n\)满足以下关系时：$$a^{-1}≡b(mod \ n)$$
我们称\(a\),\(b\)对于模数\(n\)互为模反元素，也可以表示为:$$ab≡1(mod \ n)$$
整数\(a\)对于模数\(n\)存在模反元素的充分必要条件是，\(a\)与\(n\)互质。
比如，\(5\)和\(11\)互为质数，\(5\times9-1\)可以被\(11\)整除，所以\(5\)对模数\(11\)的模反元素为\(9\)。
注意，模反元素不止一个，整数\(a\)对于模数\(n\)的模反元素为\(b\)时，则所有\(b+kn\)都是\(a\)的模反元素（\(k\)为任意整数）。证明略了！
当\(a\)和\(n\)都比较大时，求模反元素是比较麻烦的，用到了 扩展欧几里得算法，有兴趣的同学自行查找资料，一般的数论教材都会讲这个方法的。
欧拉函数
在数论中欧拉函数\(φ(n)\)是小于或者等于\(n\)的正整数中与\(n\)互质的数的数目。
比如小于\(9\)并且与\(9\)互质的数有1、2、4、5、7、8，所以\(φ(9)=6\)。
欧拉函数的计算方式并不复杂，这里简单介绍下：
- 如果\(n=1\),则\(φ(n)=1\)。因为\(1\)与任何数（包括自身）都构成互质关系。
- 如果\(n\)是质数，则\(φ(n)=n-1\)。因为质数与小于它的每一个数，都构成互质关系。
- 如果\(n\)是一个质数的某一次方，即\(n=P^k\)(P为质数，k为大于等于1的整数)，则$$φ(P^k)=P^k-P^{k-1}=P^k(1-\frac{1}{P})$$
这是因为在所有小于\(n\)的数中，只有不能被\(P\)整除时才可能与\(n\)互质。而在这些数中能被\(P\)整除的数的个数为\(P^{k-1}\)。- 如果\(n\)可以分解成两个互质的整数之积，\(n=P_{1}P_{2}\),则
$$φ(n)=φ(P_{1}P_{2})=φ(P_{1})φ(P_{2})$$
比如\(φ(56)=φ(8\times7)=φ(8)\timesφ(7)=4\times6=24\)
这条证明需要用到“中国剩余定理”，略了！- 任何一个大于1的正整数，都可以分解成一系列质数的积
$$n=P_{1}^{k_{1}}P_{2}^{k_{2}}…P_{r}^{k_{r}}$$
由4可得：$$φ(n)=φ(P_{1}^{k_{1}})φ(P_{2}^{k_{2}})…φ(P_{r}^{k_{r}})$$
由3可得：$$φ(n)=P_{1}^{k_{1}}P_{2}^{k_{2}}…P_{r}^{k_{r}}(1-\frac{1}{P_{1}})(1-\frac{1}{P_{2}})…(1-\frac{1}{P_{n}})$$
再简单点可以写成：$$φ(n)=n(1-\frac{1}{P_{1}})(1-\frac{1}{P_{2}})…(1-\frac{1}{P_{n}})$$
欧拉定理
早在1636年 皮埃尔·德·费马 提出一个猜想：
假设\(a\)是一个整数,\(P\)是一个质数,那么\(a^{P}-a\)是\(P\)的倍数，可以表示为：
$$a^{P}≡a(mod \ P)$$
也可以写成
$$a^{P-1}≡1(mod \ P)$$
这个猜想很有意思也很有用，但是费马并没有给出证明。
直到1707年4月15号，莱昂哈德·欧拉 出生，这位人类历史上最伟大的数学家之一出生后，人类数学自此开始迎来一段辉煌的时期。欧拉在数学的多个领域，包括微积分、图论都做出过重大发现。他在力学、光学、天文学等学科也都做出过巨大贡献。法国数学家 皮埃尔-西蒙·拉普拉斯曾这样评价他：“读欧拉的著作吧，在任何意义上，他都是我们的大师”。人们为了纪念他还曾将他印在法郎，邮票上，2002年一颗小行星也被命名为欧拉。欧拉是人类历史上当之无愧的大师！
1736年欧拉出版了一本名为“一些与素数（质数）有关的定理的证明”的论文集，证明了费马小定理，并且对其进行了更加一般化的扩充，变成了如下的欧拉定理：
假若\(a\)与\(n\)互质，那么\(a^{φ(n)} -1\)可被\(n\)整除，可表示为：
$$a^{φ(n)}≡1(mod \ n)$$
比如\(7\)和\(9\)是互质的，我们知道\(φ(9)=6\),立即可得:
$$7^{6}≡1(mod \ 9)$$
欧拉定理是RSA算法的核心，理解了欧拉定理就可以轻松理解RSA算法原理！
RSA加解密正确性证明
坚持看到这里的同学我可以高兴的告诉你，你基本上已经理解了RSA。
回头看RSA加密方式:\((N,e)\)是公钥，\((N,d)\)是私钥,待加密的明文为\(m\)，加密过程:(1) $$m^e≡c(mod \ N)$$
解密过程:(2) $$c^d≡m(mod \ N)$$
我们只需要证明解密同余式成立，就可以证明RSA算法的正确性。
由加密同余式可得，证明公式(2)等同于证明：
$$m^{ed}≡m(mod \ N)$$
因为\(e\),\(d\)对于模数\(φ(N)\)互为模反元素，所以\(ed≡1(mod \ φ(N))\),即\(ed=kφ(N)+1\)。因此，解密同余式可以改写成如下形式：
$$m^{kφ(N)+1}≡m(mod \ N)$$
这里我们要分两种情况讨论.
- 当\(m\)和\(N\)互质，根据欧拉定理，\(m^{φ(n)}≡1(mod \ N)\),只要上面的同余式两边同时除以m，即可得到欧拉定理，等式成立！
- 当\(m\)和\(N\)不互质时，情况稍微麻烦一些。
如果\(m\)和\(N\)不互质，则\(m\)一定是\(P\)或者\(Q\)的倍数，并且\(m\)小于\(N\)，我们假设：$$m=xP$$
那\(x\)必然小于\(Q\)（因为\(m\)小于\(N\)，而\(N=PQ\)）,又由于\(Q\)是质数。那么
$$(xP)^{φ(Q)}≡1(mod \ Q)$$
两边同时增加指数\(xP^{kφ§}\)可得
$$(xP)^{kφ(Q)φ§}=(xP)^{kφ(N)}≡
1(mod \ Q)$$
两边同时乘以\(m\)可得：
$$(xP)^{kφ(N)+1}=(xP)^{ed}≡m(mod \ Q)$$
上式可以写成如下形式：
$$(xP)^{ed}=xP+rQ$$
因为(Q)是质数，所以\(r\)必然是\(p\)的倍数，即\(r=r^{’}P\)进而：
$$(xP)^{ed}=xP+r^{’}PQ$$
因为\(m=xP\),(N=PQ),所以
$$(m)^{ed}=m+r^{’}N$$
所以
$$m^{kφ(N)+1}≡m(mod \ N)$$
成立！
至此，RSA算法原理得到证明！！！
RSA算法的可靠性
在RSA密钥生成过程中一共出现了六个数：\(P、Q、N、φ(N)、e、d、\)。
其中公钥是\((e,N)\),私钥是\((d,N)\)，除了公钥其他数字都不公开。
要想破解RSA必须得的到\(d\)才行。我们可以根据RSA的工作方式来推算\(d\).
\(ed≡1(mod \ φ(N))\),已知\(e\)的情况下只有知道\(φ(N)\)才能算出\(d\).
\(φ(N)=(P-1)(Q-1)\),只有知道\(P,Q\)才能算出\(φ(N)\).
\(N=PQ\),只有将已知的\(N\)进行因数分解才能得到\(P和Q\).
所以要想破解RSA就必须将\(N\)进行因数分解。但现在并没有很好的方法对一个数进行因数分解，唯一有效的方法就是暴力分解。
也许有人说了，现在计算机如此之快，分解一个数不是很简单么！
的确现在计算机每秒可以轻松实现几亿次计算，超级计算机甚至可以达到每秒亿亿次浮点计算。超级计算机可以瞬间分解1234567689098765432这样一个数，但是别忘了RSA密钥的长度是1024，2048，4096.一个1024bit长度的数大概长什么样子呢？大概长这样：
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
35141959745985690214341333
这个数的大小大概是1亿亿亿亿…大概30个亿吧。超级计算器也只能看看！！！
实际上人类目前借助各种工具分解过最大的数字是768个bit位！在量子计算机没有真正应用前RSA还是安全的！
结束语
这篇文章涉及数论中一些证明，有很多公式，书写起来非常麻烦。好在终于写完了，是真的累！！！！！如果能让更多人了解一下RSA原理，累也算值得吧！
后面证明的部分网上有一些版本，但是大都跳跃性比较大，不容易理解，我这里将证明过程尽量写的详细，如果还有人看不懂的话可以留言，看到我会解释的！
