一些概念

密码学要解决的问题

• 保密性 Confidentiality
• 完整性 Integrity
• 可用性 Availability

历史上的密码学

• 羊皮传书
• 藏头诗（实际上是一种隐写术）
• Caesar

密码系统的组成

• 明文 Plaintext
• 密文 Ciphertext
• 密钥 key
• 加密算法 encipher
• 解密算法 decipher

分类1:根据明文变成密文的变换方法分类

分类2:根据 key 数量

• 对称密码
  • 对称密码的一些说明：
  • 密码学假定信道本身不安全，而密钥应当双方都知道
  • 因此通信之前双方需要在某个安全通道传输密码 key
• 非对称密码
  • RSA：基于整数分解
  • DSA：基于离散对数问题
  • ECC：基于椭圆曲线
  • NTRU：基于格理论，抗量子
  • Rainbow：基于多变量多项式，用于数字签名

分类3:根据明文处理方式，对称密码还分为：

密码编码学（Cryptography）：研究如何做密码编码

密码分析学（Cryptanalysis），是破解密码的研究，是对密码攻击

• 所用的方法：
  • 经典密码分析（Classical Cryptanalysis）
    • 数学分析法：发现加密方法内部结构的分析攻击
    • 暴力破解：测试所有可能的密钥进行破解
  • 实施攻击(Implementation Attack)
    • 从旁道分析，如：测量处理私钥的处理器的功耗、电磁辐射、算法运行时的行为。前提是攻击者可以物理访问密码体制。
  • 社会工程攻击。行贿、勒索、跟踪或侦探
• 密码分析面临的情况
  • 仅知密文攻击（Ciphertext - only attack）。仅能获取到一些密文，尝试推导出明文或者密钥
  • 已知明文攻击（Known - Plaintext attack）。除了拥有一定数量的密文外，还知道与之对应的明文。
  • 选择明文攻击（Chosen - Plaintext attack）。可以任意选择明文，并获取对应的密文
  • 密文攻击（Chosen - Ciphertext attack）。攻击者可以选择特定的密文，并获取这些密文对应的明文
• 密码学（Cryptology）：就是密码编码学+密码分析学。

Kerckhoffs 原则：一个密码系统安全，不依赖算法的保密性，只依赖密钥的保密性。

• 否则一旦算法泄漏（很容易），整个密码系统就完蛋
• 公开算法，使得其受到广泛审查。假定某个人找到了密码系统的漏洞，对其最有利的做法是发论文，否则会被别人抢先。
• 公开算法，使公众可以信任它，而不是依赖测试机构的权威
• 密钥易于更换，算法不易更换

密码协议：利用密码学实现安全通信的一系列规则和步骤。例如 SSL、SSH、OAuth

密码安全

• 无条件安全：在攻击者拥有无限算力的情况下，一个密码体制也是安全的，叫做 无条件安全。密码学基本不研究这个。
• 计算安全：为了破解一个密码体制，最好的已知算法至少需要 t 个操作，叫做计算安全
  • 破解所需时间超过信息本身的有效期，或者破解的成本高于信息本身的价值
  • 存在问题：如 RSA 基于大整数因式分解，尽管因式分解算法是已知的，但我们不知道是否存在更好的因式分解算法。

数学基础

mod 与整数环

这个的系统组成一个环：

• $Z={0,1,2,…,m-1}$
• 定义两个运算符 $+, \cdot$
  • $a+b\equiv c \mod m$
  • $a\cdot b \equiv d \mod m$

性质

• 未必存在逆元（逆元定义为 $a\cdot a^{-1} \equiv 1 \mod m$）
• 当且仅当 $\gcd(a,m)=1$ 才存在逆元

替换密码

移位密码

凯撒密码（移位密码） 是一种最简单的替换密码，它把字母表向后移动 k 位，末尾放开头

• 算法（环的语言）：
  • 加密：$y\equiv x + k \mod 26$
  • 解密：$x\equiv y - k \mod 26$
• 移位密码的评价：
  • 移位密码的密钥只有 25 种，因此非常不安全。
  • 它是替换密码的一种，可以使用字母频率分析法攻击它

仿射密码，在移位密码的基础上做一些改变

• 算法：
  • 加密：$y \equiv a \cdot x + b \mod 26$
  • 解密：$x \equiv a^{-1} \cdot (y - b) \mod 26$
  • 密钥：$k = (a, b)$ ，其中 $gcd(a, 26)=1$
• 仿射密码的评价：
  • a 可能取值为 1，3，5，7，9，11，15，17，19，21，23，25
  • b 可能取值为 26 个
  • 因此密钥空间为 12x26 = 312 ，也是非常不安全

单字母表密码 算法：

1. 维护一个字母对字母的一一映射表（这个表就是密钥）
2. 按照密钥做映射即可

攻击：

1. 表面上上不同的组合有 $26!$ 种，暴力遍历需要几百年
2. 实际上有一些高效的攻击手段
   • 字母的频率是稳定的。在密文中也如此，统计密文中的字母频率可以大致推断是什么字母
   • 类似的，连续密文也是可以统计，例如英语中，U总是跟着Q
   • 如果发现了空格，可以找到高频短单词，例如 THE、AND

Playfair

单字母加密很容易被频率分析破解，因此考虑多个字母一起加密

• 多对一：分组，一次加密一组。Playfair密码
  • 例如，构造的映射表是：8字母到8字母的映射
  • 攻击者的词表就是 $26^8$ 大小
  • 字母频率也不明显了
• 一对多（维吉尼亚密码）。明文中一个字母，可能映射为多个字母

Playfair cipher 用2个字母映射2个字母，

• 19世纪发明的，最初为了配合电报机使用。

Playfair cipher 的算法：

• 密钥
  • 共25个字母（规定ij不做区分）
  • 按照惯例，密钥通常是规定某本书某一页某一位置
  • 从这一位置起，开始提取字母（丢弃重复的），得到一个长度为 25 的字母排序。
  • 这25个字母，可以写成一个 5x5 的矩阵，这就是密钥
