《密码学及应用》开卷考试宝典

n 模 m 的约简：n 除以 m 的余数 r，0 ≤ r < |m|，记作 r = n%m 或 n mod m，m 称为模数。

在密码学中：任何整数模 m 的约简都是非负数。

课件例：(24+3) = 27%26 = 1；(1−3) = −2%26 = 24。

定理 1（等价关系）：自反性、对称性、传递性。

定理 2：ax ≡ ay (mod m)，若 (a,m)=1，则 x ≡ y (mod m)。
（想"约掉"因数，必须先验证它与模数互素！）
例：95 ≡ 25 (mod 7)，(5,7)=1 ⟹ 19 ≡ 5 (mod 7)

定理 3：x ≡ y (mod m)，a>0 ⟹ ax ≡ ay (mod am)。
例：19 ≡ 5 (mod 7)，a=4 ⟹ 76 ≡ 20 (mod 28)

定理 4：x ≡ y (mod m)，若 d|(x,y,m)，则 x/d ≡ y/d (mod m/d)。
例：190 ≡ 50 (mod 70)，d=10 ⟹ 19 ≡ 5 (mod 7)

定理 5：x ≡ y (mod m)，如果 d|m，则 x ≡ y (mod d)。

定理 6：a ≡ b (mod m_i)，i=1…k ⟹ a ≡ b (mod [m₁,…,m_k])。
特别地：p、q 是两个不同素数，若 a ≡ b (mod p) 且 a ≡ b (mod q)，则 a ≡ b (mod pq)。
例：19 ≡ 7 (mod 3)，19 ≡ 7 (mod 4)，(3,4)=1 ⟹ 19 ≡ 7 (mod 12)

整数 x 和 y 不同时为 0，则其最大公因子 (x,y) 是以 ax + by 表示的最小正整数。

作用：找到整数 a 和 b，表示 x 和 y 的最大公因子：ax + by = (x,y)。

例：(3,5) = 2×3 − 1×5 = 1；(9,15) = 2×9 − 1×15 = 3

定义：m 模 n 的乘法逆 t（记作 m⁻¹%n）满足 m × t % n = 1。

存在条件：(n, m) = 1。不互素 = 无解。

定理：满足 ax + bn = 1 的整数 a 是一个 x 模 n 的乘法逆元。

英文字母 a~z 用数字 0~25 表示。

加密：y = f(x) = (x + k) % 26　　解密：x = f(y) = (y − k) % 26

密钥空间：25（k = 1~25；k=0 等于没加密）

课件例：(24+3) = 27%26 = 1；(1−3) = −2%26 = 24

算法思想：增加密钥参数，扩大密钥空间。

加密：y = E_a,b(x) = (ax + b) % 26　　解密：x = D_a,b(y) = (a⁻¹y − a⁻¹b) % 26

密钥空间：由于 a⁻¹ 必须存在，a 必须与 26 互素（共 12 个：1,3,5,7,9,11,15,17,19,21,23,25），b 有 26 个，故 12×26−1 = 311。

课件例：(a,b) = (9,3)，y = (9x+3)%26，解密 x = (3y+17)%26。
明文 meet me at midnight → 密文 hnns hn ds hxeqxfos。

针对密钥的攻击 / 唯密文攻击 / 选择明文攻击 / 已知明文攻击

穷举攻击：尝试可能的密钥（最多 311 次）。

唯密文攻击：字母频率攻击。

选择明文攻击：E_a,b(0) = b，E_a,b(1) = a+b ⟹ b = E_a,b(0)，a = (E_a,b(1) − b)%26

已知明文攻击：
a = (x−y)⁻¹(E_a,b(x) − E_a,b(y)) % 26
b = (E_a,b(x) − ax) % 26

算法原理：将明文中的每个字母移动 k_i 位，k_i 为密钥，0 ≤ k_i ≤ 25。

密钥是序列 k = (k₀, k₁, …, k_m−1)，m 为密钥长度；明文 x = (x₀, …, x_n) 分成长度为 m 的段。

加密：y_i = (x_i + k_i%m) % 26　　解密：x_i = (y_i − k_i%m) % 26

密钥特征：加密密钥和解密密钥相同。

密钥空间：与密钥长度 m 有关，为 26^m。

总体思路：找到密钥长度 m → 按 m 分组 → 每组变成移位密码 → 频率攻击。

Kasiski 方法：找重复出现的片段，量它们的距离；距离的公约数就是 m。
（密文重复 = 明文重复 + 距离是 m 的倍数，两个条件缺一不可）

Friedman 方法（重合指数）：不看重复片段，看字母分布。

算法原理：一次一密加密方式，明文和密钥一样长，密钥本身只使用一次。

加密解密与 Vigenère 相同：y_i = (x_i+k_i)%26，x_i = (y_i−k_i)%26

密码特点：密钥和明文等长，克服了 Vigenère 易受重合指数攻击的缺点。但密钥的产生、保存和传输非常重要。密钥空间与明文长度 n 有关，为 26ⁿ。

算法原理：将明文字符在消息内变换位置。

算法特点：明文和密文一样长（字母一个不多一个不少）。

举例：如将文本翻转，computersystems → SMETSYSRETUPMOC。

唯密文攻击可能得到多种不同的破译结果；如 live – evil – vile（同样是这 4 个字母，分不清原文）。

设 S 为集合，函数 f: S×S→S 称为 S 上的二元运算（用 * 表示），满足：可计算性、单值性、封闭性。

* 通常指加法 (+) 和乘法 (× 或 ·)。

结合律：(a*b)*c = a*(b*c)　　交换律：a*b = b*a

单位元：加法为 0，乘法为 1。

定义：整数模 m 剩余类（等价类）的集合，记作 Z/m 或 Z_m。

给定整数 x 和模数 m，x 模 m 等价类 = { y ∈ Z : y ≡ x (mod m) }，通常记为 x̄，又称 x 模 m 的同余类或剩余类。

举例（模 12）：0̄ = 12 = −12 = 2400；1̄ = 13 = −11 = 2401

定义：模 m 的剩余类有 m 个：0, 1, …, m−1。

已知正整数 m，则 m 个整数 x₀, x₁, …, x_m−1 为模 m 的一个完全剩余系的充要条件是它们两两不同余。

定理 2：已知整数 m, a, b，满足 (a,m)=1。若 x 遍历模 m 的一个完全剩余系，则 ax+b 也遍历模 m 的一个完全剩余系。
例：m=4, a=3, b=1，x∈{0,1,2,3} ⟹ ax+b ∈ {1,0,3,2}
反例：m=4, a=2, b=1，x∈{0,1,2,3} ⟹ ax+b ∈ {1,3,1,3}（不平移整圈）

定理 3：设 m, n 是两个互素的正整数，如果 x, y 分别遍历模 m, n 的完全剩余系，则 nx+my 遍历模 mn 的完全剩余系。

整数模 m 的简化剩余类（等价类）的集合，记作 Z_m^*。

即 Z_m 中与 m 互素的元素的集合。

举例：Z₁₀^X = {1,3,7,9}；Z₁₅^X = {1,2,4,7,8,11,13,14}；Z₁₁^X = {1,2,3,4,5,6,7,8,9,10}

元素个数 = 欧拉函数 = φ(m)。

定义：对正整数 n，与其互素的小于等于 n 的正整数的个数，表示为 φ(n)。

定理 1：若正整数 m, n 满足 (m,n)=1，则 φ(mn) = φ(m)φ(n)

定理 2：n = p₁^e1p₂^e2…p_m^em，则

φ(n) = (p₁−1)p₁^e1−1 (p₂−1)p₂^e2−1 … (p_m−1)p_m^em−1

特例：p 为素数时，φ(p) = p − 1。另 φ(1) = 1。

欧拉定理：对 n > 1，如果 (x,n) = 1，则有　x^φ(n) ≡ 1 (mod n)

费马小定理：对任意的整数 x 和素数 p，有　x^p−1 ≡ 1 (mod p)

课件例：求 3³⁰³ 展开后的最后三位数字。
解：3³⁰³ ≡ 3³ ≡ 27 (mod 1000)，因为 ord₁₀₀₀(3) = 100，而 303 ≡ 3 (mod 100)。

课件还要求：求 8¹⁰⁰¹ 展开后的最后四位数字。

幂的定义：设 <G,*> 是群，g∈G，n∈Z，则 g 的 n 次幂为 gⁿ = gⁿ⁻¹*g (n>0)、(g⁻¹)⁻ⁿ (n<0)、e (n=0)。

阶的定义：对群 <G,*>，g∈G，使得等式 g^t = e 成立的最小正整数 t 称为 g 的阶（指数），记做 |g| = t。g 称为 t 阶元。若不存在这样的整数 t，则 g 称为无限阶元。

性质：群中任何元素 g 与其逆元 g⁻¹ 具有相同的阶。

对正整数 n，如果 g 是模 n 的原根，那么对于任意的 x ∈ Z_n^x，都存在 d，使得 g^d ≡ x (mod n)。

即 g¹, g², …, g^φ(n) 组成模 n 的简化剩余系。

