【密码学与网络安全】00 课程概览

《密码学与网络安全》是经典的密码学课本，以自底向上的形式介绍密码学知识、网络安全攻防及案例研究。在数据隐私日益受到人们关注的今天，掌握一些密码学知识，是很有必要的。感兴趣的话，可以关注本系列。

注：本书的例子主要以 Java 为主，本系列会用其他语言实现。

更新历史

2021.04.29: 完成初稿

写些什么

对于经典教材的系列，以学习笔记为主，主要会写：

核心概念
更新部分过时的代码和描述
总结一些我个人学习过程中觉得有一些理解门槛的要点，帮助大家理解
在 Github 公开源码，包括作业部分

一些写作习惯：

对于专有名词，通通不翻译，请不要埋怨我中文夹英文
文章中贴出的代码很大概率是节选，但是会把完整的源代码放在 github 中，如果需要，自取
不钻牛角尖，如果是明确不推荐的写法，我会直接忽略（比如不推荐多个 Graph，非要用多个，不好意思，自己折腾谢谢）
静态博客不带评论，交流可以通过微博、邮件等等途径
非常感谢勘误，会在原文中注明，如果有不想列出名字的同学，也请顺带在勘误中告知
这个列表会随时根据我的心情增加，如果不喜欢，可以直接关掉页面，不需要告诉我

希望能在自己学习的过程中也帮助大家

文章索引

01 计算机攻击与计算机安全
02 密码技术
03 对称密钥算法与 AES
04 基于计算机的非对称密钥算法
05 公钥基础设施
06 Internet 安全协议
07 用户认证机制
08 加密与安全实现
09 网络安全、防火墙与 VPN

课程大纲

计算机攻击与计算机安全
密码技术
对称密钥算法与 AES
基于计算机的非对称密钥算法
公钥基础设施
Internet 安全协议
用户认证机制
加密与安全实现
网络安全、防火墙与 VPN

背景知识

素数 Prime Number

素数在密码学中非常重要。素数是大于 1 的正整数，且只有 1 和本身是它的因子。也就是说，素数只能被 1 和本身整除。公钥加密就是基于素数理论的
两个数互质(relatively prime)就是没有除以 1 以外的公因子。如果 a 与 n 的最大公因子(Great Common Divisor, GCD) 为 1，则可以写成 gcd(a,n)=1
可以使用欧几里得算法计算两个数的最大公因子
求模运算(Modular arithmetic)的原理很简单，模是整除的余数。一般来说，对于整数 K，如果 a = b + kn，则 $a\equiv b(mod\ n)$ ，加密算法经常使用求模运算
求模指数是加密算法中使用的单向函数，很容易解。例如，对于 $a^x(mod\ n)$ ，已知 a, x, n 的值很容易求解。但是反过来则是求一个数的离散对数，是相当困难的，例如求 x，使得 $a^x\equiv b(mod\ n)$ ，对于大数来说，这个方程很难解。
测试素数：如果 P 是奇素数，则方程 $x^2\equiv 1(mod\ p)$ 只有两个解， $x\equiv 1$ 和 $x\equiv -1$
素数的平方根模：如果 n 是两个素数的积，则求 n 的模的平方根与求 n 的因子是等价的，如果知道 n 的质因子，则很容易求出 mod n 的平方根
平方余数：如果 P 是素数，0 < a < p，则 a 是 mod p 的平方余数的条件为，对某些 x 有： $x^2\equiv a(mod\ p)$

注：本部分的代码请参考 prime.go

费尔马定理 Fermat's Theorem

如果 p 是素数，而 a 是不能被 p 整除的正整数，则 $a^{p-1}\equiv 1(mod\ p)$

该定理的另一种表示形式是，如果 p 是素数，a 是任意正整数，则 $a^p\equiv a\ mod\ p$

欧拉定理 Euler's Theorem

