公钥加密 | Codeboy's Blog

形式陈述

公钥加密是通用加密方案中把加密能力公开、解密能力保密的分支。对每个安全参数 $\lambda$ ，方案先规定公钥空间 $\mathcal K^{\mathrm{pk}}_\lambda$ 、私钥空间 $\mathcal K^{\mathrm{sk}}_\lambda$ 、消息空间 $\mathcal M_\lambda$ 与密文空间 $\mathcal C_\lambda$ 。

算法接口分成三步。密钥生成算法产生配对密钥：

(pk,sk)\leftarrow\operatorname{Gen}(1^\lambda) \in\mathcal K^{\mathrm{pk}}_\lambda\times\mathcal K^{\mathrm{sk}}_\lambda.

加密算法接收公开密钥、消息和随机币；解密算法只使用私钥恢复消息或返回失败：

r\leftarrow\mathcal R_\lambda, \qquad c:=\operatorname{Enc}_{pk}(m;r)\in\mathcal C_\lambda,

\operatorname{Dec}_{sk}(c) \in\mathcal M_\lambda\cup\{\bot\}.

正确性单独约束合法加密产生的密文。对每个 $m\in\mathcal M_\lambda$ ，要求

\Pr_{(pk,sk)\leftarrow\operatorname{Gen}(1^\lambda),\,r\leftarrow\mathcal R_\lambda} \!\left[ \operatorname{Dec}_{sk}(\operatorname{Enc}_{pk}(m;r))=m \right] \ge1-\operatorname{negl}(\lambda).

完美正确性把右侧误差取为零；允许解密失败的构造则必须把失败概率和参数范围写清楚。

进入计算安全层次后，攻击者持有 $pk$ ，本来就能自行运行加密，因此 IND-CPA 允许它选择等长挑战消息并取得其中一个的随机化加密；IND-CCA 再开放带禁止条件的解密查询。在标准的一般消息 IND-CPA 模型下，确定性 PKE 不可能安全，因为攻击者可自行加密候选消息并比较。针对高 min-entropy 消息的 deterministic-encryption 是另一个较弱定义，不与这一结论矛盾。

直觉

公钥加密把上锁与开锁能力分离：任何人可用公开密钥封装消息，只有私钥持有者能恢复内容。这缓解了预共享秘密的分发问题，却没有自动认证公钥属于谁，也没有自动认证发送者。

公钥运算通常比对称加密昂贵。工程系统因此让KEM产生共享会话密钥与短封装，再由DEM处理正文；两组件的接口、安全模型与绑定条件由KEM–DEM 组合定理承接，而不是一般 PKE 定义的一部分。

密钥生成分出公开加密密钥和秘密解密密钥，合法密文恢复原消息 — 公钥加密的密钥分工

例子与边界

RSA 函数只给出带陷门的代数映射与反演假设；朴素确定性 RSA 不满足一般 IND-CPA，因为攻击者可对候选消息计算确定密文并与挑战比较。ElGamal在指定群的 DDH 假设下满足 IND-CPA，却因乘法可塑性不满足 CCA。安全构造必须使用与目标游戏匹配的随机编码、填充或 KEM–DEM 组合；不同方案依赖的假设不能由“使用公钥”统一代替。

公钥真实性仍需证书、可信指纹或已认证信道，否则中间人可以替换 $pk$ 。公钥加密也不是“用私钥加密、公钥解密”的数字签名：签名的编码、正确性和不可伪造实验都不同。解密错误若直接暴露给网络攻击者，还可能把仅 CPA 安全的构造变成 padding-oracle 攻击面。

推论与应用

公钥加密支持开放网络中的密钥封装、混合加密和多接收者通信。CPA 与 CCA定义机密性强度；对称加密及认证模式承担高吞吐数据面，数字签名承担认证，Diffie–Hellman则提供另一种共享密钥建立方式。具体的 RSA、ElGamal 和 KEM 页面分别承担代数假设、方案证明与封装游戏，本页只保留 PKE 通用接口和安全目标。

参考资料

Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023, Chapters 11–12.
Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020, Chapters 11–13.

形式陈述 ​

反向链接

形式陈述