简介
& t' _  O; e1 P& X' [  L
" k# Q; v" u( c$ H2 H$ \( b2 ?    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。
6 q# e. R8 `+ a; k5 E3 F+ B: g( a. `  X3 a& ?  `; F
    具体是利用了：/ M/ ~* C1 }, B' k, L

$ E# u7 F( p  Q8 P/ H    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。
. B- Q* q3 x7 e4 p5 ]6 P4 r
+ D$ }# ^! c, A7 F; m  y/ o  H) R    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。4 M2 f6 ]8 z' q8 C2 ]  q
3 s9 r: z3 k- l' T
    原理* d7 Y7 a+ ]8 u4 P0 @

+ Y5 Z5 M, w$ @! d/ G$ R    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。
: I0 A- M$ p* Z: @" Z# ~2 D$ s! \8 ]" A" ~  t
    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。6 g5 }1 J) h: w& f

, o* j2 Z1 R# t: u3 ^8 P' h- a    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。* D" [8 w5 {6 ?' t0 S( m
7 q2 A& w) W) {
    解密过程：(c^d)modn=m，其中d为解密密钥。
: s$ n$ p# V/ N  V  c* i$ J2 |4 Z2 }' _+ A) W0 Z( S, R
    解密密钥d的求解：
( l# C( D8 j' \! C) ?" Y& Y3 t. F
! W. D8 t, d( Y0 E# U( ]    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn4 a9 p  C( j' |# }8 ^4 B9 E+ x

1 A; O+ [" Q+ _    费马定理：, Z3 u! \$ I+ _
8 a2 f" T' n& `0 }$ {
    若p是素数，a与p互素，则a^(p-1）≡1（modp）
+ L% n9 l- i2 f& b7 l: a
* a/ N( x0 K7 p) c    举例2 M4 c- r6 ]0 ^' z
: U( _$ K: y! C8 ]# a% z$ u
    加密过程举例（1）：
& w5 ^! E* T' L, I( K6 H, [9 k! R8 j$ }1 z" B
    1.挑选两个质数，如p=61和q=539 ]# ]% f: V. B+ N6 k
& A$ t7 y8 Z! @4 [1 b/ \
    2.计算N=p*q=3233
; y. a) h" V+ E# F$ ]. U/ t: R7 ]# a5 q( w3 v
    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】
  D8 ~( u. u8 f. ?" Q9 d" o9 b3 y' f; T) u: A: e, p
    4.选择与3120互质的一个数e=175 t! p4 g" S9 F/ D
" u3 Q! n" ~% n$ s- s
    5.计算得出d，使得d是e关于3120的模逆，得出d=27538 P9 X5 z  }9 r3 }
6 X2 J; B- w" @/ U; r) [
    6.如果明文是5，那么密文是5^17(mod3233)=3086" \6 a1 Y: @# b  }# F* b
  E4 ?7 l# |- ~! @$ t4 D7 D
    7.解密，3086^2753(mod3233)=5$ Z0 ?7 g. n  i  O/ f

9 r' f  P9 M. |4 t    关于模逆：先用“辗转相除法”…6 L2 N& n$ L" ]3 w6 o, L( U
# I2 c( ?4 h( q! L! |
    加密过程举例（2）-中间人：5 G% T) g- t" A7 {6 j3 s6 @

# z) |# w  _4 v% A8 ]( Q" e% x    A：有一个公钥n、e。例如：3127、3。9 K1 E$ ?' h" W2 b! @0 j! Z

" |5 f/ a  e; ?; F2 s7 ]    B：有一个信息m。例如：89。. Y  n7 ~8 d$ a- B
9 p! m$ ?% `+ z3 r" B
    C：偷听者
* ?' X6 ~3 P* [0 m
: F" c! f* c1 e9 r6 q& d    A：
' R7 \3 N& M) n: d8 @  i0 m2 L9 l3 ]/ P
    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。7 }  B; b5 N! v+ q2 R0 o

2 f: U" d9 R0 B* C    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。
& c4 H- @4 J# ?2 F; J; G
* {/ p6 Q; F5 M- H. H, w- Y9 z    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。
+ C( S  d$ p( t
% i. g" J5 y+ D    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。
: b# }9 i  F( z
6 t. R8 d2 c- \  t7 s    C：获得n、e& e5 n4 F! c" v4 `  n" m5 y) U

1 }# d, V7 G9 F4 o  Y: j    B：$ e' [, u6 {' u5 v
, q2 _3 |+ O- l; S5 @. d1 I, h
    第一步：获得n、e; Z# X# O$ D# g( T