• 分组。对明文，每两个字母分一组。
  • 如果某组的两个一样，则填充最后一个为 X
  • 如果为奇数个，则最后一位填充（padding）X，（现代密码的常见方法）
  • 举例。Plaintext 是 ballons，分组为 ba lx on sx
• 加密规则（以下面的密码表为例）
  1. 如果双字母在同一行，则用右边的字母代替。AR -> RM
  2. 如果双字母在同一列，则用下面的字母代替。MU -> CM
  3. 如果双字母不在同一行也不在同一列，则用对角上的字母代替。HS -> BP，EA -> IM

Playfair 同样可被攻击

• 词表共 $26\times 26 = 676$ 个元素，用现代计算机，只要截获几百个单词就可以很快破解
• 改进：提高分组大小，例如 8个一组，词表就是 $26^8$ 大小

维吉尼亚密码 的思路是使映射关系不唯一。例如，一个字母有时候按照词表1映射，有时候按照词表2映射。

一个典型做法：

• 每个词表都是凯撒密码，
• 假设密码 KEY = DECEPTIVE，第一个字母按照 k='D' 的凯撒密码加密，第二个字母按照 k='E' 的凯撒密码加密

攻击方法

• 注意到维吉尼亚加密法，其 k 是有周期的
• 一旦知道key的长度，就很容易用字频分析
• 如何找到 key 的长度呢？在密文中找周期，周期的公约数可能就是 key 的长度（多试几次）

（这个例子是故意造了个容易找周期的情况）

改进思路：

• key 不再使用周期性的循环使用，而是使用已解出的明文作为新的密码
• 这就是 Autokey Cipher

攻击方法

• Plaintext 本身也用作 key，可惜它们都是有频率分布的
• 例如，字母 E 在 Plaintext 出现概率很高，因此在 key 中的出现概率也很高，因此 E 加密 E 的概率也很高
• 因此也可以用频率统计来攻击

综上，我们如何找一个合适的密码系统呢？核心思路就是 如何屏蔽掉统计规律。

Vernam 加密

特点：

• 加密函数和解密函数是同一个函数
• 计算性能高，只需要一个 XOR 操作
• 密码序列是一串随机数，由随机数生成器生成，但是比普通的随机数生成器要求不可预测（也就是根据已生成的随机数，不能预测未来的随机数）。

Vernam 加密（Vernam Cipher）基本单位是位（bit）。其算法是明文与密文逐位 XOR 运算

• $x_i, y_i, s_i \in { 0, 1 }$
• 加密：$y_i = x_i \oplus s_i$
• 解密：$x_i = y_i \oplus s_i$
• 特点：硬件/软件实现高效，适用于实时通信；安全性取决于密钥流的不可预测性。
  • 1918年 Vernam 提出并申请专利
  • 1949年 香农证明了 OTP 就是 无条件安全的（无条件安全的密码体制很难设计）
  • OTP在下面介绍
  • OTP 的缺点是密钥分发极为困难

一次一密(OTP,One-Time Pad) 是 Vernam 密码的一个特例：

• 密钥 长度 = 明文长度；
• 密钥 真随机；
• 密钥 只使用一次，之后立即废弃；
• 密钥 保密且双方共享。

据传言，在冷战期间白宫和克里姆林宫之间的红色电话就是使用 OTP 加密的。但没有大规模使用，它有缺陷：

1. 真随机数设备有成本
2. Alice 必须把 ${ s_i }$ 安全的传递到 Bob，比如写入到 CD，让一位特工做信使
3. ${ s_i }$ 用完后，还需要再次传递

基于移位寄存器的序列密码

接上文 OTP，想到用伪随机数生成器代替真随机数生成器，来生成 ${ s_i }$，这样密钥就是 seed，但这个想法是 不可行的，解释如下：

• 随机数生成器基于线性同余发生器：$S_0 = seed, S_{i+1}\equiv A S_i + B \mod m$
• 加密方式同 OTP
  • 加密：$y_i = x_i \oplus s_i$
  • 解密：$x_i = y_i \oplus s_i$

为什么这个方案是不可行的呢？

• 如果攻击者 Oscar 猜出部分明文（比如文件头信息更容易猜），那么立即结合密文可以计算出 ${ s_i }$
• 然后解方程 $S_2 \equiv A S_1 + B \mod m; S_3 \equiv A S_2 + B \mod m$，即可得到 $A,B$
• 根据 $\gcd(S_1-S_2,m)$ 取值，可以有多解或唯一解。然后根据其它分片可以唯一得到密钥

实际上相当多的伪随机数生成器都不是密码学安全的，我们需要专门设计伪随机数生成器：例如 线性移位寄存器（LFSR）

• 许多序列密钥是利用 LFSR 来实现的，例如 A5/1
• 构建方法很多，这里只介绍一种

LFSR 是用一个电路实现的，这个电路中有 m 个触发器，

例如，m =3 的情况下，LFSR 用数学描述是：

• 初始化 $s_0,s_1,s_2$
• $s_{i+3} \equiv s_{i+1} + s_i \mod 2$

性质：

• 当然，它是一个周期序列
• 它的周期是多少取决于 m 和初始化的值。一个 m 位的 LFSR，有 $2^m-1$ 种非零状态，因此它最大可能的周期为 $2^m-1$

如何攻击？

• 只要 Oscar 知道度为 m 的 LFSR 的 2m 个输出位，就可以列方程来解出参数
• 可以得到 m 个线性等式进而用高斯消元法来计算参数
• 然而，它并没有丧失所有密码属性。有不少序列密码都是使用多个LFSR 的组合构建强壮的密码体制。

Trivium 是一个较新的序列密码，它的密钥长度为 80 位。Trivium 基于三个移位寄存器的组合。然后在得到每个寄存器的输出时使用了非线性组件。

总体来说，许多序列密码的安全性都是未知的，而且很多已经被破解了。

置换密码

字母不变，打乱其顺序

简单的置换密码

Rail Fence密码 先横向写，然后纵向取，得到密文。

例如，一个深度为 k 的 Rail Fence，如下（代码比文字更容易说明）

plaintext = 'meetmeafterthetogapartyat8pm'
ciphertext = ''
k = 5

