简介
& U5 v/ ^: h& `# J, h2 N0 Y+ w
# Z& I& T. T' r# C+ O    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。, X; K8 U, N) `* B, M1 p( g
; D9 X+ l" d! D0 t3 `8 |
    具体是利用了：
7 o; t5 {- L9 r5 V2 d
3 A) f8 @, }( z+ e, {    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。
' F: k! l8 q3 p3 O: O( R6 b; t% W: S; `4 ^7 W+ T5 V/ ]+ X: l) X. a
    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。6 U( b8 x  r4 G; r' N0 {

2 \8 w5 ?* ]' z+ _    原理
& s# @: l" d" {# I8 N( q) m
: t4 r6 h' h: I    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。
, c8 P2 ^3 v# G5 @% d: x  X/ z# a# h4 ]9 }- Y+ _4 v
    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。* U( }& S+ C" y8 E3 C% {
& g" u  {  ?. c: b0 L6 ~
    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。% R7 ?2 E, F" d+ \$ K! \9 w

4 m) l/ V  j# B8 o    解密过程：(c^d)modn=m，其中d为解密密钥。" P$ N3 \2 b" y2 G- g! k% w

* r* a2 q0 z# l, a/ I7 p$ B+ ~    解密密钥d的求解：8 w& r! m( W6 \6 I6 r! r( P8 F
7 H1 m, J; a2 b" c3 J
    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn) }6 ~3 V0 a- M8 C2 T: J