2 G" L0 p4 j# y: H) R- P    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。# |. Z" L' c* a

' R" S+ }9 b6 P+ b: @% @    第三步：发送c给A
4 ^& l) v9 B3 m5 }$ x! C# C! i  T9 a: V# {, [  }
    C：
# c( y/ [* ~4 g, d6 f+ B% _/ s! B* e& w0 B
    第一步：截获加密信息c0 m8 K+ O, {. J/ Q; h
$ }- L0 h; @# W1 \8 i- X7 X: Z! e
    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。
8 ^2 `3 g) Y% Y! A+ ?
9 t3 O! q! P8 N* s    A：
8 `4 a: W( l2 l7 y* ?+ ~2 \- I9 n: R; b
    第一步：收到加密信息c5 h$ k$ B3 C. ^& p! W8 L

( h! F+ |! J9 v. E    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。5 K. l: W% ~+ u7 y/ Z
1 K! `8 U3 {% u4 t
    完成( `: |0 ^0 o6 {6 f7 V2 R& _
" C7 G9 L2 K; ?+ R2 B. ]  g
    安全性
8 F! b/ d+ X1 f" b! b& y8 f
" M+ G* ^  I: l: Z    为什么RSA是不会被破解的呢？' M0 |1 u( u+ m4 _. B7 n4 S% v1 O

) Z9 L% ~0 f! U    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。5 s& H( w& c7 B3 P/ h
, N& L% `( @0 ?+ z  [& h8 d
    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：5 U) ?- v" b4 ?' I  `: U6 M( h
$ h7 f" U' i8 v) b, Y
    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。
4 v9 ]' _) A* T* `7 ^2 o! l3 [/ x# ^, |6 [
    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。
, g9 F2 W6 C: |: W: ~  X
: }/ b* H9 ?: n    到目前为止，关于RSA可靠性的描述：
6 }# B" o' |$ T0 s' M; |6 D1 {4 \  ]( y; j0 N) P
    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
- |  C" n  x" Y
# b: m  d9 \: g4 {  L& E# L, g3 u+ g    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。  o- J7 U9 d% a/ z; S/ A
( c! u2 O) g# t3 |# S9 ^
    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。5 m* I0 d0 a. v! H
  |8 Q# G; i/ I# ]
    RSA的正确性：) D; ]3 m/ ^1 ?, ]1 ?  b( q/ D; ^
6 M* D# q& r+ h9 g9 O  G9 s! K
    可以使用欧拉函数和欧拉定理来证明。: k. h, t  u6 a/ L4 {

* P& y" {+ `  w# H8 o. ~% Q5 `    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）0 c) H4 Q4 {4 c* K
) L9 Z: c: q) C9 P
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m0 g& L; ?% j' f- j

* m: D0 f2 m. ?, \  h/ }; ~! v, ~    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？6 c  [4 s! p& l% e/ Q1 @
. i  ^6 u& O- I0 t. u
    应用2 f' ~' M, p7 a: B" o# x% }

$ A9 `. r1 z* E  E( W8 U    RSA的应用：数字签名
- U1 Z9 A" T; C& W- d
: h2 u) M8 k. M* @$ v  a    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。) b0 Z$ n: m1 p  V/ j- H7 H
; M/ O, g- U' f' R3 }
    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。+ P! W) j$ g- v# R! q- L% L
+ U, x1 K7 `+ L' P/ }
    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。