公钥密码学
公钥（非对称）密码学使用数学关联的密钥对——一个用于加密或签名验证的公钥和一个用于解密或签名的私钥——从而使从未见过面的双方能够安全通信。
Definition
公钥密码学是密码学的一个分支，其中每个参与方都持有一对密钥——一个可以自由共享的公钥和一个保密的私钥——使得用一个密钥执行的操作可以用另一个密钥进行反转或验证。
Scope
该领域涵盖基于密钥对的密码学，其安全性依赖于计算困难性假设，例如整数分解和离散对数问题。它包括公钥加密（RSA、ElGamal）、密钥建立（Diffie-Hellman）、椭圆曲线密码学和数字签名。它解决了这些方案所依赖的陷门和单向结构以及标准安全目标（语义安全性、不可伪造性）。它不包括对称原语以及分发公钥的证书和信任基础设施（在系统和网络安全部分涵盖）。
Sub-topics
Core questions
- 双方如何在不预先共享秘密的情况下安全通信？
- 哪些计算问题（分解、离散对数）使得公钥方案难以破解？
- 什么是陷门单向函数，它如何实现公钥加密？
- 数字签名如何提供真实性和不可否认性？
- 为什么公钥密码学在实践中与对称密码学结合使用？
Key concepts
- 公钥和私钥对
- 陷门单向函数
- 整数分解问题
- 离散对数问题
- RSA
- Diffie-Hellman 密钥交换
- 椭圆曲线密码学
- 数字签名
- 混合加密
Key theories
- 陷门单向函数
- 公钥加密依赖于易于计算但如果没有秘密“陷门”信息则难以反转的函数；RSA 的模幂运算只有在知道模数分解的人才能轻松反转。
- 公钥思想和密钥交换
- Diffie 和 Hellman 表明，双方可以使用单向函数通过公共信道协商共享秘密，并提出将密码密钥分为公钥和私钥部分——从而开创了公钥密码学领域。
- 困难性假设
- 非对称安全性是条件性的：方案的安全性是相对于基础问题（如整数分解、RSA 问题以及有限域或椭圆曲线群中的离散对数）的假定难解性来证明的。
Clinical relevance
公钥密码学是几乎所有安全互联网通信的基础：TLS 使用它来认证服务器和建立会话密钥，代码签名和软件更新依赖于数字签名，安全电子邮件（PGP、S/MIME）和SSH使用密钥对，证书颁发机构将身份绑定到公钥。加密货币使用公钥签名来授权交易。在实践中，它与快速对称密码学结合在混合方案中使用。
Evidence & guidelines
RSA、Diffie-Hellman 和椭圆曲线变体（ECDH、ECDSA、EdDSA）已标准化（PKCS、NIST SP 800-56、FIPS 186）。NIST 建议至少使用 2048 位 RSA/DH 或 224 位椭圆曲线以实现经典安全性。由于 Shor 算法对量子计算机构成威胁，NIST 已标准化了后量子替代方案（单独涵盖）。
History
公钥密码学由 Diffie 和 Hellman 于 1976 年公开发表（并由 GCHQ 的 Ellis、Cocks 和 Williamson 在秘密工作中独立完成）。RSA 密码系统紧随其后于 1977-1978 年问世，提供了第一个实用的公钥加密和签名方案。ElGamal（1985 年）在离散对数基础上构建了加密和签名，Koblitz 和 Miller 于 1985 年独立提出了椭圆曲线密码学，从而实现了更小的密钥。
Key figures
- Whitfield Diffie
- Martin Hellman
- Ralph Merkle
- Ronald Rivest
- Adi Shamir
- Leonard Adleman
Related topics
Seminal works
- diffie1976
- rivest1978
- katz2020
Frequently asked questions
- 为什么公钥密码学不用于所有加密？
- 公钥操作比对称操作慢得多，并且会增加密文开销。实际系统仅使用公钥密码学来认证双方并协商对称会话密钥，然后对称加密大量数据——这是一种混合方法。
- 量子计算机是否会破解公钥密码学？
- 运行 Shor 算法的大规模量子计算机将通过高效地分解和计算离散对数来破解 RSA、Diffie-Hellman 和椭圆曲线密码学。这就是为什么基于其他难题的后量子方案正在标准化和部署的原因。