1. 公钥加密的可能性－－数论的基本知识
    1. 整数和除法
    2. 同余运算
    3. 中国剩余定理
    4. 素数和最大公约数
    5. 费马小定理
  2. 公钥加密的实现－－RSA算法
    1. 生成大素数
    2. 素数检测
    3. 使用扩展辗转相除法求e*d mod m = 1
    4. 求同余幂
  3. 公钥加密算法的应用－－HTTPS
    1. Diffie-Hellman密钥交换
    2. 中间人攻击
    3. 数字签名


整数和除法
a ／ b ＝ c
a / b = c 余 d， a mod b = d

同余运算
如果a mod m == b mod m， 则a和b同余m，记作a ≡ b mod m
同余运算具有线性的性质：
如果a ≡ b mod m, c ≡ d mod m,则：
a+c ≡ b+d mod m
a*c ≡ b*d mod m

a ≡ (a mod m ) mod m
b ≡ (b mod m ) mod m

a + b ≡ (a mod m ) + (b mod m) mod m
a*b ≡ (a mod m) * (b mod m) mod m

中国剩余定理（孙子定理）
《孙子算经》里有一道题：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

相当于求解一个一元线性同余方程组：
    1. x ≡ 2 mod 3
    2. x ≡ 3 mod 5
    3. x ≡ 2 mod 7

把后面的模数记为m1, m2, m3，中国剩余定理说明如果m1、m2、m3两两互质，该方程在0到m1*m2*m3-1之间有唯一解x，其他解和x同余于m1*m2*m3

a+5n ≡ a mod 5
找出一个5的倍数y1满足方程1， 在找出一个3的倍数y2满足方程2，那么y1+y2就同时满足两个方程


35*t1 ≡ 2 mod 3
21*t2 ≡ 3 mod 5
15*t3 ≡ 2 mod 7

问题变成求解三个一元线性同余方程
35x ≡ 2 mod 3


素数和最大公约数
如果一个整数p仅有的正因子是1和p本身，则称p为素数。
能同时整除两个数a和b的最大整数称为a和b的最大公约数。

如果两个数的最大公约数为1，则称他们互质。
如果a和b互质并且a和c互质，则a和b＊c互质。

可以通过辗转相除法（欧几里得算法）求最大公约数。

最大公约数有一个推论，如果a和b的最大公约数为c，则存在x和y使得ax + by = c
如果两个数互质，则存在x和y使得ax+by = 1


知道16和21 互质，怎么求x和y？
通过扩展的辗转相除法求ax＋by ＝ 1
21 ＝ 1*16 + 5
16 = 3*5 + 1

1 = 16 - 3*5
5 = 21 - 1*16
1 = 16 - 3*(21 - 1*16)
4*16 - 3*21 = 1
x= 4, y = -3


35x ≡ 2 mod 3
可以先求35模3的逆 x （如果a*b ≡1 mod m ,b就叫做a模m的逆）
35x ≡ 1 mod 3
因为3和5互质，3和7互质，所以3和35互质，所以一定存在35x+3y=1
35x + 3y mod 3 = 1 mod 3

35*2 - 3*23 = 1
35*2 ≡ 1 mod 3
35*2*2 ≡ 2 mod 3

35*2*2 + 21*1*3 + 15*1*2 = 140+63+30 = 233
233 ≡ 23 mod 105

由三个余数可以确定0到104之间的唯一的数，0到105之间的一个数可以由他除以3，除以5，和除以7的余数表示。



费马小定理：假如a是一个整数，p是一个质数，那么a^p - a 是p的倍数，可以表示为
a^p \equiv a \pmod{p}

如果a不是p的倍数，这个定理也可以写成
a^{p-1} \equiv 1 \pmod{p}


费马小定理的等价表述：如果p是一个质数的话，对于任意一个数a，随着i的增加a的i次方除以p的余数将呈现出p－1的周期性

i
1
2
3
4
5
6
7
8
9
3^i
3
9
27
81
243
729
2187
6561
19683
3^i mod 7
3
2
6
4
5
1
3
2
6


那么对于一个合数n来说，这个周期又会是什么样？
假设n＝35 ＝ 5＊7 ，中国剩余定理表明一个数除以35的余数可以由它除以5和除以7的余数来表示。

3^i mod 5 随着i的增长呈5-1=4的周期
3^i mod 7 随着i的增长呈7-1=6的周期
（3^i mod 5, 3^i mod 7）呈现4x6 ＝ 24的周期
a, a^25, a^49…a^241, 2^265 都同余于35

265 = 5 * 53
随便想一个不超过35的数，比如11，告诉我11^5 mod 35的余数 16,通过求
16^53 mod 35就可以还原出原来的数11

基于大数分解难的前提，找出两个大的质数p和q，计算n ＝ p* q, 求出m=（p-1）(q-1)
找出e和d使得 e*d mod m = 1
(e,n)做为用来加密的公钥，（d,n）做为用来解密的私钥。
M = C^e mod n
C = M^d mod n

RSA算法实现

Diffie-Hellman密钥交换
Alice:
23 233 2333
233^23 mod 2333 = 793

Bob:
233 2333 793
233^32 mod 2333 = 418

Bob: 793^32 mod 2333 = 1957
Alice: 418^23 mod 2333 = 1957

中间人攻击

数字签名
signature = encrypt(hash(msg), private_key)
msg, signature
msg, hash(msg) == decrypt(signature, public_key)



HTTPS相比于HTTP的三个优点：
  1. 服务器验证
  2. 数据加密
  3. 验证数据一致性

HTTPS的工作流程：
  1. 客户端服务器握手，验证服务器证书
  2. 交换加密密钥
  3. 生成和传输加密数据

数字证书认证机构 （Certificate Authority）
浏览器信任CA， CA验证服务器证书（证书包含服务器公钥）

使用RSA（不满足Perfect Forward Secrecy）或者Diffie-Hellman交换加密使用的对称密钥

发送数据包时带上消息验证码（MAC），keyed hash functions