开场

密码学（Cryptography）先回答的不是某个具体算法，而是“系统到底想保护什么”。如果从网络安全的角度看，它主要围绕保密性（Confidentiality）、完整性（Integrity）和可用性（Availability）展开。真实性（Authenticity）也需要单独看待，因为很多场景里，攻击者不只是偷看，还会伪造、篡改，甚至冒充通信一方。

在这一讲里，最核心的模型仍然是 Alice、Bob 和 Eve。Alice 想把消息发给 Bob，Eve 可以拦截、修改、伪造消息。这个模型和 COMP3357 里的私钥密码学导论是一致的，这里不再赘述，读者可以参考 COMP3357 第 1 讲：私钥密码学导论。

密码学要保护什么

理解密码学的保护对象，可以先从资产（assets）开始。硬件和软件当然要保护，但真正不可替换的是数据。硬盘坏了可以换，系统坏了可以重装，文档、邮件、照片、交易记录一旦泄露或被篡改，往往就很难恢复原样。

所以 crypto 的目标不是单纯把内容藏起来，而是围绕三类风险建立机制。

  • 保密性（Confidentiality）是别人看不懂
  • 完整性（Integrity）是别人改不了，或者改了能被发现
  • 认证和真实性（Authentication）是别人不能冒充

明文、密文、加密和解密

以下是密码学里最基本的几个概念：

  • 明文（Plaintext） 是原始的、可读的消息
  • 密文（Ciphertext） 是加密后的、不可直接读的消息
  • 加密（Encrypt） 是把明文变成密文
  • 解密（Decrypt） 是把密文恢复成明文
  • 密钥（Key） 是决定算法输出的那段信息

他们的关系可以被定义为：

$$ C = E(P, K), \qquad P = D(C, K) $$

这里 $E$ 是加密算法，$D$ 是解密算法，$P$ 是明文，$C$ 是密文，$K$ 是密钥。

也就是说，加密算法 $E$ 把明文 $P$ 和密钥 $K$ 变成密文 $C$，解密算法 $D$ 则把密文 $C$ 和同一个密钥 $K$ 变回明文 $P$。我们可以发现，密钥是整个加密系统的核心。只要密钥被泄露，整个系统就不再安全。

经典密码只是起点

最经典的加密算法是大家熟知的 Caesar cipher。它的规则很简单，明文字母整体平移固定步数 $K$，比如移 3 位。数学上可以写成

$$ C = P + K \pmod{26}, \qquad P = C - K \pmod{26} $$

然而，我们一进来就发现两个问题：

第一，密码学里的“安全”不能只靠方法古老。Caesar cipher 太容易被暴力枚举，密钥空间只有 26 种。

第二，密钥空间变大也不够。把字母任意替换的单表代换密码（substitution cipher）虽然有很大的密钥空间，但频率分析（frequency analysis）会把它拆开。也就是说，攻击者不一定靠试钥匙，也可以靠统计结构。

这部分和 COMP3357 里的古典密码分析是重合的。想看更完整的攻击模型、频率分析和“密钥空间大不等于安全”的概率视角，可以直接回看 COMP3357 第 1 讲。

对 Caesar cipher 这种线性移位来说，加密多次并不会让它真正变强，因为多次移位合起来还是一次移位。它最多只是把同一个弱方案换成了另一个弱方案。

现代密码学

现代密码学会把密码系统拆成两个明确的算法。

  • 加密：$C = E(P, K)$
  • 解密：$P = D(C, K)$

在这里，加密和解密使用的密钥可以是同一个，也可以是不同的。前者叫 对称密钥算法（symmetric-key algorithm），后者叫 非对称密钥算法（asymmetric-key algorithm）。

对称密钥

如果加密和解密用的是同一个密钥，就叫对称密钥算法（symmetric-key algorithm）。这类系统的难点在于密钥分发。Alice 和 Bob 必须先安全地共享一个密钥，然后才能在不安全信道上通信。

一次一密与流密码

One-time Pad（一次一密）把明文的每一位和密钥的对应位做异或（XOR）。由于异或满足 $x\oplus y\oplus y=x$，同一个密钥既能用于加密，也能用于解密：

$$ C = P \oplus K, \qquad P = C \oplus K $$

只要密钥是真随机、长度和明文一样长，而且只使用一次，它就能达到完美保密（perfect secrecy）。问题也很明显，密钥太长，分发成本太高，而且一旦重复使用，就会出现

$$ C_1 \oplus C_2 = P_1 \oplus P_2 $$