# （还需要padding，使其长度为 k 的整数倍）
for i in range(k):
    ciphertext += plaintext[i::k]

前面提到的羊皮传书就是一种 Rail Fence 密码

行置换密码

在 Rail Fence 的基础上添加一个规则：
纵向取的时候，按照 Key 规定的顺序取。

转子机：古典密码的最高峰

二战期间广泛使用，是一种乘积密码

Enigma 机为例

分组密码

强加密算法一般基于两种本原操作

• 混淆（Confusion）：使密钥和密文尽可能模糊
• 扩散（Diffusion）：一个明文符号影响多个密文符号

DES

• 对称密码
• 迭代算法，每个分组加密16轮

3DES:就是把3个DES连接起来

AES

特点

• 分组长度 128，密钥长度 128/192/256
• 设计简单、代码紧凑、运行速度快
• 可以在8位CPU上运行，需要4k存储空间
• 面向世界征集，最后获胜的是比利时的 Rijndael 算法

算法

• 代替-置换网络结构，每一轮有3层：线性混合层，非线性层，密钥加层
• 线性混合层作用是确保多轮后高度扩散
• 非线形层由16个S盒并置，起混淆作用。S盒使用 GF(2^8) 的乘法逆运算，其差分均匀性、线性偏差达到最佳

流密码

RC4、ChaCha20 等

非对称密码

对称密码的缺点

• 密钥分发：需要一个安全渠道分发密钥
• 没有不可否认性：只要知道密钥，就可以加密和解密
• 用户增多时，密钥数量膨胀。n个用户互相通信，需要两两密钥，就是 n(n-1)/2 个密钥。非对称密码需要 2n 个密钥（每人公私各1个）
• 非对称密码也有其缺点，就是速度较慢。一个用法是，用非对称密码来交换“对称密码的密钥”，然后用对称密码相互通信。

非对称密码的使用（A 发送给 B）

• Bob 的公钥是公开的（例如放在主页或公告板）
• Bob 的私钥是保密的，只有自己知道
• Alice 使用 Bob 的公钥加密，然后把密文传递给 Bob
• Bob 用自己的私钥解密，得到明文

公开密钥系统的 6个要素

• 明文 Plaintext
• 公开密钥（PK, Public Key）
• 私有密钥（SK, Secret Key）
• 加密算法 encipher
• 密文 Ciphertext
• 解密算法 decipher

公开密钥算法的基本要求（A 发送给 B）

• B 容易通过计算产生一对密钥（$PK_b$，$SK_b$）
• A 容易计算产生密文，$C = E_{PK_b}(M)$
• B 容易计算解密，得到解密后的明文，$M = D_{SK_b}(C) = D_{SK_b}(E_{PK_b}(M))$
• 敌对方即使知道 PK，要确定 SK，计算上不可行
• 敌对方即使知道 PK 和 Ciphertext，要确定 Plaintext，计算上不可行
• 密钥对相互可以交换使用 $M = D_{SK_b}(E_{PK_b}(M)) = D_{PK_b}(E_{SK_b}(M))$
  • 也就是说：用公钥加密的，可以用私钥解密；用私钥加密的，可以用公钥解密
  • 前者可以用来做 加密通信，后者可以用来做 数字签名
  • 上面提到的 容易计算、计算上不可行 是有严格定义的，是根据计算复杂度定义的。

签名的需求

• 身份的认证
• 抗抵赖

数字签名 （B 发送给 A）

• 过程
  • B 用自己的私钥加密，然后发送给 A
  • A 用 B 的公钥解密（验证签名的过程）
• 身份认证 A 用 B 得公钥把信息解密了，说明发送方只可能是 B
• 抗抵赖 A 可以用密文 + B 的公钥，找第三方裁决，很容易确定密文来自 B
• 对称密码系统无法解决这两个需求，因为 A 和 B 知道的信息一样多。

综上，非对称密码系统的使用场景：

• 加密通信。（对称密码也有这个功能）
• 交换密钥
• 数字签名
  • 身份认证
  • 抗抵赖

RSA

• 1977年Rivest, Shamir和Adleman提出
• 是一种分组加密算法
• 基于数论的论断：两个大素数相乘很容易，但是分解计算上不可能

RSA 密钥生成算法

• 生成两个大素数 $p$, $q$
  • 100位（十进制）以上
  • 有一些算法，复杂度是概率多项式。常见的：
    • Solovay-Strassen 素性测试
    • Miller-Rabin 素性测试
• 计算 $n = p \times q$
• 计算 $\phi(n) = (p-1)(q-1)$
  • 这是小于 n 并且与 n 互素的整数个数
• 随机选择一个数 $e$，使其满足 $1<e<\phi(n)$，并且 $\gcd (e,\phi)=1$ （也就是互素）
  • 算法复杂度为多项式。
  • 算法：找一个素数 e，并且它与 $\phi(n)$ 互素
• 解方程 $e\times d \equiv 1(\mod \phi(n))$，求出 d
  • 辗转相除法（欧几里得算法）
• 保密 $d$, 销毁 $p,q$，公开 $n,e$
• 公钥 PK = $(e,n)$
• 私钥 SK = $(d,n)$

RSA加密算法 RSA 的加密和解密过程

• 公钥为 (e, n)，私钥为 (d, n)
• 假设明文为数字 m
• 公钥加密 $c = (m^e) \mod n$ (必须满足 $m<n$，否则的话要对 m 进行分组)
• 私钥解密 $m = (c^d) \mod n$
  1. 加密算法和解密算法完全一样，因此可以用同一套硬件。（所以 RSA 是一个优秀的算法）
  2. 两个运算正好是逆运算，这个可以证明
  3. p, q 要足够大，否则容易通过公开的 n 计算出来
  4. 模指数运算 ($m = (c^d) \mod n$) 是有算法优化的（下面）
  5. 必须满足 $m<n$，否则的话要对 m 进行分组
• 公钥解密 $m = (c^e) \mod n$
• 私钥加密 $c = (m^d) \mod n$

# RSA key generation — toy example (DO NOT use in production)
# p, q are small primes just for demonstration

