KEM–DEM 混合加密 | Codeboy's Blog

KEM–DEM 混合加密把公钥加密分成两项工作：KEM 建立一个短的共享秘密，DEM 用这个秘密保护真正的消息。 公钥部分不随正文长度重复执行，对称部分则可以高效处理大文件或长消息。

接收者不需要提前与发送者共享对称密钥。发送者只需接收者的公钥，生成封装密文与会话密钥；接收者用私钥从封装密文恢复同一密钥，再解开正文。真正需要证明的是：这两个分别安全的组件，在攻击者可以修改整份密文并请求解密时，是否仍能正确组合。

形式陈述

最小构造：密文分成一个头和一个正文

(pk,sk)\leftarrow\mathrm{KGen}(1^\lambda),\qquad (K,c_0)\leftarrow\mathrm{Encaps}(pk),\qquad K'\leftarrow\mathrm{Decaps}(sk,c_0).

$\lambda$ 是安全参数， $c_0$ 是公开传输的封装密文， $K$ 是秘密。对诚实生成的封装，解封应恢复 $K$ ；对不合法输入，算法可以按定义返回失败或规定的隐式拒绝结果。

一个数据封装机制接受适配的对称密钥：

c_1\leftarrow\mathrm{DEnc}(K,m),\qquad m'\leftarrow\mathrm{DDec}(K,c_1).

最小 KEM–DEM 构造为

\begin{aligned} \mathrm{Enc}(pk,m):\quad &(K,c_0)\leftarrow\mathrm{Encaps}(pk),\\ &c_1\leftarrow\mathrm{DEnc}(K,m),\\ &\text{输出 }C=(c_0,c_1);\\[2mm] \mathrm{Dec}(sk,(c_0,c_1)):\quad &K\leftarrow\mathrm{Decaps}(sk,c_0),\\ &\text{若接口报告失败，输出 }\bot,\\ &\text{否则输出 }\mathrm{DDec}(K,c_1). \end{aligned}

$\bot$ 表示解密失败。KEM 不接收正文 $m$ ，也不要求先由调用者选一个密钥再把它加密；它本身生成密钥与封装密文。这是 KEM 接口与普通“加密一段密钥字节”的接口区别。

如果两项组件完全正确，组合自然正确。若诚实 KEM 和 DEM 的失败概率分别不超过 $\delta_K,\delta_D$ ，则组合失败概率至多为 $\delta_K+\delta_D$ ，这里 DEM 的概率应按它实际收到的密钥分布计算。正确性与下面的攻击安全性是两项不同要求。[1]

一个明确的组合命题

先考虑完全正确的组件、无额外协议上下文的最小构造，并假定 KEM 输出的密钥空间与 DEM 的均匀密钥空间相同。

KEM 的 IND-CCA 安全实验给攻击者 $pk,c_0^*$ ，以及真实会话密钥或独立均匀密钥二者之一；攻击者可以查询其他封装密文的解封，但不能查询 $c_0^*$ 。目标是分辨给出的密钥来自哪一种情况。

DEM 的一次性 IND-CCA 实验只在一个秘密均匀密钥下给出一份挑战加密：攻击者选择等长消息 $m_0,m_1$ ，收到 $\mathrm{DEnc}(K,m_b)$ ，并可按该 CCA 模型进行自适应解密查询，但不能解密挑战密文本身。这里采用允许挑战前后解密查询的模型；带 nonce 或标签时，禁止项也必须按完整的密文与标签组合定义。

组合命题。 若 KEM 满足 IND-CCA，DEM 满足上述一次性 IND-CCA，则最小 KEM–DEM 公钥加密满足 IND-CCA。一次性保密加上相应的密文完整性，也是一条构造所需 DEM 的标准途径。[1][2]

这个命题给出的是一组清晰的充分条件。它没有声称任意弱 KEM 都绝不可能在更特殊的整体构造中达到 CCA 安全，也没有要求所有实现都必须把同一长串字段重复放进关联数据。安全条件与特定协议的工程组织，应分层陈述。

直觉

为什么一次性密钥允许一次性 DEM

每次公钥加密都重新执行 Encaps，因此一条消息通常对应一个新的会话密钥。对这项构造，DEM 需要承受的是同一密钥下的一次合法加密，以及攻击者可能发起的多次解密试探。

这里的“一次性”限制的是合法加密次数，不是攻击次数。攻击者可以保留挑战头 $c_0^*$ ，反复改变正文 $c_1$ 并询问解密。若 DEM 只在被动观察时隐藏消息，却允许可预测篡改，就不能据此证明整个方案具有选择密文安全性。

