简介" q. a/ |5 V  }" D$ B: W0 B
1 `" E( X- T( A% |5 C: c( L+ T
    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。
; n5 w7 p! q' v3 Y
, X" o4 J! y! C: \' `    具体是利用了：
5 K' U2 r6 Y8 l+ G7 o( o& [2 O4 W; {) x
    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。
2 x/ A; t3 p8 y+ o4 p1 \. T* D' L$ I9 H% p- x5 S
    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。3 d5 e9 q; T6 N# V9 r4 J: @; Y7 r
* h* o3 N1 A. o/ O4 ?3 \
    原理# p; ~% o& b( Q$ M* j
% ^- ]5 n( V+ Z5 G
    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。* [$ q5 m# Q' }& X0 x/ o3 ~# `
1 E) R7 m+ X* a
    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。" Q6 c4 h. K) d- Z* J" |5 U0 r; B* |

* ?+ i9 R8 o: s    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。( i# t3 w; |1 A) R' K  D
- |; I- b- ~# Y  L1 @8 P0 I/ o
    解密过程：(c^d)modn=m，其中d为解密密钥。
9 f& p' y/ D( D0 I& W' s7 V. W" ?6 a* P1 r& u5 J+ r
    解密密钥d的求解：
' k1 r  t$ o# i0 l
3 @. V+ W1 P# C: h7 |    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
8 x* u3 Q$ `; o, P
( Q1 [" N- R- m4 `; O    费马定理：
  i4 V0 }& ?+ v
  U* ~; d% r  i( k    若p是素数，a与p互素，则a^(p-1）≡1（modp）4 C( g' K/ t* P  N

$ k. h# |2 A. Y4 p1 t    举例
" r1 U/ G# `2 s# Q
1 l/ k( [% V( q% T    加密过程举例（1）：  [: N; f" r  U
! i; b4 |; W7 Y; ^7 p4 U$ B5 M- I
    1.挑选两个质数，如p=61和q=53, m' v; o% e4 `8 T& Q3 t9 p- |
# y/ T* l6 Q4 o; U! `2 F  s
    2.计算N=p*q=3233
: ]  E4 }1 m( s1 A) P, L
4 Z: c5 n% U* Z; ~    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】: V" G6 P- ?' ]: E) u- Q

, U1 y0 F8 V8 j- C7 ]2 `6 |: G( c    4.选择与3120互质的一个数e=174 O: _: _2 `3 d! }7 j' b: T" j

& u6 c3 ]9 ~# T2 N! R    5.计算得出d，使得d是e关于3120的模逆，得出d=2753
% W- ]" ^$ }6 K: ^& J& G
5 T8 C. L3 y' H3 ]5 Y    6.如果明文是5，那么密文是5^17(mod3233)=3086
* S% e$ E: [* Q; c1 c% ~* q3 w( f# p
+ q, b5 M! l: M. l    7.解密，3086^2753(mod3233)=5+ a  y6 @* a( m9 y% z

* E4 G0 @8 I) r2 J& \5 o; ~    关于模逆：先用“辗转相除法”…! w  I- Q) u8 P" G/ V

4 \3 H% l( l) `2 Q4 }    加密过程举例（2）-中间人：
# }" }2 D9 a  C5 j# {
8 {2 i% b" @$ d    A：有一个公钥n、e。例如：3127、3。
+ a7 X3 v& b: [+ u$ C- o3 m$ v+ x! P- o
1 r( j& h. w) }8 O9 Y& J    B：有一个信息m。例如：89。
/ X$ L/ F( m( `! n3 H  M: H/ }  d' W6 j! g0 [8 e5 Q8 k
    C：偷听者
* _6 Q) ~2 J" K1 k  @8 q) s: q3 {5 V6 E0 f7 e. ^0 y' _
    A：6 n. N, x1 [- }  |5 s$ J

( Q3 N$ }, y$ G+ ?6 }. U) A    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。" O% [3 }3 E  K/ F( Q4 V  m+ a

9 ?" I2 B3 y/ k' |    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。* w# H8 J! h; T: i! g8 T4 p2 j$ R# k