from math import gcd


def egcd(a, b):
    """扩展欧几里得算法，返回 (g, x, y) 使得 ax + by = g = gcd(a,b)"""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)


def modinv(a, m):
    """模逆：返回 a 在模 m 下的乘法逆元（若存在）"""
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError("inverse does not exist")
    return x % m


# 1) 选两个素数（示例用小素数）
p, q = 61, 53

# 2) 计算 n 和 φ(n)
n = p * q
phi = (p - 1) * (q - 1)

# 3) 选择 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
#    经典选择是 65537；这里为了示例取更小的 17
e = 17
assert 1 < e < phi and gcd(e, phi) == 1

# 4) 计算 d，使 e*d ≡ 1 (mod φ(n))
d = modinv(e, phi)

print("Public Key (PK) =", (e, n))
print("Private Key (SK) =", (d, n))


# 5) 演示加解密（m 必须小于 n）
def encrypt(m, e, n):
    """RSA 加密：c = m^e mod n"""
    return pow(m, e, n)


def decrypt(c, d, n):
    """RSA 解密：m = c^d mod n"""
    return pow(c, d, n)


m = 42
c = encrypt(m, e, n)
m_dec = decrypt(c, d, n)

print("\nPlaintext  m =", m)
print("Ciphertext c =", c)
print("Decrypted  m =", m_dec)

返回：

Public Key (PK) = (17, 3233)
Private Key (SK) = (2753, 3233)
Plaintext m = 42
Ciphertext c = 2557
Decrypted m = 42

关于 模指数运算 的优化：

• 假设要计算 $11^{23} \mod 187$
• 先得到 $11^{23} \mod 187 = [(11^{1} \mod 187) * (11^{2} \mod 187) * (11^{4} \mod 187) * (11^{8} \mod 187) * (11^{8} \mod 187) * ] \mod 187$
• 然后递归计算：
  • $11^{1} \mod 187 = 11$
  • $11^{2} \mod 187 = (11*11) \mod 187 = 121$
  • $11^{4} \mod 187 = (121*121) \mod 187 = 55$
  • $11^{8} \mod 187 = (55*55) \mod 187 = 33$

RSA算法的评价

• 取决于模n分解的困难性，目前最快的算法复杂性为 $O(\exp(\sqrt{\ln(n)\ln\ln n}))$
• 但是并没有证明分解大整数是 NP 问题。
• 也没有证明对 RSA 的攻击难度与分解大整数等价
• 目前，RSA 的一些变种算法已被证明等价于大数分解
• 由于有很多大数运算，因此性能较慢，一般只用于少量数据加密
• RSA 被研究的最为广泛，普遍认为是目前最优秀的公钥方案之一

非对称密码的理论基础

单向函数

一个函数 $f(x)$，对于任意 $x$，$f(x)$ 容易计算，同时对于几乎所有 $y$，$f^{-1}(y)$ 计算上不可行，那么 $f(x)$ 叫做单向函数

可以提供单向函数的数学难题：

1. 大整数分解问题（IFP）
2. 离散对数问题（DLP）
3. 椭圆曲线离散对数问题(ECDLP)
4. 等等

单向陷门函数

一个 单向函数，如果 $f^{-1}(y)$ 在已知某些辅助信息的情况下，容易求解，那么称为单向陷门函数

构造公钥密码系统的关键就是构造合理的单向陷门函数

Diffie-Hellman

介绍

• 第一个公钥方案
• 应用广泛（如 SSH）
• 用于 安全密钥交换
  • 不能直接用做大量数据传输
  • 不直接加密消息，而是双方协商出一个共享密钥
  • 允许两个用户安全建立秘密信息，用于后续通讯
• 算法安全性依赖于 有限域上计算离散对数的问题

算法-密钥生成

• 通信双方/多方选择一个大素数 $p$，以及 $p$ 的一个原根
• 用户 A 随机选择一个数 $X_a<p$，然后计算 $Y_a = a^{X_a} \mod p$
  • $X_a$ 是私钥，$Y_a$ 是公钥
• 用户 B 随机选择一个数 $X_b<p$，然后计算 $Y_b = a^{X_b} \mod p$
  • $X_b$ 是私钥，$Y_b$ 是公钥

算法-使用

• 一方传输 $p$ 和 $a$
• 双方要传输的是某个对称密码系统的密钥 $K = a^{X_a X_b} \mod p$
  • A 通过计算得到 $K = {Y_b}^{X_a} \mod p$
  • B 通过计算得到 $K = {Y_a}^{X_b} \mod p$
  • 攻击者像获得 K，需要求解离散对数（计算上不可能）

报文鉴别

回顾安全需求：

• 保密性 Confidentiality：数据、系统（访问控制）
• 完整性 Integrity：防止未授权的修改
• 可用性 Availability：合法用户总是可以访问
• 可认证 Authentication
• 抗抵赖 Non-repudiation

报文鉴别 面临的威胁：

• 泄密
• 流量分析：第三方分析你的流量大小
• 修改内容：报文被中间人修改
• 破坏数据包收到的先后顺序
• 发送方不承认发送过某报文
• 冒名顶替

报文鉴别 的需求

1. 保护报文的完整性（报文鉴别、防篡改）：报文加密
2. 验证发送者的身份：报文鉴别码 （MAC）
3. 抗抵赖：Hash 函数

报文加密

• 对称密钥加密。攻击者不知道密码，就无法篡改信息。
  • ✅ 保密性
  • ✅ 一定程度报文鉴别
    • 只能来源于对方（因为密钥只有双方知道）
    • 防篡改（需要配合冗余/特定格式）
  • ❌ 不提供抗抵赖。双方有对称密钥，接受者有能力伪造报文。
• 公开密钥密码系统：用对方的公钥加密报文
  • ✅ 保密性
  • ❌ 报文鉴别、抗抵赖。因为中间人可以根据公钥加密并发送伪造信息。
• 公开密钥密码系统。私钥加密报文，对方用公钥解密。
  • ❌ 保密性。因为任何人都有公钥。
  • ✅ 完整性（防篡改）、抗抵赖。中间人无法用私钥加密，并保证其可以被公钥解开。