攻击者就能从两段密文中推导出两段明文之间的关系。

RC4 属于流密码（stream cipher）。它并不要求密钥本身和明文一样长，而是先由短密钥生成伪随机密钥流（keystream），再把密钥流和明文按位异或：

$$ C_i=P_i\oplus K_i. $$

这里的 $K_i$ 不是原始密钥的第 $i$ 位，而是 RC4 输出的第 $i$ 个密钥流字节。RC4 的生成过程通常分为两步：密钥调度算法（Key-Scheduling Algorithm，KSA）先根据输入密钥初始化一个 256 字节的状态数组，伪随机生成算法（Pseudo-Random Generation Algorithm，PRGA）再不断更新状态并输出密钥流。

RC4 的工程地位需要谨慎理解。它曾经被用于 WEP、WPA、SSL 和 TLS 等场景，但后来暴露出密钥流偏差等安全问题，TLS 中的 RC4 已在 2015 年被禁止继续使用。因此，RC4 适合用来理解“密钥流 $\oplus$ 明文”的流密码思想，不应作为现代系统的新选择。

DES 与分组密码结构

DES（Data Encryption Standard）属于分组密码（block cipher）。它每次处理 64 位数据块，密钥表面上是 64 位，但每个字节有 1 位用于奇偶校验，实际进入算法的有效密钥长度是 56 位。

DES 的核心不是一次简单替换，而是多轮 Feistel 结构。加密过程先做初始置换（Initial Permutation, IP），再把 64 位数据分成左右两半 $L_0,R_0$。第 $n$ 轮可以概括为

$$ L_n=R_{n-1},\qquad R_n=L_{n-1}\oplus f(R_{n-1},K_n). $$

其中 $K_n$ 是第 $n$ 轮子密钥，$f$ 是轮函数。轮函数会把 32 位右半部分扩展为 48 位，与子密钥异或后送入 S-box；每个 S-box 把 6 位输入压缩为 4 位输出，最后再经过置换。这个设计把替换和置换交替使用，使局部输入变化逐渐扩散到整个分组。

DES 的主要弱点在于密钥空间过小。56 位密钥在设计初期还具有现实阻力，但随着专用硬件和并行计算的发展，穷举成本不断下降。Triple DES 曾经作为过渡方案延长 DES 的生命周期，但它并没有改变 DES 块长较短、设计较旧的事实。

AES 的位置

AES（Advanced Encryption Standard）是 Rijndael 算法被标准化后的名称。它同样是分组密码，但块大小固定为 128 位，密钥长度可以是 128、192 或 256 位，对应 10、12 或 14 轮。

AES 不采用 DES 的 Feistel 结构，而是把 128 位分组看成一个状态矩阵，并在每一轮中执行若干类操作：字节替换（SubBytes）提供非线性，行移位（ShiftRows）和列混合（MixColumns）扩散局部变化，轮密钥加（AddRoundKey）把密钥材料注入状态。它们共同服务于两个目标：

  • 混淆（confusion）：让密文和密钥、明文之间的关系尽量复杂。
  • 扩散（diffusion）：让明文或密钥中的微小变化影响尽可能多的密文位。

因此，DES 和 AES 都是分组密码，但它们处在不同的历史阶段。DES 展示了早期标准化分组密码的基本结构，AES 则代表了更现代的参数规模和设计方法。

对称密钥体系还有一个很现实的问题，就是密钥爆炸（key explosion）。如果系统里有 n 个用户，每一对用户都要一把单独的共享密钥，那么总密钥数就是

$$ \frac{n(n-1)}{2} $$

用户越多，新增用户时需要补充的共享密钥就越多，分发和管理复杂度也会随之上升。

非对称密钥

如果加密和解密使用不同的密钥，就叫非对称密钥算法（asymmetric-key algorithm） 或者公钥密码学（public-key cryptography）。

公钥系统把密钥分发问题换成了密钥绑定问题。每个用户有一把公钥和一把私钥，公钥可以公开，私钥必须保密。对 $n$ 个用户而言，系统大致只需要 $2n$ 把密钥；新增一个用户时，主要是生成并发布一对新密钥，而不是和每个旧用户分别建立共享密钥。

需要注意，公钥公开不等于可以随意相信。真正的系统还必须回答“这把公钥到底属于谁”，这会引出后续的证书和 PKI。这里只先讨论公钥算法本身。

RSA 需要的数论基础