/ }9 N) B' _' j1 V( t    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。( @" s- a# e/ z

+ P* Z; B: V6 L0 p    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。7 v, J. _/ {8 o" S
5 i3 J# s; B2 G4 |0 U, H5 G
    C：获得n、e6 b  I. N1 Q" n/ Y5 x) B0 n$ ^
8 |7 W$ v7 z: M3 U% B
    B：. e( O1 z* z/ L  S+ M, l! r3 B
0 S* ]" v( F" y9 A- }
    第一步：获得n、e
# B! t8 J8 V+ d# `9 {. y9 _% Y9 D( i8 _/ a
, I0 p/ n, a, H* ?    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。2 y7 c, S4 w$ B4 e" y7 c- ?  N( {, ^

- G, g% X8 y0 _9 L. d: H    第三步：发送c给A& m+ I7 X8 S$ R8 m0 f
: P$ T) I  V: R" ~! H. g1 Z
    C：
0 j) U! l0 ]$ ^+ k. P$ w8 q. R
+ [# i) l* {( \1 K    第一步：截获加密信息c$ f5 p) r" V- R* C
1 g2 C! `. g& |" W
    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。
: b2 P+ i8 n+ _% ~1 `3 `# M, z, G: y# O& K  f9 S
    A：6 F' ?& H: \* }% b% Z& S  `. J6 L1 q
8 w% p/ m+ y9 z" c
    第一步：收到加密信息c( {- P4 P/ k& z  Z" |* L' z. U

- K  g- ~  Y3 a/ T6 C    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。& `7 g% x, {; p. T0 X6 p

4 Z( T( t  q" |9 F& j    完成# d! ~$ R* t! b% `- W* t( g% H

% F7 |- a5 M2 j) D9 f/ f- @    安全性) q- P& _: b( D% \
" B3 O* v4 L9 s$ ]: Q7 y
    为什么RSA是不会被破解的呢？
  O% w: d+ ~( N. m* p2 v  E% g
6 A) V3 p9 @: E4 v% `1 N; K    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。
) A5 x$ |$ W  e7 u8 I& c5 Z1 P+ ~) K# Q, M  ]8 o
    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：: i/ h8 Q9 t6 o& R+ |
# o2 \8 i# }- R- W
    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。/ j! {: N( S  x* L

. Q/ T% B+ s. q+ c+ i9 r  [* R/ V    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。& ]+ a  d6 ~% s" R$ V- l; v
/ Q% F7 e2 T( ^: p- e7 _
    到目前为止，关于RSA可靠性的描述：
) }. A. ?1 e9 h# p+ K2 q
) g, K& v: ~' s9 E. n/ X9 ]* H9 f% T    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。4 ~+ j! H* J# ]1 t

( X* P% Q! X5 X5 n! {  I( t5 Z    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。/ Q* H/ T8 z& U  U9 \. z# w% p0 y

$ X+ D& A% F9 Q3 t/ d    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。- }6 q+ V0 q1 Y/ u* \  D+ t# C9 d  g

$ j" n( G3 `/ g5 e$ _3 _& @    RSA的正确性：9 n( q' ]4 A0 U3 d% B& h: X. S

6 e" b6 k! ^0 s7 N; ^1 j    可以使用欧拉函数和欧拉定理来证明。8 v3 ?: Y2 \1 t1 [

5 T3 s. O9 J) ~+ W; Z    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）
9 L' x7 k/ |, H, f* m) T1 l1 q/ y( `2 z
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m
% E: M: i9 a& j. v# a2 P
! `# P6 W; b3 t1 i+ s2 [4 Y6 S    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？
6 G. r( H& _' K& s4 s  a3 w5 A9 q% i" J4 R7 H; ^/ _0 n9 d
    应用1 c0 l" T% G7 Q/ F4 C

% P2 V' U4 P9 f; ]2 e+ B    RSA的应用：数字签名" v) f  e+ l) f9 A+ t) A6 }
5 c: ?6 S" I( k$ @/ Y7 }
    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。2 |  h3 O( O) d" k+ @# ]0 U6 {
3 w0 R- K/ r7 ?; A: G! C
    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。3 M2 }) D& b# ?2 A6 i
, a6 s" Q' J4 j7 b
    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。