• 文档
• 教程
• 知识库

本文以 信息安全（五）——消息认证、数字签名及PGP.md 为核心，系统讲解消息认证（Message Authentication）、散列函数（Hash Function）、数字签名（Digital Signature）与 PGP 邮件加密体系四大主题。读者读完本文后，将掌握鉴别系统的组成与三类鉴别函数、MAC 与 HMAC 的构造原理、散列函数的七项安全需求与生日攻击推导、RSA / ElGamal / DSA 三种签名算法的完整流程与数学证明，以及 PGP 从会话密钥生成到密钥环管理的端到端工作机制，可直接用于 408 信息安全课程复习与网络安全工程实践。

本文属于 CS-Xmind-Note 仓库信息安全系列的第五讲。整个系列以斯托林斯《密码编码学与网络安全（第六版）》为教材骨架，前四讲分别覆盖了信息安全概述、密码学基本概念与经典密码体制、对称密码体制（DES/AES/分组密码工作模式）与公私钥密码体制（RSA/ElGamal/Diffie-Hellman）。本篇在前四讲的基础上，把"保密"（confidentiality）与"鉴别/认证"（authentication）两个概念彻底分离开来，形成一条从消息认证到数字签名再到 PGP 综合应用的完整知识链。

一、消息认证：概念、目的与鉴别模型

1.1 什么是消息认证

消息认证（Message Authentication）是一个证实收到的消息来自可信的源点且未被篡改的过程。它回答两个问题：

• 消息真的是来自声称的发送者吗？
• 消息在传输或存储过程中有没有被改动？

这与加密是本质不同的两个目标：加密解决"别人看不懂"（保密性），消息认证解决"别人改不了、冒充不了、抵赖不了"（真实性与完整性）。

1.2 鉴别的目的

鉴别（Authentication）的主要目的有二：

1. 信源识别：验证信息的发送者是真正的发送者，而不是冒充者；
2. 完整性验证：验证信息在传送或存储过程中未被篡改、重放或延迟。

注意这里把"重放"（replay）和"延迟"（delay）也纳入完整性范畴——攻击者即使不能读懂消息，也可以把旧消息原样重放以制造混乱，因此一个完整的鉴别方案通常还要配合时间戳、序号等防重放机制。

1.3 鉴别系统的组成

一个单纯鉴别系统的模型由三部分组成：发送方的鉴别编码器、接收方的鉴别译码器，以及双方共享的鉴别函数。鉴别编码器和鉴别译码器可以抽象为鉴别函数（Authentication Function）。

一个安全的鉴别系统必须满足三个条件：

1. 接收者能够检验和证实消息的合法性、真实性和完整性；
2. 消息的发送者和接收者不能抵赖（即不可否认性）；
3. 除了合法的消息发送者，其他人不能伪造合法的消息。

要构造这样的系统，首先要选好恰当的鉴别函数，由该函数产生一个鉴别标识（authenticator / tag）；然后在此基础上设计合理的鉴别协议（Authentication Protocol），使接收者能够完成消息的鉴别。

1.4 鉴别函数的三大分类

可用来做鉴别的函数分为三类：

三类函数的地位并不相同：加密函数和 MAC 都依赖密钥，散列函数本身是公开的、无密钥的。散列函数通常作为"压缩器"嵌入 MAC 与数字签名方案中（HMAC、DSA/SHA 组合都是典型例子），因此本文后面的内容实际围绕"散列函数 + 密钥/私钥"的组合展开。

二、基于加密的消息认证：加密认证

用完整信息的密文作为对信息的鉴别，称为加密认证。它分为对称密码体制与公钥密码体制两条路线。

2.1 对称密码体制的加密认证

在对称密码体制下，发送者 A 与接收者 B 共享同一密钥 K。A 用 K 加密明文 M 得到密文 C 并发送；B 用 K 解密。只要解密成功且语义合理，B 就能相信消息来自持有 K 的 A 且未被篡改——因为只有共享密钥 K 的双方能产生和恢复该密文。参见对称密码体制笔记中对 DES/AES 及 ECB、CBC、CFB 等工作模式的讲解，其中 CFB、OFB 等流式工作模式天然适合对逐块到达的消息提供完整性保护。

对称加密认证的主要限制是：密钥必须通过安全信道预先共享，且共享密钥的两方之间无法相互区分——A 可以否认自己发过消息（因为 B 也能用同样的密钥构造密文），所以对称加密认证不能提供数字签名意义上的不可否认性。

2.2 公钥密码体制的加密认证

公钥密码体制下，情况变得微妙：

• 用公开密钥加密明文，只能提供保密而不能提供认证。因为任何人都能用 A 的公钥加密，接收者无法据此判断发送者身份；
• 为了提供认证，发送者 A 用私钥对明文进行加密，任意接收者都可以用 A 的公钥解密。由于只有 A 能够产生该密文，其它任何一方都不能产生该密文，因此这种方式既提供了认证，也提供了数字签名；
• 从效果上看，A 已经用私钥对明文进行了签名；
• 必须注意：只用私钥加密不能提供保密性——任何人只要有 A 的公开密钥，就能对该密文进行解密。

