之前翼火蛇已经对RSA算法进行过简单的介绍。到目前为止，世界上还没有任何可靠的攻击RSA的方式。只要密钥的长度足够长，理论上RSA几乎无法被破解。
那么，RSA算法的原理是什么呢？下面，就来为你揭开RSA制霸加密算法界的奥秘。
RSA算法的原理
1 随机选择一对不相等的、足够大的质数p和q
什么是质数呢？
在大于1的自然数中，除了1和本身之外，不能被其他数整除的正整数，称之为质数。如2、3、5、7、11、13等。
2 计算p和q的乘积n
3 计算n的欧拉函数φ(n)= (p-1)(q-1)
这个公式的意义是：在小于等于n的正整数中，有多少个与n构成互质关系？这个数值用φ(n)表示。举个例子：假如n=10，在1到10之间，与10构成互质关系的有3、5、7、9，所以φ(10)=4
4 随机选择一个与φ(n) 互质的整数e，且1< e < φ(n)
什么是互质关系？
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。例如13和37没有公因子，所以它们是互质关系。而49和91有公因子7，所以不构成互质关系。
5 计算e对于φ(n)的模反元素d，使得ed ≡ 1 mod φ(n)
上面公式中“≡”是数论中表示同余的符号。公式ed ≡ 1 mod φ(n)表示ed和1 mod φ(n)同时做模运算后的余数相等。
什么是模运算？
假设有整数m和n，让m被n整除，取所得余数作为结果，这个过程就叫做模运算，用公式表示为m mod n。比如10mod3=1，10除以3的余数是1。
什么是模反元素？
如果两个正整数e和n互质，那么一定可以找到整数d，使得 ed-1 被n整除，或者说ed被n除的余数是1。那么d就叫做e的模反元素。
6 封装公钥和私钥，公钥KU=(e,n)，私钥KR=(d,n)
7 加密时，将明文变换成整数A，0<A<n-1，设密文为B，加密过程如下：B ≡ Ae (mod n)
8 解密时，根据A ≡ Bd (mod n)，解密出A，最后还原出明文
RSA算法加解密实例
数学原理太深奥？不用管这些，我们只管用就好了。通过一个例子，我们就很容易理解RSA加解密的过程。
比如，发一个单词love给女神小丽。怎么做呢？
首先，我们利用RSA算法制作公钥和密钥。我们选取两个质数p=3，q=11（为方便计算和理解，我们选择的数值很小。实际运用中选取的数值则大得多）。那么，n=p*q=33，φ(n)= (p-1)(q-1)=20。取e=3，公式ed ≡ 1 mod φ(n)等价于ed-1=kφ(n)，即3*d-1= k20（K为整数）。我们为k取值1、2、3……通过简单的试算，当k=1时，可求得d=7。此时，ed=21，被20整除，余数为1，ed ≡ 1 mod φ(n)成立，因此d=7。由此，我们得到公钥KU=(e,n)=(3,33)，私钥KR=(d,n)=(7,33)。
下面，我们开始进行加密。我们需要对明文数字化。这个规则可以自定义，比如将love的编码按照英文字母顺序排列数值，即a,b,c,d……x,y,z对应1,2,3……24,25,26。据此规则，love的明文信息表示为12，15，22，5。
根据公式B ≡ Ae (mod n)，对信息进行加密。
B1 ≡ 123 (mod 33)=12
B2 ≡ 153 (mod 33)=9
B3 ≡ 223 (mod 33)=22
B4 ≡ 53 (mod 33)=26
当小丽接到这串数字后，她会根据公式A ≡ Bd (mod n)进行解密。因为公钥KU=(e,n)是公开的，所以她得知n=33，同时她掏出任何人都不知道的密钥d，就完成解密了。
A1 ≡ 127 (mod 33)=12
A2 ≡ 97 (mod 33)=15
A3 ≡ 227 (mod 33)=22
A4 ≡ 267 (mod 33)=5
然后，小丽根据英文字母顺序表，对照得到四个字母l，o，v，e。这样的表白方式是不是很浪漫？而且非常安全，任何人截取了，都不能明白其中含义。
为什么RSA密码难以被破解？
从上面的加解密过程，我们可以看出要破解密码，必须知道d的取值。而要求出d，根据ed ≡ 1 mod φ(n)，必须知道e和n。因为公钥是对所有人公开的，所以e，n的取值是明确的。那么φ(n)怎么破解？我们知道φ(n)= (p-1)(q-1)，那么必须算出p和q。所以破解RSA算法的关键就是：根据n=p*q，如何求出p和q。
然而，这几乎是个不可能完成的任务。当p和q是非常大的质数时，根据pq的乘积去分解因子p和q，这是数学上公认的难题。
通常，p和q都会选的非常大，比如说200位。这导致n也非常大，有400位。寻找一个400位数字的质数分解并不容易，我们要做的除法运算次数大约为10 199！世界最强的超级计算机天河2号每秒浮点运算是1016级别。那么，分解出p和q，大约需要10174年。10174就是1的后面跟上174个0，时间是不是很长？
当pq大到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。所以“地球上最有影响力的加密算法”这个称号，RSA当之无愧。
有一个事实翼火蛇要表述一下：翼火蛇开发的加密软件科诺斯科正是采用了RSA算法。
不信，你试试。 |
