什么是RSA
. b0 }$ R- u1 ]前面文章我们讲了AES算法，AES算法是一种是对称加密算法，本文我们来介绍一个十分常用的非对称加密算法RSA。
. {. N9 {/ \! Q# y3 {: A非对称加密算法也叫公钥密码算法，通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。
8 Z- F, n1 a" f8 F" ?RSA公司在1983年为RSA算法申请了专利。
/ g7 J( x: k3 \RSA的加密* ]; Z3 d% A7 @+ h  V8 j# X7 V9 x. k2 F
RSA的加密可以用下面的公式来表示：- A5 B! f# U# v; U1 w( Y% i# d; W

/ E/ K9 p. }4 [& @1 K4 a. ~通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算，可以算是非常简单明了了。
; A" W% g9 q; I2 w( ]简洁的才是最好的，这可能也是RSA算法这么通用的原因吧。) k3 K4 A3 b+ v: C
如果知道了E和N，那么就可以得到密文，所以我们把E和N的组合称为公钥，可以这样表示 公钥{E,N}。) g+ s3 E: m" g/ i
如何选择E和N是一个复杂的数学过程，我们会在后面讲到。
% @3 w$ x/ j8 ?( I* [RSA的解密
; z: `4 w: s0 t7 ]& n7 R. {8 I+ c先看一下RSA解密的公式：
) B9 r: w1 k0 q- u
1 C% T7 ]- g) g通过公式可以看到，明文是通过密文的D次方，再和N取模得到的。这里的N和加密的N是同一个数字。
2 m. y) Z: V' M/ v4 iD和N的组合表示为私钥{D,N}。7 `: p; r9 ?- F$ w8 t! D# w
N,E,D的生成
3 }& x' B8 k- F- C知道了RSA的加密和解密原理之后，接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。
2 H" _" H+ k+ x( @# o8 k生成过程如下：
' N/ t. w7 ?# A9 x: B5 i1. 生成N# V$ G5 h  p2 R* I- X5 E
生成N的公式如下：5 b; m4 r& D* h( c* D
: o9 n5 e, X: H9 z; z
p和q是两个很大的质数，太小的话容易被破译，太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数，它是通过不断的重试得到的。
4 q6 w3 [4 Y3 v( T0 }# z. ]/ s2. 求L
7 m  C# g' w8 t; d. lL是一个中间数，它和p，q一样，不会出现在RSA的加密和解密过程。  R, K4 e7 o( D$ o4 l; `
L的计算公式如下：
6 O: v' e  n8 A6 H, z
' [# @; d: g+ z. ^4 r0 `# J# dL是p-1和q-1的最小公倍数; R) u* `6 z4 x3 _$ J
3. 求E
- b8 z0 Y$ @% {E就是用来加密的公钥了，E是一个比1大，比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。, `# t: j8 |, k
% h' a5 L# C( ^' p/ g0 E
这里E也是通过伪随机数生成器来生成的。- N. R+ g! n' Q* J3 N; w
找到了E和N，我们的公钥就生成了。& l  N2 S  n8 I
4. 求D
: C" s0 J) X* ]. @6 I- o计算D的公式如下：% o: Q8 B6 p( E% R6 z% `

7 f3 U. N7 a  X$ \0 L, M4 y" ~破解RSA9 k6 I) B. X% i1 M1 _
如果想破解RSA， 对于密码破解者来说，他知道了公钥{E,N}, 知道了密文，根据公式：
9 j( ]# |" L1 S) w$ @9 _& H+ h
$ s9 r  u' \! J( b! C) D有没有可能直接通过已知的三个变量，求出未知变量明文呢？4 w- f' L: L5 k( B* |8 D6 H
这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。
1 R& h' M3 g% N) x) e1 S那么有没有可能通够暴力破解来得出密钥中的D呢？  v0 v0 v8 Z4 q3 X& V
目前RSA算法中p和q的长度一般为1024比特以上，生成的N的长度为2048比特以上，E和D的长度和N差不多，如果要暴力破解2048比特的D是非常困难的。
6 N9 B( B* K3 c4 q由公式：  {! h/ o/ }9 r3 E' K

; u7 D$ ^* m1 f  r2 t可知，如果破解者知道了L的值，那么就可以轻易的求出D。而L是通过p和q计算出来的，所以p和q一定要保密，否则跟密码泄露是一样的。
; n/ D( V# @4 @- l, b因为 N= p * q ， 而p和q都是质数， N又是已知的，那么我们可不可以通过质因数分解来得到?p和q呢？$ V3 B) S4 S2 Q% O8 O/ m8 ]
目前来说，还没有有效的对大整数进行质因素分解的高效算法，所以目前来说RSA算法还是很安全的，但是一旦有这样的算法出现，那么RSA将会很容易被攻破。
" f$ @% s: L1 k" h所以官方推荐：1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。