由此引出三个重要结论：

1. 保密性与真实性是两个不同的概念。根本上，信息加密提供的是保密性而非真实性，两者不能混为一谈；
2. 加密代价大（公钥算法代价更大）。对长消息整体做公钥运算在计算上不可接受；
3. 鉴别函数与保密函数的分离能提供功能上的灵活性。理由包括：广播的信息难以使用加密（信息量大）；某些信息只需要真实性、不需要保密性。

正是基于这些考量，实际系统普遍采用"散列函数压缩 + 少量数据签名"的组合，而不是对整条消息做私钥加密。

三、消息认证码 MAC 与 HMAC

3.1 MAC 的基本原理

消息认证码（Message Authentication Code）本质上是带密钥的散列函数，适用于通信双方基于共享的同一密钥来认证彼此之间交互的信息。

MAC 函数将密钥和数据块作为输入，产生一个 hash 值作为 MAC 码。设 M 是变长的消息，K 是仅由收发双方共享的密钥，则 M 的 MAC 由如下函数生成：

$$MAC = C_k(M)$$

其中 $C_k(M)$ 是定长的。发送者每次将 MAC 附加到消息中一并发送，接收者用同一密钥重新计算 MAC 并对消息进行认证。如果收到的 MAC 与本地计算得出的 MAC 相同，则接收者可以认为：

• 消息未被更改过；
• 消息来自与他共享密钥的发送者。

3.2 MAC 与加密函数的区别

MAC 函数类似于加密函数，但二者有一个关键区别：

• MAC 函数不需要可逆性——它只要求"给定密钥和消息，能算出一个定长值"；
• 加密函数必须是可逆的——必须能从密文还原明文。

由于不需要满足可逆性约束，认证函数比加密函数更不易破解，设计空间更大、性能也更好。

3.3 MAC 的边界与 HMAC

需要强调：因为收发双方共享同一个密钥，上述 MAC 过程只提供认证而不提供保密，也不能提供数字签名。接收者能确认消息来自"持有该密钥的另一方"，但无法向第三方证明是哪一方发的——这是对称体制的固有局限。

用散列函数来构造 MAC 是常见做法，HMAC（Hash-based MAC）为其中之一。HMAC 的核心思想是把密钥经过两次填充后与消息混合，再送入公开的散列函数（如 SHA-256）迭代计算，从而把一个无密钥的公开散列函数"改造"成带密钥的 MAC。HMAC 的安全性不依赖于底层散列函数的碰撞抵抗强度（在特定条件下），且实现简单、性能高，因此在 TLS、IPsec 等协议中被广泛采用。

四、散列函数：概念、安全需求与生日攻击

4.1 基本概念

散列函数（Hash Function）以一个变长的报文作为输入，产生一个定长的散列码作为输出，有时也称报文摘要（message digest）：

$$h = H(M)$$

其中 M 是变长的消息，h 是定长的散列值（消息摘要）。散列函数又称杂凑函数，是对不定长输入产生定长输出的特殊函数。

散列函数 H 是公开的。典型用法是：散列值在信源处被附加在消息上，接收方重新计算散列值来保证消息未被篡改。

关键安全注意：由于函数本身公开，传送过程中对散列值需要另外的加密保护——如果没有对散列值的保护，篡改者可以在修改消息的同时修改散列值，从而使散列值的认证功能失效。这正是"裸散列只能检测意外损坏、不能抵抗恶意篡改"的原因。

4.2 散列函数的基本用法

用法一：消息认证。用散列函数做消息认证的核心模式是把散列值与消息一起（或以某种受密钥保护的方式）传送，接收方重算散列值并与收到的值比对。常见的几种组合方式包括：散列值用对称密钥加密（等价于带密钥的 MAC）、散列值与消息一起用对称密钥加密（同时提供保密与认证）、散列值用发送方私钥加密（即数字签名）。

用法二：数字签名。先用散列函数压缩消息，再对短小的散列值做私钥运算（签名）。散列函数的无碰撞性保证了签名的有效性——签名短、运算快，且因为找不到另一条消息有相同摘要，签名无法被移植到别的消息上。

用法三：其他应用。包括单向口令文件（系统只保存口令的散列值，不保存明文口令）、入侵检测和病毒检测（为系统文件建立散列指纹，比对发现被篡改的文件）、构建随机函数或伪随机函数等。

4.3 两个简单的 Hash 函数

为理解散列函数的最小工作原理，教材给出两个简化模型：

1. 分组对应位异或：把消息分成若干等长分组，逐位异或（XOR）所有分组，得到定长的散列值。它实现简单，但对分组重排不敏感（异或满足交换律），安全性很弱；
2. 移位分组对应位异或：对每个分组先做循环移位再异或，使散列值依赖分组的相对位置，抗重排能力比简单异或略强。

这两个例子说明：散列函数的本质工作是把"整个消息的结构信息"压缩进一个定长值，压缩方式越能体现消息内部次序与每一位的贡献，抗碰撞能力越强。

4.4 散列函数的安全需求（重点）

散列函数的目的是为文件、消息或其他的分组数据产生"指纹"。用于消息认证的散列函数 H 必须具有如下性质：

