什么是RSA
% C) d& t# Z; p, X2 r# o前面文章我们讲了AES算法，AES算法是一种是对称加密算法，本文我们来介绍一个十分常用的非对称加密算法RSA。
& y  A4 d9 n1 @! }! z非对称加密算法也叫公钥密码算法，通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。1 V* ~( u# Y/ x6 x
RSA公司在1983年为RSA算法申请了专利。4 q5 d2 S6 M( w5 ~
RSA的加密
- b; M+ L8 w% q( A1 J; vRSA的加密可以用下面的公式来表示：
) ^2 [+ D0 @, g' g& X
# m; s6 R9 I' t$ Q) I& |  @- I通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算，可以算是非常简单明了了。
' o. T! B3 O0 _3 ~8 x, d简洁的才是最好的，这可能也是RSA算法这么通用的原因吧。
* y0 O  l+ H3 N% h, s4 I如果知道了E和N，那么就可以得到密文，所以我们把E和N的组合称为公钥，可以这样表示 公钥{E,N}。
6 F, I7 P6 r- O! s9 t5 o1 t如何选择E和N是一个复杂的数学过程，我们会在后面讲到。
/ d' J) |9 d( pRSA的解密
! M+ j; v/ ~. U/ n9 X+ g先看一下RSA解密的公式：$ B- e! K, r  y9 S
& a* P% X( p( V7 m
通过公式可以看到，明文是通过密文的D次方，再和N取模得到的。这里的N和加密的N是同一个数字。1 Q' L# D& `: b, m
D和N的组合表示为私钥{D,N}。
1 A! k; z9 X6 Z: E- c8 H( NN,E,D的生成
# z* I0 U$ |0 Y: T! X知道了RSA的加密和解密原理之后，接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。9 k3 Z8 i% p6 \3 W; `
生成过程如下：' T# G2 g8 K/ h, d" y. c
1. 生成N$ G: M) u' Y+ o$ R
生成N的公式如下：
, S/ K* _  J+ p) G
. y1 n: ~9 b" hp和q是两个很大的质数，太小的话容易被破译，太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数，它是通过不断的重试得到的。
" T% O. a$ r" |0 s2. 求L% e& T) e9 }+ T# t: T% D4 i$ D
L是一个中间数，它和p，q一样，不会出现在RSA的加密和解密过程。+ U9 Q, p& G5 P3 L: s4 ]
L的计算公式如下：2 W2 }5 k% L, }& v+ X6 x
6 [( ^* w( H2 {! i. Q) h- J* i
L是p-1和q-1的最小公倍数
- y9 g8 R& I! R% N0 q  W6 z3. 求E
0 t9 u- s1 S. W; KE就是用来加密的公钥了，E是一个比1大，比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。
' D$ E3 y; n4 n, Y- O
" \) I7 n  J* V0 N& {/ t3 u9 G0 G这里E也是通过伪随机数生成器来生成的。3 S' V6 I: c+ j- i% o6 B, v
找到了E和N，我们的公钥就生成了。6 `/ G) j6 _  ~0 M! w  |, R
4. 求D4 X$ ~; ^* r7 H! `2 D
计算D的公式如下：% L6 ]' `) K: Y, C6 q, y) m3 b

8 v  J2 h1 Y! r% o/ j" ~破解RSA
& N1 [9 d( W% M' v, n如果想破解RSA， 对于密码破解者来说，他知道了公钥{E,N}, 知道了密文，根据公式：
6 j9 _% Z* F4 e8 b; Z) V3 ]! L+ J0 K- x( e/ R) K. `7 V5 _. b
有没有可能直接通过已知的三个变量，求出未知变量明文呢？
- S* S  H3 ]( s. A" Z) H- @这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。! l- J/ ?& W/ I# q7 _% t) k$ P1 R
那么有没有可能通够暴力破解来得出密钥中的D呢？
; _. U2 f' G7 c; s& A目前RSA算法中p和q的长度一般为1024比特以上，生成的N的长度为2048比特以上，E和D的长度和N差不多，如果要暴力破解2048比特的D是非常困难的。, B% _+ P6 ?# P4 L/ R3 A
由公式：/ j( U4 _; ^& h  G2 t9 g
" h) }. y7 s* ~6 p7 t6 S
可知，如果破解者知道了L的值，那么就可以轻易的求出D。而L是通过p和q计算出来的，所以p和q一定要保密，否则跟密码泄露是一样的。# T6 X5 E& H4 P/ m  p
因为 N= p * q ， 而p和q都是质数， N又是已知的，那么我们可不可以通过质因数分解来得到?p和q呢？
) g& k) b) e- u$ ]9 d# i目前来说，还没有有效的对大整数进行质因素分解的高效算法，所以目前来说RSA算法还是很安全的，但是一旦有这样的算法出现，那么RSA将会很容易被攻破。
$ v5 ]/ T/ p0 ^6 L3 j. ^; L9 N所以官方推荐：1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。