什么是RSA7 Q1 z0 E/ a6 j: [" O
前面文章我们讲了AES算法，AES算法是一种是对称加密算法，本文我们来介绍一个十分常用的非对称加密算法RSA。: _$ Q% X& V/ j
非对称加密算法也叫公钥密码算法，通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。
3 M$ r+ U- w+ E; d2 s9 f; P+ bRSA公司在1983年为RSA算法申请了专利。. X4 a% E% J. a4 H
RSA的加密$ l- L' s- s; }, K) l% |+ h. O
RSA的加密可以用下面的公式来表示：
* |3 m  q# D* c9 @6 N4 Y' Y9 ]2 J+ S4 t. b8 X7 H
通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算，可以算是非常简单明了了。
" h5 E! g0 T7 t& b4 t9 g5 P简洁的才是最好的，这可能也是RSA算法这么通用的原因吧。0 i( b2 M4 y  v  ?
如果知道了E和N，那么就可以得到密文，所以我们把E和N的组合称为公钥，可以这样表示 公钥{E,N}。
& n5 u% y8 N" L/ [: o! d如何选择E和N是一个复杂的数学过程，我们会在后面讲到。
+ D$ k0 t3 M& }# \0 w* qRSA的解密: R: f, g+ d' ~2 P5 f
先看一下RSA解密的公式：2 s+ ]  s/ o, f3 x7 m
8 ~( L: f6 o6 R6 ?$ a+ D/ J+ I
通过公式可以看到，明文是通过密文的D次方，再和N取模得到的。这里的N和加密的N是同一个数字。+ \& y/ O* a* Z5 H, d
D和N的组合表示为私钥{D,N}。: _; o! g7 j( K* L1 i5 d: Y
N,E,D的生成
6 b; z# }$ t! J8 G- K; T+ O9 E知道了RSA的加密和解密原理之后，接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。
5 o% f* [. A4 c9 T1 A" [生成过程如下：6 p4 h9 j3 d* ?  u4 ^( P4 q
1. 生成N
6 p% R- z4 v& i' H% D$ ~7 I( {' r7 S生成N的公式如下：! e0 X, v1 `$ U; n, ~
7 z+ M: j+ \& q" O0 B$ ]0 K
p和q是两个很大的质数，太小的话容易被破译，太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数，它是通过不断的重试得到的。: X! |) R8 x/ H3 C4 O0 G# ?+ j
2. 求L
8 I8 ^$ s/ `8 ?# xL是一个中间数，它和p，q一样，不会出现在RSA的加密和解密过程。/ t8 h% O5 |% w' u, d0 c
L的计算公式如下：
  H9 N0 \, F- A* P3 Z0 g" ~# B$ L# v% B* s. K: G
L是p-1和q-1的最小公倍数
" s" ~; r& R+ }8 w9 m3. 求E
5 Z& K( n9 x  ^% ]/ q2 Q# SE就是用来加密的公钥了，E是一个比1大，比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。5 l: r0 k: Z3 z& O

9 }1 l& ~. H" I) R' r0 ?这里E也是通过伪随机数生成器来生成的。
, Q' J+ b  K" O; g1 P8 Q9 |找到了E和N，我们的公钥就生成了。
3 ~6 c$ p: i' v: u% Z+ E$ Q, F! D- P6 |4. 求D
; P8 c2 J% V+ a计算D的公式如下：) i; r3 s6 j/ E5 q( p: j

7 Y, q) {/ E7 P  n破解RSA
! G  I4 W4 O! c3 S如果想破解RSA， 对于密码破解者来说，他知道了公钥{E,N}, 知道了密文，根据公式：# w- h1 @8 x2 J( U- f

3 H4 d$ U" b# g, t, U2 q+ i: z有没有可能直接通过已知的三个变量，求出未知变量明文呢？) x! R; C& b  q  x% a
这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。
' K  J$ b2 U5 h" k2 [8 a那么有没有可能通够暴力破解来得出密钥中的D呢？% K+ V, U5 Z+ F
目前RSA算法中p和q的长度一般为1024比特以上，生成的N的长度为2048比特以上，E和D的长度和N差不多，如果要暴力破解2048比特的D是非常困难的。
; ]2 z& p/ E  I8 i9 t3 @4 M1 i/ r由公式：5 l3 T1 k+ t  G) N. t; a& U

' I9 g1 v% F( \$ U3 S4 q  p可知，如果破解者知道了L的值，那么就可以轻易的求出D。而L是通过p和q计算出来的，所以p和q一定要保密，否则跟密码泄露是一样的。% m+ L. n1 j4 F; o+ C: I
因为 N= p * q ， 而p和q都是质数， N又是已知的，那么我们可不可以通过质因数分解来得到?p和q呢？. X. C' z7 \8 `1 \
目前来说，还没有有效的对大整数进行质因素分解的高效算法，所以目前来说RSA算法还是很安全的，但是一旦有这样的算法出现，那么RSA将会很容易被攻破。! n3 H9 o/ X# a( W6 r7 q/ T
所以官方推荐：1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。