先介绍 Euler-Toient 函数，记为 $\phi(n)$ ，其中 $\phi(n)$ 是个正整数，指的是小于 n 且与 n 互质的个数。例如 n=6 时，比 6 小且和 6 互质的只有 1 和 5，所以 $\phi(n)=2$ ，一般来说，对于素数 $\phi(n)=n-1$ 。

此外，假设 q 和 p 是两个素数，对于 n=pq ，可以得到 $\phi(n)=\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$

根据这个结果，欧拉定理指出，对于每个互质的 a 与 n，可以得到 $a\phi(n)\equiv 1(mod\ n)$

中国剩余定理

如果某个数小于两个素数的乘积，那么这个数可以唯一地用对这些素数取模的余数来表示。

对于任意 a < p 和 b < q，其中 p 和 q 互质，一定有唯一的 x 使得 $x < pq$ 和 $x\equiv a\ mod\ p$ 且 $x \equiv b\ mod\ q$

拉格朗日符号

如果 a 是任意整数，p 是大于 2 的素数，那么拉格朗日符号的含义如下：

L(a, p)=0，a 被 p 整除
L(a, p)=1，a 是用 p 求模的平方余数
L(a, p)= -1，a 不是用 p 求模的平方余数

雅可比符号

雅可比符号是拉格朗日符号的一般形式，对于任意整数 a 和奇数 n，有如下性质

J(a, n) 仅当 n 为奇数时有值
J(0, n) = 0
J(a, n) = 0，n 为素数，且被 a 整除
J(a, n) = 1，n 为素数，且 a 是用 n 求模的平方余数
J(a, n) = -1，n 为素数，且 a 不是用 n 求模的平方余数

哈赛定理

如果 n 是椭圆曲线上的点数，则 $p+1-2\sqrt p < N < p+1+2\sqrt p$

平方互换定理

如果 p 与 q 是不同素数，则下列同余式都可解或不可解，除非 p 与 q 除以 4 的余数为 3：

$x^2 \equiv q(mod\ p)$ 和 $x^2 \equiv p(mod\ q)$

信息理论

信息量(amount of information)：编码消息的所有含义所需的最小位数，假设所有含义的发生概率相同
完美秘密(perfect secrecy)：加密系统中如果密文绝对不含明文信息（除了长度）。这要求可能的密钥个数大于或等于可能的消息个数，即密钥不必消息短，没有复用密钥
Unicity 距离是密文的近似量，使相应文本中的实际信息（熵）和加上加密密钥的熵等于使用的密文位数。此外，长度超过这个距离的密文一定只能解密为一个明文。另一方面，长度小于这个距离的密文通常具有多个同样有效的解密结果。因此，这样更加安全，密码分析员要从中选择正确的结果。

重要 RFC 文档

RFC(Request For Comment)是关于某种技术或协议的正式说明规范。原文可以访问 www.ietf.org 获得

RFC-1847：用于 MIME 的多方安全：多方签名与多方加密
RFC-1958：Internet 的体系原则
RFC-2268：关于 RC2(r) 加密算法的描述
RFC-2311：S/MIME 消息描述，第 2 版
RFC-2315：PKCS#7：加密消息语法，第 1.5 版
RFC-2409：Internet 密钥交换(Internet Key Exchange, IKE)
RFC-2437：PKCS#1：RSA 加密说明规范
RFC-2459：Internet X.509 公钥基础设施认证与 CRL 文档
RFC-2510：Internet X.509 公钥基础设施认证管理协议
RFC-2511：Internet X.509 认证请求消息格式
RFC-2527：Internet X.509 公钥基础设施认证策略与证书实行框架
RFC-2560：Internet X.509 公钥基础设施在线认证状态协议(Online Certificate Status Protocol, OCSP)
RFC-2587：Internet X.509 公钥基础设施 LDAPv2 方案
RFC-2630：加密消息语法
RFC-2712：往传输层安全增加 Kerboros 加密套件
RFC-2807：XML 签名需求
RFC-2817：在 HTTP/1.1 内更新到 TLS
RFC-2818：HTTP-Over TLS