1. 输入长度可变：H 能用于任何大小的数据分组；
2. 输出长度固定：H 都能产生定长的输出；
3. 效率：对于任何给定的 x，H(x) 要相对易于计算；
4. 抗原像攻击（单向性）：对任何给定的散列码 h，寻找 x 使得 H(x)=h 在计算上不可行；
5. 抗第二原像攻击（弱抗冲突）：对任何给定的分组 x，寻找不等于 x 的 y，使得 H(x)=H(y) 在计算上不可行；
6. 抗强碰撞攻击（强抗冲突）：寻找任何的 (x, y) 使得 H(x)=H(y) 在计算上不可行；
7. 伪随机性：H 的输入输出满足伪随机性测试标准。

这些性质的工程含义可以逐条对应：

• 第 1、2 条要求具有实用性——任意长输入都能得到定长输出；
• 第 2、3 条合起来是单向性质——给定消息可以产生散列码，而给定散列码在计算上不可能反推出对应的消息；
• 第 4 条保证给定一个消息的散列码，不能找到与之相同的另外的消息，即防止伪造；
• 第 5 条是对生日攻击方法的防御能力。

4.5 弱无碰撞与强无碰撞

从攻击者 Oscar 的视角可以更精确地描述碰撞抵抗。Oscar 以一个 x 开始，先计算 z = h(x)，并企图找到一个 x' 满足 h(x')=h(x)。若他做到这一点，x' 也将是有效消息。为防止这一点，要求函数 h 具有无碰撞特性：

• 定义 1（弱无碰撞）：散列函数 h 称为弱无碰撞的，是指对给定消息 x∈X，在计算上几乎找不到不等于 x 的 x'∈X，使 h(x)=h(x')；
• 定义 2（强无碰撞）：散列函数 h 被称为强无碰撞的，是指在计算上几乎不可能找到任意的相异的 x、x'，使得 h(x)=h(x')。

注意：强无碰撞自然蕴含弱无碰撞。弱无碰撞只防御"针对特定 x 找替身"的攻击；强无碰撞要防御"任意两条消息撞在一起"的攻击，难度更高，也是现代散列函数设计（如 SHA-256）追求的目标。

4.6 生日攻击：为什么 64 位散列码不安全

假定使用 64 位的散列码，是否安全？答案是否定的。考虑这样的场景：采用"传输加密的散列码 + 不加密的报文 M"，对手需要找到 M' 使得 H(M')=H(M)，以便用替代报文欺骗接收者。一种基于生日悖论的攻击可以做到这一点。

生日问题：一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于 1/2？

推理过程如下（假定一年按 365 天计算，每人生日等概率）：

• n 个人生日各不相同的概率为：

$$\frac{365 \times 364 \times 363 \times \cdots \times (365-n+1)}{365^n}$$

• 因而 n 个人中至少有两个人生日相同的概率为：

$$P = 1 - \frac{365 \times 364 \times 363 \times \cdots \times (365-n+1)}{365^n}$$

• 若要使 P ≥ 0.5，n = 23 即可；在 64 人的班级中，"至少两人生日相同"的概率约为 0.997（n=46 时，P ≈ 94.15%）。

把生日悖论推广到散列函数：给定一个散列函数，有 n 个可能的输出（m 位，n = 2^m），输出值为 H(x)。如果产生 k 个随机输入 y，要使至少存在一个输入 y 使得 H(y)=H(x) 的概率大于 0.5，k 必须多大？

• 对单个 y，H(y)=H(x) 的概率为 1/n，H(y)≠H(x) 的概率为 1-(1/n)；
• 产生 k 个随机值 y，它们两两不匹配的概率等于每个个体不匹配概率的乘积，即 $[1-(1/n)]^k$；
• 因此至少有一个匹配的概率为 $1 - [1-(1/n)]^k \approx 1 - [1 - k/n] = k/n$；
• 要概率等于 0.5，只需 $k = n/2 = 2^{m-1}$；
• 更一般地，对长度为 m 位的散列码，共有 $2^m$ 个可能的散列码。若要使任意的 x、y 有 H(x)=H(y) 的概率为 0.5，只需 $k = 2^{m/2}$。

结论：散列码的有效安全强度只有其比特长度的一半。64 位散列码只需约 $2^{32}$ 次尝试就能以 50% 的概率找到碰撞，这在现代计算机上轻而易举。这也是为什么现代散列函数至少要 160 位（如 SHA-1，也已告急）乃至 256 位（SHA-256）输出。

4.7 散列函数的结构：Merkle 迭代结构

现代散列函数普遍采用 Merkle 于 1989 年提出的迭代结构（Merkle-Damgård 结构），Ron Rivest 于 1990 年提出的 MD4 即基于此，该结构几乎被所有 hash 函数使用。

具体做法：

1. 把原始消息 M 分成一些固定长度的块 $Y_i$；
2. 最后一块做填充（padding），并使其包含消息 M 的长度；
3. 设定初始值 $CV_0$（chaining value）；
4. 重复使用压缩函数 f：$CV_i = f(CV_{i-1}, Y_{i-1})$；
5. 最后一个 $CV_i$ 即为 hash 值。

