4.1 公钥密码体制的基本原理

4.1.1 公钥密码体制的概念

1976年由Diffie和Hellman在其“密码学新方向”一文中提出了不对称密钥密码的思想，首次证明发送端和接收端无密钥传输的保密通信是可能的，公钥算法具有以下特点：

● 加密与解密由不同的密钥完成，其中KU是公开的，称为公开密钥（public key），KR是保密的，称为私有密钥（private key）。

加密：X→Y:Y = EKU（X）

解密：Y→X:X = DKR（Y）= DKR（EKU（X））

● 知道加密算法，从加密密钥得到解密密钥在计算上是不可行的。

● 两个密钥中任何一个都可以用做加密而另一个用做解密，这一条不是必需的。

X = DKR（EKU（X））= EKU（DKR（X））

公钥密码算法可以用于加密、数字签名（身份鉴别）和密钥交换。基于公钥密码算法的加解密过程如图4.1所示。其主要步骤如下：

（1）每一个用户拥有自己的密钥对（KU，KR）。

（2）每一个用户把公钥KU公开，私钥KR保密，每一用户可以拥有其他用户的公钥。

（3）若A要给B发送消息，则用B的公钥KUb对消息X加密，A→B: Y = EKUb（X）。

（4）当B收到密文Y后，用私钥KRb解密，DKRb（Y）= DKRb（EKUb（X））= X，由于只有B拥有自己的私钥KRb，所有其他接收者都不能解密消息。

用公钥密码实现鉴别的过程如图4.2所示，主要步骤如下：

（1）用户A用自己的私钥对消息X签名，A→ALL: Y = EKRa（X）。

（2）收到签名Y 的其他人都可以用A的公钥KUa对消息的签名进行验证，DKUa（Y）=DKUa（EKRa（X））= X，因为只有A才拥有能产生KUa能验证的签名的私钥KRa，如果验证正确的话，就可以相信消息的确是A发出的。

如果两次使用公钥密码算法，则可以既实现鉴别，又保证消息的保密性，其主要步骤如下：

（1）发送方A先用自己的私钥KRa对消息进行签名，然后再用接收方B的公钥KUb加密，A→B: Z = EKUb（DKRa（X））。

（2）接收方B收到密文，先用自己的私钥KRb解密，再用对方的公钥KUa验证签名的正确性，EKUa（DKRb（Z））= X。

4.1.2 公钥密码体制的应用

一般地，公钥密码体制的应用可以分为三类：

● 加解密：发送方用接收方的公钥加密，接收方用自己的私钥解密。

● 数字签名：发送方用自己的私钥对消息签名，接收方用发送方的公钥验证签名。我们将在第5章讨论数字签名的特性和相关问题。

● 密钥交换：通信双方交换会话密钥。有多种方法可用于密钥交换。

有些算法可用于上述三种应用，而一些算法只适用于其中的一两种应用。表4.1列出了一些典型的公钥算法及其应用。

4.1.3 公钥密码体制的思想和要求

公钥密码体制涉及到三方：发送方、接收方、攻击者，涉及到数据有：公钥、私钥、明文和密文。Diffie和Hellman并没有给出具体的公钥密码体制，但对这种体制提出了一些要求。公钥算法的基本要求包含安全性和计算可行性两方面，分述如下：

● 用户B产生一对密钥（公钥KUb，私钥KRb）是计算可行的。

● 已知B的公钥KUb和明文X，发送方A产生密文Y是计算可行的。

● 接收方B利用其私钥KRb来解密密文Y是计算可行的。

● 对于攻击者，利用B的公钥KUb来推断其私钥KRb是计算不可行的。

● 已知公钥KUb和密文Y，恢复明文X是计算不可行的。

● 加密和解密的顺序可交换，这一条对于算法不是必需的。

从数学上可以使用单向陷门函数来表示以上要求，单向陷门函数是满足下列条件的函数f：

（1）给定x，计算y = fk（x）是容易的。

（2）给定y，计算x使x = fk-1（y）是不可行的。

（3）存在k，已知k 时，对给定的任何y，若相应的x存在，则计算x = fk-1（y）是容易的。

通常，容易是指一个问题可以在输入长度的多项式时间内得到解决。不可行的定义比较模糊，一般而言，若解决一个问题所需要的时间比输入规模的多项式时间增长更快，则称问题是不可行的。

