公钥密码

针对对称加密（又称单钥加密）中密钥交换困难等缺陷，1976年，美国学者W.迪菲和M.赫尔曼在《密码学的新方向》一文中提出公钥密码的思想，并提出了第一个基于公钥密码的密钥交换算法。此算法有效解决了通信双方在无安全信道的情况下进行首次密钥交换的问题，大大降低了多用户通信环境中单个用户密钥存储及管理的复杂性，简化了密钥管理。

公钥密码的基本思想

将加密密钥与解密密钥分开，即每个用户拥有一对密钥，分别用于消息加密和解密。用户将加密密钥（简称公钥）公开，解密密钥（简称私钥）保密。任何可以获得公钥的人都可以实现对消息的加密；而仅私钥的持有者能实现解密。公钥密码的安全性要求攻击者从已知的公钥、加密算法与截获到的密文不能恢复出明文或者私钥。

分类及算法

公钥密码中最重要的两个分类是公钥加密与数字签名。①公钥加密。1978年，美国学者R.利维斯特，A.沙米尔和L.阿德曼基于大整数分解和欧拉定理发明了RSA公钥密码体制，首次实现了公钥加密。1984年，塔特尔加玛尔提出了基于离散对数问题的公钥密码体制ElGamal。其他典型的公钥密码体制包括Rabin公钥加密、Goldwasser-Micali公钥加密、Pailler公钥加密等。②数字签名。其含义是用户使用私钥对需验证的消息进行签名，而其他人则可借助公钥对签名进行验证。即可实现签名的公开可验证性以及签名人的不可否认性。典型的数字签名包括Schnorr签名、DSA签名等。

公钥密码算法一般基于某个计算困难问题，其方案的安全性建立在该问题在多项式时间内不可解的前提假设之下。公钥密码学中的典型困难问题包括大整数分解问题、离散对数（含椭圆曲线离散对数）问题、背包问题、LWE问题等。这些困难问题又派生出很多新的困难问题，如二次剩余问题、（强）RSA问题、计算性/判定性Diffie-Hellman问题等。称一个公钥密码体制是“安全”的，一般是指在给定的安全模型下，可形式化地证明该体制的安全性可以被规约到某困难问题的难解性之上。有很多因为缺乏安全证明或是安全证明有缺陷而导致公钥密码被攻破的例子。

应用

公钥密码学在理论及工程领域均取得长足进展。在理论方面，基于公钥/私钥的不同产生方式，由最初始的公钥密码体制（PKI）已经演化出基于身份的公钥密码、无证书的公钥密码、基于属性的公钥密码、基于谓词的公钥密码、功能密码体制等诸多变体。数字签名领域则有门限签名、盲签名、群签名、环签名、代理签名等许多变体。在工程领域，公钥密码的典型应用场景包括X.509、S/MIME、PGP、TLS、SSH、比特币和区块链等。在标准化领域，基于RSA的公钥密码和基于离散对数的多个公钥密码算法都进入了ISO和NIST等国际标准，如支持加密的RSA-OAEP算法、Cramer-Shoup算法、DHIES算法等。