Z_n^x 中的阶：对任意 x ∈ Z_n^x，即 (g,n)=1，存在正整数 t 满足 g^t ≡ 1 (mod n)，则满足条件的最小正整数 t 是 g 模 n 的指数或阶，记为 ord_n(g)。

循环群：设 <G,*> 是群，若存在元素 g∈G，使得 G = {g^k | k∈Z}，称 G 为循环群，记 G = <g>，g 称为生成元。

定理 1：模 n 原根 g 存在的充要条件是 n = 2, 4, p^e, 2p^e（p 为奇素数，e ≥ 1）。
举例：6 有原根 5；9 有原根 2。

定理 2：设 n > 1，φ(n) = q₁×q₂×…×q_k（q_i 为素因子），则 g 是模 n 的一个原根的充要条件是

g^φ(n)/q_i ≢ 1 (mod n)，　i = 1, …, k

举例：对 n=11，测试 g=2, g=3。

计算 x^e 时，将 e 表示为一个二进制整数 e = e₀ + e₁·2 + e₂·2² + … + e_n·2ⁿ，e_i ∈ {0,1}。

x^e = x^e0 · (x²)^e1 · (x⁴)^e2 … (x²ⁿ)^en

若 e_i=0 则忽略该项；若 e_i=1 则包含该项。

举例：x⁵ = x⁽¹⁰¹⁾ = x¹·(x²)⁰·(x⁴)¹；x¹³ = x⁽¹¹⁰¹⁾ = x¹·(x²)⁰·(x⁴)¹·(x⁸)¹

定义 1：设 S = {1,2,…,n}，S 上的任何双射映射函数 δ: S→S 称为 S 上的 n 元置换，记为 δ = (1 2 … n / δ(1) δ(2) … δ(n))。

定义 2：设 S = {1,2,…,n}，S 上的 n! 个置换构成集合 S_n，则称 S_n 与置换的复合运算 ∘ 构成的群 <S_n, ∘> 为 S 上的 n 元对称群；<S_n, ∘> 的任意子群称为 S 上的 n 元置换群。

元素个数为 n!；g∘h 表示先应用 h 再应用 g。

k 循环：在一个 n 元置换 g 中，有 k 个元素满足 f(i₁)=i₂, f(i₂)=i₃, …, f(i_k)=i₁；对于任意 j ∉ (i₁,…,i_k)，f(j)=j，则称 g 为 k 循环，记作 (i₁ i₂ … i_k)。

例：(1 2 3 / 2 1 3) = (1 2)；(1 2 3 / 2 3 1) = (1 2 3) = (2 3 1) = (3 1 2)

注意：一个 k 循环有 k 种表示法。比较 (1 2 3) 与 (1 3 2) 是不同的。

循环置换的阶：若置换 g 是一个 k 循环，则 g^k = e，g 的阶为 k。

不相交循环：若循环 g 和 h 的元素列表不相交，则 gh = hg。

置换的表示：任何置换都可以表示为不相交循环的乘积，不考虑乘积次序时该表达式是唯一的。

置换 g 的阶 k = 不相交循环分解中各循环长度的最小公倍数（lcm）

课件例：g = (1 2 3 4 5 6 7 / 4 3 2 5 7 6 1) = (1 4 5 7)(2 3)(6)，循环长度 4、2、1 ⟹ 阶 = lcm(4,2,1) = 4。

2n 张牌记作 1, 2, …, n, n+1, …, 2n−1, 2n

• 不好的洗牌（两半交错）：n+1, 1, n+2, 2, …, 2n−1, n−1, 2n, n
• 完美洗牌：1, n+1, 2, n+2, …, n−1, 2n−1, n, 2n
• 完美快速洗牌（本章重点）：f(x) = (2x) mod (2n+1)

1973 年 5 月 15 日 NBS 开始公开征集标准加密算法 DES（Data Encryption Standard），并公布了设计要求：

• 算法必须提供高度的安全性
• 算法必须有详细的说明，并易于理解
• 算法的安全性取决于密钥，不依赖于算法
• 算法适用于所有用户
• 算法适用于不同应用场合
• 算法必须高效、经济
• 算法必须能被证实有效
• 算法必须是可出口的

1974 年 8 月 27 日第二次征集，IBM 提交了算法 LUCIFER；1975 年 3 月公开发表；1977 年 1 月由美国国家标准局 NBS 颁布为数据加密标准 DES；1983 年 ISO 同意将 DES 作为国际标准，称之为 DEA-1；1998 年美国政府不再将 DES 作为联邦加密标准，但其结构和部件一直作为分组密码设计的标准参照物。

将经过 IP 置换后的数据分成 32 位的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的 32 位进行一系列的加密变换，然后把左边的 32 位与右边得到的 32 位逐位进行异或操作，作为下一轮迭代时左边的段。

迭代公式：L_i = R_i−1，R_i = L_i−1 ⊕ f(R_i−1, k_i)

⊕：按位异或运算符，即按位作模 2 相加。运算规则：1⊕0=1，0⊕1=1，0⊕0=0，1⊕1=0

f 的功能：将 32 比特的数据经过选择扩展运算 E、密钥加密运算、选择压缩运算 S、置换运算 P 转换为 32 比特的输出。

将密钥加密运算后的 48 比特数据从左至右分成 8 组，每组为 6 比特，并行送入 8 个 S 盒后转换成 32 比特输出。

每个 S 盒的输入为 6 比特，输出为 4 比特。（8 盒 × 4 位 = 32 位）

64 比特初始密钥 k 经过换位函数 PC-1，将位置号为 8,16,24,32,40,48,56 和 64 的 8 位奇偶位去掉并换位；换位后的数据分为 2 组，经过循环左移位 LS_i 和换位函数 PC-2 变换后得到每次迭代加密用的子密钥 k_i。

来学嘉和 James Massey 于 1990 年公布，1992 年更名为 IDEA（国际数据加密算法，International Data Encryption Algorithm）。

• 分组长度为 64 位，分 4 个 16 位子分组
• 密钥长度 128 位
• 使用异或、模 2¹⁶ 加、模 2¹⁶+1 乘三个混合运算，在 16 位子分组上进行
• 共进行8 轮操作，每轮与 6 个 16 位子密钥异或、相加、相乘；在每轮之间，第 2 个和第 3 个子分组交换
• 最终由一个输出变换
• 强化了抗差分分析能力，应用于 PGP 中
• 软件实现 IDEA 比 DES 快两倍
• 乘加结构（MA）保证了扩散的特点

子密钥生成：128 位的 k 分组：k₁, k₂, …, k₈；然后进行左环移 25 位。

发布：1997 年 NIST 征集，2002 年正式公布。由 Vincent Rijmen 和 Joan Daemen 设计，原名 Rijndael 算法。

特点：安全，易实现，算法灵活与简便。

• 128 位分组，密钥长度 l 为 128 / 192 / 256 位
• 4×4 字节矩阵，r = (l/32 + 6) 轮迭代，r+1 个子密钥

128 比特的明文分组被分成 4×4 的字节矩阵（称为状态 State）。

1. 字节替换 SubBytes：非线性置换，独立作用于状态中的每一个字节。（逆运算 InvSubBytes 用逆 S 盒）
2. 行移位 ShiftRows：字节循环移位运算，第 1 行~第 4 行字节分别向左移动 0~3 列。（逆运算 InvShiftRows 向右移动 0~3 列）
3. 列混合 MixColumns：由一个线性变换对状态的每一列进行变换。（逆运算 InvMixColumns）

   [0E 0B 0D 09] [a0]     [b0]        [1 0 0 0]
   [09 0E 0B 0D] [a1]  =  [b1]   .    [0 1 0 0]
   [0D 09 0E 0B] [a2]     [b2]        [0 0 1 0]
   [0B 0D 09 0E] [a3]     [b3]        [0 0 0 1]

4. 轮密钥加 AddRoundKey：与相应的密钥进行异或。

算法步骤小结：字节替换（非线性置换 S 盒，混淆）→ 行移位（字节矩阵按行移位 0~3 列）→ 列混合（线性矩阵模乘运算，扩散）→ 轮密钥加（混入密钥信息）。

不可约多项式：设 f(x) 是整环 R 上的非常数多项式，如果除了 1 和 f(x) 外没有其他因式，则 f(x) 叫做不可约多项式，否则称为可约多项式或者合式。

举例 1：多项式 x²+1 在 Z(x) 中不可约，在有限域 F₂[x]（通常记做 GF(2ⁿ)）中可约，因为在 F₂[x] 中 x²+1 = (x+1)²。

举例 2：GF(2²) 中不可约多项式有 x, x+1；GF(2³) 中二次不可约多项式有 x²+x+1；GF(2⁴) 中三次不可约多项式有 x³+x+1, x³+x²+1。

AES 中以字节为单位进行模 x⁸+x⁴+x³+x+1 运算。

Rijndael(State, CipherKey){
    KeyExpansion(CipherKey, W[1,…,Nb*(Nr+1)]);
    AddRoundKey(State, W[0,…,Nb-1]);
    for (i=1; i<Nr; i++) {
        SubBytes(State);
        ShiftRows(State);
        MixColumns(State);
        AddRoundKey(State, W[i*Nb,…,(i+1)*Nb-1]);
    } // 中间 Nr-1 轮
    SubBytes(State); ShiftRows(State); // 末轮
    AddRoundKey(State, W[Nr*Nb,…,(Nr+1)*Nb-1]);
}