RSA 依赖几个初等数论概念。

  • 因子（factor）：若 $B$ 能整除 $A$，则 $B$ 是 $A$ 的因子。例如 $12$ 的因子包括 $1,2,3,4,6,12$。
  • 素数（prime）：只有 $1$ 和自身两个正因子的整数。$1$ 不是素数，$2,3,5,7,11$ 是素数。
  • 互素（coprime）：两个整数的最大公因数为 $1$。例如 $12$ 和 $5$ 互素，$12$ 和 $18$ 不互素。
  • 模运算（modulo）：记录整数除法的余数。例如 $53\bmod 5=3$，因为 $53=5\cdot 10+3$。

最大公因数（Greatest Common Divisor，GCD）可以高效计算。欧几里得算法的基本递推是

$$ \gcd(a,b)=\gcd(b,a\bmod b). $$

这件事在 RSA 中很重要：如果两个公开模数 $N_1,N_2$ 不小心共享同一个素因子 $P$，那么

$$ \gcd(N_1,N_2)=P $$

就会直接暴露私钥材料。弱随机数生成器导致的重复素因子，曾经在真实 TLS 证书和 SSH 主机密钥中造成过大规模风险。

RSA 还需要欧拉函数。对两个不同素数 $P,Q$，若

$$ N=P\cdot Q, $$

则小于等于 $N$ 且与 $N$ 互素的正整数个数为

$$ \varphi(N)=(P-1)(Q-1). $$

最后还要用到模逆元。若 $e$ 与 $\varphi(N)$ 互素，就存在整数 $d$，使得

$$ e\cdot d\equiv 1\pmod{\varphi(N)}. $$

这个 $d$ 就是 $e$ 在模 $\varphi(N)$ 意义下的逆元。讲义中的写法

$$ d=\frac{k\varphi(N)+1}{e} $$

表达的是同一件事：选择某个整数 $k$，使分子能被 $e$ 整除。

RSA

RSA（Rivest-Shamir-Adleman）发表于 1977 年，是最常见的公钥加密算法之一。它的核心思想是构造一对相互配合的指数：一个公开用于加密，另一个保密用于解密。

RSA 的密钥生成通常从两个素数开始。设

$$ N = P \cdot Q $$

再计算欧拉函数

$$ \varphi(N) = (P-1)(Q-1) $$

然后选一个整数 $e$，要求它和 $\varphi(N)$ 互素，再求出 $d$，使得

$$ e \cdot d \equiv 1 \pmod{\varphi(N)} $$

最后得到公钥 $(e,N)$ 和私钥 $(d,N)$。加密和解密分别写成

$$ C = M^e \bmod N, \qquad M = C^d \bmod N $$

一个小例子可以说明流程。取 $P=3$、$Q=7$，则 $N=21$，$\varphi(N)=12$。选择 $e=5$，因为 $5$ 与 $12$ 互素。再找 $d$ 满足

$$ 5d\equiv 1\pmod{12}. $$

可以取 $d=17$，因为 $5\cdot 17=85=7\cdot 12+1$。因此公钥为 $(5,21)$，私钥为 $(17,21)$。若明文数字 $M=2$，则

$$ C=2^5\bmod 21=32\bmod 21=11, $$

解密时

$$ M=11^{17}\bmod 21=2. $$

真实系统不会使用这么小的数。讲义中用它说明公式成立，但工程上 $N$ 的位数通常是 1024 位、2048 位或更高。明文也必须先编码成数字，再分块并填充；不能把任意文件直接当成一个超大整数输入 RSA。

RSA 的安全性依赖因式分解（factorization）的困难性。攻击者看到的是公钥 $(e,N)$，其中 $N=P\cdot Q$。如果能把 $N$ 分解回 $P$ 和 $Q$，就能计算 $\varphi(N)$，再求出私钥指数 $d$。因此，素数生成质量和模数大小都直接影响安全性。

公开指数 $e$ 也需要谨慎选择。常见选择是 $65537$，也就是十六进制的 0x10001。它足够小，便于高效加密和验签；同时又比 $e=3$ 更不容易触发低指数场景中的风险。

$e=3$ 的典型问题是 Håstad’s Broadcast Attack。假设同一个消息 $M$ 没有正确填充，被分别发送给三个接收者，并且三者都使用 $e=3$：

$$ C_1=M^3\bmod N_1,\qquad C_2=M^3\bmod N_2,\qquad C_3=M^3\bmod N_3. $$