• 公开密钥密码系统。发送者用私钥加密，然后用接受者的公钥再次加密
  • ✅ 保密性、完整性、抗抵赖
  • 缺点是加密两次

报文鉴别码（MAC， Message Authentication Code）

• 报文加密的缺点：开销大、较难自动化
• 固定长度的比特串（如128bit）
• 由MAC算法生成
  • 输入：报文和密钥
  • 类似对称密钥
  • 附加到报文上，用于报文鉴别
• 接受者做一样的检查，从而确保：
  • 报文来自发送者
  • 报文未被篡改

用法a（图）:

• ❌ 保密性
• ✅ 完整性、验证发送者身份
• ❌ 抗抵赖：因为 K 是双方共享的

用法b，先 mac，然后用另一个对称密钥系统做加密

• ✅ 保密性
• ✅ 完整性、验证发送者身份
• ❌ 抗抵赖：因为 K1 和 K2 是双方共享的

用法c，先用对称密钥系统加密，然后 mac

• ✅ 保密性
• ✅ 完整性、验证发送者身份
• ❌ 抗抵赖：因为 K1 和 K2 是双方共享的

MAC 的性质（要求）mac = $C_K(M)$

• M 可变
• 使用密钥 K
• 输出固定长度的 mac
• 必然是一个多对一的函数
• 攻击：找到另一个 $M’$ 使得 $C_K(M’)=C_K(M)$，为了防止攻击，要求：
  • 知道 mac，找到另一个 mac 值相同的报文非常困难
  • MAC 应当是均匀分布的
  • MAC 应当取决于报文的每一位
• 有哪些 MAC 生成算法
  • 分组密码的 CBC（Cipher Block Chaining）模式的最后一个密文块作为 MAC
    • Data Authentication Algorithm（DAA）是一个早期 MAC 生成算法，它基于 DES-CBC。 但是 MAC 太短（16-64个bit），不够安全

Hash 函数

Hash函数本身不使用密钥，并且是公开的

• 可以防止传输错误
• 无法防止恶意篡改，因为攻击者可能把 Hash 值一起改了
• 要用 Hash + 数字签名系统才可以防止恶意篡改

对 Hash 算法的攻击，叫做 Hash 碰撞攻击

• 单向性：已知 h，无法计算得到 x，使得 $h=H(m)$
• 弱抗碰撞性，给定 x，找到y，使得 $H(x) = H(y)$ 是计算上不可行的
• 强抗碰撞性，找到任意 x，y，使得 $H(x) = H(y)$ 是计算上不可行的

Hash的用法（参考下图）

这 6 种用法的解释：

1. 【a】配合对称加密系统，对全文加密，可以提供保密性、完整性、身份验证。需要共享密钥，不提供不可抵赖性。
2. 【b】配合对称加密系统，对Hash值加密。（前面写的报文鉴别码）。提供安全性、身份验证。
3. 【c】配合公钥加密系统，用私钥对Hash值加密，接收方用公钥对Hash值解密，然后对比。完整性、身份验证、抗抵赖。
4. 【d】：在 【c】的基础上，传输前加密。
5. 【e】：图中的 s 是一个随机数，这种用法常见于口令文件的保护。
6. 【f】：在【e】的基础上，传输前加密

接下来介绍一些 Hash 算法

最简单的 Hash 函数：对报文分组异或

• 可以防止随机比特错误，但不能防止蓄意破坏

MD5

• Ronald 设计（他也是 RSA 的设计者之一）
• 系列算法 MD2，MD4
• 128bit哈希值
• 成为 Internet 标准 RFC1321
• 200x年起，有一些碰撞攻击的进展

SHA

• NIST和NSA与1993年设计（美国国标）
• 1995年修订为 SHA-1
• Internet 标准 RFC3174
• 基于 MD4
• 160bit哈希值
• 2005年后，有一些碰撞攻击的进展
• 之后开发了 SHA-256, SHA-384,SHA-512
  • 它们与 AES 兼容

RIPEMD-160

• 欧洲开发
• 160bit哈希值
• 比 SHA-1 慢，更安全

生日攻击

• 生日悖论：一个班级，至少2个人生日相同的概率是多少？23个人是50%，30个人是70%
• 推广：如果有 $N$ 种可能，$n$ 个人随机选择他们，那么相同（碰撞）的概率约等于 $P \approx 1 - e^{-n^2/(2N)}$
• 如果 $n=\sqrt N$，那么 $P \approx 1/2$
• 也就是说，如果我们有 $\sqrt N$ 个报文，那么匹配的可能性为 50%
• 生日悖论的原因 是：我们不是找给定某个人的同生日概率，而是找一批人种任意两个同生日的概率
• 假设哈希值为 128-bit，那么列表长度为 $2^{64} \approx 10^{19}$ 即可发生 50% 概率碰撞

PKI

PKI（公开密钥基础设施，Public Key Infrastructure）

为什么？

• 中间人攻击：中间人用自己的公钥来伪造（替换）A的公钥。这样B以为在与A通信，实际上是在与中间人通信。
• 以上问题的核心：为什么要相信某个公钥，确实是某个人的公钥
• 解决方案：通过 证书（certificate） 来把公钥和身份关联在一起
• 证书由由公信力的第三方 CA（Certification Authority） 来证明
  • 同时还可以提供其它功能：密钥生命周期、密钥如何获取

一个完整的PKI应该包括

• 证书授权中心(CA)
• 证书库
• 证书注销
• 密钥备份和恢复
• 自动密钥更新
• 密钥历史档案
• 交叉认证
• 支持不可否认
• 时间戳
• 客户端软件

常见证书格式标准为 X.509 v3

CA系统职责

• 接受用户的请求
• (由RA负责对用户的身份信息进行验证)
• 用自己的私钥签发证书
• 提供证书查询
• 接受证书注销请求
• 提供证书注销表

CA系统组成

• RA(Registration Authority)
  • 用户和CA之间
  • 接受用户的注册申请，收集用户信息和确认用户身份，对用户进行资格审查，决定是否同意CA给其签发数字证书并向CA提出证书请求
  • 向LDAP服务器和安全服务器转发CA颁发的数字证书和证书撤消列表。
