什么是RSA2 B1 V/ Z' x' {" D
前面文章我们讲了AES算法，AES算法是一种是对称加密算法，本文我们来介绍一个十分常用的非对称加密算法RSA。2 M; p! p& a- z, m
非对称加密算法也叫公钥密码算法，通过生成的公私钥来对明文密文进行加密解密。 RSA的名字是由它的三个开发者Ron Rivest, Adi Shamir和 Leonard Adleman的首字母而来的。0 g+ i& D: ?( x4 c9 x/ e
RSA公司在1983年为RSA算法申请了专利。
8 J0 y7 n. b, i) Z3 d% n) p) LRSA的加密! O" B& o7 ~% A3 s1 w2 u
RSA的加密可以用下面的公式来表示：. Z1 \( x1 P. K0 n
3 n, }4 @* ^& ^) t4 H- [! F# M
通过公式我们可以知道RSA的密文是通过明文的E次方再对N进行mod运算得到的。这个加密过程只用到了阶乘和取模运算，可以算是非常简单明了了。! k& k$ i9 S" a' E
简洁的才是最好的，这可能也是RSA算法这么通用的原因吧。6 }- O5 K( d/ W7 _3 Y/ [
如果知道了E和N，那么就可以得到密文，所以我们把E和N的组合称为公钥，可以这样表示 公钥{E,N}。; ]. a" d1 E! P: \  p& \
如何选择E和N是一个复杂的数学过程，我们会在后面讲到。
1 G' z2 l, h# N$ J% ?RSA的解密
" }; [( B9 @3 I) Q: j4 y9 d# t先看一下RSA解密的公式：
; `) B+ {0 f! d5 l" t! N9 `
* j: N" H2 n* U) b. ?# \, y6 z8 F通过公式可以看到，明文是通过密文的D次方，再和N取模得到的。这里的N和加密的N是同一个数字。
: }& L+ T0 E6 ]D和N的组合表示为私钥{D,N}。" i* z- `$ E3 \: |5 D0 Z
N,E,D的生成) Q' `% U0 Y! M5 r5 A) S
知道了RSA的加密和解密原理之后，接下来我们就要探讨一下加密和解密过程中的N,E,D是怎么生成的。3 F. Q. S" S" P7 I
生成过程如下：) Y$ L# e5 X$ o' |5 c
1. 生成N
. K: w+ z# ?8 t; r, K1 P生成N的公式如下：0 n. C1 {2 n. ?6 l( B3 O6 ?

1 M0 b+ a6 A" np和q是两个很大的质数，太小的话容易被破译，太大的话会影响计算速度。通常p和q的大小为1024比特。这两个数是通过伪随机数生成器生成的。伪随机数生成器不能直接生成质数，它是通过不断的重试得到的。
/ S8 q! Y* ~1 u8 g1 J. H& w6 b8 O2. 求L
0 f* M; I  \- v9 m" x) W. mL是一个中间数，它和p，q一样，不会出现在RSA的加密和解密过程。* F# k- ?/ \7 G; d: x1 T; V
L的计算公式如下：
8 |4 S# W" ~! m1 P, C+ f4 b" f; J, \9 \0 p3 `  F
L是p-1和q-1的最小公倍数
4 F; @8 w! |7 }3. 求E9 b7 p$ C. S" w+ u. D6 s5 `
E就是用来加密的公钥了，E是一个比1大，比L小的数。并且E和L必须互质。只有E和L互质才能计算出D值。
9 B' [1 O% _+ ^& n) `8 r& w
/ ^- a. j1 K/ }* c, c3 o2 `这里E也是通过伪随机数生成器来生成的。1 p6 E3 z$ }1 R- H- a
找到了E和N，我们的公钥就生成了。
3 O& o: b3 o, D  Y) d2 C4. 求D8 J" |* g. u8 A3 v9 I) I6 x: @
计算D的公式如下：) U# S' f3 `- O3 v# Q5 j6 ~) s

8 g( A- X& ?; n  l3 _, o: P破解RSA: z& k9 {$ b! z; I7 k7 `
如果想破解RSA， 对于密码破解者来说，他知道了公钥{E,N}, 知道了密文，根据公式：
7 V; O2 o4 k' @' U4 ~# e) g' g/ R8 }
# _* f% K" B! B* }4 b& b  D0 @1 L有没有可能直接通过已知的三个变量，求出未知变量明文呢？1 l1 s9 N* U# D' v) C
这个求解其实是一个离散对数的问题。目前还没有发现求离散对数的高效的方法。可以说是非常困难的。
6 {( V5 |4 e! z9 ?' V' Q# U那么有没有可能通够暴力破解来得出密钥中的D呢？9 h" e! ~. `" y5 H
目前RSA算法中p和q的长度一般为1024比特以上，生成的N的长度为2048比特以上，E和D的长度和N差不多，如果要暴力破解2048比特的D是非常困难的。2 k( o% ~" l: \0 W' i5 R, Q
由公式：; W$ y, D$ Y5 h6 z' d
' m& f+ I4 v% W  p- l1 K( L. q
可知，如果破解者知道了L的值，那么就可以轻易的求出D。而L是通过p和q计算出来的，所以p和q一定要保密，否则跟密码泄露是一样的。! Y9 k& f& g5 }- O$ C* o  |) R9 a
因为 N= p * q ， 而p和q都是质数， N又是已知的，那么我们可不可以通过质因数分解来得到?p和q呢？
) O5 f7 [) X5 P2 ]  z2 T目前来说，还没有有效的对大整数进行质因素分解的高效算法，所以目前来说RSA算法还是很安全的，但是一旦有这样的算法出现，那么RSA将会很容易被攻破。7 n) I. c# P* i7 `9 P
所以官方推荐：1024比特的RSA算法不应该被用于新的用途。2048比特的RSA算法可以用到2030年，4096比特的算法可以用到2031年。