这种"分组 + 链式压缩"的框架，使得一个只能处理固定长度输入的压缩函数 f，可以安全地处理任意长度的消息，并且每一比特的变化都会通过链式传播影响最终摘要。

4.8 MD5 算法

历史脉络：

• Merkle 于 1989 年提出 hash function 模型；
• Ron Rivest 于 1990 年提出 MD4；
• 1992 年，MD5（RFC 1321）由 MIT 的 Ron Rivest 开发。

MD5 的技术要点：

• MD5 把数据分成512-bit 块处理；
• MD5 的 hash 值是128-bit；
• 在最近数年之前，MD5 是最主要的 hash 算法；
• 美国标准 SHA-1 以 MD5 的前身 MD4 为基础；
• 该算法以任意长度的报文作为输入，产生一个 128 bit 的报文摘要作为输出，输入按 512 bit 的分组处理。

MD5 小结：

• MD5 使用小数在前（little-endian）的字节序约定；
• Dobbertin 在 1996 年找到了两个不同的 512-bit 块，它们在 MD5 计算下产生相同的 hash——这宣告了 MD5 不再满足强抗碰撞需求；
• 结论：MD5 不是足够安全的，不宜用于需要抗碰撞的认证与签名场景；
• MD5 在线查询破解服务已经非常成熟（通过彩虹表等预计算手段，常见弱口令的 MD5 可被秒查），这进一步说明 MD5 摘要不能作为口令等敏感数据的"保险箱"。

MD5 的 32 位与 16 位编码：MD5 通常是 32 位的十六进制编码，而在不少地方会用到 16 位的编码——16 位就是从 32 位 MD5 散列中把中间 16 位提取出来。以明文admin为例：

• 16 位：7a57a5a743894a0e
• 32 位：21232f297a57a5a743894a0e4a801fc3

可以看到，16 位摘要正是 32 位摘要中间的 16 位（7a57a5a743894a0e）。这种"截取中间位"的做法只是为了缩短显示长度，并不会提升安全性，反而进一步缩小了散列空间。

4.9 SHA 算法族

SHA-512 的逻辑（对应 FIPS 180 系列的安全散列算法）：

• 步骤 1 附加填充位：消息长度填充到与模 1024 同余 896；
• 步骤 2 附加长度：最后附加 128 位——用一个 128 位无符号整数表明消息的长度；
• 初始化 Hash 缓冲区：Hash 函数的中间结果和最终结果保存在 512 位的缓冲区中，缓冲区用 8 个 64 位寄存器（a、b、c、d、e、f、g、h）实现；
• 以 1024 位的分组（128 个字节）为单位处理消息；
• 输出最终摘要。

SHA Summary（要点回顾）：

• 密码散列函数的应用：消息认证（Message authentication）、数字签名（Digital signatures）以及其他应用；
• 需求与安全：密码散列函数的安全需求、暴力攻击（Brute-force attacks）、密码分析（Cryptanalysis）；
• 基于密码分组链的散列函数（Hash functions based on cipher block chaining）；
• 安全散列算法（Secure Hash Algorithm, SHA）：SHA-512 逻辑、SHA-512 轮函数；
• SHA-3：采用海绵结构（The sponge construction）与 SHA-3 迭代函数 f，与 Merkle-Damgård 结构的 MD5/SHA-1/SHA-2 有本质区别。

与 MD5 相比，SHA 家族输出更长（SHA-1 为 160 位，SHA-256 为 256 位，SHA-512 为 512 位），抗生日攻击的安全余量更大，是当前实际部署的主流选择。

五、数字签名体制

5.1 为什么需要数字签名

数字签名（Digital Signature）是一种防止源点或终点抵赖的鉴别技术。

需要理解消息认证的边界：消息认证保护双方之间的数据交换不被第三方侵犯，但它并不保证双方自身的相互欺骗。假定 A 发送一个认证信息给 B，双方之间的争议可能有多种形式：

• B 伪造一个不同的消息，但声称是从 A 收到的；
• A 可以否认发过该消息，B 无法证明 A 确实发了该消息。

现实例子：股票交易指令亏损后抵赖——交易者下指令买入，亏损后声称"我没下过这个指令"，此时需要数字签名来提供不可否认性（non-repudiation）。

5.2 数字签名应满足的条件

一个数字签名至少应满足以下几个条件：

1. 依赖性：数字签名必须依赖于要签名报文的比特模式（类似于笔迹签名与被签文件的不可分离性）；
2. 唯一性：数字签名必须使用对签名者来说是唯一的信息，以防伪造和否认；
3. 可验证：数字签名必须是在算法上可验证的；
4. 抗伪造：伪造一个数字签名在计算上不可行——无论是通过以后的数字签名来构造新报文，还是对给定的报文构造一个虚假的数字签名（类似笔迹签名的不可模仿性）；
5. 可用性：数字签名的产生、识别和证实必须相对简单，并且其备份在存储上是可实现的。

5.3 数字签名的类别

按不同维度划分：

