公钥密码学是密码学的一个分支,使用在数学上相关但作用不同的成对密钥:可以公开分发的公钥,以及必须保密的私钥。根据所采用的密码方案,这些密钥可用于保密通信、签名验证或共享秘密的建立。即使知道公钥,在计算上也应难以执行相应的私钥操作。
其核心创新在于,将执行某项密码操作的能力与执行其对应操作的能力分离。人们无须持有接收方的解密密钥,就能为其加密消息;也无须持有签名密钥,就能验证签名。这种分离是现代网络安全诸多应用的基础,包括安全的网页连接、软件更新验证、电子身份系统和加密即时通信。不过,仅凭这种分离并不能确定公钥属于谁;这还需要额外的身份认证与信任机制。
公钥密码系统的计算开销通常高于对称密码系统,因此实际系统会将其与快速的对称密钥算法结合使用。其安全性取决于数学假设、严谨的协议设计、可靠的实现以及对私钥的保护。大规模量子计算的潜在发展,也推动了基于不同数学问题的公钥密码方案的研发与标准化。
起源与历史发展
在公钥密码学出现之前,传统加密要求通信双方共享秘密密钥材料。加密算法可以公开,但通常情况下,任何能够使用共享密钥加密的人也能够解密。如何安全地分发这些秘密,是实际运作中的一大难题。在一个有 名参与者且任意两人之间都需要通信的群体中,为每一对参与者分配独立的对称密钥,需要 个密钥,不过集中式密钥分发系统可以采用不同的方式处理这一问题。
惠特菲尔德·迪菲和马丁·赫尔曼在1976年发表的论文《密码学的新方向》中,公开阐述了公钥密码系统的构想,并提出了一种通过不安全信道建立共享秘密的实用方法。拉尔夫·默克尔也独立提出了无须预先共享秘密即可通信的相关构想;他基于谜题的方法于1978年发表。这些贡献表明,安全通信并不一定要从以实体方式交付共同的秘密密钥开始。
罗纳德·李维斯特、阿迪·沙米尔和伦纳德·阿德尔曼于1977年开发了RSA密码系统,并于1978年发表了介绍该系统的主要学术论文。RSA通过模幂运算,给出了支持公钥加密和数字签名的具体构造。RSA的出现推动公钥密码学从概念上的可能性转变为能够广泛实现的技术。此后的系统引入了其他数学框架,并在密钥长度、速度和安全性假设之间作出了不同的权衡。
与此同时,另一段发展历史被保密了数十年。在英国政府通信总部,詹姆斯·埃利斯于1970年阐述了非秘密加密的可能性。克利福德·科克斯于1973年设计了一种类似RSA的构造,马尔科姆·威廉森则于1974年提出了一种与迪菲—赫尔曼方法密切相关的密钥交换构造。这些成果于1997年公开。它们并未推动早期的公开研究,但证明了这一构想的关键部分曾被独立发现。
后续的里程碑包括塔希尔·埃尔加马尔于1985年提出的加密和签名构造,以及尼尔·科布利茨和维克托·米勒同样于1985年各自独立提出的、在公钥系统中使用椭圆曲线的方案。随着网络安全协议、商用浏览器以及1991年首次发布的Pretty Good Privacy等软件的推广,公钥技术的普及速度不断加快。公钥技术成为互联网运行基础设施的一部分,不再主要局限于专业机构使用。近年来,抗量子密码的标准化工作进一步拓展了这一发展历程,使其超越了早期部署中占主导地位的整数分解和离散对数问题。
密钥、加密、签名与密钥建立
公钥方案首先通过密钥生成算法生成密钥。给定安全参数和随机性来源,该算法会生成公钥 和私钥 。安全参数决定预期的抗攻击强度,通常也会影响密钥大小和计算开销。公钥不一定是较短的数值,私钥也不一定用单个秘密整数表示;它们的结构取决于具体构造。
在公钥加密中,任何持有 的人都可以将消息 转换为密文。其典型的抽象描述为
其中, 是安全参数, 表示本次加密新生成的随机量。正确性要求有效密文能够解密为原始消息:要么始终成功,要么失败概率小到可按要求忽略不计。现代安全加密通常采用随机化方式:对同一消息加密两次,不应泄露两次加密的原始消息相同这一信息。
数字签名的用途则不同。签名私钥用于对消息生成签名,验证公钥用于检验签名。签名为特定数据获得签名密钥授权提供证据,并使未经授权的篡改可以被检测出来。签名不会隐藏消息。有效签名本身也不能独立证明某个特定的人有意批准了相关内容:遭到入侵的设备、受委托的签名服务以及自动化流程,都可能生成密码学上有效的签名。
密钥建立为后续的对称密码运算创建共享秘密材料。在迪菲–赫尔曼密钥交换等密钥协商过程中,双方都参与最终秘密的生成。在密钥封装机制(简称 KEM)中,封装算法使用接收方的公钥,同时生成共享秘密和封装密文。接收方使用私钥恢复出相同的秘密。KEM 通常不接受任意应用消息作为明文;它输出的是密钥材料。
这些功能不应混为一谈。将签名描述为“用私钥加密”是一种常见但具有误导性的说法,即使对于底层算术运算可支持这两种功能的 RSA 也是如此。安全的加密方案和签名方案采用不同的编码方式、安全性定义和处理规则。许多重要算法只支持其中一种功能。椭圆曲线签名密钥并不天然就是加密密钥,后量子 KEM 也不是签名算法。因此,协议会按用途标识密钥,并且通常将签名密钥、解密密钥和密钥协商密钥分开。
数学基础与计算假设
公钥密码学利用这样一类数学运算:沿授权方向计算时效率很高,但在没有额外信息的情况下,逆向计算被认为十分困难。陷门函数体现了这一思想的一种重要形式:函数求值高效,求逆通常很困难,而秘密信息可以使求逆变得高效。并非所有公钥构造都最适合用陷门函数来描述,但合法计算容易、未授权计算困难这一对比是其根本所在。
RSA 展示了如何利用保密的因数分解进行算术运算。两个大素数 和 定义模数 。选择一个在模 下可逆的公钥指数 ,并使私钥指数 满足
其底层变换为
知道 和 就能高效地算出私钥指数。因此,分解模数即可破坏普通 RSA 的密钥安全性。不过,恢复 RSA 明文这一一般性问题尚未被证明与整数分解等价。这些等式描述的是算术核心,而不是一套完整且安全的加密方案。
离散对数系统使用这样一种群:其中的幂运算可以高效完成,但求出指数被认为十分困难。在生成元为 的适当循环群中,秘密值 确定公开值 。根据 和 计算 ,就是离散对数问题。Diffie–Hellman 的安全性涉及一些相关假设,即根据公开值 和 计算 ,或辨别某个值是否为 的困难性。这些假设彼此相关,但并非在所有群或证明中都能互换。
椭圆曲线密码学使用由有限域上椭圆曲线的点构成的群。其基本运算是标量乘法,记作 :按照群运算法则,将点 与自身反复相加。对于经过妥善选择的曲线和参数,根据 和 求出 被认为十分困难。由于目前已知最优的通用经典攻击与针对有限域离散对数或整数分解的攻击具有不同的复杂度特征,椭圆曲线可以用小得多的公钥表示实现相当的安全性。
这里的“困难”是计算意义上的,而非绝对意义上的。计算复杂性为分析算法和攻击者所需资源提供了一个框架,但实际安全性还取决于具体的攻击成本和数学结构。目前,尚无一般性证明能够表明,广泛部署的经典公钥方案所依赖的假设确实具有计算困难性。不合适的群、薄弱的素数生成方法、特殊的曲线结构,或未曾预料到的算法,都可能使原本看似合理的安全性估计失效。因此,参数选择既依赖形式化定义,也依赖持续深入的数学分析。
主要算法族与参数选择
RSA 因其部署广泛、实现支持成熟,以及在采用适当方案时既可用于加密也可用于签名,至今仍是一个主要的算法族。现代 RSA 加密通常采用最优非对称加密填充(OAEP),而 RSA-PSS 则是一种已被广泛纳入标准的概率签名方案。这些方案各自的编码方式是其构造不可或缺的组成部分。仅由模幂运算构成的“教科书式 RSA”具有确定性和代数可延展性,无法提供现代加密所要求的安全性。
基于有限域离散对数的系统包括传统的 Diffie–Hellman 和 ElGamal 加密。在适当群的乘法记号下,ElGamal 公钥为 。使用新生成的随机数 对群元素 加密,得到
利用私钥可恢复出 。这一构造展示了如何通过共享秘密的计算来掩蔽消息,但基本的 ElGamal 密文具有可延展性。在攻击者能够提交经修改的密文并请求解密的场景中,还必须采用额外的构造。
椭圆曲线系统包括用于密钥协商的 ECDH,以及用于签名的 ECDSA 和 EdDSA。X25519 是一种广泛部署的椭圆曲线 Diffie–Hellman 函数,而 Ed25519 则是 EdDSA 族中的一种签名系统。它们的名称表明其数学背景相关,并不意味着密钥类型可以互换,也不意味着它们在协议中的作用相同。不同标准采用的曲线模型、坐标表示、编码方式和公钥验证规则也各不相同。
不同算法族的密钥长度不能直接比较。在常用的经典安全性估算中,采用 3,072 位模数的 RSA,以及群参数约为 256 位的适当椭圆曲线系统,目标安全强度均约为 128 位。这意味着,在相关模型下,估计的攻击成本与 次基本运算处于同一数量级,而不是说每一种攻击都必须恰好执行这么多次运算。公钥长度、私钥长度、签名长度和安全强度是彼此独立的量。
其他算法族进一步拓展了公钥密码学的数学基础。基于格的构造利用涉及高维格的问题,通常以带噪声的模方程组为基础。基于编码的构造则利用这样一种困难性:在不知道秘密结构的情况下,对适当的纠错码进行译码十分困难。基于散列的签名通过密码散列函数构建认证机制,而不是依赖整数分解或离散对数。这些方法在公钥大小、密文或签名大小、计算量以及运行约束方面存在显著差异。与此同时,基于配对的系统能够实现基于身份的加密和某些聚合签名等专门功能,但需要采用普通椭圆曲线乘法之外的假设与实现技术。
安全定义与对手模型
一个密码系统即使能够防止私钥被恢复,也仍可能泄露有关消息的有用信息。因此,现代密码学根据对手的能力和可量化的攻击成功程度来定义安全性,而不只是考察某个数学逆运算是否困难。威胁模型规定了攻击者能否观察通信流量、选择消息、请求签名、篡改协议交互,或获取选定密文的解密结果。
对于加密,一个核心目标是选择明文攻击下的不可区分性,通常缩写为 IND-CPA。通俗地说,攻击者选择两条等长消息,并获得其中一条消息的密文。攻击者判断究竟哪条消息被加密时,相比随机猜测所能获得的优势应当可以忽略不计。由于任何人都可以使用公钥进行加密,确定性公钥加密通常无法满足这一定义:攻击者可以加密候选消息,再比较所得结果。随机化可以防止这种简单的试探。
选择密文安全性针对的是能力更强的攻击者:这类攻击者可以访问解密服务,但须遵守某些限制,例如不得提交挑战密文本身。自适应选择密文安全性,即 IND-CCA2,涵盖了后续查询依赖先前回答的攻击。这对实际协议十分重要,因为错误消息、时间差异和应用程序的响应都可能泄露有关解密结果的信息。一种能够抵御被动观察的方案,在嵌入交互式系统后却可能不再安全。
对于签名,标准目标是自适应选择消息攻击下的存在性不可伪造性。攻击者可以获取其自行选择的消息的签名,但应当无法为一条新消息生成有效签名。更强的定义还禁止攻击者为已经签过名的消息生成新的有效签名。仅靠签名验证无法防止重放:协议必须将签名与预期的上下文、身份、交易或会话绑定。
安全性证明将这些定义与假设联系起来。归约论证通常表明,如果存在能够成功攻破某方案的攻击者,就可以将其转化为求解某个被认为很难的问题的算法。这类结果的价值取决于所依据的假设、归约在定量上的紧致程度,以及所采用的模型。有些方案是在随机预言机模型中分析的,其中以一个理想化的随机函数代替哈希函数。这样的证明提供了重要依据,但并不等同于对每一种具体哈希实现都给出了证明。
这些定义也有适用边界。它们可能并不涵盖流量分析、端点失陷、物理泄露,或对已恢复明文的滥用。形式验证可以在明确的假设下,证明协议模型和实现具备某些性质,但这些模型与实际部署环境之间是否相符,仍然至关重要。数学安全性、协议安全性和运行安全性是相互关联的不同层次,而不是可以彼此替代的保障。
混合加密与网络协议
公钥算法通常不适合直接加密大批量数据。与对称算法相比,它们的计算开销更高,往往限制输入大小,还可能需要复杂的编码。因此,实际系统采用混合加密:先通过公钥机制建立共享秘密,再用密钥派生函数将该秘密转化为应用所需的密钥,最后用对称密码保护实际数据。
现代混合加密设计通常将密钥封装机制(KEM)与数据加密机制相结合。封装过程产生密文 和共享秘密 。密钥派生函数根据 派生出对称密钥,通常还会纳入协议标识符和上下文信息。随后,应用消息通过认证加密得到保护,既能确保机密性,又能检测未经授权的改动。传输的内容包括封装密文和经过对称加密的载荷。各部分必须正确组合:某个组件本身安全,并不意味着包含它的所有组合都安全。
传输层安全协议展示了这些机制如何协同工作。在典型的基于证书认证的 TLS 1.3 连接中,临时 Diffie–Hellman 密钥交换用于建立共享秘密,服务器签名用于认证握手,而对称认证加密则保护应用流量。TLS 1.3 还支持具有不同特性的预共享密钥模式。RSA 可以通过签名对 TLS 1.3 服务器进行认证,但用服务器的 RSA 密钥加密预主密钥这一较早的做法,并不属于 TLS 1.3 的一部分。
这一区别对前向保密至关重要。如果会话密钥依赖于每次新生成、且随后会被擦除的临时 Diffie–Hellman 秘密值,那么长期认证密钥的泄露未必会导致过去被记录的会话内容暴露。相反,如果攻击者记录了采用静态 RSA 密钥传输的会话,之后又获取了相应的 RSA 私钥,就可能恢复该会话的预主密钥。因此,前向保密是协议及其密钥处理方式的一种属性,而不是公钥加密普遍具备的属性。
未经认证的 Diffie–Hellman 密钥交换无法阻止主动的中间人分别与双方建立共享秘密,并在篡改通信内容后进行转发。认证必须将此次交换与预期的通信对端及相关的握手记录绑定。安全协议还会将算法选择和参与方角色纳入计算,以抵御替换攻击、降级攻击和跨协议攻击。
包括混合公钥加密(HPKE)在内的标准化混合加密构造,明确规定了封装、派生、加密与上下文绑定如何配合。其他协议还加入持续的密钥更新或棘轮机制,使系统在密钥泄露和后续恢复方面的安全特性随时间演变。这些设计说明了为什么公钥密码学通常只是一个更大的有状态系统中的组件:身份、消息顺序、重放防护和密钥删除,都会影响应用最终获得的安全保障。
公钥分发与信任基础设施
公钥可以公开发布,但发布本身并不能证明其归属。如果攻击者将加密密钥替换为另一把密钥,发送方就可能直接为攻击者加密机密信息。同样,如果将攻击者的验证密钥误认为属于可信的软件发布者,恶意签名就会显得有效。公钥密码学将密钥分发问题的重心,从对密钥保密转向了验证公钥的真实性。
公钥基础设施(PKI)通过证书、签发者、验证规则和信任锚来组织这种身份认证。X.509 证书将公钥与名称或其他属性绑定,并附有签发者的数字签名。验证方会检查通向本地受信任机构的证书路径,验证签名和有效期,并施加有关密钥用途、名称和签发机构权限的约束。正确验证证书上的签名是必要条件,但并不充分:证书还必须适用于当前请求所涉及的特定身份和用途。
在万维网上,证书颁发机构为域名签发证书,网页浏览器及其他客户端则维护信任库。一个域名的证书通常不适用于另一个域名。客户端必须将所请求的服务身份与证书允许的名称进行匹配,并应用相关验证规则。即使与经过身份认证的域名进行加密通信,也不能据此认定该域名的运营者诚实可信,或其内容安全。
证书有有效期,也可能需要在到期前撤销。证书撤销列表和在线证书状态协议提供了通报证书状态的机制,但可用性、隐私、缓存和客户端行为等因素使其使用变得复杂。证书透明度为证书增加了可公开审计、仅允许追加的日志。日志记录有助于发现未经授权的证书签发,但不能替代证书验证,也不能单凭日志就认定某次签发是合法的。
其他信任模型则绕开或补充了层级式证书颁发机构体系。安全外壳协议(SSH)通常采用首次使用信任机制:客户端保存首次遇到的主机密钥,并在密钥发生变化时发出警告。只有最初建立的关联可信,这种机制才能保护后续连接。OpenPGP 支持用户之间相互认证公钥,并可结合社交信任关系或直接核验来使用。一些即时通信系统会显示指纹或简短认证字符串,供参与者通过另一条渠道比对公钥身份。
信任也会随时间变化。密钥会轮换,组织的运营者会变更,设备会丢失,算法也会过时。密钥标识符或指纹有助于区分密钥,但如果没有经过认证的关联,就无法证明密钥归谁所有。同样,数字签名的证据意义取决于相关的身份确认流程、记录及适用规则;仅凭数学验证结果,无法判定这些问题。
实现安全与密钥管理
密码方案即使在数学上严密可靠,也可能因实现问题而失效。密钥生成需要从合适的随机数生成器获取不可预测的秘密材料。随机数重复或存在偏差,可能危及整批密钥的安全。2012 年,研究人员发现,从网络设备收集到的部分 RSA 公钥具有共同的素因子。通过计算受影响模数之间的最大公约数,便能推导出对应的私钥,而无须在通用整数分解方法上取得突破。
每条消息所用的随机数同样可能至关重要。在 ECDSA 中,签名包含一个由秘密的一次性随机数 推导出的值,其中一个分量满足
其中, 是签名私钥, 是消息哈希值的代表值。对不同消息重复使用同一个一次性随机数,可能使攻击者先恢复 ,进而恢复 。随机数的偏差或部分泄露也可能带来危险。确定性的一次性随机数生成过程根据秘密输入和与消息相关的输入推导出一次性随机数,从而减少对新生成的外部随机数的依赖,但这并不能消除所有实现风险。
侧信道攻击利用预期输入和输出之外的信息来恢复秘密,例如执行时间、缓存行为、功耗或电磁辐射。恒定时间编程力求防止控制流和内存访问随秘密数据而变化。RSA 盲化通过随机化中间计算过程来减少某些形式的信息泄露。故障攻击则利用人为诱发的错误;例如,使用中国剩余定理计算出的错误 RSA 签名,若没有保护性检查加以拦截,就可能泄露模数的一个因子。
输入处理是另一个重要的安全边界。公钥、群元素、密文和签名都必须按照具体方案的要求进行解码和验证。缺少检查可能导致无效曲线攻击或小子群攻击。不同的曲线构造需要不同的处理方式,因此不能无视算法规范,将一种算法的验证规则直接套用于另一种算法。错误处理也必须避免泄露解密是否在某个敏感的中间阶段失败。
丹尼尔·布莱兴巴赫于 1998 年针对采用 PKCS #1 v1.5 的 RSA 加密发起的攻击,展示了区分此类失败情况的后果。如果一项服务会透露解密后数据的格式是否有效,它就可能成为解密预言机。通过反复进行自适应查询,攻击者即使无法获取私钥,也能恢复明文。这一事件促使人们认识到,外部可观察到的失败行为也是密码接口的一部分。
私钥还需要全生命周期的管理与控制。硬件安全模块可以生成和使用密钥,而不向普通应用软件暴露密钥的原始值。但它无法自动阻止已获授权却遭到入侵的应用程序请求生成恶意签名。访问控制、审计、备份策略、删除以及职责分离仍然不可或缺。密钥管理要求也因用途而异:恢复组织的加密密钥可能有助于保留对记录的访问能力,而复制签名密钥则会增加能够生成签名的位置。
量子计算与后量子转型
主要的经典公钥密码体系面临着来自量子算法的独特威胁。1994 年,彼得·肖尔提出了可在多项式时间内完成整数分解和求解离散对数的量子算法。在规模足够大、具备容错能力的量子计算机上,这些算法将破坏 RSA、有限域迪菲–赫尔曼、椭圆曲线迪菲–赫尔曼以及广泛使用的离散对数签名方案的安全性。这种威胁源于底层数学问题,而不只是参数选得太小。
实施这些攻击所需的条件,远不止演示少量物理量子比特的运行。长时间的计算需要可靠的逻辑操作和大量的量子纠错。资源需求的估算取决于目标算法、硬件错误率、体系架构以及允许的运行时间。尽管如此,这种数学上的脆弱性仍促使人们在此类机器问世之前就做好准备,尤其是在系统或受保护信息需要长期使用或保密的场景中。
在保密性方面,存在一种跨越时间的风险,通常称为“现在收集,日后解密”。攻击者可以在今天记录加密通信,待未来具备相应能力时再尝试恢复其密钥。经典的临时迪菲–赫尔曼密钥交换能够提供前向保密性,抵御长期认证密钥日后泄露带来的威胁;但如果未来的算法能够求解该交换所依赖的底层数学问题,它就无法保护已经被记录下来的交换过程。抗量子能力与前向保密性应对的是不同的威胁。
后量子密码学致力于开发在常规计算硬件上运行、旨在同时抵御经典攻击和量子攻击的方案。2024 年 8 月,美国国家标准与技术研究院发布了针对 ML-KEM 的 FIPS 203、针对 ML-DSA 的 FIPS 204,以及针对 SLH-DSA 的 FIPS 205;这三种方案分别源自 CRYSTALS-Kyber、CRYSTALS-Dilithium 和 SPHINCS+。这些标准涵盖密钥封装以及两种不同的数字签名技术路线。标准化并不意味着一种方案不再依赖安全假设,但它提供了可互操作的规范,以及以公开评估为依据的参数。
迁移所涉及的远不只是选择替代算法。后量子方案的公钥、密文或签名可能远大于相应的椭圆曲线方案,进而影响握手数据量、证书处理、内存占用以及资源受限设备的运行。一些过渡设计将经典机制与后量子机制结合起来,使得只要至少一个组件仍然安全,最终得到的秘密就依然受到保护。要实现这一目标,需要设计合理的组合机制和经过认证的协商,而不是简单地拼接任意输出。
量子密钥分发是另一种独立的技术,它使用量子通信,同时仍然需要经过认证的经典通信。它不能取代公钥签名的一般功能,也不能直接替代普通互联网中的公钥基础设施(PKI)。对于公钥系统,持续开展的研究则着重探索抗量子的安全假设、更紧致的安全归约、高效的实现,以及能够适应算法变更而不引入降级攻击途径或破坏身份验证的协议设计。