简介
! i/ g4 j- \/ E$ |0 Y4 L# R7 {- `& H* v( l- H; u& w" U6 n+ ^
    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。
- w: ~: R! |( T, l- R7 ~( @& P
# a4 i4 B; u4 A9 _: D, S$ M    具体是利用了：8 _/ @) P/ k1 g

2 P, F* p) D$ Q% K* H/ O9 D    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。) K* z3 [$ q7 u
- J/ j; J' p( L" ]# [2 P
    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。# j& `6 e7 P0 N6 d, z% X- m
' s. H5 s. k. }! X& }' V
    原理/ B0 c$ f! X3 C8 G; a+ V
6 W4 X8 x% J7 L
    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。+ X- e1 S# W9 {
- T0 w5 [) F8 M, S' k; F  Q9 z
    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。* \# }0 I: U: J/ q7 G" F. }

  I9 T# t  M4 \; o% n. L    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。
+ E* J# C( d2 I$ h2 P9 C  H% N: s0 D$ T' {* y; B6 f% J6 @
    解密过程：(c^d)modn=m，其中d为解密密钥。
) T9 V  I" H( a& q8 }
6 W" E  u4 d  T    解密密钥d的求解：
# `) j8 _* ~- `1 R# `  P. N% ]0 M' y5 B4 o" |0 a4 j; k# G' d
    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn- M- Y9 P% @) f2 f# j! S) z% z
' T. {- {1 b  ~$ ^( s
    费马定理：5 s# V5 A5 ]# t( z( n1 H

# v" y2 Q* D5 s7 b7 h    若p是素数，a与p互素，则a^(p-1）≡1（modp）
( j5 ~, [$ ~, h% H! w: E* V; c8 _
6 }. I& R4 ~; G! k    举例
+ z, w. ]8 y5 B' P1 F5 V8 J5 {4 C
% p, q% v' d. @    加密过程举例（1）：
& S. i/ S; b) g7 C* g
" t4 @" D& `+ a% [$ O" }1 `    1.挑选两个质数，如p=61和q=53/ M8 l' ^" m2 j% e2 j

$ M" D! D: \! i    2.计算N=p*q=3233
# L/ t5 D( W) }& ~7 u  ]# c
: q0 v6 H+ X9 N- A    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】
4 G7 e% g1 @4 [+ x2 x: B8 R
; Y( h" U3 G4 \: L1 z, T    4.选择与3120互质的一个数e=17& }: r4 P8 y& w( _: W$ T- O! V

) Z7 u3 L0 N. d    5.计算得出d，使得d是e关于3120的模逆，得出d=2753
; R1 x5 D2 z& l9 h$ [- Z& p
. m% l# v: X4 U, U( L/ L$ o! C3 Q5 S    6.如果明文是5，那么密文是5^17(mod3233)=3086
4 F3 P9 O: Y* Z* C0 L2 E" H; [, W
    7.解密，3086^2753(mod3233)=5) L; m: F5 X4 _* o) |
