简介+ }4 p- y: v# N8 `/ C4 {
. P" C7 k* m) b
    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。
2 o2 {4 S5 H( t& q' _5 W. K4 ?9 E' ?) W* b
    具体是利用了：
5 z  D0 c2 d: f; Q2 z% h/ }& m0 I! Q, V
    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。
  }4 ^" [+ @$ C* v3 x. N# {5 o: Y' _; k0 @
    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。6 a6 g3 h# I$ Z( e3 I, y

8 u* S% N+ x: B3 j4 u4 v    原理7 q1 z7 U/ u# b+ \" Z

0 Z# H9 X, G6 k% M5 N0 `9 M; m% D    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。2 d3 Q1 _0 O: W) u- D. e/ `) k0 L8 e# \

# l7 {$ I/ h6 u7 J- I; t    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。
; t5 y" t- o7 O7 Z. {) T! h; x4 \7 E$ u
    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。; a5 z2 U9 H$ p1 T- K# Q$ X/ E

, C1 B1 i4 P. I" \3 e    解密过程：(c^d)modn=m，其中d为解密密钥。
5 ?' F9 c- e* @8 a& ]- |
4 r% H7 f# D4 _    解密密钥d的求解：
; z" \% M$ _" u, K. W9 L
6 H( J9 p8 U7 l8 [+ u3 c  K    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn) D/ ?0 y3 c% Z1 C# F
7 X0 }8 D. R1 z( g; l& J
    费马定理：
" n; v  _2 H+ d8 A3 u# \0 k6 c( R0 ^( d% i% |. F$ t
    若p是素数，a与p互素，则a^(p-1）≡1（modp）" v* b4 ?: F8 U+ j, d

2 V3 N# O$ S/ B$ ~1 P. `    举例
6 Z1 H, v- Z) ^4 n0 f, O8 @1 F' T+ ~% ?# c. [# L$ z
    加密过程举例（1）：
  K! w$ Y) @2 m5 d5 {& j* j
5 y# E2 |2 F7 \: K1 _    1.挑选两个质数，如p=61和q=53
( t0 @- ]9 ?! c+ k" h1 [! @: p* m9 l  ]( `
    2.计算N=p*q=3233
3 }* I' P9 Z  \" O
# q) x4 S) X& o  Q    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】/ C+ W. b6 O" V6 {& T! B- T" t% v

" W  @3 d# q; z3 D  l    4.选择与3120互质的一个数e=17
8 x# `/ |; E5 C) _. x6 B6 i: s7 e* Q; F
- y6 j( F" H: ^3 Y1 A; |    5.计算得出d，使得d是e关于3120的模逆，得出d=27533 L7 i& u: v2 o8 z2 j6 e+ ?

& [% B7 o2 E  G9 S6 w# c$ K    6.如果明文是5，那么密文是5^17(mod3233)=3086
/ m* f0 M7 j4 p. J0 @. R, `+ g
1 q$ _" E  f# K; [. u3 |    7.解密，3086^2753(mod3233)=5, H. U! L  N6 Z/ [
( k" T5 p/ b2 B
    关于模逆：先用“辗转相除法”…7 j# t+ P1 D6 q6 N8 J; L* u: Z/ ]

! c. B/ v/ w; j+ z8 l    加密过程举例（2）-中间人：9 @! \1 e( _8 f
( g1 m. M* D9 ]
    A：有一个公钥n、e。例如：3127、3。
. _( m" E1 m$ `6 X" i- m& ?# r* a% j; z0 I1 h! D7 e1 x
    B：有一个信息m。例如：89。+ D4 I3 C2 f! k7 ?6 ]5 e

2 f  ]. e; i0 C7 x$ c7 u    C：偷听者% O' z) e" Y3 m5 Z( v
& }: g, H& u+ y  M) b
    A：' l1 i- \" F8 f" w

8 m3 Z0 B/ I* Z    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。: y& m" {; X, }

$ I/ H3 P- J# Z: x    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。
8 {; [4 o3 K" I, f
! V2 l  {; C5 l+ }) E' [    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。
+ ~, \7 u0 }& C; |- o8 @" q1 @) f- ?, v* H! w: ^8 x
    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。
