什么是RSA: {/ V5 r9 d) t3 J' c1 k( [3 P
前面文章我们讲了AES算法，AES算法是一种是对称加密算法，本文我们来介绍一个十分常用的非对称加密算法RSA。; v, x7 m, g5 g
非对称加密算法也叫公钥密码算法，通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。0 _+ F. i7 a0 B9 D
RSA公司在1983年为RSA算法申请了专利。9 y7 m2 k) D" d
RSA的加密- R2 c6 a, ?, @( ]& q
RSA的加密可以用下面的公式来表示：
. ~' c* ?8 F0 B/ P! l$ l5 ~" L8 m) T7 c
通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算，可以算是非常简单明了了。
$ `& ?/ K# v! t简洁的才是最好的，这可能也是RSA算法这么通用的原因吧。
1 G- n& J1 E  ?) i如果知道了E和N，那么就可以得到密文，所以我们把E和N的组合称为公钥，可以这样表示 公钥{E,N}。- q8 }% J0 ^5 X5 [
如何选择E和N是一个复杂的数学过程，我们会在后面讲到。
+ u$ r- k) T9 w+ y$ g8 @5 w4 w. f. ~RSA的解密
0 @. p3 O6 N) C先看一下RSA解密的公式：8 a7 y9 N; t! ?* D

$ c2 o; ?. t1 K3 ]1 k: ^通过公式可以看到，明文是通过密文的D次方，再和N取模得到的。这里的N和加密的N是同一个数字。
. a/ K8 m- n3 TD和N的组合表示为私钥{D,N}。) Q6 a9 r6 |9 {! b' _/ V
N,E,D的生成- P0 L8 |% k& k# T7 ]' k
知道了RSA的加密和解密原理之后，接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。  H: L. e9 z/ l  o& q
生成过程如下：, }: r3 c6 _/ u8 Z. p& m- P
1. 生成N/ L& c2 ~7 s( m) s1 x( O% V
生成N的公式如下：: Y; z9 Z  `- ?3 R
, U/ m; e6 m  E2 j$ q
p和q是两个很大的质数，太小的话容易被破译，太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数，它是通过不断的重试得到的。
) N! R, _" N+ }" b( h8 z- [2. 求L! C; o3 R% b# q3 w
L是一个中间数，它和p，q一样，不会出现在RSA的加密和解密过程。
1 a. Y9 k, T0 q, K" o5 _L的计算公式如下：! j* _: H4 L2 S$ _/ h" \$ D

0 P5 Q) @$ r) HL是p-1和q-1的最小公倍数( b) o9 S4 F+ g
3. 求E
; w' D. ~5 H2 |, Q& JE就是用来加密的公钥了，E是一个比1大，比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。
0 J" O; N0 N3 h3 U# b- g' o2 U& `; P/ X
这里E也是通过伪随机数生成器来生成的。# V( Q) l) j6 f8 {: x. F  X1 r
找到了E和N，我们的公钥就生成了。0 P% b1 O' o4 q) P7 p1 b+ \4 d7 ^
4. 求D7 v+ o4 Y$ Q; p2 c% N9 A7 v! [' D: O
计算D的公式如下：
: q2 Z1 b3 }1 \) Z; _8 d; i/ W
1 Q6 ]4 K% f+ p! K* W5 G破解RSA* l, w8 U9 b! ^: E+ ]4 B; Q0 ^
如果想破解RSA， 对于密码破解者来说，他知道了公钥{E,N}, 知道了密文，根据公式：, I8 x" t  |7 h) n6 d+ E) k

; k8 A1 u: E1 o2 J9 L7 O& u/ L: U有没有可能直接通过已知的三个变量，求出未知变量明文呢？# j5 ]6 V4 @& i0 r: A
这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。
& q; X' `! r  N3 P# c那么有没有可能通够暴力破解来得出密钥中的D呢？
- Z" P' D  s' u3 U; k) P$ x# i目前RSA算法中p和q的长度一般为1024比特以上，生成的N的长度为2048比特以上，E和D的长度和N差不多，如果要暴力破解2048比特的D是非常困难的。' C. ]! O, }+ o$ x  v
由公式：/ y# X( H8 L2 j

, m" k0 R1 e* \% K7 k. B7 D可知，如果破解者知道了L的值，那么就可以轻易的求出D。而L是通过p和q计算出来的，所以p和q一定要保密，否则跟密码泄露是一样的。  ?/ @& Z$ L$ y( u, b2 Y' `
因为 N= p * q ， 而p和q都是质数， N又是已知的，那么我们可不可以通过质因数分解来得到?p和q呢？  u! R$ P; k: ~( e. n3 W: U
目前来说，还没有有效的对大整数进行质因素分解的高效算法，所以目前来说RSA算法还是很安全的，但是一旦有这样的算法出现，那么RSA将会很容易被攻破。
( s! j5 ^* U  i所以官方推荐：1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。