什么是RSA3 n) Y" m1 r6 P4 y! u
前面文章我们讲了AES算法，AES算法是一种是对称加密算法，本文我们来介绍一个十分常用的非对称加密算法RSA。
/ t2 \4 f3 q/ H8 W/ o& i2 G3 j# X非对称加密算法也叫公钥密码算法，通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。
8 r1 m6 S8 K/ n: @/ ]  W$ x3 LRSA公司在1983年为RSA算法申请了专利。
/ X1 d4 |/ k7 q3 Y: iRSA的加密
9 E/ e1 [/ ?) U* v7 O, C3 U  GRSA的加密可以用下面的公式来表示：
; z: a) t: \( ~( l/ n1 U, R! U% s9 h' {7 W
通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算，可以算是非常简单明了了。3 P" \$ K7 b& T( _0 j
简洁的才是最好的，这可能也是RSA算法这么通用的原因吧。
" q9 V: ~! Q7 Q如果知道了E和N，那么就可以得到密文，所以我们把E和N的组合称为公钥，可以这样表示 公钥{E,N}。( B" \7 E' f: W! {/ K( U
如何选择E和N是一个复杂的数学过程，我们会在后面讲到。  k! J; e. F+ v8 Z
RSA的解密# R% `( g, o/ C" y3 Z, `
先看一下RSA解密的公式：
9 p7 H; F$ `/ h: j. |: v* w% V" G% a$ {6 a" D% ~
通过公式可以看到，明文是通过密文的D次方，再和N取模得到的。这里的N和加密的N是同一个数字。  ]& _5 O: q7 t6 e! Y: l; W
D和N的组合表示为私钥{D,N}。: A! z/ J0 W" U6 G* R. J7 b! j2 H; U
N,E,D的生成
/ s, \- m; i6 ]1 ?知道了RSA的加密和解密原理之后，接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。
; c* o; k& _3 O% j  t* G0 c/ |生成过程如下：  E! R6 D3 ^/ ]7 Z! P
1. 生成N1 h( E. @8 R# r# X) V0 q  ~
生成N的公式如下：
3 @0 }; X0 w4 E) `( M/ x: d$ Q/ c0 A# i7 x* T
p和q是两个很大的质数，太小的话容易被破译，太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数，它是通过不断的重试得到的。# K9 Q. n) U" U: B
2. 求L
' X: d/ u5 `0 \( ]L是一个中间数，它和p，q一样，不会出现在RSA的加密和解密过程。( U# E9 ?5 s: ?1 I% x, F' @
L的计算公式如下：
# J( ?7 h: D$ m- l, I  ^4 L
7 K9 n" H! F/ I1 K5 A& q* v( WL是p-1和q-1的最小公倍数3 a" l, I" O/ f' B1 z/ L1 ?
3. 求E# q$ w# n) n" q( t- W3 b" H
E就是用来加密的公钥了，E是一个比1大，比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。
; H( H5 q7 Z" Q9 q: q
& u" P% @6 n* P2 O$ G这里E也是通过伪随机数生成器来生成的。" E/ X! _" Z; p: g2 }4 w
找到了E和N，我们的公钥就生成了。. M) P' K. H4 E# o% Q4 N! {
4. 求D
* F) Y4 T9 ^7 ?$ h1 p* h. n计算D的公式如下：7 P2 I# k4 s# T

$ _2 t8 U6 F5 r' x2 I2 R破解RSA
" t. _' Z' u: d  X$ Q( P; B如果想破解RSA， 对于密码破解者来说，他知道了公钥{E,N}, 知道了密文，根据公式：
( h, {7 F( v* i
* p3 C. U& N0 {* H有没有可能直接通过已知的三个变量，求出未知变量明文呢？
. m' s3 Y. ^' O. q1 f这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。
( Q! l# @0 t  H! e+ F那么有没有可能通够暴力破解来得出密钥中的D呢？
3 h, f* W8 \* H" }; {目前RSA算法中p和q的长度一般为1024比特以上，生成的N的长度为2048比特以上，E和D的长度和N差不多，如果要暴力破解2048比特的D是非常困难的。
9 ]- M0 Y, C' b4 @由公式：
  o) L% K- n8 C$ c3 n" F5 k8 e3 A: }/ _! ~" ?4 s$ b
可知，如果破解者知道了L的值，那么就可以轻易的求出D。而L是通过p和q计算出来的，所以p和q一定要保密，否则跟密码泄露是一样的。* b3 h! W- L0 m: |- M
因为 N= p * q ， 而p和q都是质数， N又是已知的，那么我们可不可以通过质因数分解来得到?p和q呢？" |; ?* S8 s! q) {( n# O9 T( L
目前来说，还没有有效的对大整数进行质因素分解的高效算法，所以目前来说RSA算法还是很安全的，但是一旦有这样的算法出现，那么RSA将会很容易被攻破。# W6 R8 _  ]3 r9 D6 a
所以官方推荐：1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。