8 ?1 `$ s" u6 U! a! ]7 Y+ Q" T  P( ^8 }- ?4 N) H
    C：获得n、e6 k3 ^5 @6 d, k

( e; r! j& n& t( {8 u1 e    B：
2 \$ s9 H! X- Q  ^2 R  y/ C/ q" g+ Z) w& Q; b* w( L5 O) _
    第一步：获得n、e+ |, a6 q9 s( e: j+ s

* s  s2 z9 x) [/ b' ]    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。3 S$ Y9 h5 ?4 h1 k6 t
7 e  y4 S  j( Z: z8 ^, B% c
    第三步：发送c给A, q2 A( z- k$ Z: ^/ V, p5 z6 t
3 |8 }0 c, e, M6 U/ j1 B) M  b
    C：+ t3 y1 Y$ U+ n4 w% M' v' b3 p
4 }. J. |: g  Z: R- d; }/ ]; `6 w: O7 G/ s
    第一步：截获加密信息c
) I7 [0 v/ T& k& O7 }% l* w, W
3 E# a* C/ H& r# U& b0 B    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。
4 }; z8 E  s8 w1 }
+ Y) w: I' \$ [7 J" D! T    A：
7 ^5 M% L$ q+ I" J
6 `9 Q# ]5 {/ k# d! f    第一步：收到加密信息c: I0 @. M8 a; {* ]9 b
1 O6 `6 _8 D+ D! a0 p8 p: u
    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。4 |  ~- _* G/ O& F8 R
2 X9 p# \7 t" S6 p' t
    完成
5 `  c/ W6 t  S: N$ h) P9 }/ b7 D! J8 q# F$ Y& S: O0 p
    安全性8 s3 @3 h, r8 A  _( w

0 k# b$ Q6 ^. \1 I* u% C    为什么RSA是不会被破解的呢？
, x0 a8 J: h( ?( r' b3 E* E: Z, {1 V! d
    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。
% k  s" ~( ~, j7 \- H- q0 B8 n, P) ~% D0 f
    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：% K- V, ^+ y3 a2 J6 d1 R( n3 M; |

8 g$ R. _( b6 v+ O) t    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。
) T: r+ g& \) F, {4 d; D
/ P1 n4 H5 z' }* O1 x; @    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。) ^! A+ K$ k. g% A% Y, ]
0 C. J  l4 q' Y4 M2 p5 ^
    到目前为止，关于RSA可靠性的描述：
. R" U3 ?+ H& ]8 Q% B
8 L1 |$ r6 E" f0 z+ ?3 P    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。0 \9 D' ]$ U( m+ F6 w
$ _+ k; {# \+ u
    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
( C2 Z- ^% }5 r9 L; Q7 B" S' Z* B2 a' g3 s, D
    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。: o# e, [, M) R$ F
' W1 S/ P" e' O8 e, C- P# S7 j
    RSA的正确性：  I7 I) k+ n6 C3 `* K. Z; \! s

  k& A' U: G# I0 v# \* a    可以使用欧拉函数和欧拉定理来证明。6 \+ o$ b$ z9 x) G1 B7 V! p. M0 \

6 _2 ^- o8 h* d, ~  o% d    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）
" ^5 G; Z7 |4 ?% h* P$ L) [+ c; n/ K* {7 E5 M& b, f1 n
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m
+ _7 d( S- F! L* {+ G5 ~( g& L0 T4 S. Z# `
    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？9 K) a3 Z2 r6 Q/ `4 `/ M- \
9 o, u, g$ I  K
    应用
. l' G* ^6 I3 u. H+ v8 N  i  y. v3 ]9 m. J
    RSA的应用：数字签名: L8 N% p' a2 C) S) y/ H
7 B# E" h% c+ k; t2 h1 x; @% Z
    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。6 _7 H. o! o5 C

& [! E$ d% u4 I  A5 G. `" z    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。
% m0 r4 [" h+ w, r$ D0 B& Y* r% m1 T: \# X, b3 ]
    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。