简介
" h, B' j7 S4 v& t; x4 q( E6 y( @& h. o  S& K% p
    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。
2 l4 B4 h4 a; N4 Y
9 K5 t5 f/ \7 Y8 j    具体是利用了：
5 l2 e8 ]2 t$ X. I0 W9 {
8 C( s4 z. ?' G' W# n) y    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。
! k# e! h7 J% N8 Y7 ?
2 E$ Q5 y3 L2 l% ]2 l1 h    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。
6 i3 E( g* d5 a* T7 @2 M0 Q
& [3 Y- I8 [" K7 }) O) n$ F    原理
( v1 p" `. V9 P4 o9 ?( r" S4 r: M  \' c8 A. p9 W
    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。; K- j5 @8 g' m1 K

8 g* s0 _  m5 G3 f2 ?* l- ^) @    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。6 c6 u5 ?9 J' y" K7 Q4 x
; r: K" B5 C& N- L# c
    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。
* E; R0 P2 F5 w( C0 b  e4 z5 m! R$ [
    解密过程：(c^d)modn=m，其中d为解密密钥。
, u2 K3 d2 B. c4 K& B
0 ^" f/ K) Z, F9 |    解密密钥d的求解：
8 ]% x" j! ]' r6 a- ^: Z+ j1 b# F
    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
0 n$ S5 n- x% B. E2 n$ Q! I9 f9 Q1 V, C; R7 {- C' ]3 C  p
    费马定理：: M) W) m3 `/ |- u# n

! `# C: @% ?! I9 Y; Q9 e    若p是素数，a与p互素，则a^(p-1）≡1（modp）
8 G& }9 {1 h: P5 t  s# b! c5 _: h4 r; H2 |7 ~" r5 l# W
    举例
  K( j( [' T% E' ^* q! d6 x: d! s6 A& t) D
    加密过程举例（1）：8 H. }5 E9 D. s4 G& A
9 C5 }/ V. E9 k8 R7 F" Q! O8 q
    1.挑选两个质数，如p=61和q=532 J, k/ R4 i$ e
; c/ M7 j2 ]# U# W4 E5 U
    2.计算N=p*q=3233
& R7 L& K8 F* T
4 i# h7 H& S* M) ^% U: e    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】
2 p: o3 h$ F, Q/ }  o7 Y0 o1 z3 P/ x6 }$ {7 _9 U
    4.选择与3120互质的一个数e=17
. b, D) Y( b4 \: E
$ Z2 V& g, D4 g7 X% Z/ p9 |    5.计算得出d，使得d是e关于3120的模逆，得出d=2753, P; q6 x  ]* N! `& G
3 |+ P4 F5 @9 b8 J% f
    6.如果明文是5，那么密文是5^17(mod3233)=3086
, O8 v1 d3 E: r: S. S7 {3 \! y% O0 Z
    7.解密，3086^2753(mod3233)=51 ~0 Z# ~7 D" b# g& w! k2 h1 S

- U# l/ C) d: N1 Z" u0 s. O    关于模逆：先用“辗转相除法”…$ s* H% _8 ^0 p

3 ]& J  {$ u  ~) @    加密过程举例（2）-中间人：
! w% K0 q9 c8 M' u. e/ @5 c5 W# p8 d  G. e8 K4 b
    A：有一个公钥n、e。例如：3127、3。
/ T0 C. F/ z5 Q1 \# a, m$ R1 {& a
4 o, W6 g/ f2 O+ t    B：有一个信息m。例如：89。
& w% B5 l7 m  X, d. A5 {
$ W& Y/ I% Z5 b4 c; \    C：偷听者
( N- y1 P4 r  c- u
* Y" e- e( ^; X% Q& [0 X9 n    A：2 Z* b" T" s4 I& R9 W# A, E3 [3 K& `
8 p- z9 w& L' z; J- S6 e/ Z
    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。
. I0 R- \) E/ n# ^7 `  [# w! F! W
" R( _* `4 i' [( b& R$ [    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。
2 p9 K3 G$ v* B2 `. r: P9 m
" ]9 D2 L# B. G+ Q- p% I    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。& a# C& r% X7 S7 B9 V

0 [3 w+ U) V8 L% u    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。; M$ z* m( c, n# r  |! D/ S
. }. `& ^# ^" h8 I. }
    C：获得n、e
