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

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

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

更新历史

写些什么

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

一些写作习惯：

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

素数在密码学中非常重要。素数是大于 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

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

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

先介绍 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 的素数，那么拉格朗日符号的含义如下：

雅可比符号是拉格朗日符号的一般形式，对于任意整数 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(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