什么是RSA) \9 F' T: s, P0 v7 x0 H
前面文章我们讲了AES算法，AES算法是一种是对称加密算法，本文我们来介绍一个十分常用的非对称加密算法RSA。$ X5 f, x1 Q- n+ C. h) G
非对称加密算法也叫公钥密码算法，通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。- H5 s) {/ j; u. y3 _. a/ ]: N
RSA公司在1983年为RSA算法申请了专利。" @% E# |) P# m  Z7 |
RSA的加密
3 Z7 M: H$ L9 m, dRSA的加密可以用下面的公式来表示：9 N, p  D  w. q- u2 g! x6 F

; Y: i1 W3 K0 i7 N+ V. Y. B6 g! I通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算，可以算是非常简单明了了。
& R6 m. {) \6 h( ]简洁的才是最好的，这可能也是RSA算法这么通用的原因吧。
& F9 g: F( `% Y4 R  x2 I如果知道了E和N，那么就可以得到密文，所以我们把E和N的组合称为公钥，可以这样表示 公钥{E,N}。; H( \3 _9 u0 E; j! P
如何选择E和N是一个复杂的数学过程，我们会在后面讲到。
; X% a  [0 i! |RSA的解密+ s7 u, u/ ], ?0 q
先看一下RSA解密的公式：. X( K( {* m3 L. z9 }
4 k! h5 m+ H4 M2 T3 }! G/ L
通过公式可以看到，明文是通过密文的D次方，再和N取模得到的。这里的N和加密的N是同一个数字。
7 R0 i- L7 J2 \; JD和N的组合表示为私钥{D,N}。, Q1 I7 Q5 p4 j& S3 O
N,E,D的生成
6 P3 ]# b; e4 s( O, b5 s+ M知道了RSA的加密和解密原理之后，接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。
& q$ G; V$ j$ n8 E! b生成过程如下：$ y, Z% X# f( T" ]! G
1. 生成N) v, v$ S" w) K! c; e' p8 E
生成N的公式如下：3 |$ h/ P6 ^3 T1 D/ a! P4 ]
( o  G( {' ~( S2 [" u- N- [
p和q是两个很大的质数，太小的话容易被破译，太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数，它是通过不断的重试得到的。' L1 ^* M# L9 p9 H
2. 求L: j5 ~8 a' v  ]9 |5 V3 V$ Y
L是一个中间数，它和p，q一样，不会出现在RSA的加密和解密过程。
$ @& G3 w) O' _' a: x  h" W. qL的计算公式如下：3 Q2 O+ u7 d( o; d# y5 i- b) j. S! k
; b6 V/ n4 \; [3 R9 ?- D. Q
L是p-1和q-1的最小公倍数, g4 @" S( B1 j; G6 i8 `; O: q' [5 \) @
3. 求E
/ K* Z- f( e, B' \" lE就是用来加密的公钥了，E是一个比1大，比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。" T4 R" M) d: ?

2 M4 W3 N- g- a- P( G这里E也是通过伪随机数生成器来生成的。& z7 l$ y6 a' w0 {' f
找到了E和N，我们的公钥就生成了。! \( Y3 u. e5 ?# T- ~2 t+ R
4. 求D& z) o9 U; s5 s4 O% ^( ]
计算D的公式如下：* k. l0 m- @0 a* O1 ~; k
' K4 r8 T8 F4 I& t, H0 I
破解RSA
* `* \- A9 ?* C4 B2 Z9 Q如果想破解RSA， 对于密码破解者来说，他知道了公钥{E,N}, 知道了密文，根据公式：
1 r# N2 D0 ?$ I0 f0 T2 I( o% Y/ {! e
有没有可能直接通过已知的三个变量，求出未知变量明文呢？- q) @* D3 D. q6 I2 I
这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。* T/ T0 X/ U  q) i& E% Z; ~) `
那么有没有可能通够暴力破解来得出密钥中的D呢？! M. b3 I) M) B& Z- o& \$ Z5 i7 F9 N
目前RSA算法中p和q的长度一般为1024比特以上，生成的N的长度为2048比特以上，E和D的长度和N差不多，如果要暴力破解2048比特的D是非常困难的。5 P* a/ x# W  R( v/ I7 T
由公式：
! u9 u- R+ J. z( I8 @2 ?
& N: i3 T0 \7 {7 a; P* r8 t6 O* z可知，如果破解者知道了L的值，那么就可以轻易的求出D。而L是通过p和q计算出来的，所以p和q一定要保密，否则跟密码泄露是一样的。
) U1 h, a9 A3 D' c9 L5 u- G3 B: K% s因为 N= p * q ， 而p和q都是质数， N又是已知的，那么我们可不可以通过质因数分解来得到?p和q呢？
  W) W* U( H% G: _目前来说，还没有有效的对大整数进行质因素分解的高效算法，所以目前来说RSA算法还是很安全的，但是一旦有这样的算法出现，那么RSA将会很容易被攻破。, C; j* w  d" r
所以官方推荐：1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。