• 以方式分：直接数字签名（direct digital signature）、仲裁数字签名（arbitrated digital signature）；
• 以安全性分：无条件安全的数字签名、计算上安全的数字签名；
• 以可签名次数分：一次性的数字签名、多次性的数字签名。

5.4 普通数字签名算法：RSA 签名

RSA 签名的基本流程（假设 A 的公钥私钥对为 ${KU_a \parallel KR_a}$）：

$$S_A = E_{KR_a}(M)$$

即 A 用自己的私钥 $KR_a$ 对消息 M "加密"得到签名 $S_A$。接收者用 A 的公钥 $KU_a$ 解密即可验证。

RSA 直接对整条消息签名存在明显问题：

• 速度慢——公钥运算开销大；
• 信息量大——签名与消息等长；
• 第三方仲裁时必须暴露明文信息；
• 因此实际方案都用散列函数先压缩消息再签名，hash 函数的无碰撞性保证了签名的有效性。

5.5 签名与加密的组合

签名提供真实性（authentication），加密提供保密性（confidentiality），"签名+加密"提供"真实性+保密性"。在 A→B 方向上，有两种实现方式：

1. 先签名，后加密：$E_{KUb}{M \parallel Sig_A(M)}$——先用自己的私钥签名，再用 B 的公钥整体加密；
2. 先加密，后签名：${E_{KUb}(M) \parallel Sig_A(E_{KUb}(M))}$——先用 B 的公钥加密，再对密文签名。

方式 2 存在三个问题：

• 发生争议时，B 需要向仲裁者提供自己的私钥（才能解开 $E_{KUb}(M)$ 验证签名对应的明文），这破坏了 B 私钥的保密性；
• 安全漏洞：攻击者 E 截获消息，把 $Sig_A(E_{KUb}(M))$ 换成 $Sig_E(E_{KUb}(M))$，让 B 以为该消息来自 E（签名被"剥离重贴"）；
• 保存信息多：除了 M 和 $Sig_A(E_{KUb}(M))$，还要保存 $E_{KUb}(M)$，因为 $KUb$ 可能过期，事后仲裁需要保留加密版本。

因此实践中更倾向于方式 1（先签名后加密），或者干脆采用"签名 + 单独加密"的分离设计。

5.6 ElGamal 签名方案

ElGamal 签名方案由 T. ElGamal 于 1985 年提出，其变体用于 DSS 中，安全性依赖于有限域上离散对数的困难性（与 RSA 依赖大整数分解不同，参见公私钥密码体制笔记中的 DLP 基础）。

构造参数：

• 全局参数：p 是一个大素数；g 是 $Z_p$ 中乘法群 $Z_p^*$ 的一个生成元；
• 私钥参数：x 是用户的私钥，$x \in Z_p^*$；
• 公钥参数：y 是用户的公钥，$y = g^x \bmod p$；
• 算法中还常使用一个随机数 k。

签名过程（给定要签名的明文 M）：

1. 生成一个随机数 k，$k \in Z_p^*$；
2. 计算 r：$r = g^k \bmod p$；
3. 计算 s：$s = (H(M) - xr)k^{-1} \bmod (p-1)$，到此签名结果为 $(r, s)$；
4. 把消息和签名结果 $(M, r, s)$ 发给接收者。

认证过程：

1. 取得发送方的公钥 y；
2. 预查合法性：若 $1 \le r \le p-1$，继续；否则签名不合法；
3. 计算 $v_1 = y^r r^s \bmod p$；
4. 计算 $v_2 = g^{H(M)} \bmod p$；
5. 比较 $v_1$ 和 $v_2$：如果 $v_1 = v_2$，表示签名有效；否则无效。

证明（正确性推导）：先对 s 进行处理：

$$s = (H(M) - xr)k^{-1} \bmod (p-1)$$

两边乘以 k：

$$ks = (H(M) - xr) \bmod (p-1)$$

移项得：

$$H(M) = xr + ks \bmod (p-1)$$

考察认证过程中的等式 $v_2 = g^{H(M)} \bmod p$：

$$v_2 = g^{xr+ks \bmod (p-1)} \bmod p = (g^x)^r (g^k)^s \bmod p$$

$$v_2 = y^r r^s \bmod p = v_1$$

因为 $v_2 = v_1$，所以该算法成立。注意证明中利用了费马小定理的推论（指数模 $p-1$ 约化）以及 $g^k \bmod p = r$ 的定义。

5.7 DSS / DSA：数字签名标准

数字签名标准（DSS）由美国国家标准与技术研究所（NIST）公布的联邦信息标准FIPS 186定义，其核心算法称为数字签名算法（DSA）。

FIPS 186-3 的最新版本包括三个算法：

• DSA（基于离散对数）；
• 基于 RSA 的数字签名算法RSA-PSS；
• 椭圆曲线的数字签名算法ECDSA。

与 RSA 不同，DSA 算法是一种签名方案，但不能用于加密或密钥交换。DSA 的安全性建立在离散对数的困难性上。

DSS 的参数与算法细节如下：

全局公开密钥分量：