& x$ s* K  c/ ]! j
; J/ H: I/ w% C( |) e1 N    B：) g: ]5 v% V1 p! ^: o- m. O+ D
+ s" B: |, Z2 @" w
    第一步：获得n、e
, x- v7 I; \4 T
( d7 F( L2 `, m  Z8 \    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。) F3 a3 {# ?+ k( H& M
6 u( f" J# o2 y& a% ?) M
    第三步：发送c给A2 m3 {3 ~9 P  ]" ^% _

( d. {! J1 d- ~7 R6 G! ?% C    C：
: l2 t1 \) Z" b! H! A+ N" S; |% e+ ~; W4 A; `  u6 x* ]7 V! H
    第一步：截获加密信息c$ ]: w& q4 w6 q. q7 l" d
/ b7 K* W& h- S5 o- c
    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。9 M& u8 a* t9 s
& q% |$ K  w: Z. A) i/ w; s: [
    A：
5 a  I2 W4 ?; }  K6 ]1 {4 f5 v. j' i5 D% m6 \
    第一步：收到加密信息c5 I( H& |* t0 X3 u% [+ l6 k. \
& a" s* d1 W0 g  h8 R& d. D$ }
    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。
  K. R) e6 G& c, n# B1 |1 `- d) X0 x1 I0 ?3 a' j: k
    完成
$ x' O7 a8 B  [" K2 k3 m
( e5 ~* T! C- d9 H1 f# ^; p    安全性
- o# a0 d3 N: _6 X% n8 @7 y
3 ?7 V2 k$ E: y& T, f9 a/ W    为什么RSA是不会被破解的呢？
7 M: b& H3 a; b, E7 N" D1 M5 a: m
- I9 X$ b' X* m% |7 ]/ q: ~0 d    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。" k0 f  x& Z( Z4 x

. u$ g7 A' h3 S. R    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：# I" e0 s; l- e1 J  v8 R& C
. O' c2 Z' u" u5 `9 O
    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。0 w2 x' K! u( m7 F% t

. q) o& n- `" t* Y) s+ ^3 O$ ?    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。: }+ f# C  A- |+ |1 \; j1 @

& h# \& m# E8 v, W& v: [* B    到目前为止，关于RSA可靠性的描述：
. g4 P! \5 ~1 F  U7 I
% g, ^3 _2 Q: Y1 f; _8 C2 V    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
8 E* B+ J6 l$ T. g; g
! X; }; r) }% ^, D8 p: K; v$ i    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
6 U% j  G0 P6 T5 ^# O$ b
0 i# K4 D* d2 E7 `% b% m9 r, x' Y    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。/ w) {4 F4 h' \3 }

/ K$ I1 I) Y+ M7 S% V* N    RSA的正确性：
4 @8 v" c7 h) M- ?3 U- \
5 k. V& W7 L9 Z5 N6 `8 m    可以使用欧拉函数和欧拉定理来证明。( ~% w# @' Z/ j3 j# ?2 N' a

1 W% M. x6 e- C- F( S5 D' l    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）8 t0 W9 I* g5 u+ T; a: o: j; {
$ }. b4 v, N) p2 A* e
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m$ c/ d7 W" E% P3 t
3 i3 Q3 z# Z6 l4 O+ b+ O. i8 Q
    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？
' j2 U% v2 J9 E4 v) x" X: J4 U% N9 ]: w" p
    应用
! n( D5 p9 `. a' U7 S, G2 [+ Y, N7 k: E& _
    RSA的应用：数字签名1 \% q7 k: c$ W, P
  O' p7 @" k5 q- s, N4 f
    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。, \; D; u' S" n; A& H* R5 ?. }, m

: O7 A$ e, \* \    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。
6 l9 z3 O' H$ l6 H2 m( Z  |- G( v8 g/ H+ f
    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。