简介
/ N. c" y: A! @# c/ X
: B1 l6 O6 ?# L: B' Z    1977年，MIT的三位老师Rivest、Shamir和Adleman设计了一种算法，可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单，反向求解很复杂的特性。. b% W/ e8 k/ R; d& j' p# R: v  d+ @

4 ?. d, m) ~. z3 e' w    具体是利用了：* j% \7 q. d3 W  A
/ A+ G* q- Y- h+ y( a
    1.对两个质数相乘容易，而将其合数分解很难。即n=p1*p2，已知p1、p2求n简单，已知n求p1、p2困难。" d8 K: ~) w* W; p! O0 o$ w  i$ M  q

. B: U) b' D, J# A' k: @7 n    2.(m^e)modn=c，已知m、e、n求c简单，已知e、n、c求m很难。
( H' l3 B: C" X9 O; `  ]! }4 `3 ^2 C9 F
    原理
" H9 X3 L+ ~( w$ t. `% W: ]2 |6 k1 x: \/ u
    RSA加密，实现了公开密钥，就是A可以给所有人发送公钥，其他人把要加密的信息用这把公钥加密后发送给A，A用私钥解密就可以获得加密的信息了。反过来，A要发送加密信息给B，只要知道B的公钥就可以了，而这个公钥是公开的。
0 w, S2 G+ g/ k1 R& R5 F8 n9 Z3 d5 t' }4 W/ H! e+ Z4 ~
    公钥n、e的生成：随机选取两个质数p1、p2，n=p1*p2，再随机选取一个整数e，e与φ(n)互质。, t& [! ]+ z0 w* {
& [# Q2 \- ^# _# R  N
    加密过程：(m^e)modn=c，其中m为原信息，c为密文，n、e为公钥。) x; R$ k" F! J; d

0 z+ D. D  ^+ Y8 M7 B3 d3 k5 l4 E    解密过程：(c^d)modn=m，其中d为解密密钥。5 b$ t! N& _: I' a
: }( g8 E) m# K' }
    解密密钥d的求解：
, X9 Q& z# ^7 x, Y, {
% R$ M; d/ }# n$ K% C    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn
# Q( c  U: e5 }3 u9 F% M5 N; m
' U* X$ R7 y9 V: O. N    费马定理：# ~5 x" J" O7 q7 p! Q' w

1 U, ~+ g& S% Z% o+ @, j% U' n0 n    若p是素数，a与p互素，则a^(p-1）≡1（modp）
) N8 ]8 ^& t& h' L& }9 R0 h+ R+ m, v3 Y+ a3 [
    举例
) |2 k+ N0 n! k# T9 K3 e; i  R! ?6 o4 f6 k" C3 O3 M0 k
    加密过程举例（1）：
* o7 r9 Q4 D- z/ }  K( J
% q8 x9 Z6 K  T% E! c2 o    1.挑选两个质数，如p=61和q=536 V  q: t8 D" ?/ z3 F4 ^9 R
5 j% V; f+ m# E4 x
    2.计算N=p*q=3233
: }; |8 Q7 b  [# F
6 N1 K. k( o( O- r1 n    3.计算（p-1）(q-1)=60*52=3120【这一步可以计算（p-1）和（q-1）的最小公倍数，从而使得计算的d比较小；17关于780的模逆是413，比2753要小】
( D) B  {9 v& s% p+ G
# m) T6 N+ `) a! X    4.选择与3120互质的一个数e=17
4 I4 q. b2 G; ]1 p8 d* {$ a8 W% Y$ K
3 Z! R, w! G$ J  k( v# G    5.计算得出d，使得d是e关于3120的模逆，得出d=2753
' I# A, p' p7 Q* ]
  A+ x& [: i5 r' @& \* z    6.如果明文是5，那么密文是5^17(mod3233)=3086* z5 v; w1 \( I
! N. ^8 e1 O/ G$ s
    7.解密，3086^2753(mod3233)=5& x9 m: e6 _) ]
7 U% ^  i( E& W# H) I* W( d
    关于模逆：先用“辗转相除法”…
+ e- s7 w8 s/ g6 q6 g3 }# P: L  c  r. V5 J
    加密过程举例（2）-中间人：
+ u% P. f- W8 V/ o4 ^. R4 }8 C& k6 X/ o* \: m4 Q' a+ D
    A：有一个公钥n、e。例如：3127、3。
- Z( K* Q4 C3 n! [& k. ^1 l2 @8 q( J' x6 S2 t% \
    B：有一个信息m。例如：89。: P/ q' G, s% Z4 {9 L

7 J* Z- z, U4 @* ]: n; {4 n  d    C：偷听者% s* I, o4 i' m7 @8 S9 q
4 D3 B7 n4 \4 P$ U, A
    A：
! H  W4 \; G, }7 M) F% T0 a4 v) q" _3 s
    第一步：随机找两个质数p1、p2，一个奇数e。例如：53、59、3。
0 u6 l% A. T0 B' ]) w  H3 e' A  M1 ~+ `
9 `2 c% d; E" p    第二步：计算n=p1*p2得到n，计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n)，计算钥匙d=(k*φ(n)+1)/e得到d。
6 M# u$ D  y, W. ?; n# l/ `9 K7 d  F( I  k: o1 q; _2 q
    例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。" c2 a4 K, ]% H0 T# N

) w1 ~/ b+ s# z" w% j+ U3 r    第三步：发送n、e给大家知道//n、e就是公钥，d就是密钥。
. s: S- l! K- q8 Z. r. y! T2 T! A- L  c- J" [4 w
    C：获得n、e
- o  w7 m% Q' ]/ e* J0 Q  ?( m3 j; k, m0 i4 r  N# x
    B：' B8 `' s  S" O& q/ W! S" N
6 c8 S0 x) ^- k; y7 u3 ?% u" m
    第一步：获得n、e: q; h$ t  j$ I4 z# k& H1 ^
5 Q) x8 V4 B: _+ D+ m
    第二步：加密信息m，(m^e)modn=c，获得加密信息c。例如：(89^3)mod3127=1394。
