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