• CA(Certificate Authority)
  • 发证
• 证书库/目录
  • 保存证书，供公开访问
• LDAP服务器
  • 提供目录浏览服务，将 RA 传输过来的用户信息以及数字证书加入到服务器上。这样其他用户通过访问LDAP服务器就能够得到其他用户的数字证书。
• 安全服务器
  • 面向普通用户，
  • 提供证书申请、浏览、证书撤消列表、证书下载等安全服务

证书注销：维护一个证书注销列表CRL(Certificate Revocation List)

• 标准：X.509 V2
• 延迟可能有 24小时

多个CA结构

层次结构CA

CA层次结构的建立

• 根CA具有一个自签名的证书
• 每个节点依次对子节点CA进行签名
• 叶子节点上的CA用于对安全主体进行签名
• 对于主体而言，它只需信任根CA （不关心中间的CA）；同时它的证书是由底层的 CA 签发的
• 在CA的机构中，要维护这棵树
• 在每个节点CA上，需要保存两种cert
  • Forward Certificates: 其他CA发给它的certs
  • Reverse Certificates: 它发给其他CA的certs

层次结构CA中证书的验证

• 假设主体A看到B的一个证书
• B的证书中含有签发该证书的CA的信息
• 从 B 的 CA 开始，沿着层次树往上找，可以构成一条证书链，直到根证书
• 验证过程：
  • 沿相反的方向，从根证书开始，依次往下验证每一个证书中的签名。其中，根证书是自签名的，用它自己 的公钥进行验证
  • 一直到验证B的证书中的签名
  • 如果所有的签名验证都通过，则A可以确定所有的证书都是正确的，如果他信任根CA，则他可以相信B的证 书和公钥

交叉结构CA

• 一个CA向另一个CA签发证书
• 可以单向签发，也可以互相签发
• 约束
  • 限定名字
  • 路径长度。可以让太长的路径失效
  • 策略

其它结构CA

身份认证

身份认证（Authentication）定义：

• 宣称者向验证者出示证据，证明其身份
• 至少2个参与者
• 是一种协议
• 分为单向认证、双向认证
• 最大的威胁：重放攻击

安全性排序

• 【弱】基于口令
  • 【半强】基于动态口令
• 【强】基于密码技术
• 基于可信第三方：不但实现身份认证，还解决密钥分发问题
  • Needham-Schroeder 协议
  • Kerberos 协议

基于口令的身份认证

• 口令做 Hash 后存放
• 加盐

字典攻击。字典是人们常用的密码，或者已经泄漏的其他密码数据库

• 在线字典攻击：攻击者在网站上一个一个去试。很慢。
• 离线字典攻击：假设攻击者已经盗取了 Hash 值表，可以用密码字典去比较，从而得到密码
  • 加盐大大提高攻击成本。因为攻击者需要把字典中的每个密码，与每个盐值结合起来才能计算 md5

Unix的做法

• 用 DES 做 Hash 函数
• 加盐，盐取决于系统时间
  • 具体做法：salt 值+密码+其它信息拼接起来，然后整体做 Hash
  • 这个 salt 值与口令文件（含Hash值的那个文件），一起存放
• 身份认证过程：先查询 salt 值，然后计算 md5，进而比对

动态口令（One Time Password， OTP）

• 最早是 Lamppost 动态口令方案（1981年）
  • 事先分享一组口令序列，按照顺序使用
  • 一组口令的生成：h[t+1] = Hash(h[t])
  • B 仅知道 h[N]
  • A 从 N-1 开始使用，按照 h[N-1], h[N-2], ..., h[1] 的顺序使用它
  • 每次 A 给 B 出示口令后，B 做 1次 Hash，即可验证。B 验证后 h[k] 后，保存 h[k+1]

评价：

• 可以防止重放攻击（replay attack）
• 但是不能防止 预先播放（Pre-play attack）攻击。就是攻击者获取了一组口令。
• 口令更新的时间窗口（1分钟、30秒）内还是会有重放攻击
• 用很多次后，需要重新初始化。成本很高。
• 不支持双向认证，没法确定口令给到了真正的 B

基于对称密码的身份认证

质询与应答（Challenge-Response）基本逻辑。假设B要完成对A的身份认证

• 身份认证基于 A 知道的某个秘密（如密钥）
• 首先 B 发给 A 一个随机数（Challenge）（有时候叫做 Nonce， Number used ONCE）
• A 收到随机数后，对它做某种变换，得到 Response，并把它发送回去
  • Response 同时依赖随机数和 A 知道的秘密
  • 构造的算法是此协议的核心
• B 收到 Response，验证 A 是知道这个秘密的

实现方式

• 对称密钥
  • 对称密钥加密
  • 报文鉴别码
• 非对称密钥
  • 数字签名

基于对称密钥的单向身份认证 算法过程

• Challenge 是随机数
  • 每次不同（符合 One Time Password），
  • ✅ 用来防止重放攻击
• 双方共享秘密 KA，Alice 使用 KA 加密 “Challenge + B”
  • 为什么要连同 B 一起加密？为了抗 反射攻击（Reflection Attack）
  • 假设没有连同 B 加密，并且是双向身份认证系统，就可以实施反射攻击：
  • 攻击者用相同的随机数去质询 B，B 就会返回加密后的信息。而这段信息与 B 质询 A 的所需要返回的正确信息一模一样。
  • 约定加入目标信息 B 之后，加密文本对应的明文就有目标信息，B 发现目标信息不对，就不响应。
• Bob Server 使用 KA 解密，然后比对随机数是否一致

基于对称密钥的单向身份认证2:基于时间戳 一个更简洁的算法

• 算法流程基本相同，只是不再使用随机数，而是时间戳
• B 比对返回的时间戳，与本地时间戳的误差是否可以接受

基于对称密钥的双向身份认证

• Bob 给 Alice 发送 Challenge （随机数 rb）
• A 返回的加密内容中，不但有 rb，还有自己生成的随机数 ra
• B 返回加密后的 ra, rb