• 分组密码：将明文分组进行加密
• 序列密码：将明文按字节或位进行加密

序列密码算法原理：密钥流 ⊕ 明文 = 密文。

密钥流的生成方式：RC4 → 字节流；同余发生器 → 数据流；移位寄存器 → 位流。

发布：Ron Rivest 在 1987 年设计（也是 RSA 中的 R：Ron Rivest、Adi Shamir、Len Adleman）。

• 简单，速度快，10 倍于 DES 的速度
• 面向字节的流密码，密钥独立于明文
• 应用广泛，很多 HTTPS 网站使用 RC4
• 有一个 256 字节的 S 盒：S₀, S₁, …, S₂₅₅；S_i 的值是 0 到 255 之间不重复的值
• 密钥长度可变

s_n+1 = (a · s_n + b) mod m

其中 0 < a < m，0 ≤ b < m，初值 s₀ 称为种子。

a、b、m 的取值是产生高质量随机数的关键。

线性同余发生器 s_n+1 = a·s_n (mod p) 的周期为 a 在乘法群 Z_p^* 中的阶 l。

• p 为素数时，l | p−1；当 a 为模 p 的本原根时，l = p−1
• 种子 s₀ 不等于坏种子

坏种子：s_bad ≡ −(a−1)⁻¹ · b (mod p)

为什么是坏种子：若 s = (as+b) mod p，则 s(1−a) = b ⟹ s = b/(1−a) = −(a−1)⁻¹b。种子落在此处，序列永远卡死，周期退化为 1。

课件举例 1：求 s_n+1 = 7s_n+2 (mod 13) 的坏种子 s_bad。
a=7, b=2, p=13 ⟹ s_bad = −(6)⁻¹×2 mod 13。6⁻¹ = 11（因 13−2×6=1 ⟹ 6⁻¹=−2=11）⟹ s_bad = −11×2 = −22 ≡ 4 (mod 13)。
验算：(7×4+2) = 30，30 mod 13 = 4 ✓ 果然卡死。

基于移位寄存器的序列密码被广泛应用于军事密码学中。由两部分组成：移位寄存器和反馈函数。

最简单的是 LFSR。

b_n+1 = c_nb_n + c_n−1b_n−1 + … + c₂b₂ + c₁b₁，　c_i ∈ {0,1}

参与异或的位置称为抽头，一串 c_i 称为抽头序列。

是一个公开的函数，它将任意长的信息映射成一个固定长度的信息（数字摘要 / 散列值 / 数字指纹）。

消息摘要（Message Digest）或杂凑函数，由 Ronald Rivest 1992 年开发。

输入消息 x，输出为 128 位的消息摘要值。

算法包括 5 个步骤：

1. 附加填充比特：在消息 x 后填充串 1000…，使得消息的长度满足 |x| ≡ 448 mod 512；填充比特总是有效，填充数为 1~512
2. 附加长度：将原始消息的长度（64 比特）附加到填充后的消息后面，填充后消息的总长为 512 比特的倍数；设消息最终分成 n 个 512 的消息块 V₁~V_n，每个消息块 V 分成 16 个 32 比特的子块 X[0]~X[15]
3. 初始化或填充 MD 缓冲区：4 个 32 比特的寄存器 A, B, C, D。对 V₁ 操作时初始值：
   • a = A = 0x01234567
   • b = B = 0x89abcdef
   • c = C = 0xfedcba98
   • d = D = 0x76543210
   否则为前一消息块的迭代输出
4. 按每块 16×32（512 比特）对数据进行处理：主循环有 4 轮，每轮进行 16 次操作。

   轮数   X[k] 的 k 值
    1     0,1,2,3,…,15
    2     1,6,11,0,…,12
    3     5,8,11,14,…,2
    4     0,7,14,5,…,9

   说明：X[k] 为消息块 X 的第 k 个子分组（0~15）；T[i] 为 2³²×abs(sin(i)) 的整数部分，i 为弧度。
   4 轮操作：b = b + (a + (g(b,c,d) + X[k] + T[i]) <<< s)，g 在每轮中分别为 F、G、H、I 逻辑函数。
   第 1 轮：b = b + (a + (F(b,c,d) + X[k] + T[i]) <<< s)
5. 输出：a = (A+a) mod 2³²；b = (B+b) mod 2³²；c = (C+c) mod 2³²；d = (D+d) mod 2³²

SHA（Secure Hash Algorithm）由 NIST 开发并于 1993 年采纳为标准，其基础是 MD4，因此其设计与 MD5 类似。

SHA 算法流程（5 步）：附加填充比特 → 附加长度 → 初始化缓冲区 → 80 次迭代 → 输出。

以分组 512 比特为单位对消息进行 4 轮压缩处理，每轮处理过程对缓冲区进行 20 次迭代运算。

32 比特寄存器初始值：
A = 0x67452301　B = 0xefcdab89　C = 0x98badcfe　D = 0x10325476　E = 0xc3d2e1f0

• 公钥密码学概念 —— 1976 年 Diffie 和 Hellman 提出
• 特点：加密密钥公开，密钥管理简单
• 代表性算法：RSA、ElGamal、ECC 等
• 安全性：基于数学难题，运算速度较慢

对正整数 n，若 g^t ≡ x mod n，则 t 称为 x 的以 g 为底模 n 的离散对数，记为 log_gx mod ord_n(g)。

举例：3² ≡ 9 (mod 13) ⟹ log₃9 ≡ 2 (mod 3)；因为 3¹=3, 3²=9, 3³=1。

离散对数问题 DLP：给定素数 p、Z_p^x 的生成元 g 以及整数 x ∈ Z_p^x，求解 t 满足 g^t ≡ x mod n。

• 易：g, t, n → x
• 难：g, x, n → t（当 n 很大时，是一个难题）

应用：很多密码技术的安全性建立在离散对数难题上，如 ELGamal、ECC 等。

定义：设整数 m > 0，f(x) 为多项式且 f(x) = a_nxⁿ+…+a₁x+a₀，a_i 为整数，则 f(x) ≡ 0 (mod m) 叫做模 m 同余式；若 a_n ≠ 0，则 n 叫做 f(x) 的次数。

定理：设 m | a，d = (a,m)，则模 m 的一次同余式 ax ≡ y (mod m) 有解的充要条件是 d | y；解的个数是 d。

又称孙子定理：最早见于《孙子算经》中的"物不知数"问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

已知 m₁, m₂, …, m_n 两两互素，则同余方程组

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
    …
x ≡ an (mod mn)

令 M_n = m₁×m₂×…×m_n，W_i = M_n/m_i，T_i = W_i⁻¹ mod m_i

x ≡ a₁T₁W₁ + … + a_nT_nW_n (mod M_n)

课件例：x≡2(3), x≡3(5), x≡2(7)
x ≡ 2×35×(35⁻¹ mod 3) + 3×21×(21⁻¹ mod 5) + 2×15×(15⁻¹ mod 7)
≡ 2×35×2 + 3×21×1 + 2×15×1 (mod 105) ≡ 23 (mod 105)

两式情形：x≡a₁(m₁), x≡a₂(m₂) 有解
x ≡ a₁·m₂·(m₂⁻¹ mod m₁) + a₂·m₁·(m₁⁻¹ mod m₂)

二次同余式：一般形式 ay²+by+c ≡ 0 (mod n)，其中 n 为正整数且 a ≠ 0，可化简为：
(2ay+b)² ≡ b²−4ac (mod n)，等价于 x² ≡ d (mod n)，(d,n)=1

平方剩余：整数 n > 0，(a,n) = 1，若 x² ≡ a (mod n) 有解，则 a 称为模 n 的平方剩余（二次剩余）；否则 a 称为模 n 的平方非剩余。

举例：1, 2, 4 是模 7 的平方剩余；−1, 1, 2, 4, 8, 9, 13, 15 是模 17 的平方剩余。

设 p 为奇素数，(a,p) = 1，则

• a^(p−1)/2 ≡ 1 (mod p) 时，a 是模 p 的平方剩余
• a^(p−1)/2 ≡ −1 (mod p) 时，a 是模 p 的平方非剩余

举例：14 是模 101 的平方剩余吗？

定理：设 p 是满足 p ≡ 3 (mod 4) 的素数，如果同余式 x² ≡ a (mod p) 有解，则其解是

x ≡ a^(p+1)/4 (mod p)

证明：由于 y 是模 p 的平方数，设 y = x²，则有 (y^(p+1)/4)² = y^(p+1)/2 = x^p+1 = x^p·x = x·x = y

举例：求 6 模 19 的二次根
a^(p−1)/2 mod p = 6⁹ mod 19 = 1
x = ±a^(p+1)/4 mod p = ±6⁵ mod 19 = ±5 mod 19 ✓

模是合数 n = p₁p₂…p_k：拆成多个方程，用中国剩余定理合并。

课件的例子：解 x² ≡ −1 (mod 13×17×29)
x² ≡ −1 (mod 13) ⟹ x ≡ ±5 (mod 13)
x² ≡ −1 (mod 17) ⟹ x ≡ ±4 (mod 17)
x² ≡ −1 (mod 29) ⟹ x ≡ ±12 (mod 29)
⟹ 8 个解（2×2×2）

