简介
7 ~3 \# u- ^$ V5 ~- O/ n% m2 F% B+ D+ O$ T# f5 g* E
    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。1 l( m2 p2 r) q3 M0 \& B
) T0 b8 ^9 V4 C2 P
    具体是利用了：
, w9 l4 R" J0 l: V% M1 A% v" `3 a* r
) d+ n$ l6 s0 o) v- z* P: t9 X    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。
) ^2 S* I$ U( k2 t
3 S6 M8 J- o$ P% d0 L    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。1 A* F: M* ~$ q) A+ f: ?

: F; z# o# \+ T6 O( [- R, T    原理
8 |  b" r, Z+ ^& R6 ?: E; M
8 `' L+ b* _$ Y5 {1 s) Y4 t    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。
) y+ M0 v' Y; Y
# \" u+ M3 x0 P. F2 v2 o4 _( Z    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。$ n. |: l2 J8 r& Z' m$ Z7 o

% h# a  U" a( ]5 f4 z# X6 H. ]    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。5 Y1 _7 \. K6 f; _" l
! m' D! D! q- k
    解密过程：(c^d)modn=m，其中d为解密密钥。
% A  S% u% L7 E* Q8 ^9 t: E: ]/ D
; g, C, L, C  A9 z2 h4 ]  E9 W    解密密钥d的求解：
9 L+ \& h2 g9 o( J0 g0 K! w9 |
+ r7 I* O" z6 ]5 j    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn& s2 V8 \7 V8 \& A* R' Z- O

# E* W7 h1 O: `9 q! I9 p4 N/ e1 z    费马定理：
. ~0 a7 R' Q. d) h8 s) m5 n9 m# F# D# |0 F
    若p是素数，a与p互素，则a^(p-1）≡1（modp）
0 T: b9 B! o$ o8 A& ~" {5 W$ e5 F$ y8 p$ ]( H
    举例
0 v# v3 _7 Q* [$ ]/ x9 m# x
5 s- K# W9 J1 ?4 E4 B2 a. q    加密过程举例（1）：$ u! g/ S5 y7 Y- ^1 |' ]7 K
0 T' B/ f& s6 p+ ]6 v8 r4 l" j, D: t3 x
    1.挑选两个质数，如p=61和q=53
  {9 [. B0 u6 }# j
& Q; \1 H& K# Y' x% ]7 k# d5 u    2.计算N=p*q=3233$ G- F5 R; s6 P3 I& f/ f, J
6 e3 ^: I  f8 f- U
    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】
& I$ }5 U/ `- b6 `- @8 @3 {; g% x- a  K5 z2 f. [( ]( d4 Y
    4.选择与3120互质的一个数e=17
* l; Y# E# k9 ^3 F6 y  D; R1 l/ i/ e, j) z: [" H2 T+ z
    5.计算得出d，使得d是e关于3120的模逆，得出d=2753* f2 S! t- I' V5 b
$ Z' G# U8 n5 @" ]+ i! {1 d6 y
    6.如果明文是5，那么密文是5^17(mod3233)=30863 p+ `& r* r0 Z! i  q" w+ _
/ P* ?$ M$ L7 G5 Y. M' Y6 e
    7.解密，3086^2753(mod3233)=5& q7 @2 R7 k+ K. ?) {! A

- z( V8 i& }! n6 ?. M$ G$ Q    关于模逆：先用“辗转相除法”…
, o3 b, ?% D) j2 {7 ~1 E% F. M  f
    加密过程举例（2）-中间人：% J+ r' \  h- ~; M; y! x7 ?
7 F1 w8 X+ z" B9 X
    A：有一个公钥n、e。例如：3127、3。5 {2 x8 `0 u. c& L4 a0 r% p

7 B& [3 n& V; g4 n    B：有一个信息m。例如：89。( w, L9 j+ X* [* |( |
, a& F6 D4 N; N# A" `( z
    C：偷听者
4 q3 |1 K: P* J5 y! C+ t' {0 X2 Z2 G( y1 g9 B
    A：
! A% i+ t# ?" M0 P( j  e- M
/ ]# U' x4 |" R* `" S6 P0 i    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。
( p7 v$ e/ B# D* \* S4 U7 b, A
5 y" S, X- w, P+ F    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。
. E# H1 N, J8 t2 T0 b! Q) j! z. ^1 n7 g9 V- I
    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。) u4 k  b% m* A
; N( |  l# k0 P( w
    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。
$ q/ I+ a; w( N' Y8 o+ [  a" U% b- j  W. p3 z
    C：获得n、e
( c' q7 A/ `5 U9 K7 A3 E' {0 h7 ]9 h$ @3 x4 t; f
    B：, u  Y- x+ W8 P1 U" L1 [8 N) m: {

% E( y$ j, U7 X- {# T1 d    第一步：获得n、e
" v1 A  y6 n, L$ k  X8 `
  W0 B7 ?* W' T' s    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。* s7 N6 f9 Y$ O6 o" w+ ~  o
2 @7 V% J% k) V8 ], g
    第三步：发送c给A- |; Q, a+ j4 g6 P; h9 |; r  V

7 v, A( K, z) a) i% V- D( p    C：
  w" \7 n# p$ y7 ?! @3 `7 ~4 |" Y% {0 z) p& M
    第一步：截获加密信息c6 S" z) o. u4 g2 t7 D# n
: P) D% j2 c( L. ?+ {5 }# R; W
    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。
/ _7 _, u7 {6 w4 }5 ~/ x7 B4 I
# |+ R9 V; v5 ]3 Y( k    A：$ O( ^! w9 B( F
5 Q- l$ ?6 E% x& V6 ^$ ]9 J1 C
    第一步：收到加密信息c$ [  D* Y* Y2 p7 o) A2 p

) Z6 h  x! y8 c/ T    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。7 {$ [: h# J  v

7 i) I2 l: i! @" X) a    完成' A. A. H  w7 O: ^! ^

9 p2 E/ H4 u( i- C' `3 j" g8 j    安全性
8 H" y" b  E+ X/ ^  j2 ?% \0 X8 x4 w( F* d
    为什么RSA是不会被破解的呢？: j/ _& K. C  X& F

5 A3 \* t# G" T: Z( `' D    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。
5 k2 `7 \7 N2 g, }8 f- p: a  U! l( l% p" _- P$ f# L
    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：
* ^/ ]1 y/ E5 A+ h& y7 f' F7 Q( [: i& F1 F" y1 v- {7 ~, m; ~. b
    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。
9 }2 [; ?, k- Z- y
1 t3 [) g9 {& Z* z    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。$ m# ?/ z: }/ h
7 |9 N3 e8 Y  ]6 p6 e8 ?. E1 I
    到目前为止，关于RSA可靠性的描述：
% B2 Q5 P' Z+ D% w1 y' C7 l5 X
; m2 Z( t/ o% j; K    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
% G0 E# G& J8 G4 ]" J6 K: z0 k0 k* N& W5 p0 \; a
    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。! V" v) `- ?6 I. H4 X: }
5 T& o# Y% a7 E/ ]$ z; n! C
    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。
# e8 Q+ Q! t. S" ^1 k: q3 G2 I4 Y. V' Q' Y+ s0 |
    RSA的正确性：+ u; a+ c/ G) }& g

' d7 i1 Y) n, {; F0 c3 V# K# f; P: J    可以使用欧拉函数和欧拉定理来证明。
7 i2 c1 |, |! W* W8 D7 j. t1 Q- X& y# o5 y' [: c. Y
    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）- ]9 C  p) {. u: ]8 v
5 d* l7 [$ h5 S
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m! C) c& V4 Z' ~8 n8 \
  B4 k/ a5 o3 ]* d1 Z% |' c
    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？3 X0 [7 r: [4 c4 q8 r
; W- P: G2 s, B2 B5 W
    应用8 Q5 _0 m( i) S# A! z

, ~2 K: p, {9 c    RSA的应用：数字签名
8 O" e4 {; x% O
0 j+ ^5 d6 [2 E3 d# d    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。: V( o' F8 G0 Y; ~7 X- r
$ Z# M& N! F9 i9 T( `
    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。' `' j% m& }3 T3 P3 \# o
$ ^) P1 o2 [. V5 I2 f
    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。