例如只使用一次性掩码 $c_1=m\oplus K$ ，被动保密性很好；但攻击者把某个比特翻转，解密也会在相同位置翻转。拿这种正文配上一个强 KEM，并不会自动消除正文的可塑性。需要给 DEM 配备与目标安全定义匹配的认证保护，或直接要求它满足一次性选择密文安全。

在实际实现里，AEAD 常承担这项工作：它同时保护消息保密性与密文完整性，并允许认证公开的关联数据。不过，AEAD 的 nonce 约定、解密查询范围和密钥分布，仍需与组合中的用法一致。

密文头负责传递会话密钥，正文密文负责保护消息；图中以 AEAD 作为 DEM 的具体实现。

证明的核心：按封装头是否相同分流

记挑战密文为 $(c_0^*,c_1^*)$ 。攻击者的合法解密查询分成两类：

查询	归约如何处理
$c_0\ne c_0^*$	解封这个非挑战头，再正常解密正文
$c_0=c_0^$ ，但 $c_1\ne c_1^$	使用挑战会话密钥对应的 DEM 解密接口

第二类正是组合证明中容易遗漏的地方。攻击者被禁止查询的是整份挑战密文，并不是被禁止继续使用挑战头。若把所有相同头的请求一律排除，就证明了一个比真实 CCA 攻击弱的模型。

证明使用混合论证。固定挑战消息分支 $b$ ，把真实挑战会话密钥替换成独立均匀密钥，同时让所有相同挑战头的正文解密也使用这个替代密钥。KEM 归约已经拿到了“真实或随机”的候选密钥，因此能直接处理这类正文解密；其他头交给 KEM 解封 oracle。真实世界与替代世界的差异由 KEM 的 CCA 安全界控制。

替换以后，会话密钥与 $pk,c_0^*$ 独立。此时可以把挑战正文交给 DEM 安全实验：其他头的解密由归约自己生成的 KEM 私钥处理，相同头的解密则交给 DEM oracle。于是 $m_0$ 与 $m_1$ 的正文挑战由一次性 DEM 的 CCA 安全界连接。

最后在另一个消息分支中把均匀密钥换回真实密钥。若统一使用“两实验输出 1 的概率差”作为优势，且相关资源范围内两项组件优势分别不超过 $\varepsilon_K,\varepsilon_D$ ，这个三段论证给出

\operatorname{Adv}_{\mathrm{PKE}}^{\mathrm{CCA}} \le2\varepsilon_K+\varepsilon_D.

两个 KEM 项对应两个消息分支的替换，并不是忽略了攻击者的一半查询。采用其他优势归一化、允许诚实解封失败或讨论多用户资源时，常数与附加项需要据相应实验重新记账；上面的界对应此处已经固定的完全正确、单用户模型。

补充示意图

KEM–DEM 混合加密：加解密数据流与安全游戏梯子 — KEM–DEM 混合加密示意图

例子与边界

把 DEM 实现成 AEAD 时，多了哪些字段

对 AEAD，常把正文密文写成

c_1=(N,\mathrm{Seal}(K,N,A,m)),

其中 $N$ 是 nonce， $A$ 是公开但需认证的关联数据。接收者用相同的 $N,A$ 调用 Open，只有认证成功才得到可交给上层使用的明文。

一种清晰的协议封装是

A=\mathrm{Encode}( \text{协议版本},\text{套件标识},\text{接收者标识},c_0,N,\text{业务上下文}).

这是一种足够明确、便于检查的绑定方式，而不是最小组合定理要求的唯一字段清单。具体字段还可以通过 KDF 的上下文、外层认证协议或其他已证明等价的方式绑定；重要的是消息被解释时所依赖的语义确实受到认证。

Encode 必须让不同字段元组得到不同编码，例如使用长度前缀或固定长度字段。直接拼接可变长字符串时，("ab","c") 与 ("a","bc") 都变成同一串字节。认证只能保护它看到的字节，不能修复上层已经产生的语义歧义。

一个上下文移植的例子

假设同一系统用同一个接收者公钥加密多个文件，密文外有一个未认证的 file_id。攻击者把一份完整合法密文从文件 A 的位置搬到文件 B 的位置，密码层仍可能正确解密原正文，因为它没有被要求区分这两个业务用途。

把 file_id 纳入关联数据或密钥派生上下文后，接收端会按预期文件标识验证，这种移植就会触发认证失败。这里修补的是业务上下文绑定，不是说原来的抽象公钥加密已经被攻破。

同理，重放一份完全相同的合法密文，不一定违反 AEAD 或 IND-CCA 定义。需要拒绝重放的协议，应额外管理序号、请求标识或已接收状态，并把相应标识绑定到认证语义中。

KDF、nonce 与多记录会话