而严格单向函数是不能用于加解密的，一个单射函数f：X→Y称为是严格单向函数，如果下述条件成立：存在一个有效的方法，对所有的x∈X可计算f（x），但不存在一个有效的办法，对所有的y∈Y由y = f（x）计算x。现在还无法证明严格单向函数的存在。

4.1.4 公钥密码体制的安全性

4.1.4.1 公钥密码体制的安全目标和攻击类型

公钥密码体制用于加密时，其安全性按照目标可以分为三种：

● 单向性（One-way, OW）：指没有密钥时密文不能恢复相应的明文，这是一个加密机制最基本的要求。

● 不可区分性（Indistinguish ability, IND）：指给定的两个明文，加密者随机地选择其中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密。

● 非延展性（Non-malleability，NM）：指给定一个密文，攻击者的目的是构造与已给密文相关的新密文，而安全性要求攻击者无法构造与已给密文相关的新密文。

以上安全性概念依次加强，NM比IND安全性强，IND比OW安全性强。

按照攻击者模型可分为：

● 选择明文（Chosen plain text attack, CPA）攻击：攻击者可以适当地选择明文，获得相应的密文。在公钥密码中，攻击者拥有公钥，可以随便加密，进而实现选择明文攻击。为了抵抗选择明文攻击，可以通过对报文附加随机比特来实现。

● 明文校验攻击（Plain text check attack, PCA）：攻击者可以对一个明文密文对（m，c），回答c是否由m加密得来。

● 选择密文攻击（Chosen cipher text attack，CCA）：攻击者可以选择密文获得相应的解密。选择密文攻击可以进一步分为非适应性和适应性两种。适应性选择密文攻击强度最高。

公钥密码和对称方案一样，进行强力攻击是计算上不可行的。公钥密码体制的安全性基于一些陷门单向函数，只是计算上不可行，要求使用非常大的数，通常要大于512 位，因此比对称方案计算速度慢。由于公钥密码体制的安全性是指计算上的安全性，安全性的理论基础是复杂性理论。关于复杂性理论，我们给出以下一些概念的简单介绍。

4.1.4.2 算法复杂性

问题是需要回答的一般性提问，通常含有若干个未定参数或自由变量。对问题的描述包括两部分，一部分是给定所有的未定参数的一般性描述，另一部分是陈述“答案”或“解”必须满足的性质。

算法是求解某个问题的一系列具体步骤，通常可理解为求解某个问题的通用计算机程序。一个算法的复杂性由该算法所需求的最大时间（T）和存储空间（S）度量。由于算法用于同一问题的不同规模实例所需求的时间和空间往往不同，所以总是将它们表示成问题实例的规模 n的函数，n表示描述该实例所需的输入数据长度。

算法复杂性用“大O”的符号来表示，它表示算法复杂性的数量级。f（n）= O（g（n））意味着存在常数c和n0，使得对一切n≥ n0，有f(n)≤ c g(n)。通常按时间（或空间）复杂性对算法进行分类。一个输入数据规模为n的算法被称为是：

● 线性的：如果运行时间是O（n）。

● 多项式的：如果运行时间是O（nt），其中t是一个常数。

● 指数的：如果运行时间是O（th（n）），其中t是一个常数，h（n）是一个多项式。

一般地，一个可以在多项式时间内解决的问题被认为是可解的，而需要比多项式时间更长的时间，尤其是指数时间求解的问题在实践中往往被认为是不可解的。

4.1.4.3 问题复杂性

问题复杂性理论利用算法复杂性理论作为工具，将大量典型的问题按求解代价进行分类。

图灵机是一种具有无限读、写能力的有限状态机。图灵机分为确定型和非确定型两种。确定型是指图灵机的每一步操作的结果是唯一确定的。所谓非确定型图灵机的每一步操作结果及下一步操作都允许有多种选择，不是唯一确定的。

一个问题的最坏情况下的复杂性由在图灵机上解此问题的最难实例所需要的最小时间与空间决定，即解此问题的最有效算法所需的时间与空间来度量。在确定型图灵机上用多项式时间可解的问题，称为易处理问题。易处理判定问题的全体称为确定型多项式时间可解判定问题类，记为P。在非确定型图灵机上用多项式时间可解的判定问题，称为非确定型多项式时间可解判定问题，简称NP问题。NP问题的全体称为非确定性多项式时间可解判定问题类，记为NP。对于NP问题的求解一般分为猜测和验证阶段。目前还没有人证明P≠NP。背包问题（knapsack），又称子集和问题（subset sum），属于NP问题。