如果 $N_1,N_2,N_3$ 两两互素，中国剩余定理（Chinese Remainder Theorem）可以把这三个同余式合成为一个关于 $X=M^3$ 的同余式。当 $M $$ M^3这时恢复出的 $X$ 就是普通整数意义下的 $M^3$，攻击者直接开三次方即可得到 $M$。问题的根源不是 RSA 公式本身，而是小指数、重复明文和缺失填充共同破坏了安全条件。

实际操作里，RSA 的生成、导出和检查经常交给 OpenSSL 等工具完成。真正需要理解的是：公钥为什么能公开，私钥为什么不能从公钥轻易推出，以及错误参数为什么会把数学困难性变成工程漏洞。

共同建立密钥

一种直接做法是由一方生成密钥，再用某种方式把密钥送给另一方。更合理的做法是让双方共同参与密钥生成，这就引出了 Diffie-Hellman 密钥交换（Diffie-Hellman key exchange）。

这一类协议的本质是，Alice 和 Bob 都参与密钥生成，而不是由一方把密钥悄悄送给另一方。双方先公开参数 $p,g$，再各自保留私有随机数，最后得到相同的共享密钥。

讲义中的例子取

$$ p=23,\qquad g=11. $$

Alice 选择私有数 $a=6$，计算

$$ A=g^a\bmod p=11^6\bmod 23=9. $$

Bob 选择私有数 $b=5$，计算

$$ B=g^b\bmod p=11^5\bmod 23=5. $$

双方交换 $A$ 和 $B$ 后，Alice 计算

$$ K=B^a\bmod p=5^6\bmod 23=8, $$

Bob 计算

$$ K=A^b\bmod p=9^5\bmod 23=8. $$

两边得到同一个共享密钥 $K=8$。旁观者能看到 $p,g,A,B$，但如果参数足够大、选择得当，要从 $g^a\bmod p$ 反推出 $a$ 通常被认为很困难。这就是离散对数问题在密钥交换中的作用。

数字签名

到了数字签名（Digital Signature），需要先分清“签名”和“加密”不是一回事。

加密保护的是内容能不能被别人看懂；签名保护的是内容有没有被改，以及是不是确实来自某个持有私钥的人。也就是说，签名更偏向完整性和认证。

典型流程如下。

  1. 先对文件做哈希，得到消息摘要（message digest）
  2. 再用私钥对摘要做签名
  3. 接收方用公钥验证签名，并重新计算摘要比对

只要文件被改过，摘要就会变，验证就会失败。

讲义中的实验可以这样理解。Alice 直接把文件放到公开网络时，Eve 可以替换文件，Bob 无法判断文件是否被改过。加入签名后，Alice 发送“文件 + 签名”，Bob 用 Alice 的公钥验证签名，并把自己重新计算出的摘要与签名中的摘要比较。

如果 Eve 只修改文件，摘要会不一致；如果 Eve 连签名也修改，公钥验证会失败。因此，签名同时依赖两个条件：私钥不能被 Eve 获得，哈希函数也不能让 Eve 轻易构造相同摘要的不同文件。

哈希函数

哈希算法（Hash Algorithm）把任意长度的数据映射成固定长度的摘要。这里先看两个最常见的用途。

  • 检查文件有没有被修改
  • 作为数字签名的输入

如果原文件改了，哈希值通常会完全不同，所以它能很快发现篡改。

MD5 已经不该再用。原因不是它“看起来旧”，而是碰撞（collision）已经被实质性攻破。只要攻击者能构造出两个不同文件却得到同一摘要，哈希在完整性上的意义就会大幅下降。

一个具体时间点很能说明问题。MD5 在 2004 年被王小云等人攻破，碰撞可以在很短时间内找到。

因此，MD5 不应再被用作安全哈希算法。

讲义最后的 MD5 碰撞实验正是为了说明这一点。如果 Eve 能构造一个不同文件，却让它和 Alice 的原文件具有相同 MD5 摘要，那么 Bob 即使用签名流程检查摘要，也可能被误导。因此，数字签名并不是孤立成立的；它还依赖可靠的哈希算法、正确的密钥管理和清晰的验证流程。

整体理解

密码学不是某一种算法，而是一整套工具箱。你要先分清楚你在保护什么，再分清楚对手能做什么，最后才谈用加密、密钥交换、签名还是哈希。

如果只看实现，很多东西像是不同算法。可一旦放回到目标里，它们其实是在分别解决四件事。

  • 保密性
  • 完整性
  • 认证
  • 密钥如何安全建立

这也是为什么这一讲虽然从经典密码讲起，但最后会落到现代密码系统、密钥交换、数字签名和哈希上。它不是在堆算法名，而是在搭整套通信防护的骨架。

返回目录