模是合数 n = p^k：用亨泽尔定理。假设 f 是一个多项式，p 为素数，如果 x = x₁ mod p 是同余式 f(x) ≡ 0 (mod p) 的一个解，且 (f'(x₁), p) = 1，则同余式 f(x) ≡ 0 (mod p^k) 有解 x = x_k mod p^k，其中 x_k 由下面关系式递归得到：
x_i ≡ x_i−1 − f(x_i−1)f'(x₁)⁻¹ (mod pⁱ)，i = 2,…,k

(a/p) =  0    若 p | a
         1    若 a 是模 p 的平方剩余
        -1    若 a 是模 p 的平方非剩余

(1/7) = (2/7) = (4/7) = 1    平方剩余
(3/7) = (5/7) = (6/7) = -1   平方非剩余

说明：如果素数 p 改为正奇数 n，即为 Jacobi 符号。

定理：素数 p > 2，对于任意整数 a 有 (a/p) ≡ a^(p−1)/2 (mod p)

性质：素数 p > 2，对于整数 a 和 b 有

(1/p) = (a²/p) = 1        (-1/p) = (-1)^((p-1)/2)      (2/p) = (-1)^((p²-1)/8)
(ab/p) = (a/p)(b/p)       (a+p/p) = (a/p)
若 a ≡ b (mod p)，则 (a/p) = (b/p)

如果 p, q 是不同的奇素数，那么

(q/p) = (−1)^{(p−1)(q−1)/4} (p/q)

素数的产生：采用素性检测法对随机产生的数进行检测。没有发现产生素数的模型或有效公式。

例如：中国古代数学家提出，若 n | 2ⁿ−2，则 n 为素数。（n=3, 5, 7 成立）
但是当 n = 341 = 11×31 时不成立（2³⁴⁰ = (3×341+1)³⁴ ≡ 1 (mod 341)）。

素数有无穷个：设 p₁,…,p_n 为所有素数，根据 q = p₁p₂…p_n+1 可知必然存在一个除 p₁~p_n 之外的新素数。

数值越大，个数越少：[1,100] 25 个；[1000,1100] 16 个；[100000,100100] 6 个；[10000000,10000100] 2 个。

筛法求素数：1914 年 D.N.Lehmer 编制出 10⁷ 以内的素数表。

梅森（Mersenne）素数：形如 M_n = 2ⁿ−1 的素数（n 为素数）。
举例：n = 2(3), 3(7), 5(31), 7(127), 13(8191), 17(131071), 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 21701, …
但 M₁₁ = 2047 = 23×89 不是素数。

费马（Fermat）素数：形如 F_n = 2²ⁿ+1 的素数（n 为自然数）。
举例：n = 1(5), 2(17), 3(257), 4(65537), …
但 F₅ = 4294967297 = 641×6700417 不是素数。

威尔逊（Wilson）判别法：n 是素数的充要条件是 (n−1)! ≡ −1 (mod n)

费马（Fermat）判别法：如果 n 为素数，(a,n) = 1，那么 aⁿ⁻¹ ≡ 1 (mod n)

费马伪素数：设 n 是奇数，(n,a) = 1，如果 aⁿ⁻¹ ≡ 1 (mod n)，则整数 n 对于基数 a 是费马伪素数。
举例：整数 n = 63 对于基数 a = 8 是伪素数；整数 n = 341 对于基数 a = 2 是伪素数。

① Fermat 算法
原理：由费马判别法可知，若 n 不是素数，则 a⁽ⁿ⁻¹⁾ (mod n) 的值不恒为 1。
描述：(1) 随机选 2 ≤ a ≤ n−2；(2) 计算 r ≡ aⁿ⁻¹ (mod n)。r ≠ 1 ⟹ n 为合数，终止；r = 1 ⟹ n 大于 50% 概率为素数，继续。

② Lehmann 算法
原理：由欧拉判别准则可知，若 n 不是素数，则 a^(n−1)/2 (mod n) 对于不同的 a 就是随机的。
描述：(1) 随机选 a < n；(2) 计算 a^(n−1)/2 (mod n)。≠ ±1 ⟹ n 为合数，终止；= ±1 ⟹ n 以 50% 概率为素数，继续；(3) 对 a 选 t 次重复，若结果等于 ±1 并不恒为 1，则 n 以 (1 − 1/2^t) 概率为素数。

③ Solovay-Strassen 算法
原理：由欧拉判别准则和二次符号可知，若 n 是素数，则 (a/n) ≡ a^(n−1)/2 (mod n)。
描述：(1) 随机选 a < n；(2) 计算 j = a^(n−1)/2 和 J = (a/n)。j ≠ J ⟹ n 为合数，终止；j = J ⟹ n 以 50% 概率为素数，继续。

④ Miller-Rabin 算法
原理：若 n 是素数，则 Z_n^x 中只有 1 的两个平方根，即 1 和 n−1。
描述：奇整数 n 因式分解为 n−1 = 2^r·m，m 为奇数。若 a^m ≡ ±1 (mod n)，或对某些 0 < s < r 满足 a^2s·m ≡ −1 (mod n)，则 n 是基数为 a 的强伪素数。

发布：1977 年发明，1978 年正式公布。Ron Rivest、Adi Shamir、Len Adleman，2002 年图灵奖。

应用：最广泛，既可加密，又可签名。

数学基础：Euler（欧拉）定理、因子分解难题。

① Pollard's Rho 算法

给定整数 n，设初始值 x = 2，y = x²+1：

1. 计算 g = (x−y, n)
2. 若 1 < g < n，则停止，g 为 n 的一个因子
3. 若 g = 1，x²+1 → x，(y²+1)²+1 % n → y，返回 (1)
4. 若 g = n，失败，需要对算法重新初始化

课件例（n=1133）：(1) 选 x=2, y=5；(2) g = gcd(3,1133) = 1；(3) x = 5，y = (5²+1)²+1 % 1133 = 677；(4) g = gcd(677−5, 1133) = 1；(5) x = 26，y = (667²+1)²+1 % 1133 = 884；(6) g = gcd(884−26, 1133) = gcd(858, 1133) = 11 ⟹ n 的一个真因子为 11。

② Pollard's P−1 算法

选择随机整数 b，1 < b < n：

1. 计算 g = gcd(b, n)，若 g > 1，找到真因子，停止；否则令 p_i = {2,3,5,7,…}
2. 令 i = 0，按 q = p_i，r = floor(log_qn)，计算 b^qr mod n，g = gcd(b^qr−1, n)

课件例（n=9991）：(1) b=3，g = gcd(3,9991) = 1；(2) q=2, r = floor(log₂9991) = 13，3²¹³ mod 9991 = 229，g = gcd(228, 9991) = 1；(3) q=3, r = floor(log₃9991) = 8，3³⁸ mod 9991 = 3202，g = gcd(3201, 9991) = 97 ⟹ n = 9991 的一个因子为 97。

1985 年发表，既可用于数字签名又用于加密。其安全性依赖于离散对数难题。

【密钥生成】
  选取素数 p > 10^150，一个模 p 的原根 g，以及随机整数 d (1 < d < p)
  计算 e = g^d mod p
  则公钥为 (e, g, p)，私钥为 d

【加密 m】选择随机数 k，得到密文对 (a, b)：
  a = g^k mod p
  b = m · e^k mod p

【解密 (a,b)】
  b · a^(-d) mod p = m · e^k · (g^k)^(-d) mod p = m

课件算例：p=11, g=2, 私钥 d=4 ⟹ 公钥 e = 2⁴ mod 11 = 5；加密消息 m=3，选 k=4：
a = 2⁴ mod 11 = 5；b = 3·5⁴ mod 11 = 5
解密 (5,5)：5·5⁻⁴ mod 11 = 3 ✓

特点：通过选择不同的 k，即使是相同的加密密钥，可将相同明文加密成不同的密文对。

1985 年 N.Koblitz 和 V.Miller 分别独立提出了椭圆曲线密码体制（ECC），其安全性依赖于定义在椭圆曲线点群上的离散对数问题（ECDLP）的难解性。

已知有限域 GF(p)（p = qⁿ, q > 3）上的椭圆曲线群：

E_p(a,b): y² = x³ + ax + b (mod p)，a, b ∈ GF(p)，4a³ + 27b² ≠ 0

性质（设 P, Q ∈ E_p(a,b)）：

• P + O = P，P + Q = Q + P（O 为无穷远点）
• 若 P + Q = O，则 Q = −P 为 P 的加法逆元
• 设 P = (x₁,y₁)，Q = (x₂,y₂)，P ≠ −Q，则 P+Q = (x₃,y₃)：
  • x₃ = λ² − x₁ − x₂ (mod p)
  • y₃ = λ(x₁ − x₃) − y₁ (mod p)
  • λ = (y₂−y₁)/(x₂−x₁) 当 P ≠ Q；λ = (3x₁²+a)/(2y₁) 当 P = Q
• 点 Q 的倍数：在 Q 点做一条切线，与椭圆曲线相交于点 S，则 2Q = Q+Q = −S
• 在 E_p(a,b) 中有 P, Q，Q = kP，k < p，则由 k 和 P 算 Q 易，由 P 和 Q 算 k 难

由 Ralph Merkle 和 Martin Hellman 开发，只能用于加密，安全性基于子集和问题，已被证明不安全。

背包问题描述：y = d₁x₁ + d₂x₂ + … + d_nx_n，明文分组长度为 n，消息为 x₁~x_n，密文为 y。

课件例：明文 1 1 0 1 0 1；背包 62 93 81 88 102 37；密文 y = 62+93+88+37 = 280
解密：280 = 62x₁+93x₂+81x₃+88x₄+102x₅+37x₆（需 2⁶ 次测试）

1991 年 NIST 提出 DSA 用于数字签名标准中；美国（2000 年）和中国（2005 年）通过法律颁布数字签名和传统签名具有同等法律效力。

但 RSA 算法的供应商反对：DSA 不能用于加密或者密钥分配；由 NSA 研制，可能有陷门；速度比 RSA 慢；RSA 是事实上的标准。

1994 年该标准被颁布。NIST 1998 年 12 月规定 DSA 或 RSA 签名方案都可用于数字签名，2000 年又颁布椭圆曲线数字签名算法 ECDSA 也可用于签名。

签名的性质：可信，防伪造，防篡改，防抵赖，不可重用。

【密钥生成】
  选择两个大素数 p 和 q，计算 n = pq 以及 φ(n) = (p-1)(q-1)
  选择随机数 1 < e < φ(n)，gcd(e, φ(n)) = 1，计算 d = e⁻¹ mod φ(n)
  公开公钥 (e, n)，保密私钥 (d, p, q)

【签名过程】Alice 对消息 m 签名，得到 s = m^d mod n，发送 (m ‖ s)
【验证过程】Bob 验证签名 s：s^e mod n 是否等于 m

签名密钥：签名私钥为 d，验证公钥为 e = g^d mod p

选择 k（gcd(k, p-1) = 1），计算签名对 (r, s)：
  r = g^k mod p
  m = (dr + ks) mod p-1
验证：若 e^r · r^s mod p = g^m mod p，则签名有效

数字签名算法 DSA（Digital Signature Algorithm）：是 ElGamal 和 Schnorr 签名方案的变形；1994 年被 NIST 采纳作为数字签名标准 DSS，使用 SHA 作为散列函数。

【密钥参数】
  p：L 位长的素数，512 ≤ L ≤ 1024，64 | L
  q：160 位的素数且 q | p-1
  g：g = h^((p-1)/q) mod p，1 < h < p-1，g > 1
  用户私钥：d，0 < d < q        用户公钥：e，e = g^d mod p

【签名】选 k < p，计算 m 的签名 (r, s)：
  Alice：r = (g^k mod p) mod q
         s = (k⁻¹(H(m) + dr)) mod q
  发送 (r, s), H(m)

【验证】
  Bob：w = s⁻¹ mod q
       u1 = (H(m) × w) mod q
       u2 = (r × w) mod q
       验证：r == ((g^u1 · e^u2) mod p) mod q

【密钥参数】
  选取素数 p 和 q，且 q | p-1，a ≠ 1 且 a^q ≡ 1 (mod p)
  用户私钥：d，0 < d < q
  用户公钥：e，e = a^(-d) mod p

【签名】选 k < q，计算 m 的签名 (r, s)：
  Alice：x = a^k mod p，r = H(m, x)，s = (k + dr) mod q
  发送 (r, s), m

【验证】
  Bob：x' = a^s · e^r mod p
       验证：r == H(m, x')

DSA 是离散对数签名方案的一种。

选择大素数 p 和 q，q | p-1
选择 g 满足：1 < g < p 且 g^q = 1 mod p
选私钥 d < p，则公钥 e = g^d mod p

【签名与验证】
  选择随机数 k < p，r = g^k mod p，r' = r mod q
  签名等式：a·k = b + c·d (mod q)
  验证等式：r^a mod p 是否等于 g^b · e^c mod p

a, b, c 的值是 r'、m、s 的组合，产生多达 13000 种变型。

由国家密码局发布，主要有 SM 系列。算法公开的有 SM2、SM3、SM4，密钥长度和分组长度均为 128 位。

• 2006 年公布，无限局域网产品使用的 SM4 算法
• 分组长度和密钥长度为 128 位，32 轮，子块 32 位
• 轮函数：X_i+4 = F(X_i, X_i+1, X_i+2, X_i+3, rk_i) = X_i ⊕ T(X_i+1 ⊕ X_i+2 ⊕ X_i+3 ⊕ rk_i)
• 非线性置换：4 个平行的 8 位 S 盒
• 线性置换：C = L(B) = B ⊕ (B<<<2) ⊕ (B<<<10) ⊕ (B<<<18) ⊕ (B<<<24)

2010 年公布，基于椭圆曲线的 SM2 算法。

曲线方程：y² = x³ + ax + b (mod p)

2010 年公布，在 SHA-256 基础上改进的 SM3 算法。

分组长度 512 位，摘要长度 256 位，64 次迭代。

【初始化或填充缓冲区】
  A=0x7380166f  B=0x4914b2b9  C=0x172442d7  D=0xda8a0600
  E=0xa96f30bc  F=0x163138aa  G=0xe38dee4d  H=0xb0fb0e4e

【64 次迭代】
       0x79cc4519   0 ≤ t < 16
  Kt =
       0x7a879d8a   16 ≤ t < 64

                    A ⊕ B ⊕ C                0 ≤ t < 16
  ft = f(t,A,B,C) =
                    (A∧B)∨(A∧C)∨(B∧C)        16 ≤ t < 64

                    A ⊕ B ⊕ C                0 ≤ t < 16
  gt = g(t,A,B,C) =
                    (A∧B)∨(A∧C)              16 ≤ t < 64

        X[t]                                      0 ≤ t < 16
  Wt =
        Q(W_{t-16}⊕W_{t-9}⊕(W_{t-3}<<<15))⊕(W_{t-13}<<<7)⊕W_{t-6}   16 ≤ t < 68

  W′t = Wt ⊕ W_{t+4}    0 ≤ t < 64      Q(x) = x ⊕ (x<<<15) ⊕ (x<<<23)
  P(x) = x ⊕ (x<<<9) ⊕ (x<<<17)

  Vi+1 = ABCDEFG ⊕ Vi
  Vn = ABCDEFG

密码协议又称为安全协议，由密码算法设计而成，在网络环境中提供各种安全服务。

常用"零件"：对称密码算法（DES、IDEA、AES、SM4；RC4）、公钥密码算法（ECC、RSA、SM2）、数字摘要算法（SHA、MD5、SM3）、数字签名算法（RSA、DSA、SM2）。

按仲裁者分：

• 基于对称密码 ⟹ 仲裁协议
• 基于公钥密码 ⟹ 裁决协议
• 区别：裁决协议中仲裁者不直接参与协议执行过程
• 仲裁者：公正的第三方，如公证人、法院、KDC 等

按应用分：保密通信协议、密钥协商协议、身份鉴别协议、数字签名协议、秘密共享协议、盲签名协议、安全计算协议、匿名通信协议……

可以对密码算法和协议的密码技术进行攻击，也可以对协议本身进行攻击。

• 被动攻击：窃听协议的一部分或全部，目的是获取消息，不影响协议的执行
• 主动攻击：改变协议以对自己有利，插入、删除和修改消息，破坏通信等等
• 骗子：协议中的一方，不遵守协议或者破坏协议

1. 通信双方协商密码算法和密钥
2. 发送者将明文 m 加密成密文 c
3. 发送者发送密文消息 c
4. 接收者对密文 c 解密获得明文 m

通信目的：产生临时会话密钥，实现保密通信。

协议思想：使用密码技术，保证密钥传送的安全性（公钥密码 / 对称密码）。

发送过程：将密钥 k 加密成密文 c；接收过程：将密文 c 解密后获得密钥 k。

协议思想：不需要事先分配公钥或者对称密钥。

协议背景：1976 年由 Diffie 和 Hellman 发明，基于离散对数难题，用于密钥分配。（Whitfield Diffie、Martin E. Hellman，2015 年图灵奖获得者）

Alice 和 Bob 共享公开的大素数 p 及原根 g

  选 x                                       选 y
  Alice ──── g^x mod p ──→ 公共网络 ──→ g^y mod p ──── Bob

  共享密钥为 g^(xy) mod p

选择原因（课件给的小例子）：p=7, g=2 → 3；p=7, g=3 → 6

协议扩充：很容易扩充到三人或者更多人。

安全性：易受中间人攻击；可增加计算轮数来增强。

先选取满足方程 y² = x³+ax+b (mod p)，4a³+27b² ≠ 0 的椭圆曲线以及其上的点构成的 Abel 群 E_P(a,b)，G 是 (a,b) 的生成元。

  选 x                                 选 y
  Alice ──── xG ────→ 公共网络 ────→ yG ──── Bob

  共享密钥为 xyG

由 Steve Bellovin 和 Michael Merritt 设计。

思想：用共享密钥 p 加密随机产生的公开密钥 k_Ap，建立会话密钥 k。

Alice（产生 kAp/kAv）           Bob
  ──── A, Ep(kAp) ────────────→  解密得到 kAp，选 k
  ←─── Ep(EAp(k)) ────────────
  ──── Ek(RA) ────────────────→  解密获得 RA，选 RB
  ←─── Ek(RA, RB) ────────────
  解密得 RA 和 RB，验证 RA     解密并验证 RB，通过则采用 k
  ──── Ek(RB) ────────────────→
证明双方确知密钥（防中间人）

对于任意 P, Q, R ∈ G₁ 和 a, b ∈ Z_q^x，有

ê(P,P) ≠ 1
ê(P+Q, R) = ê(P,R) ê(Q,R)      ê(PQ, R) = ê(P,R) ê(Q,R)
ê(R, P+Q) = ê(R,P) ê(R,Q)      ê(R, PQ) = ê(R,P) ê(R,Q)
ê(aP, bQ) = ê(abP, Q) = ê(P, abQ) = ê(P,Q)^(ab)
ê(P^a, Q^b) = ê(P^(ab), Q) = ê(P, Q^(ab)) = ê(P,Q)^(ab)

三个性质：

• 非退化性：存在 P, Q ∈ G₁，使得 ê(P,Q) ≠ 1
• 对称性：存在 P, Q ∈ G₁，使得 ê(P,Q) = ê(Q,P)
• 可计算性：对于任意的 P, Q ∈ G₁，存在一个高效的算法计算 ê(P,Q)

协议思想：使用密码技术，保证签名性质（密文防止篡改，密钥代表身份）。

• 签名过程：将 m 用密钥 k 加密作为消息的签名 s = E_k(m)
• 验证过程：将签名 s 用密钥 k 解密获得 m' = D_k(s) 与 m 比较

场景：Alice 向 Bob 借 50 万。共享密钥 k。

缺点：不能保证签名的性质（因为 Alice 和 Bob 都知道 k，Bob 也能伪造 Alice 的签名）。

改进：引入可信第三方 TTP 参与协议（借据由 TTP 中转，双方各自用共享密钥签名）。

设定：TTP（Trent）与 Alice 共享密钥 k_A，与 Bob 共享密钥 k_B。

                        kA              kA
   Alice: m1 ──EA(m1)──→ c1 ──DA(c1)──→ m1      (① ②)
                        kB              kB
   Trent: m2 = S(A) ‖ m1 ‖ c1                    (③)
                        kB              kB
   Bob:   m2 ──DB(c2)──→ c2 ──EB(m2)──→ m2       (⑤ ④)

签名性质分析：

• 签名可信：由 Trent 提供 S(A) 证明
• 签名不可伪造：只有 Alice 知道 k_A
• 签名不可重用、签名文件不能改变：m₂ 包含了文件消息 m₁ 和 c₁，m₁ 的改变将使得其与 c₁ 不匹配
• 签名不可抵赖：由 S(A) 和 c₁ 证明

缺点：需要仲裁人参与，扩展性差，适用于小规模环境。

用 Alice 的私钥 k_Av，公钥 k_Ap。

Alice ── m ──EAv(m)──→ c ──DAp(c)──→ m ── Bob
                 KAv            KAp

签名性质分析：

1. 签名可信、不可伪造：由 Alice 的私钥保证
2. 签名不可重用：签名是文件的函数
3. 签名文件不能改变：由 Alice 的私钥保证
4. 签名不可抵赖：只有 Alice 拥有私钥

缺点：运算速度慢，效率低。

① 签名方：m ├── H(m) ──→ m1（sha256 摘要）
             │
② 用私钥签名：SAv(m1) ──→ s
③ 发送 m ‖ s
④ 验证方：s ├── VAp(s) ──→ m2     用签名方公钥验证
             │
   再算 H(m) 与 m2 比较，根据 m1 = m2 判断

为什么是 sha256RSA：先用 hash 把任意长消息压成固定短摘要，再用 RSA 对摘要签名，效率大幅提高。

交叉使用"保密通信协议"和"数字签名协议"：

保密通信：m ──EBp(m)──→ c ──DBv(c)──→ m        接收方公钥 / 接收方私钥
数字签名：m ──SAv(m)──→ m‖s ──VAp(s)──→ m      签名方私钥 / 签名方公钥

带加密的数字签名：
签名方 ──SAv(m)──→ s ──EBp(s')──→ c
                m‖s ─────────────────────→ m‖s
验证方 ←── DBv(c) ──→ s' ──VAp(s)──→ m
  签名密钥为 Ap/Av        加密密钥为 Bp/Bv

优化思路（课件作业）：利用混合密码协议和哈希+公钥的数字签名协议进行优化。

签名者参与验证的协议（David Chaum）

密钥关系：私钥 d，公钥 e = g^d mod p
签名过程：签名方对消息 m 签名得到 s = m^d mod p

验证过程：
  验证方选 a, b
    ① x = s^a · e^b ────────→ 签名方
                             签名方计算 z = d⁻¹ mod p-1
    ② ←──── y = x^z mod p
    ③ 验证：y = m^a · g^b mod p

身份鉴别：确认实体是它所申明的，而非假冒。（课件用"天王盖地虎，宝塔镇河妖"、"长江长江，我是黄河"作引子）

哈希函数性质：公开性（算法公开）、扩散性（雪崩效应）、抗碰撞性（x≠y 时 h(x)=h(y) 的概率很小）、单向性（x → h(x) 易，h(x) → x 难）。

单向 hash 链：r → x₀ → x₁ → x₂ → … → x_n−1 → x_n

x_i+1 = h(x_i)，则 x_i → x_i+1 易，x_i+1 → x_i 难。

前提：拥有共享密钥 k。　思想：根据密钥 k 确认身份。

① Bob ── RA ──→ Alice
② Alice 选随机数 RB，计算 Hk(RA,RB,B) ──→ Bob
③ Bob 计算并比较 RB, Hk(RA,RB,B)
④ Bob ── Hk(RB,A) ──→ Alice
⑤ Alice 计算并比较 Hk(RB,A)

前提：用户保存自己的私钥 k_v，公开公钥 k_p。

思想：拥有与公钥 k_p 对应的私钥 k_v 的人即可确认身份。

Bob ── 请求 ──→ Alice
Bob ── 随机数 r ──→ Alice
Alice ── zs, EAv(r) ──→ Bob      （对 r 加密）
Bob 在数据库中查找 Alice 的公钥 kAp 验证

• 密钥托管：必须在加密系统中加入能够保证法律执行部门可方便获得明文的密钥恢复机制，否则将不允许推广使用，并于 1993 年颁布了 EES 标准。
  矛盾：政府主张托管一把密钥用于反恐（国家安全）；民间团体质疑后门大开侵犯隐私（公民隐私）。
• 核按钮手提箱：总统、国防部长和参谋总长中有两个被按下按钮，俄军战略部门就会收到核打击代码。
• 航天测控网横跨全球，密钥若集中存放一旦被敌方获取将危及航天器安全 ⟹ 门限分割 + 托管备案（(3,5 门限方案) + (2,5 门限方案)）。

简单分割：将秘密简单从物理上分割。

分割前的明文  11011920161008610000
分割后的密文  1101  1920  1610  0861  0000

安全隐患：秘密份额中直接包含明文，安全性差。

加密分割：将秘密通过加密变换成若干密文。

选择 4 个随机数 k1~k4，计算 c = m ⊕ k1 ⊕ k2 ⊕ k3 ⊕ k4

分割前的明文   m
分割后的密文   c    k1    k2    k3    k4

c ⊕ k1 ⊕ k2 ⊕ k3 ⊕ k4 = m ⊕ k1 ⊕ k2 ⊕ k3 ⊕ k4 ⊕ k1 ⊕ k2 ⊕ k3 ⊕ k4 = m

特点：明文被隐藏，安全性好；但必须全部份额收齐才能恢复（不是门限方案）。

协议思想：(k, n) 门限方案，秘密分割成 n 份，≥k（k < n）份可恢复。

【秘密分割】
  1. 构建 k-1 次多项式  f(x) = m + a1x + a2x² + … + ak-1x^(k-1)  mod p
  2. 计算 Di = f(i)，i = 1, …, n
  3. 将 D1, D2, …, Dn 分给 n 个人保管

【秘密恢复】（拉格朗日插值）
  1. 获取 k 个秘密份额 Dj1, Dj2, …, Djk
  2. 计算 f(x) = Σᵢ ( Dji × Π_{s≠i} (x - js)/(ji - js) ) mod p
  3. 恢复的秘密 m = f(0)

选取 n 个严格递增的 m1, m2, …, mn，满足 gcd(mi, mj) = 1
计算 Mt = t 个 mi 的乘积
  Sk     = m1 × m2 × … × mk-1 × mk
  Lk-1   = mn × mn-1 × … × mn-(k-1)+1
要求 Sk ≥ (N+1)Lk-1，N 为一个大的整数
对于任意的秘密 x（Lk-1 < x < Sk）
计算：ai = x % mi
则 {(a1,m1), (a2,m2), …, (an,mn)} 是一个 (k,n) 门限方案

课件数值：m₁=9, m₂=11, m₃=13, m₄=14

取 k=3, n=4：S₃ = 9×11×13 = 1287；L₂ = 14×13 = 182；满足 182 < 500 < 1287。

则消息 x = 500 的 (3,4) 门限方案为：{(5,9) (5,11) (6,13) (10,14)}

a1 = 500 mod 9  = 5
a2 = 500 mod 11 = 5
a3 = 500 mod 13 = 6
a4 = 500 mod 14 = 10

Alice 选择 5 个比 p-1 小的整数 S1 ~ S5
Alice 的私钥为：S = (S1 + S2 + S3 + S4 + S5)
公钥为：t = g^S mod p
  计算 ti = g^(Si) mod p

   Alice ── S1, t1 ──→ 1 号托管人
                    : i 号托管人
   Alice ── t ──→ Bob    对 ti 签名，保存 Si
   Bob 验证：t = t1 × t2 × t3 × t4 × t5 mod p
   成立则认可该公钥

特点：公钥的托管，可靠性验证。

1. 不协商密钥能否进行保密通信？（对应三次传输协议）
2. 网络虚拟世界如何保证公平性？（对应智力扑克、不经意传输）

协议目的：允许 Alice 和 Bob 在不知道对方密钥的情况下通信，不能防止中间人攻击。

协议描述：Alice 和 Bob 协商一个加密算法 E。算法可公开，满足交换律，如 RSA、异或。

A 方加密        B 方选择        A 方解密       B 方解密
原始明文  m ──EkA(m)──→ 密文 ──EkB(EkA(m))──→ ──EkB(m)──→ ──→ 获得明文 m

Alice：选 kA 对 m 加密：EkA(m) ──→
Bob：  选 kB 对信息加密：EkB(EkA(m)) ──→
Alice：用 kA 对信息解密：EkB(m) ──→
Bob：  用 kB 对信息解密：m ✓

三次传输协议的特点：重重加密，依次解密；加解密的运算顺序可交换。

思考题：能否用异或运算？分析安全性？

（异或的问题：EkA(m) = m ⊕ kA，则 EkB(EkA(m)) = m ⊕ kA ⊕ kB；Alice 用 kA 解密得到 m ⊕ kB，再传给 Bob，Bob 用 kB 解密得到 m。看上去可行，但攻击者若截获全部三段，可推出 kA ⊕ kB 等信息，安全性差。）

在很多协议中密钥的安全性很重要，由可信的 TTP 产生和分配。如何避免 TTP 知道用户选择的密钥？

协议思想：TTP 产生足够长的密钥序列，用自己的公钥加密传到网上。Alice 挑出其中一个用自己的公钥再加密。

Alice 密钥 Ap/Av，TTP 密钥 Kp/Kv

TTP：EKp(ki) 加密后发布一批 ──────→ 网上
Alice：选其中一个，用 Ap 再加密
        EAp(EKp(ka))
TTP：用 Kv 解密得到 EAp(ka)，但看不到 ka
Alice：用 Av 解密得到 ka ✓

协议特点：保证密钥的保密性，减弱对 KDC 安全性的依赖。

Alice 和 Bob 通过网络玩五张牌游戏，如何保证保密性和公平性。

思想：Alice 发牌，每人发五张牌。Alice 产生 52 个消息 m₁~m₅₂，用自己的公钥 Ap 加密，发送给 Bob。

① Alice 产生 m1~m52
   c1~c52 = EAp(mi) ──────────→ Bob

② Bob 随机选五张：EBp(EAp(mj)) ──→ Alice
③ Alice 用 Av 解密 → EBp(mj) ──→ Bob 用 Bv 解密获得自己的牌

④ Bob 另随机选五张：EAp(mk) ──→ Alice 用 Av 解密获得自己的牌

协议特点：公钥密码算法，避免网络游戏的作弊。

关键：Bob 选牌时是"盲选"（Alice 不知道他选了哪几张）；Alice 拿到自己牌的同时无法知道 Bob 的牌。

Alice 将两个秘密中的一个传给 Bob，但不知 Bob 收到其中的哪一个。

变体：1/2-out-of-1、1-out-of-2、1-out-of-n、m-out-of-n

Alice 产生 kp1/kv1 和 kp2/kv2
  ① kp1, kp2 ────────────────→ Bob
  Bob 选择对称密钥 k
  ② ←──── Epi(k) ────────────   （Bob 用其中一对公钥加密）
  ③ Alice 解密：Dvj(Epi(k)) = k  (i=j)
                Dvj(Epi(k)) = k' (i≠j)
  ④ Ek(m1), Ek'(m2) ─────────→ Bob
  ⑤ Bob 用 k 解密得到消息的一部分

思考：是否可用 ⊕ 实现？

应用：隐私保护的安全计算。

解决互不信任的参与方之间保护隐私的协同计算问题。

生活中的例子：

• 数据挖掘（"购买了该商品的用户还购买了……"、"根据浏览猜我喜欢……"）⟹ 隐私泄露
• 基于位置的服务（导航、兴趣点查询）⟹ 隐私保护、可追溯性
• 离线支付 ⟹ 同态加密

核心问题：如何在数据保密的同时实现数据的运算？

同态加密：具有同态性质的加密函数满足

D(E(a) ⊗ E(b)) = a ⊗ b

应用场景举例：钱包余额 ≥ 支付金额（在不知道具体金额的前提下完成判断）

无线传感器网络中的节点可能新加入、可能退出、可能叛变。

思考：如何解决在广播或组播环境下节点之间的保密通信问题？

协议思想：A 将消息 m 用会话密钥 k_s 加密，然后分别用和 B、C、E 的共享密钥 k_B, k_C, k_E 加密 k_s 后广播。

广播内容：Eks(m)  ‖  EkB(ks), EkC(ks), EkE(ks)

协议分析：A 做 4 次加密计算，广播数据包 4 个；每个接收者做 3 次或 4 次解密计算。

协议目的：敏感信息保护机制中，实现机密性和不可否认性。如网络竞标中如何保证投标者不变更价格。

协议描述：Alice 对 Bob 承诺一个位，直到某个时间后才揭示，承诺后不能改变想法。

协议目的：A 要向 B 证明她拥有一些秘密，且在证明中不泄漏任何信息。

协议描述：采用交互式协议的形式：B 问 A 一系列与秘密无关的问题，若 A 知道秘密，她能回答所有问题；否则只有 50% 的机会欺骗。

签名者不知道所签文件的内容。如公证员只要证明某一时刻公证过这个文件，并不关心文件内容。

Alice 和 Bob 想签订合同，已经协商好内容，但每个人都想等对方签名后再签。

生活中的投票需求：授权、防篡改、投一次、确保选票计算、保密（防止欺骗、保护隐私）。

课前思考的问题：如何设计投票协议，使投票具有现场投票的效果（即实现"匿名"）？

事例：Alice、Bob 和 Carol 在餐馆进餐，账单匿名支付，能否确定是他们三人中的一个付账还是 NSA 付账？

游戏：两两抛币，每个人说出与其他两人抛币的正反面是"相同"或"不同"；付账的人说假话。

判断依据：说"不同"的人数为
  奇数 ⟹ 三人中的一个在付账
  偶数 ⟹ NSA 付账

• 匿名性（Anonymity）：一种在一组对象中不被识别的状态。
• 不可关联性（Unlinkability）：不能获得系统中对象之间是否相关的判断。
• 不可观察性（Unobservability）：不能观察到对象是否发送或接收了消息。

匿名集：S = {s₁, s₂, …, s_n}，经过若干中间节点 P₁, P₂, …, P_l 到达 R。

• 通信关系安全：消息的发送者与接收者的保密性
• 身份匿名（Identity Privacy）：源节点和目的节点的身份信息是保密的，它们也不知道路径上中间节点的真实身份（发送者匿名、接收者匿名、通信关系匿名）
• 位置匿名（Location Privacy）：源节点和目的节点的具体位置是保密的，其他节点不知道它们到源节点或目的节点的跳数
• 路由匿名（Route Privacy）：不管攻击者是否在转发路径上，它都不能进行数据包追踪到源节点或者目的节点

2019 年 10 月 24 日，国家领导人在中共中央政治局学习中指出要加快推动区块链技术和产业创新发展，把区块链作为核心技术自主创新。

依赖大量的第三方中介机构才能保证电子货币的流通，不仅引入中心化的风险，也提升了传输成本，必然会要求一个与之匹配的高效可靠的价值传输系统。

• 电子支付：银行账户上做数字的加法和减法，只有银行有记账权。
• 新型货币：如何创造新型支付体系，大家都有权来记账，如比特币。

通过构造一个以竞争 — 记账 — 奖励为核心的经济系统解决了去中心化记账的难题。

应用领域：金融领域、票据管理、产品溯源、存证取证、数据共享。

用于在分散的计算机网络中达成协议、信任和安全的方法。

作用：确保所有参与者都能够对网络事件进行有效记录。

分类：竞争式或投票式原理，包括权益证明、工作证明等。

课件拓展：从原理、特点和应用角度综述区块链协议中的共识机制。

• 起源：2008 年，一位化名为中本聪的人，在一篇为《比特币：一个点对点的电子现金系统》的论文中首先提出比特币
• 运行：2009 年，系统开始运行，用于交易和炒作
• 记账权：工作量证明 POW（Proof of Work）
• 挖矿：寻找 Nonce 满足 h(Nonce ‖ Prev_Hash ‖ Tx) < Bits
  • h() —— SHA256 哈希函数
  • Bits —— 目标值，48 个 0 开始的比特串；每 10 分钟产生一个块；每 2016 个块后（两周 = 2016×10 分钟）调整
  • Nonce —— 是一个答案且对于每个区块是唯一的，第一个找出 Nonce 的用户得到奖金
• 账本：全世界的矿机共同维护一个比特币历史交易记录
• 奖励减半：50 BTC（210000 个块 / 4 年）→ 25 BTC → 12.5 BTC → …… 即 50×(1/2)ⁿ；预计 2140 年全部 BTC 被挖完（21×10⁶ 个）

为什么需要"模式"：对称密码算法的输入固定，而明文消息长度不定，因此加密时要对明文分组再进行加密运算。

• DES：64 位
• AES：128 位

四种基本模式：ECB 模式（基本密码）、CBC 模式（一些反馈）、CFB 模式（一些简单运算）、OFB 模式。

思考的问题：如果密文被替换，是否影响解密？在实际应用中，是否存在安全问题？

消息尾部可能会出现一个短分组；采用一些方式将其填充成一个完整的分组。规则模式和密文挪用两种填充方案。

① 规则模式：全 0、全 1 或者 0,1 交替填充。

X X X 00 0 0 5      ← 最后的 5 表示填充了 5 个字节

② 密文挪用：把前一个分组的密文"借"一部分来补足最后一个短分组。

明文分组  P1   P2   …   Pn-2  Pn-1  Pn
          Ek   Ek        Ek    Ek    Ek
密文分组  C1   C2   …   Cn-2  Cn-1  Cn

ECB 模式又称为电子密码本模式，最简单，每一分组独立进行加密或解密处理。

明文分组  P1   P2   …   Pi-1  Pi   …
          Ek   Ek        Ek    Ek
密文分组  C1   C2   …   Ci-1  Ci   …

加密：Ci = Ek(Pi)
解密：Pi = Dk(Ci)

CBC 模式是将前一分组的加密结果反馈到当前分组的加密中。

明文分组  P1   P2   …   Pi-1  Pi   …
IV  ⊕         ⊕         ⊕     ⊕
    Ek        Ek        Ek    Ek
密文分组  C1   C2   …   Ci-1  Ci   …

加密：Ci = Ek(Pi ⊕ Ci-1)
解密：Pi = Ci-1 ⊕ Dk(Ci)

CFB 模式中的反馈在分组内和分组间进行。

                        Ci-1
                          ↓
                       加密（k）
                          ↓
        最左端字节 j=1~8   kj   C'i-1
                          ↓
                Pij  ⊕ ──→ Cij

模式分析：一开始 C₀ 用 IV 填充，然后加密成 C₀'，将 C₀' 和 P₁ 的低 8 位异或，形成密文的 8 位，并将此 8 位加入到 C₀ 的序列中，重复此过程，直到 P₁ 加密完毕，形成 C₁。

CFB 模式
明文分组  P1    P2    …   Pi-1   Pi   …
IV Ek  ⊕      ⊕         ⊕      ⊕
            Ek         Ek     Ek
密文分组  C1    C2    …   Ci-1   Ci   …

加密：Ci = Pi ⊕ Ek(Ci-1)
解密：Pi = Ci ⊕ Ek(Ci-1)

（说明：课件上解密式写作 D_k(C_i−1)，但 CFB 的正确形式是加解密都用加密函数 E_k —— 因为 CFB 把分组密码当作"密钥流发生器"来用，两个方向都只做加密运算。答题时按课件写法即可，理解上按标准形式。）

与 CFB 模式类似，但其反馈机制独立于明文和密文，因此可以将大部分工作于明文前（即可以预先算出密钥流）。

                        Si-1
                          ↓
                       加密（k）
                          ↓
        最左端字节         ki      S'i-1
                          ↓
                Pi  ⊕ ──→ Si ──→ Ci

模式分析：一开始 S₀ 用 IV 填充，然后加密成 S₀'，将 S₀' 和 P₁ 的低 8 位异或，形成密文的 8 位，并将 S₀' 的 8 位加入到 S₀ 的序列中，重复此过程，直到 P₁ 加密完毕，形成 C₁。

明文分组  P1    P2    …   Pi-1   Pi   …
          ⊕     ⊕          ⊕      ⊕
IV Ek           Ek         Ek     Ek
密文分组  C1    C2    …   Ci-1   Ci   …

加密：Ci = Pi ⊕ Si，Si = Ek(Si-1)
解密：Pi = Ci ⊕ Si，Si = Ek(Si-1)

简单地将分组密码算法的输入与前面所有密文分组的异或值相异或。

加密：Ci = Ek(Pi ⊕ Fi)     Fi+1 = Fi ⊕ Ci
解密：Pi = Fi ⊕ Dk(Ci)     Fi+1 = Fi ⊕ Ci
其中：F1 = IV

与 CBC 模式不同的是，在加密前将前面的明文分组、密文分组及当前明文分组相异或。

明文  Pi-1   Pi   Pi+1
      ⊕      ⊕     ⊕
      ⊕      ⊕     ⊕
      Ek    Ek    Ek
密文  Ci-1   Ci   Ci+1

加密：Ci = Ek(Pi ⊕ Ci-1 ⊕ Pi-1)
解密：Pi = Ci-1 ⊕ Pi-1 ⊕ Dk(Ci)

PCBC 模式被用在 Kerberos 4 中，但 Kerberos 5 发现了其存在问题，用 CBC 模式取代。

密码系统 = 明文、密文、加解密算法、密钥、密钥空间。

思考：密钥如此重要，如何管理？

密钥生成 → 密钥存储 → 密钥传输 → 密钥使用 → 密钥更新 → 密钥销毁

普通密钥泛指人们生活中的各种登录口令。

口令选择：人们选择自己的密钥时，通常选择一个弱密钥，如选择的是 zs111 而不是 *9(hH/A。

字典攻击：根据用户信息尝试最可能的密钥。

• 用户姓名、电话、身份证、帐户等有关信息
• 各种单词的不同置换形式，如大小写、简写

撞库攻击：攻击者先通过收集互联网已泄露的用户+密码信息，生成对应的字典表；再用字典中罗列的用户和密码，尝试批量登录其他网站。

拖库攻击：攻击者入侵有价值的网站，把注册用户的资料数据库全部盗走的行为。（互联网各种信息泄露事件）

随机密钥一般应用于各种网络通信中。

任意由确定过程生成的随机数序列，从实际意义上讲都不是随机的。

伪随机数发生器 PRNG（pseudo-random number generators）：随机数产生的周期足够长。

• 线性同余发生器（见 2.2.2）
• 反馈移位寄存器（见 2.2.3）

[参考] Paul Garrett 著，吴世忠等译. 密码学导引. 机械工业出版社

Kerberos：应用于 TCP/IP 网络的可信第三方鉴别协议。

最初是在麻省理工学院为 Athena 项目开发的模型，基于对称密码。

Kerberos 有一个保存所有客户及其共享密钥的数据库，能：

• 产生消息向一个实体证实另一个实体的身份
• 产生会话密钥，加密双方之间的通信

① 票据（Ticket Granting Ticket，TGT）：用作向服务器提供身份鉴别，包括客户名、服务器名、网络地址、时间标记和会话密钥。

T_c,tgs = { c, tgs, addr, realm, t, K_c,tgs }

② 鉴别码（Authenticator）：客户每次需要使用服务器上的服务时，都要产生一个鉴别码，包括用户名、时间标记和网络范围。

A_c,s = { c, s, realm, t }

使用不同浏览器访问银行网站，可能出现两种不同的结果。

思考：为什么出现两种不同的结果？（一种是受信任的证书 ⟹ 安全连接；一种是证书不受信任 ⟹ 警告）

网络中公钥的获得（三条途径）：

• 从对方处获得
• 从可信的中央数据库获得
• 从自己的私人数据库获得

问题：如何保证可靠性？⟹ 避免中间人攻击⟹ 数字证书

概念：公钥证书 ⟹ 身份鉴别（像"身份证"、"名片"）。

定义：简称证书，由可信的证书机关 CA 将公钥的值绑定到持有对应私钥的个人、设备或服务的身份。

• ISO 鉴别框架：X.509 标准，于 1988 年公布
• 国际电信联盟-电信（ITU-T）部分标准和国际标准化组织（ISO）的证书格式标准
• 定义了公开密钥的证书结构
• 是 PKI（公钥基础设施）的重要组成部分

三个问题：通过证书对身份的信任程度？谁可以作为唯一可信实体？证书链可以有多长？

答案：一个唯一可信任的实体 ⟹ 可信任代理机构 CA。

• 主机将颁发者证书放到主机的受信任根证书颁发机构的证书存储区，将其指定为受信任的根颁发机构。
• 中间的或从属的证书颁发机构受到信任的条件是：他们拥有受信任根证书颁发机构的有效证书路径。