KEM 提供的秘密未必已经是目标 AEAD 所需的密钥长度和用途。协议可以经 KDF 派生正文密钥、基础 nonce、导出秘密等：

K_{\mathrm{aead}}=\mathrm{KDF}(K,\text{suite},\text{context},\text{用途标签}).

不同用途使用不同标签，可以把密钥用途明确分开。但“经过一个 hash”本身不是任意输入分布都变成均匀密钥的证明；需要 KEM 提供的伪随机性和 KDF 相应的安全性质共同支撑接口转换。

对一次封装只加密一次的最小构造，nonce 的要求是在这一个新密钥下满足 AEAD 约定。有些方案可以在每个全新密钥下使用同一个固定 nonce 值；这与在同一密钥下重复 nonce 完全不同。因而“不允许 nonce 重复”必须说明比较范围是同一密钥，而不是整个系统所有消息。

若一次封装建立的是多记录会话，则已经超出一次性 DEM 的最小模型。此时需要同密钥多次加密的 AEAD 保证，并正确管理序号、nonce 上限、消息排序和认证上下文。分块传输还要说明每块何时可交付，以及怎样防止截断、重排或跨会话拼接；一条消息安全的定理不会自动替代这些协议规则。

推论与应用

HPKE 是这条主线的标准化实例

RFC 9180 的 HPKE 把 KEM、KDF 和 AEAD 接成明确的密钥调度与记录加密接口。它派生 AEAD 密钥与基础 nonce，并用序号构造记录 nonce，同时区分 Base、PSK、Auth 和 AuthPSK 等模式。[3]

HPKE 是理解工程接口的好例子，但不应把上面的抽象组合证明逐字套成所有 HPKE 模式的完整证明。具体模式还包含身份、预共享密钥、上下文与不同威胁模型，需按 RFC 的定义理解。

一个特别容易误解的点是：有 AEAD 标签，不等于已经认证发送者身份。 在仅凭接收者公钥的 Base 型加密中，任何拿到公钥的人都能自己封装新密钥并生成合法正文。AEAD 可以检验一份既定密文是否被无密钥者篡改，但不会阻止另一个人新建一份自己的合法密文。发送者认证需要额外的密钥或签名等机制，且与不可否认性又是不同性质。

“KEM–DEM 混合加密”中的混合，指非对称封装与对称正文保护的组合。它不自动意味着同时组合经典算法与后量子算法；后者是另一条独立的组合维度，可以发生在 KEM 内部或更上层协议中。

阅读或实现时抓住三个接口

核对一个具体方案时，应把重点放在三处连接：KEM 输出与 DEM 密钥分布是否匹配；攻击者保留挑战头时，正文修改由什么安全性质处理；协议上下文、nonce 和多记录状态如何进入认证语义。

格式解析、失败处理和认证前明文交付也应与抽象接口一致。例如证明只把 Open 的最终成功明文或 $\bot$ 暴露给对手，实际接口却提前泄露未验证正文，就已经给出了不同的攻击观察。这里需要检查的是实现是否兑现了证明中的接口，而不是在正文后再补一句笼统的“两个组件都很安全”。

这项构造的价值，正在于可以把一个复杂的公钥消息加密任务，分解成边界清楚、能够分别分析的组件，再通过明确的混合论证重新组合起来。

本页已规定Encode必须无歧义，并说明上下文可由AAD或KDF绑定。协议字段编码把这项要求展开为编码/解析往返、规范字节、资源上限与单射证明；域分离再给出互不相交输入域的随机函数论证。多记录会话接口承担逐条接收状态，不改变本页一次性KEM–DEM的组合定理。

参考资料

[1] Victor Shoup, A Proposal for an ISO Standard for Public Key Encryption, version 2.1, 2001，§§3–5 与 §10：KEM、DEM、安全实验和混合组合；该文是历史提案，不替代现行标准文本。

[2] Ronald Cramer and Victor Shoup, “Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack,” SIAM Journal on Computing 33(1), 2003, pp. 167–226，选择密文安全与认证混合加密的分析。

[3] Richard Barnes et al., RFC 9180: Hybrid Public Key Encryption, 2022，KEM/KDF/AEAD 接口、密钥调度、模式与安全性质。

[4] Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，混合公钥加密与 CCA 安全的教材处理。

形式陈述 ​

最小构造：密文分成一个头和一个正文 ​

一个明确的组合命题 ​

为什么一次性密钥允许一次性 DEM ​

证明的核心：按封装头是否相同分流 ​

把 DEM 实现成 AEAD 时，多了哪些字段 ​

一个上下文移植的例子 ​

KDF、nonce 与多记录会话 ​

HPKE 是这条主线的标准化实例 ​

阅读或实现时抓住三个接口 ​

反向链接