- r7 B# b7 Q  J$ U" Q# U* I
    费马定理：0 ~8 I1 F) V1 Z; [

: x9 A- N* d% ~1 k    若p是素数，a与p互素，则a^(p-1）≡1（modp）
/ m# h# ~9 R& L7 j' k2 @, _; a% h- `6 W9 _9 z; Q; k8 C
    举例
1 y; `. t: s: v) u  k& T8 ]
/ Y$ ^6 Q) |0 y0 l! L3 J2 ~9 |) o    加密过程举例（1）：
; F( o( ~1 ^7 D
* d# b6 C! j" b7 m% p    1.挑选两个质数，如p=61和q=538 K  g/ y  n; a) Z

* l8 u/ s3 v0 W$ J+ [# D    2.计算N=p*q=32335 {( v( |$ O9 [2 q

# W4 S' j6 x8 S4 W' B3 n    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】
7 b/ R  t6 s) H1 @3 W
$ E; U, Y+ l/ [  r8 E) B$ U    4.选择与3120互质的一个数e=17
3 O5 `) z% b" s
- k: p( `( z) G; \$ c! K    5.计算得出d，使得d是e关于3120的模逆，得出d=2753# ]) D, D1 _' e, g4 m
4 d5 s% p; V/ S
    6.如果明文是5，那么密文是5^17(mod3233)=30869 ]8 i+ Z- B5 y- Y  e: S/ _, g

# a: h6 @$ H! L0 W    7.解密，3086^2753(mod3233)=5& C, T# V# v9 G

" w3 ?8 f  E5 e% O' G    关于模逆：先用“辗转相除法”…
1 X  g- Y% T) A* [: f2 g! K+ W5 |* O, Z' j3 ?) _
    加密过程举例（2）-中间人：% w: k4 `' F( r

& {( `6 W/ b! L1 b1 ~* ]. S    A：有一个公钥n、e。例如：3127、3。0 K& e7 @' ~9 c; `: b
' c) _9 i9 E& Q6 T6 ^$ V0 v& ^
    B：有一个信息m。例如：89。: v5 L: Y. ^0 |
; Y! l7 b  C  M) z  k+ \. S' `, J9 a
    C：偷听者% [9 R& F3 k  p
" ~  V) Q2 B' Q. Z
    A：8 Q  }- n$ ?2 y
+ G3 l! e2 i8 F, L, P9 d" |
    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。7 j/ r1 |9 u8 s1 S/ x

! D; a2 l6 _7 f5 ^% i    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。' D( V& O# W0 ~2 H  ?+ G3 b) a

- S$ r% c! I& W& [0 P. R+ i    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。% L+ Z, I; U7 [3 q
- b( ^" O4 e% w  ^2 T4 j* [5 c
    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。
' Y4 W2 o& ?' [) T& K0 U0 s/ n
) I5 z  Y% y% b& W+ ]    C：获得n、e
4 I8 O8 N+ ?% z. Y* G
; ?; f2 u6 U* L6 c- {% u6 o    B：
3 u1 c/ J* ^( Y
2 x3 _' l: X7 z4 l$ x" t1 L    第一步：获得n、e
  d' J- }+ R+ b: I) _
6 q: ~, U4 M3 T) _    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。
  F/ O" E. j+ b: w) R
* ~4 z$ H1 ?; p+ X/ _: p% i8 y    第三步：发送c给A  B% D3 i: V0 ~0 h
  Z2 ^! S% ?1 V( s4 J( K: o
    C：
3 i( k( S2 t* S& B; B( u$ j2 O5 B% z' v1 L: q, H8 A5 v
    第一步：截获加密信息c6 D) @9 ]& O/ D

4 _" h, p; U& p    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。0 Y4 u  |- ^4 ^( o& @! c9 l' T1 g
. G  L3 Y" W/ ?. W# Y3 ]& q3 v
    A：' Z$ l+ r3 y# w$ B1 V
# H9 i1 }" e3 A! N
    第一步：收到加密信息c
) t( s) _2 K+ g  n
) k# T& n5 _& [6 d3 |    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。
7 n" Q( J) \5 S3 l9 y$ t: c0 Z
2 B; p4 B2 ?% R3 o    完成
2 B7 F3 G6 r! C  j! s7 e, e, Q! X5 o8 D- f! ?$ H
    安全性: L/ ?9 b( W) l6 [8 a

0 ?% G% H, e: V- g! P" Y& S    为什么RSA是不会被破解的呢？7 u; P; j% d6 z. G

5 X+ B) i9 W0 L% W$ r6 E    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。: B+ N2 c  ]2 o- `' g( L7 g
! m- E% x* Q. [- N
    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：& x7 x2 O6 n; Q  p& \1 S' }, ~

4 t+ \7 ^% Z& P& W    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。
, O, i7 c* m! Y, `
# p% c- R. Y# F    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。
3 L. A) M  B9 b  P- w. v/ e, l6 G  k% M/ \5 K+ s
    到目前为止，关于RSA可靠性的描述：. N* P: C: s% u8 X

" ?  r! Z) T/ ?, Z* e% O# L# M    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
* X2 w8 H* y5 K, a  J" x8 p# `9 a! p- W7 n: d- r/ X
    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。$ B; g7 o- K5 u) S, L  t" [9 r7 X

2 n9 G: o: {1 j# ]7 B* L+ S    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。
1 J4 `7 r6 J* L" b
' }4 h1 [6 @( V/ e) d1 `# Y0 P2 B1 l& V    RSA的正确性：
1 p2 G8 u$ i% `7 r
2 o# ^2 u7 Q  ~' q8 C6 W    可以使用欧拉函数和欧拉定理来证明。3 o: j; r: X5 O: y! z0 t
" r% P7 I" z- J
    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）0 o; A+ {- _# K
" i- X! _- r4 Q0 T0 T1 A: S' W6 c
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m7 A, \  j: u% B2 v9 c

  a1 [/ Q- x, e* D    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？$ j$ E, B" H) B8 E& H
- f- N7 L0 f, u+ t7 M
    应用
. J% E  U* d8 g" k
. F) h, p, v5 Y; n! k    RSA的应用：数字签名
2 j' Y$ [0 l, h9 j4 Q  ~6 ?6 C8 z! o- K) J8 K% Z
    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。" H, I5 u; v0 ^/ U
$ j8 }  f* a$ Y& y
    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。
  J6 `' h! v1 m9 M$ q/ e, g# k
- B& x6 K, L" |% \5 {5 I" U    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。