• p：素数，其中 $2^{L-1} < p < 2^L$，$512 \le L < 1024$，且 L 为 64 的倍数——即比特长度在 512 到 1024 之间，长度增量为 64 比特；
• q：(p-1) 的素因子，其中 $2^{159} < q < 2^{160}$，比特长度为 160；
• g：$g = h^{(p-1)/q} \bmod p$，其中 h 是一整数，$1 < h < (p-1)$。

用户私有密钥：x，随机或伪随机整数，其中 $0 < x < q$。

用户公开密钥：$y = g^x \bmod p$。

用户每个报文的密钥：k，随机或伪随机整数，其中 $0 < k < q$。

签名：

$$r = (g^k \bmod p) \bmod q$$

$$s = [k^{-1}(H(M) + xr)] \bmod q$$

签名 = $(r, s)$。

验证：

$$w = (s')^{-1} \bmod q$$

$$u_1 = [H(M')w] \bmod q, \quad u_2 = (r')w \bmod q$$

$$v = [(g^{u_1} y^{u_2}) \bmod p] \bmod q$$

测试：$v = r'$ 则签名有效。

符号约定：

• M：要签名的消息；
• H(M)：使用 SHA-1 生成的 M 的散列码；
• M'、r'、s'：接收到的 M、r、s 版本（验证方用自己的计算与收到的签名比对）。

DSS 的特点：

• DSS 的签名比验证快得多（签名中只有少数模幂运算，验证中涉及更多的公开参数运算，具体快慢关系取决于实现，教材结论是签名侧计算量显著低于验证侧）；
• DSS不能用于加密或者密钥分配，是纯签名方案；
• $s^{-1} \bmod q$ 要存在，须满足 $s \ne 0 \bmod q$；如果 $s \equiv 0 \bmod q$ 发生，接收者可拒绝该签名并要求重新构造该签名——实际上 $s \equiv 0 \bmod q$ 的概率非常小；
• 若 p 为 512 位、q 为 160 位，则 DSS 的签名只需两个 160 位分量，即仅 320 位——相比 RSA 签名（与模长等长，如 1024 位），DSS 的签名要短得多。

5.8 特殊数字签名算法

不可否认的数字签名：一般数字签名由发送方 A 将消息加密后送给接收方，任何一个只要知道 A 公钥的人都可以对此签名进行验证。不可否认签名则具有新颖特性：没有签名者的合作，接收者就无法验证签名，在某种程度上保护了签名者的利益。例如，软件开发者可利用不可否认的数字签名保护他们的软件，使得只有付了钱的顾客才能验证签名并相信开发者仍然对软件负责。

群签名算法：群中各个成员以群的名义匿名地签发消息，也称为团体签名。例如在投标中，所有投标公司组成一个团体，每个公司都用群签名方式对标书签名。群签名具有如下特性：

• 只有群成员能代表所在的群签名；
• 接收者能验证签名所在的群，但不知道签名者；
• 需要时，可借助于群成员或者可信机构找到签名者（可追踪性）。

盲签名算法：假定请求签名者 A、签名者（仲裁者）B。盲签名就是要求 A 让 B 签署一个文件，而不让 B 知悉文件的内容，仅仅要求以后在需要时 B 可以对他所签署的文件进行仲裁。应用场景包括电子货币、电子选举。

盲签名的基本思想：

1. 求签名者把明文消息做盲变换得到 M'，M' 隐藏了明文 M 的内容；
2. 把 M' 给签名者（仲裁者）进行签名，得到签名结果 S(M')；
3. 最后，求签名者取回 S(M')，采用逆盲变换处理得到 S(M)，即为 M 的签名。

流程可概括为：消息 → 盲变换 → 签名 → 接收者 → 逆盲变换。

盲签名协议中常采用分割-选择（Cut-and-Choose）技术，可以使签名者 B 知道他签署的是哪方面的信息，但仍然保留盲签名的特征。经典例子是反间谍人员化名的签名：反间谍组织的成员身份保密，甚至机构头目也不知道；机构头目要给每个成员一个签字文件，文件内容是"持有该文件的人具有外交豁免权"。文件中必须使用反间谍组织成员的化名，同时机构头目也不能对任意的文件签名（假定成员为 A，机构头目是签名者 B）。这个场景正是盲签名"内容盲化 + 条件受控"特性的直观体现。

六、PGP：Pretty Good Privacy

6.1 PGP 概述

PGP（Pretty Good Privacy）由Phil Zimmermann编写，提供可用于电子邮件和文件存储应用的保密与鉴别服务。其设计理念包括：

• 支持版本多：PGP 支持各种系统平台和不同商业版本；
• 选择众所周知的算法，避免算法的安全性争议：公钥加密包括 RSA、DSS、Diffie-Hellman，对称加密包括 CAST-128、IDEA、3DES、AES，以及 SHA-1 散列算法；
• 适用性强：既可用于机构，也可用于个人；
• 可自主使用：不由政府或标准化组织所控制。

6.2 PGP 安全服务

PGP 提供的安全服务由一组"久经考验"的算法组合而成：

这种"对称加密消息 + 公钥加密会话密钥 + 散列签名 + 压缩 + 文本编码"的分层组合，是 PGP 的核心架构思想。

6.3 PGP 运行流程中的符号约定

在描述 PGP 流程前，先明确符号：

• $K_s$：session key（一次性会话密钥）；
• $K_{Ra}$、$K_{Ua}$：用户 A 的私钥和用户 A 的公钥；
• EP、DP：公钥加密和公钥解密；
• EC、DC：常规加密和常规解密；
• H：散列函数；
• Z：用 ZIP 算法数据压缩；
• R64：用 radix64 转换到 ASCII 格式。

6.4 PGP 的五步处理流程

步骤 1：认证（签名）。

• SHA-1 生成消息的 160 位 HASH 码；
• SHA-1 和 RSA 结合提供了一个高效的数字签名方案；
• DSS/SHA-1 作为可选替代方案。

步骤 2：加密（保密 + 鉴别同时运用）。

发送方：

1. 生成消息 M，并为该消息生成一个随机数作为会话密钥；
2. 用会话密钥加密 M（采用 CAST-128、IDEA 或 3DES）；
3. 用接收者的公钥加密会话密钥（RSA），并与消息 M 结合。

接收方：

1. 用自己的私钥解密恢复会话密钥；
2. 用会话密钥解密恢复消息 M。

这就是著名的混合加密（hybrid encryption）：公钥算法只保护短小的会话密钥，消息本体由快速的对称算法保护，兼顾了安全与性能。

步骤 3：数据压缩。

• 压缩的位置：发生在签名后、加密前；
• 因为压缩之前生成签名，所以验证时无须压缩（验证的是压缩前消息的摘要），也避免了压缩算法的多样性问题；
• 在加密前压缩，压缩的报文更难分析（去除了明文冗余，增加了密码分析的难度）；
• 对邮件传输或存储都有节省空间的好处。

步骤 4：E-mail 兼容性。

• 加密后是任意的 8 位字节，而很多邮件系统需要 ASCII 正文组成的块，因此需要转换到 ASCII 格式；
• Radix 64将 3 字节输入转换到 4 个 ASCII 字符，并带 CRC 校验，属盲目转换——即输入流即使是 ASCII，算法也会将其转换（不判断内容）。

步骤 5：分段与重组。

• Email 常常受限制于最大消息长度（一般限制在最大 50000 字节）；
• 更长的消息要进行分段，每一段分别邮寄；
• PGP 自动分段并在接收时自动恢复；
• 签名只需一次，在第一段中。

6.5 PGP 消息的传送与接收

PGP 消息的整体格式由若干部分拼接而成：签名部分（含时间戳、消息摘要、KeyID 等）、会话密钥部分（含 KeyID 与加密的会话密钥）、消息部分（压缩并加密后的数据）。接收方按照相反顺序：先取会话密钥部分中的 KeyID 定位自己的私钥恢复会话密钥，解密得到压缩数据，解压后得到消息与签名，再用发送方的公钥验证签名。

发送消息的格式（自内向外）可以概括为：

1. 原始消息 M；
2. 对 H(M) 用发送方私钥签名，得到签名部分；
3. 将 (消息 || 签名) 用 ZIP 压缩；
4. 用随机会话密钥 $K_s$ 以 CAST-128/IDEA/3DES 加密压缩后的数据；
5. 用接收方公钥加密 $K_s$，连同两个 KeyID 一起作为会话密钥部分；
6. 整体经 Radix 64 转换为 ASCII，必要时分段发送。

6.6 PGP 密钥需求

PGP 使用四种类型的密钥：

1. 一次性会话的常规密钥；
2. 公钥；
3. 私钥；
4. 基于口令短语的常规密钥（用于加密保护私钥环）。

这些密钥存在三种独立需求：

• 需要一种生成不可预知的会话密钥的手段；
• 需要某种手段来标识具体的密钥；
• 一个用户拥有多个公钥/私钥对（用于更换、分组等）。

每个 PGP 实体需要维护一个文件保存其公钥私钥对（私钥环），和一个文件保存通信对方的公钥（公钥环）。

6.7 会话密钥的生成（以 CAST-128 为例）

以 CAST-128 为例说明 PGP 如何生成 128 位的会话密钥：

• 128 位的随机数由 CAST-128 自己生成。输入包括一个 128 位的密钥和两个 64 位的数据块作为加密的输入；
• 使用CFB（密码反馈）方式，CAST-128 产生两个 64 位的加密数据块，这两个数据块的结合构成 128 位的会话密钥；
• 作为明文输入的两个 64 位数据块，是从一个 128 位的随机数流中导出的；
• 这些数基于用户的键盘输入——键盘输入的时间和内容用来产生随机流。因此，如果用户以他通常的步调敲击任意键，将会产生合理的随机性。

这体现了 PGP 的设计哲学：不依赖昂贵的硬件随机源，而是把"用户敲键节奏"这种难以预测的物理事件作为熵来源。CFB 模式的相关细节可参考对称密码体制笔记中对 CFB 工作模式的讲解。

6.8 密钥标识符 KeyID

一个用户有多个公钥/私钥对时，接收者如何知道发送者用的是哪个公钥来加密会话密钥？有三种候选方案：

1. 将公钥与消息一起传送——浪费空间；
2. 将一个标识符与一个公钥关联，对一个用户做到一一对应——管理上带来负担；
3. PGP 给每个公开密钥指定 KeyID，KeyID 由公开密钥的最低 64 比特组成，包括 64 个有效位：$(K_{Ua} \bmod 2^{64})$。

PGP 数字签名同样也需要 KeyID（接收者需要知道用哪个公钥验证签名）。

6.9 密钥环

KeyID 对于 PGP 非常关键——两个 keyID 包含在任何 PGP 消息中，分别提供保密（定位解密私钥）与鉴别（定位验证公钥）功能。由于一个节点上可能保存大量密钥，需要一种系统化的方法存储和组织这些 key 以保证使用。

PGP 在每一个节点上提供一对数据结构：

• 私有密钥环：存储该节点拥有的公钥/私钥对；
• 公开密钥环：存储本节点知道的其他用户的公钥。

6.10 私有密钥环

私有密钥环中每个条目包含以下字段：

• 时间戳：密钥对生成的日期/时间；
• 密钥 ID：公开密钥的低 64 位（即 KeyID）；
• 私有密钥：密钥对的私有部分（该字段被加密保护）；
• 用户 ID：该字段的典型值是用户的邮件地址，用户也可为每个密钥对选择不同的名字。

注意私有密钥字段是加密存储的——PGP 用"基于口令短语的常规密钥"对其加密，这样即使私钥环文件泄露，攻击者也无法直接使用私钥，必须破解口令短语。

6.11 公开密钥环

公开密钥环中每个条目包含：

• UserID：公钥的拥有者。多个 UserID 可以对应一个公钥；
• 公钥环可以用UserID 或 KeyID 索引。

6.12 PGP 报文传输过程（发送方）

签名阶段：

1. 从私钥环中得到私钥，利用 userid 作为索引；
2. PGP 提示输入口令短语，恢复私钥（解密私钥环中的私钥字段）；
3. 构造签名部分。

加密阶段：

1. PGP 产生一个会话密钥，并加密消息；
2. PGP 用接收者 userid 从公钥环中获取其公钥；
3. 构造消息的会话密钥部分。

6.13 PGP 报文接收过程（接收方）

解密消息：

1. PGP 用消息的会话密钥部分中的 KeyID 作为索引，从私钥环中获取私钥；
2. PGP 提示输入口令短语，恢复未加密的私钥；
3. PGP 恢复会话密钥，并解密消息。

验证消息：

1. 用消息的签名部分中的 KeyID 作为索引，从公钥环中获取发送者的公钥；
2. PGP 恢复被传输过来的消息摘要；
3. PGP 对接收到的消息重新做摘要，并与上一步的结果作比较——一致则签名有效。

6.14 公钥管理问题：PGP 的信任短板

由于 PGP 重在广泛地在正式或非正式环境下应用，没有建立严格的公钥管理模式，因此存在信任与认证的安全缺口。

典型攻击场景：如果 A 的公钥环上有一个从 BBS 上获得的、B 发布的公钥，但已被攻击者 C 替换，这时就存在两条"信任通道"：

• C 可以向 A 发信并冒充 B 的签名，A 以为是来自 B；
• A 与 B 的任何加密消息 C 都可以读取。

这暴露了 PGP 的先天局限：密钥分发与公钥真实性验证不依赖集中式 CA，而是依赖"信任网"（web of trust）与用户自行核验。密钥指纹核验、密钥签名（相互签名以担保真实性）等机制就是为缓解这一短板而设计的。

七、总结：一条贯穿全篇的主线

回顾全文，可以提炼出一条清晰的主线：

1. 消息认证解决"消息是谁发的、有没有被改"（第三方攻击），靠的是鉴别函数——加密、MAC 或散列函数；
2. 散列函数是把任意长消息压成定长指纹的公开函数，其七项安全需求中最关键的是单向性与抗碰撞性，而生日攻击把有效强度削减到一半，因此散列码必须足够长（≥160 位）;
3. 数字签名解决"双方互相抵赖"（不可否认性），本质是"私钥签署消息摘要"；RSA（基于大整数分解）、ElGamal/DSA（基于离散对数）、以及不可否认签名、群签名、盲签名等变体构成了完整的签名算法谱系；
4. PGP是把上述所有机制组合成可用产品的经典范例：混合加密（对称加密消息 + 公钥加密会话密钥）、SHA-1+RSA/DSS 签名、ZIP 压缩、Radix 64 编码、KeyID + 双密钥环管理，五步流程环环相扣。

信息安全系列笔记在仓库中以 信息安全/README.md 为总入口，前四讲分别奠定安全概述与安全服务、密码学与经典密码体制、对称密码体制、公私钥密码体制的基础，本篇（第五讲）则完成了"从保密到鉴别、从鉴别到签名、从签名到综合应用"的收尾。建议读者将本篇与第四讲中的 RSA、ElGamal 数学基础对照阅读，两者共享离散对数与大整数分解两条安全基石，能够更完整地理解现代密码系统的设计逻辑。

• 文档
• 教程
• 知识库