RSA算法
浏览数：25 /
时间：2015年06月08日
RSA算法其实在大学本科的课程已经学过了，不过当时理解的不深，这篇博客就当加深理解和复习了。
首先抛出2个问题：
为什么要用对称加密，解决了什么问题？
RSA算法是怎么保证加密信息不被破解的？
先回答第一个问题：
最初的加密算法是对称加密算法，加密和解密方式都是同一种规则。
例如：
A使用某一个加密规则，对信息进行加密。B使用同样的规则，对信息进行解密。这个加密规则我们称为密钥。这个加密模式带来了另外一个问题就是如何保证密钥的安全传输。
非对称加密算法就解决了上面的问题。A方首先生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
B获取A的公钥并且对信息进行加密。
A获取加密的信息后，使用私钥解密。
因为私钥是不公开的，从而避免上面的问题。
第二个问题，RSA算法是怎么保证加密信息不被破解的？
要知道RSA算法是怎么保证加密信息不被破解的，需要来看下他的生成密钥和公钥的过程，下面举个例子：
第一步，选择两个不相同的质数p和q
例如选择了31和101
第二步，计算p和q的乘积n
n = 31 * 101= 3131
n的长度就是密钥的长度，3131写成二进制是110000111011 一共12位，所以这个密钥就是12位，实际中RSA密钥一般是1024位，重要场合为2048位
第三步，计算n的欧拉函数φ(n)
根据公式 φ(n) = (p-1)(q-1)
φ(n) = 3000
第四步，随机选择一个整数e,条件是1<e<φ(n) ,且e与φ(n)互质。
这里选择e为311
第五步，计算e对于φ(n)的模反元素d
所谓的模反元素就是指有一个整数d，可以使得ed被φ(n)除的余数为1.
ed=1(mod φ(n))
这个式子等价于
ed-1=kφ(n)
上面式子实质上就是对ex + φ(n)y = 1，这个二元一次方程求解。
已知e=311,φ(n)=3000,
311x+3000y= 1
这个方程可以用‘扩展欧几里得算法’求解，（ｘ，ｙ）＝（791，-82）
所以d=791
第六步，将n和e封装为公钥,n和d封装为私钥。
n=3131 ,e=311,d=791
所以公钥就是(3131，311)，私钥就是(791)
RSA算法的可靠性：
上面生成密钥的步骤，一共出现了六个数字。
p,q,n,φ(n),e,d
上面六个数字中公钥用到了两个n和e，其余的四个数字都是不公开的，其中最重要的是d,因为n和d组成了私钥，一旦d泄漏就等于私钥泄漏了。
有没有可能在已知n和e的情况下，推导出d？
首先 ed=(mod φ(n))，只有知道e和φ(n)，才能算出d。
然后 φ(n)=(p-1)(q-1),只有知道p和q，才能算出φ(n)。
最后n=pq。只有将n因数分解，才能算出p和q。
也就是说如果n可以被因数分解，d就可以算出来了，也就以为这私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠
举个例子：你可以对3133（31*101）进行因数分解，但是我们很难弄对下面数字进行因数分解
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413
它等于这样两个质数的乘积：
33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917
事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。
所以可以看到RSA的的安全性是依赖于大数字的因数分解的。而大数字的因数分解，目前来说还没高效的方法解决，所以RSA的安全性是很高的。而且密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
最后看一下如果根据公钥加密，私钥解密。
（1）加密要用公钥 (n,e)
假设我们要加密的的字符为‘w‘ ，这里用ascii作为编码格式w对应十进制的值为119，需要注意的是需要加密的信息的值必须要小于n。
所谓加密，就是算出下面式子的c：
me ≡ c (mod n)
公钥是(3131，311) n=3131, e =311
119311 ≡ c(mod 3131)
可以求出c=564
（2）解密要用私钥(n,d)
拿到c=564之后，就用自己的私钥（3131,791）解密
可以证明下面的等式一定成立，这里就不证明了。
cd ≡ m (mod n)
564791 ≡ m (mod 3131)
可以求出m=119
这样子就可以解密得出119了。
至此，加密解密过程完成。
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
还有个问题，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法"（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
还有个问题，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法"（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
