📚 课程目录第1章常数时间密码实现工程导论

1. 常数时间密码实现工程导论

在密码学中，算法安全性通常以数学证明的形式给出：AES 的分组置换、RSA 的模幂运算、椭圆曲线上的标量乘法，都被证明在特定假设下难以攻破。然而，一个在数学上无懈可击的算法，如果其软件或硬件实现的行为会随密钥、明文或中间值的变化而变化，攻击者就可能绕过数学难题，直接从实现的"物理行为"中提取秘密。这类攻击被称为侧信道攻击（Side-Channel Attack, SCA），而其中最容易观测、最容易利用的一类，就是时间侧信道。

常数时间密码实现工程，正是为应对时间侧信道威胁而发展起来的一整套设计、编码、验证与测试方法。它的目标不是让程序"跑得更快"，而是让程序的执行时间与秘密数据无关——无论密钥比特是 0 还是 1，无论中间值是大是小，代码路径、内存访问模式、分支跳转和指令序列都应保持一致。本章将建立这门课程的基本概念框架：什么是常数时间、威胁模型如何刻画、工程目标是什么，以及后续 29 章将沿着怎样的路线展开。

1.1 什么是常数时间

"常数时间"（constant-time）在密码工程中有一个精确但常被误解的含义。它不是指程序运行时间是一个固定不变的常数——任何程序都会因 CPU 频率、缓存状态、输入长度等因素产生波动。它指的是：程序的执行时间（更准确地说，是执行时间的可观测特征）不依赖于任何秘密输入。

形式化地，设程序 P 接受公开输入 pub 和秘密输入 sec，其执行时间为 T(pub, sec)。常数时间要求：对于任意两个秘密输入 sec₁ 和 sec₂，以及任意公开输入 pub，T(pub, sec₁) 与 T(pub, sec₂) 在统计上不可区分。工程上更实用的表述是：不存在一条依赖于秘密值的分支、循环次数、内存地址或指令类型。

需要特别区分三个层次：

算法级常数时间：算法本身没有数据相关的分支或循环，例如固定轮数的 AES。
实现级常数时间：编译器、指令集、缓存、分支预测器等底层机制不会因秘密值产生可观测差异。这是工程中最难保证的部分。
系统级常数时间：整个调用链（包括库函数、系统调用、网络协议栈）都不会泄露秘密相关信息。

一个经典的反面例子是"提前返回"的字节比较函数：

int bad_compare(const uint8_t *a, const uint8_t *b, size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (a[i] != b[i]) return 0;   // 提前返回，泄露首个不匹配位置
    }
    return 1;
}

攻击者可以通过测量比较耗时，逐字节推断出正确值——耗时越长，匹配的前缀越长。这就是著名的"逐字节时间攻击"，曾成功攻击过多种 MAC 校验和密码比较实现。常数时间版本必须遍历全部 n 字节，并用位运算累积差异：

int ct_compare(const uint8_t *a, const uint8_t *b, size_t n) {
    uint8_t diff = 0;
    for (size_t i = 0; i < n; i++) {
        diff |= a[i] ^ b[i];   // 无分支，累积所有差异
    }
    return diff == 0;
}

1.2 时间侧信道威胁模型

要设计有效的防御，必须先明确攻击者能观测什么、控制什么、目标是什么。时间侧信道的威胁模型通常从三个维度刻画：

观测能力：攻击者可以测量加密操作的墙钟时间、CPU 周期数、缓存命中/缺失模式、分支预测器状态，甚至通过共享硬件（如 SMT 超线程、共享缓存）进行细粒度探测。远程攻击者通常只能获得粗粒度时间（毫秒级），本地攻击者可达纳秒级。

控制能力：攻击者可能控制部分明文、密文、IV、随机数，甚至能触发特定错误路径。在"选择明文"模型下，攻击者可以反复提交精心构造的输入，观察时间差异并做统计分析。

目标：最常见的是恢复长期密钥（如 AES 密钥、RSA 私钥），其次是恢复会话密钥、明文或认证标签。不同目标对应不同的攻击复杂度和防御强度。

根据攻击者位置，可分为远程时间攻击（如 Lucky13 对 TLS CBC 的攻击）、本地时间攻击（如针对 RSA 模幂的 Kocher 攻击）、以及微架构攻击（如 Spectre、Meltdown 利用推测执行泄露秘密）。后者的出现说明：即使源代码是常数时间的，底层微架构仍可能引入时间差异，这使常数时间工程从"写对代码"升级为"理解整个执行栈"。

1.3 工程目标与课程路线图

常数时间密码实现工程的目标可以概括为三句话：让执行时间与秘密无关，让验证手段可重复，让工程实践可落地。这三者缺一不可——只追求"写对"而不验证，无法发现编译器优化引入的差异；只做统计测试而不理解原理，无法定位根因；只关注单个函数而忽略系统调用和库依赖，防御会在边界处失效。

本课程共 30 章，按"概念—原理—实现—验证—工程化"的递进路线组织：

第 1–4 章（概念与威胁）：建立常数时间定义、威胁模型、攻击分类与工程目标，理解为什么"数学安全 ≠ 实现安全"。
第 5–10 章（语言与编码基础）：从 C/C++、Rust、汇编层面讲解分支消除、位运算技巧、掩码选择、条件移动、内存访问模式固定等核心编码手法。
第 11–16 章（典型算法实现）：覆盖 AES、SHA-2/SHA-3、RSA 模幂、ECC 标量乘法、MAC 校验、KDF 等典型密码原语的常数时间实现要点与常见陷阱。
第 17–22 章（验证与测试）：介绍 dudect、ctgrind、Valgrind、形式化验证、侧信道测试平台、统计检验方法，以及如何设计可复现的验证流程。
第 23–27 章（工程化与系统）：讨论编译器与优化、操作系统与系统调用、缓存与微架构、多线程与共享资源、密钥生命周期管理等系统级问题。
第 28–30 章（综合与前沿）：通过完整案例复盘、前沿攻击与防御、工程规范与团队协作，形成可迁移的工程能力。

学习建议：常数时间工程是一门"细节决定成败"的学科。建议在阅读每一章时，都准备一个可编译、可运行的最小示例，亲手观察编译器生成的汇编、测量执行时间分布、尝试用统计方法检验差异。只有把"看不见的时间"变成"看得见的数据"，才能真正掌握这门工程。

最后需要强调：常数时间不是密码实现的"可选项"，而是现代密码工程的基本要求。随着远程时间攻击、微架构攻击的不断演进，常数时间工程已经从学术研究走向工业标准——TLS 库、操作系统内核、硬件安全模块、可信执行环境，都在把常数时间作为密码代码的准入门槛。掌握这套方法，意味着你不仅能写出"功能正确"的密码代码，更能写出"在真实攻击者面前依然安全"的密码代码。