【评价】基于对称密钥的身份认证：

• 需要双方共享密钥
• 密钥如何分发？如何管理？尤其是大规模、分布式系统中

基于报文鉴别码的身份认证

基于报文鉴别码（MAC）的身份认证，有两个经典协议

• SKID2（单向）
• SKID3（双向）

与前面的“基于对称密码的身份认证”基本类似，只是把加密函数，换成了哈希函数。

基于公钥系统的身份认证

基于公钥系统的单向身份认证 算法流程

• Bob -> Alice: r_B （随机数）
• Alice -> Bob: cert_A, r_A, B, S(r_A, r_B, B)
  • cert_A 是 A 的签名证书，配合 PKI，可以获取到 A 的公钥
  • B 标记报文方向，防止 “反射攻击”（前面介绍过）
  • r_A 放到签名块中，是为了防止 选择文本攻击（chosen-text attacks）
    • 如果不加 r_A，攻击者用假的信息让 Alice 签名，从而获得假的签名

基于公钥系统的双向身份认证 算法流程

• Bob -> Alice: r_B （随机数）
• Alice -> Bob: cert_A, r_A, B, S(r_A, r_B, B)
• Bob -> Alice: cert_B, A, S(r_A, r_B, A)

还可以基于时间戳

一些典型的身份认证协议

Needham-Schroeder 协议

• 基于对称密钥的身份认证，密钥分发是个问题
  • 假设有 n 个参与者，那么就需要 $n(n-1)/2$ 个对称密钥
• Needham-Schroeder 协议 就是为了解决这个问题
• 它使用 可信第三方 来解决这个问题
• 每参与者与可信第三方共享密钥即可，共需要 $n$ 个对称密钥
  • 两个参与者需要的对称密钥（称为会话密钥，session key），在需要时由可信第三方来分发
  • 通信完成后，丢弃会话密钥

Needham-Schroeder 协议

• 1978年提出
• 既解决密钥分发问题，也解决身份认证问题
• 这个协议有一些问题，中间人如果拿到历史的会话密钥，可以实施攻击。
• 这个协议不断改进，最终演化为 Kerberos 协议

Kerberos协议

• 经过长期考验。
• 80年代中期，MIT提出
• 解决的问题：认证、完整性、保密性
• 使用在分布式环境，C/S模型，服务器与用户之间的双向认证
• 使用对称加密（DES）
• 也是基于可信第三方的
• 处理三种威胁
  • 用户伪装成另一个用户
  • 攻击者把自己的地址伪造成另一个用户的
  • 用户窃听报文，利用重放攻击进入服务器

一些符号

• C = 客户
• AS = 认证服务器（存放所有用户和用户口令）
• V = 应用服务器，有很多，为了解释简单，只描述一个
• IDc = C 上用户的标识符
• IDv = V 上用户的标识符
• Pc = C 上的用户口令
• ADc = C 的网络地址
• Kv = AS 和 V 共享的加密密钥

简单的认证对话

1. C -> AS: IDc

   Pc

   IDv

2. AS -> C: Ticket

   • Ticket = E_Kv(IDc

     ADc

     IDv)

3. C -> V: IDc

   Ticket

Needham-Schroeder 协议

Kerberos协议

Web 和电子商务安全

Web的脆弱性的原因

• Web 是外网可见的
• 复杂的软件会隐藏漏洞
• Web容易配置和管理
• 可悲用作跳板对内网攻击
• 用户没有意识到威胁存在

基于 HTTP 协议的 Web 应用：

• 安全吗？
  • ❌ 保密性。HTTP 协议是明文传输的
  • ❌ 完整性。明文传输，中间人攻击
  • ❌ 可用性。会被 DDos
  • ❌ 可认证。
• 结论：需要安全机制
• 威胁在哪里
  • 网络上：网络窃听、报文篡改
  • 服务端：网络钓鱼、使用相同口令（用户在高安全、低安全站点使用相同的口令）
  • 客户端：恶意软件（间谍软件、木马软件）

SSL

SSL（安全套接字协议Secure Socket Layer）、TLS（Transport Layer Security，传输层安全协议）

• SSL协议，网景公司开发的，有 V1，V2，V3 版本，后来成为 Internet 标准，改名为 TLS
• TLS 的 v1.0 可以认为是 SSL v3.1

差别

• 网络层加密，加密过程可以交给路由器做。
• 主机上，每个层都可以实现加密
• 保护范围不同。例如，只做网络层加密的话，应用层传出的就是明文。

SSL

• 浏览器上出现“https”时，SSL就已经生效了
• SSL协议分两层：
  • 底层：SSL记录协议
  • 上层：SSL握手协议（支持双向身份认证，实际使用多为单向）、SSL密码变化协议、SSL警告协议
• SSL记录协议
  • 建立在TCP上
  • 提供连接安全性：
    • 保密性：使用对称加密算法
    • 完整性：使用 MAC 算法
  • 用来封装高层的协议

SSL的工作流程

• 握手
  • 单向身份认证，双向认证（可选）
  • 协商 SSL会话的密钥等参数
• SSL记录协议
  • 加密会话数据
  • 提供完整性、保密性支持
• 会话

struct {
    ContentType type; // 8位，上层协议类型
    ProtocolVersion version;
    unit16 length; // 加密后数据的长度
    EncryptedData fragment; // 密文数据
} SSLCiphertext;

SET

SET（Secure Electronic Transaction）

• 开放的安全电子交易安全规范
• 保护 Internet 上信用卡支付交易
• 由 Mastercard, Visa 发起，参与者还包括 IBM, Microsoft, Netscape, RSA, Verisin
• 不是支付系统
• 是一系列安全协议和规范格式
• 太过复杂，没有一个商用系统基于它（很多用它的一个子集）

交易的10个步骤

1. The customer opens an account.
2. The customer receives a certificate.
3. Merchants have their own certificates.
4. The customer places an order.
5. The merchant is verified.
6. The order and payment are sent.
7. The merchant request payment authorization.
8. The merchant confirm the order.
9. The merchant provides the goods or service.
10. The merchant requests payments.

区块链