# H/ I7 C% F5 [+ c. T
    关于模逆：先用“辗转相除法”…& }8 O& [' {) ^2 f! r/ Q: ^

( x8 X4 Q: `: q    加密过程举例（2）-中间人：  K- e* R: _0 m$ g. v+ U5 y: p
4 Z+ j4 M7 \& T( `3 W2 }" X
    A：有一个公钥n、e。例如：3127、3。3 p7 S2 L- U& {1 Y4 t

' ]! X# w7 h& D' m1 R    B：有一个信息m。例如：89。. y1 X+ N! G2 s' X0 d+ l# u0 N% M

0 R7 {! G, i7 m$ n9 ?' f/ r, {7 @' [    C：偷听者# c% L( h2 C: |+ L; h& ~
2 U; H* M4 A& v2 d) `( }
    A：8 L+ e# B1 n" P; K* H' O5 X6 u
+ [* M) S9 D6 O  g5 A/ u
    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。
/ ], ~/ f5 @$ J7 h8 }7 n" c* }2 L) B. _5 e
    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。8 ?' H# L5 k. O+ N; i- D4 w5 k/ f& o

: u; c# o& H+ g" Q+ z    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。
6 ^0 w) T1 z3 D# i6 k
' `* `3 n- k7 _2 U    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。
, Y# \7 S7 l, A' L$ Q  _2 ~- K' T& D4 H( {# V1 i* x  \' q
    C：获得n、e8 I$ r! t+ A- K9 e/ \* [+ J- N, S
$ Q6 X% O& m& l
    B：
* ~, i. ]$ Y- o; K* Q
" {( L7 @; N" ~' t  v* u    第一步：获得n、e. J; L+ v6 q/ }% h6 B/ U; P5 Y

8 s  a& T% k9 Y5 [    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。* ^% J) L5 Z6 v6 Z( ~
! }3 L: W( J. l' {- t. K' E
    第三步：发送c给A) `8 V) x) \# Z) {8 g. K9 y9 ?
- p4 m3 d6 ~" s4 h+ m, E; d+ q/ Y
    C：
" O% F3 o0 T2 o1 Q! i
! e5 c$ O. ]2 x4 ]    第一步：截获加密信息c8 O# ~7 T) {, ~

, t% X; R$ S. y! k; d& c& O# X5 P    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。! {! ]* v# _- g
7 A% N) ~  E. ^6 F
    A：% c7 {! K/ u: H" I' A7 I7 a
4 L; f0 E  W4 }) H3 n$ K  P
    第一步：收到加密信息c7 O7 `, R8 h  X

; W9 x7 t) @7 h& i2 s9 u* [    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。1 a+ F5 j% b, [. ]4 f8 G' M/ g
- F& n3 f7 g$ r
    完成) i1 L4 s( C7 B0 P  T. n
; `& I3 g4 R$ q9 g+ ^0 S
    安全性7 O$ }2 `$ \8 I7 m- u; f" _+ W

0 n: c' F8 W% D( v) p    为什么RSA是不会被破解的呢？
  |- J. n- D* P) Y" G" `& n: H. z( x# e& u
    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。# m7 f: w& D  q+ O3 X9 J
$ z0 ~+ O3 Y! u  h( o# b5 z
    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：
$ H; G3 e$ H* g7 o+ d  @: _) [( W+ p0 g! k# H
    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。
$ }! S' W) C5 I& w, D
) H' |3 U4 d" P    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。: E, `5 ^' Z1 i# ~/ m

. ]& H( y1 H# G9 r; d$ V    到目前为止，关于RSA可靠性的描述：
) D# r1 A: N) s( }. v) K5 S
5 F7 G8 I/ ~/ ]: \' O% \    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
9 R% M4 B$ p3 K0 O+ M$ t* M9 X* {8 S2 c7 R; c' h9 E/ e( T
    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
! e) A3 L( q, R
& g3 ]7 ]  U& q; d1 K    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。5 g8 \6 F, t7 ^/ |* ?

, c# o1 o3 B6 Q- D& M9 _$ _7 H    RSA的正确性：
4 G( j1 q5 c' H' B3 W7 \. s9 L2 i1 C- y& u' f( B
    可以使用欧拉函数和欧拉定理来证明。8 D# r5 W, x* N. X4 u- U  O
0 t' d1 l; W6 ^( `
    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）
# F, A/ I) w9 j' d( b$ g& X0 L. G( l% q+ i! H8 @1 r
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m* N" r2 p- C; b7 z( l$ @. y9 v

; z, Z/ l8 u$ |3 O8 O! b    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？. B( }2 ^; V7 O9 v, E% J; _

- s$ n- }6 F; F( n# c, c: a& H    应用3 p% ~8 c0 _, {! Z- }$ j, D7 g! U
: ^4 H! [; P3 x0 ~) c' `
    RSA的应用：数字签名6 S7 W, L  U1 p. ]8 [6 b# _
' s: f* ^1 J" b
    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。
# Y- y6 [' j  ?% q) D# ?# U! h4 v) z4 O- {& v" x/ V3 j  K
    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。1 k+ X& r3 X+ _8 T& b' |, W
% [5 N; D/ g+ K
    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。