第1章 传统公钥加密

1.1 引言

为了保障存储和传输数据的机密性，需要对原始数据（称为明文）进行加密处理，把明文转换成无实际意义的乱码（称为密文）。在公钥密码体制以前的整个密码学历史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，大多基于代换和置换两个基本运算。在基于代换-置换网络设计的加密算法中，加密数据使用的秘密值（加密密钥）和解密密文使用的秘密值（解密密钥）是相同的，这类算法体制称为单密钥体制或对称密码体制。对称密码体制具有加密和解密效率高的特点，但要求双方在通信前，事先共享一个会话密钥（也称为数据加密密钥），在跨域系统中存在密钥分配的难题。同时，在多用户的网络中，任何两个用户之间都需要有共享的会话密钥，当网络中有很多用户时，每个用户需要管理的会话密钥数量非常大，存在密钥管理问题。此外，当接收方Bob收到发送方Alice的电子文档时，无法向第三方证明此电子文档来源于Alice，不能实现不可抵赖性。

为了解决对称密码体制存在的上述问题，美国斯坦福大学的Whitefield Diffie和Martin Hellman于1976年提出了公钥密码体制（Public Key Cryptosystem，PKC）的概念。公钥密码体制为密码学的发展提供了新的理论和技术基础，公钥密码算法的基本工具不再是代换和置换，而是陷门单向函数。在公钥密码体制中，采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公钥，用于加密。另一个密钥是用户专用的，因而是保密的，称为私钥，用于解密。在已知公钥的情况下，求解对应的私钥在计算上是不可行的。公钥密码体制也称为双钥密码体制或非对称密码体制。公钥加密体制的框架如图1-1所示。

设用户Alice的公私钥对为(pk_A,sk_A)，用户Bob的公私钥对为(pk_B,sk_B)，其中pk_A和pk_B分别为Alice和Bob的公钥，sk_A和sk_B分别为Alice和Bob的私钥。如果Alice需要安全发送消息M给Bob，可利用Bob的公钥pk_B加密消息M并把密文C发送给Bob。当收到来自Alice的密文C后，Bob利用自己的私钥sk_B对密文进行解密，进而恢复出明文数据M。一方面由于pk_B是公开的，任何人都可以给Bob发送加密数据；另一方面sk_B只有Bob知道，因此只有Bob才能够正确解密。公钥密码体制有效解决了对称密码体制中存在的密钥管理和密钥分配问题。

公钥密码算法是以非对称的形式巧妙地使用两个密钥。两个密钥的使用对保密性、密钥分配、认证等都有深刻的意义。公钥密码体制的出现在密码学历史上是一个伟大的革命，它在密钥分配和数字签名（数字签字）领域起到重要作用。本章将着重介绍4个经典且具有代表性的公钥加密算法并给出对应的安全性分析，包括RSA公钥加密算法、ElGamal公钥加密算法、Cramer-Shoup公钥加密算法和我国自主设计的SM2公钥加密算法。