区块链是密码学技术（和P2P网络）的集大成应用

去中心化机制

• 账本公开
  • 账本不记录余额，而只记录每笔交易
  • 任何参与者都有一份账本
• 基本假设：一半以上的人诚实守信。即使少部分人伪造账本，真账本也不会被替代
• 区块
  • 每个区块都是账本
  • 最重要的是完整性
    • 交易历史的完整性
    • 交易本身的完整性

Merkle树：是一种 Hash 二叉树，用于快速归纳和校验大规模数据完整性

• 这个树本身不存储在区块中。只有根本存储在区块中（具体来说，区块头）。而各个子节点呢？可以根据本区块的交易记录来计算。
• 检查某元素是否在树中的性能是 $\log N$
• 使用两次 SHA256（叫做 double-SHA256）
• 参考下面的图解释
• 构造树
  • 假设两次 SHA256 操作，记为 DHash(input) = SHA256(SHA256(input))
  • H_A = DHash(A)
  • H_AB = DHash(H_A, H_B)
  • H_ABCD = DHash(H_AB, H_CD)
• 查询，假设需要查询 A 是否在树中
  • 先计算 H_A，查询其兄弟节点，得到 H_B，进而计算得到 H_AB
  • 然后查询 H_AB 的兄弟节点，计算得到父节点
  • 直到得到根节点的 Hash 值，完成查询

谁来记账：矿工

• 挖矿过程：把最近交易记录记录在账本上（生成区块，并加入链条）
• 矿工有一定可能获得报酬
• 矿工可以随时退出，随时加入（P2P的特性）
• 挖矿有难度（有一定计算量），矿工之间有竞争关系

矿工的工作

• 收集交易单
  • 付款人把交易单给到收款人，同时投递到矿工小组的收件箱中
  • 矿工定期把交易单取出
• 填写账本
  • 填写区块头
  • 按比填写交易记录
• 工作量证明（Proof-of-work）
  • 新区块被别的矿工认可：别的矿工开始在这个区块上计算下一个区块
  • 新区块头的 HASH 必须满足计算量的要求。矿工需要找到一个合适的随机数 Nonce，使其满足 H(头) = 0x00..00FF..FFF（共64位16进制） ，其中F的个数取决于 难度值
    • 计算很难，验证很简单
    • 难度值动态变化，每2016个区块更新一次。目的是使区块的生成速度不能太快，使其平均在10分钟左右

共识机制：与工作量证明一起，保证完整性

• 报酬：每个矿工的交易清单第一笔交易，就是“系统向本矿工支付50个比特币”
  • 最早是50个比特币，规定每 210,000 个区块减半一次，2025年已经衰减到 3.125BTC 了
    • 因此，比特币最多就 2100万个
  • 除了固定奖励，还有该区块所有交易的手续费（通常0.1-0.5BTC）作为报酬
• 矿工完成计算后，立即请求别的矿工确认
• 所有矿工收到新区块时，立即停止挖矿并确认
  • Hash 是否满足难度值要求
  • 前一个区块确实是自己的最后一个区块，且 Hash 正确
  • 交易清单有效：付款人有余额
• 新区块被别的矿工认可：别的矿工开始在这个区块上计算下一个区块

问题讨论

问题1:同时收到2个合法区块

• 由于矿工们是并行的，完全可能同时收到两个合法的新区块
• 答：不以线形方式组织账本，而是树状，任何时刻以当前最长分支位主账本，但保留其它分支
• 规定：收款人在公告挂出后不能立即确认交易完成，而是再等待6个区块，并且之前的区块没有被取消
• Proof-of-work，正是为了防御 伪造区块攻击，它在落后6个区块的情况下，赶超主分支非常困难。需要算力超过所有其它算力之和

问题2：通货膨胀

• 挖矿报酬不能一直进行下去，而是（前面提到的）减半
• 一旦挖完，挖矿报酬就只有手续费

问题3:防篡改 Hash（double-SHA256）来保证

• 攻击1:改变区块内的交易记录，那么 Merkle 根对不上
• 攻击2:改变交易记录和 Merkle 根，那么区块 Hash 对不上
• 攻击3:攻击者没有达到难度就提交区块，用公式很容易验证
• 攻击4:攻击者改变区块内容、区块Hash，那么本区块的下一个区块头保存的 prev_hash 对不上
• 攻击5:攻击者掌握51%以上算力，那么确实可以修改所有区块，这他做合法公民的收益更大、更安全

交易记录：公钥系统实现身份标识+交易签名

• 交易记录中的内容
  • 唯一编号
  • 交易内容
  • 付款人的签名：E_付款人的SK(当前交易 + 收款人的 PK)
• 如何验证一笔交易
  • 验证签名
  • 验证交易的钱大于余额

关于钱包地址、公钥、私钥之间的关系，

• SECP256K1 算法（基于 ECC），算法强度强、公钥长度短

隐私保护

• 账本公开，是否某比特币拥有者的账目都查出来了？
• 不是，每次交易使用不同的公钥，就查不到同一个人的所有账目了

防火墙

找到关键节点（路由）

防火墙能为我们做什么

• 访问控制
  • 服务控制：确定哪些服务可以被访问
  • 方向控制：确定哪个方向可以通过防火墙
  • 用户控制：哪些用户可以访问
  • 行为控制：控制特定服务的行为
• 监视个字安全时间，审计、报警
• 其它功能：地址转换、Internet 日志、审计、计费
• IPSec 实现平台
• 不能做什么
  • 绕过防火墙的行为。内部拨号、VPN、用http协议虚拟一个tcp-ip协议
  • 内部对内部的攻击
  • 不能过滤带病毒稳文件
  • 性能影响（网络延迟、通信瓶颈、单点失效）
  • 入侵检测系统（IDS，Intrusion Detection System）与防火墙有区别。
    • IDS 可以联动防火墙。
    • IPS（入侵防护系统，Intrusion Prevention System）。是IDS和防火墙的组合

参考

• 【国家精品课程】复旦大学：信息安全
• 《深入浅出密码学》
• 撰写本文过程中，用ppt画了一些图片，原件根据需要自取