' G( m4 J: A5 d1 q8 q; Q7 q2 d( i2 d; k$ i
    第三步：发送c给A5 T0 L6 V' N7 N
  @' k, i% F! o8 n! \, W0 Q
    C：
7 j5 R$ {0 `6 Q+ m( d+ o" ~7 l: X) }% Z2 c, }$ f1 s
    第一步：截获加密信息c
; d" p9 ^& ?' L* p$ L
* t% H$ {: j5 [% B" q1 ]6 T    第二步：破解信息c，此时C只有n、e、c，只有把n分解质因数才能破解，而此分解很困难特别是当n很大的时候。* ?1 T5 G- {( b9 i, G5 T1 ^. w2 C
- T/ ?) N5 x) D
    A：0 {- d6 u* ?( q- W+ b* X& }7 y

( y3 z! E, z) [6 W" y3 S    第一步：收到加密信息c
' ?- L1 \! C. i  n! \  U
6 E* F( G( P/ `; v7 j+ C    第二步：解密信息c，(c^d)modn=m，获得信息m。例如：(1394^2011)mod3127=89。
2 ^7 D7 s: ~( U1 x; _. v5 M
4 C) a+ b% c1 V; z: G    完成3 E* `4 J; Z; z( Y0 u5 u$ @
3 T$ D1 _/ ^& J! c8 \; W
    安全性
7 @  }* `8 \# X3 O! p
- ?2 r5 T+ _4 R! t6 }8 o    为什么RSA是不会被破解的呢？
! ]$ s3 Y) t, f" ?# }  a  v+ L8 k/ X. a
    为了解密，关键是要找出私钥。如果已知（p-1）(q-1)，那么就很容易算出来私钥。而为了获得（p-1）(q-1)，就需要知道p和q的值。为了获得p和q的值，就必须对N进行因式分解。
. |' z% ~) _0 M, b0 A0 g
8 O' w6 l, Z0 K8 g    1874年，WilliamStanleyJevons就在自己的书《科学的原则》中写道：/ |( L& M9 V! M" v1 Y: v. [' c

! r% E" w& C, V* N    读者中有人能发现是哪两个数的乘积为8616460799吗？我想这个答案只有我自己知道。. A6 v9 R0 W  ]; O( N
7 Z1 ^% D9 x$ l' F! X# i
    书中他描述了单向函数（one-wayfunction）与密码学的关系，还提出了因子分解问题可以用作创建trapdoor函数。" ~: z8 x0 G) r* D' }

, o7 c$ m+ e; \8 F0 t6 v2 R    到目前为止，关于RSA可靠性的描述：
( B5 V/ i2 d* L- _1 f" z4 ]! `: x1 \/ N- l' k
    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
" h! M! L% a: z5 Y2 }2 U- ?- f* n. ?% a- I, T  j6 c0 {- @9 {
    假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
0 t0 {7 ?, v& C* F$ f  P' Z  `6 i/ u. a; B3 P6 U
    只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。
* p! D+ s) x! i5 Y) f* x/ F! E: v8 _) S" ?; E6 G. y
    RSA的正确性：+ m9 D" b' s" \2 u; d% k
5 F6 G1 t  |) Z
    可以使用欧拉函数和欧拉定理来证明。
8 h7 L4 d; y7 c) _3 h4 Q# T6 l* L' a; F, ~! L- K* o8 v
    （这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。）
2 B" @! e9 d! }  E3 \9 S  a. S" O% u) O% X4 W! Z  R
    如果m和n不互质，因为n是两个质数p和q的乘积，所以m必然是p或q的倍数（因为要求m
, J7 m* A3 {; [) c: X  t8 [8 @3 p' T9 L4 z& f
    那么问题来了，如果黎曼猜想真的被证明了，那么RSA算法的可靠性是否会成空中楼阁呢？/ L, L  W; S7 u' d2 ?8 E
5 z4 l' X6 G7 M2 j
    应用9 t8 u; I+ n3 o- T3 Z7 {' x

( l8 K, R3 a! `5 D8 w    RSA的应用：数字签名5 ^. o, x. k3 d) ^3 s8 Z0 w$ ]- [

& `; w* D+ l# B4 A! |' I/ a    最普遍的应用，网站身份认证。如何证明我们连上的网站就是支付宝alipay呢？如果因为各种原因，如域名污染，我们的浏览器访问了攻击者网站，这时一定要进行验证。7 S. n" R6 B" I( r$ g# c3 s: ~' m

: ]( [5 e7 Q/ f8 x6 p    验证，就是要检查一个证书。当我们以HTTPS的方式连上一个网站时，网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后，首先用第三方公信机构CA的公钥对这个证书解密，然后查看和比对证书里的域名和浏览器地址栏的域名，完全匹配才认为是正确的网站。! L$ H6 a5 _  d) @. v

+ w4 d9 X& R" D; ~/ V. ]    如果域名被污染，虽然攻击者网站可以拷贝一份正常网站的证书，但是因为证书中包括了正常网站的公钥，如果它不能获得正常网站的私钥，那么它就没有办法对加密信息进行解密。从而不能正常建立连接。