在本节中，我们将关注基于第8.2.4节中定义的RSA假设的加密方案。我们注意到，尽管基于RSA的加密在今天得到了广泛的使用，但由于基于RSA的方案需要更长的密钥长度，目前也逐渐从使用RSA转向使用依赖于椭圆曲线组的基于CDH/DDH的加密系统。我们参考第9.3节进行进一步讨论。

11.5.1 普通RSA Plain RSA

我们首先描述一个基于RSA问题的简单加密方案。尽管该方案是不安全的，但它为随后的安全方案提供了一个有用的起点。假设GenRSA是一个ppt算法，它在输入1n上输出一个模N，该模N是两个N位素数的乘积，以及满足ed=1 mod φ（N）的整数e，d。（通常，该算法失败的概率可以忽略不计，但我们忽略了这一点。）回顾第8.2.4节，该算法可以很容易地从输出复合模N及其因子分解的任何算法GenModules构建；见算法11.25。

11.5.2 填充RSA和PKCS#1 v1.5 Padded RSA and PKCS #1 v1.5

11.5.3 无随机预言的CPA安全加密 CPA-Secure Encryption without Random Oracles

11.5.4 OAEP和RSA PKCS#1 v2.0 OAEP and RSA PKCS #1 v2.0

11.5.5 随机预言模型中的CCA安全KEM A CCA-Secure KEM in the Random-Oracle Model

我们在这里展示了一个基于RSA的KEM的构造，它在随机oracle模型中是CCA安全的。（回想定理11.14，任何此类构造都可以与任何CCA安全私钥加密方案结合使用，以提供CCA安全公钥加密方案。）与上一节中的RSA-OAEP方案相比，主要优势在于构造及其安全性证明的简单性。它的主要缺点是在加密短消息时会导致更长的密文，因为它需要KEM/DEM范式，而RSA-OAEP则不需要。然而，对于加密长消息，RSA-OAEP也将作为混合加密方案的一部分使用，并将导致加密方案具有与使用此处所示KEM获得的加密方案类似的效率。

我们描述的KEM是ISO/IEC 18033-2公钥加密标准的一部分。在该方案中，公钥通常包括<N、e>，并且指定了一个函数 alt ，该函数将在分析中建模为随机预言。（如第5.5节所述，此函数可以基于一些底层加密哈希函数。我们省略了细节。）为了封装密钥，发送方选择统一的 alt 然后计算密文 alt 和密钥k:=H（r）。要解密密文c，接收方只需以通常的方式恢复r，然后重新导出相同的密钥k:=H（r）。见第11.37节。

结构 11.37 CCA安全KEM（在随机oracle模型中） A CCA-secure KEM (in the random-oracle model)

让GenRSA像往常一样，按如下方式构造KEM：

Gen：在输入时，运行以计算<N，e，d>。公钥是<N，e>，私钥是<N，d>。作为密钥生成的一部分，函数指定了，但我们将其保留为隐式。
Encaps：在输入公钥<N、e>和时，选择一个统一的r∈ 输出密文和密钥k:=H（r）。
Decaps：输入私钥<N、d>和密文，计算并输出键k:=H（r）。

该计划的CPA安全性是即时的。事实上，密文c对于均匀 alt 等于 alt ，因此RSA假设意味着观察c的窃听者将无法计算r。这意味着窃听者不会查询r到H，因此从攻击者的角度来看，密钥 alt 的值保持一致。

事实上，上面的扩展也显示了CCA安全性。这是因为回答任何密文的解封装oracle查询 alt 只涉及在某些输入 alt 处计算H。因此，攻击者的解封装oracle查询不会显示有关质询密文封装的密钥H（r）的任何其他信息。（由于我们必须展示如何在不知道私钥的情况下模拟解封装oracle查询的答案，因此正式证明要稍微复杂一些。然而，这并不是很困难。）

定理 11.38

THEOREM 11.38 If the RSA problem is hard relative to GenRSA and H is modeled as a random oracle, then Construction 11.37 is CCA-secure.

如果RSA问题相对于GenRSA是困难的，且H被建模为随机预言，则构造11.37是CCA安全的。

Proof

设∏表示构造11.37，设A为概率多项式时间对手。为了方便起见，并且因为这是我们使用随机预言模型的全部功能的第一个证明，我们明确描述了实验 alt 的步骤：

运行以获得（N，e，d）。另外，一个随机函数已选择。
选择统一，并计算密文和密钥k:=H（r）。
均匀位b∈ 已选择{0，1}。如果b=0，则设置。如果b=1，则选择一个统一的。
A给定pk=<N、e>、c和，并且可以查询H（·）（在任何输入上）和任何密文上的解封装oracle。
A输出位b'。如果b'=b，则实验输出定义为1，否则为0。

在执行实验 alt 时，让Query为以下事件：

在执行过程中的任意一点，A向随机预言符H查询r。我们让Success表示b'=b的事件（即，实验输出1）。然后 alt

其中，所有概率均超过了 alt 实验中使用的随机性。我们证明了 alt 和Pr[Query]是可以忽略的。定理如下。

我们首先认为Pr=1。如果Pr[Query]=0，这是立即的。否则， alt 。现在，以 alt 为条件，正确键k=H（r）的值是一致的，因为H是一个随机函数。在实验 alt 中考虑A'关于K的信息。公钥pk和密文c本身不包含关于k的任何信息。（它们确实唯一地确定了r，但由于H是独立于其他任何东西而选择的，因此没有给出关于H（r）的信息。）

A对H的查询也不会显示关于r的任何信息，除非A对H的查询（在这种情况下发生查询）；这同样依赖于H是一个随机函数这一事实。最后，A对其解封装oracle进行的查询只显示了 alt 。这是因为 alt ，其中 alt ，但 alt 意味着 alt 。再一次，这和H是一个随机函数的事实意味着除非发生查询，否则不会显示关于H（r）的信息。

上述情况表明，只要不发生查询，正确密钥k的值是一致的，即使给定了A对公钥、密文和所有oracle查询的答案的看法。那么，在这种情况下，A无法区分（比随机猜测更好的） alt 是正确的键还是统一的独立键。因此， alt 。

我们要强调的是，在上述论证中，我们没有依赖于A在计算上是有界的这一事实，事实上，即使没有对A施加计算限制，也没有依赖于 alt 。这表明了随机预言模型的部分威力。

为了完成定理的证明，我们展示

CLAIM 11.39

CLAIM 11.39 If the RSA problem is hard relative to GenRSA and H is modeled as a random oracle, then Pr[Query] is negligible.

如果RSA问题相对于GenRSA来说很难解决，并且H被建模为随机oracle，那么Pr[Query]可以忽略不计。

为了证明这一点，我们构造了一个算法A'，该算法使用A作为子例程。A'给出了RSA问题的一个实例N、e、c，其目标是计算r，其中 alt 。为此，它将运行A，回答其对H和Decaps的查询。处理对H的查询很简单，因为A'只能返回一个随机值。然而，由于A'不知道与有效公钥<N，e>相关联的私钥，因此对Decaps的查询更为棘手。

然而，进一步考虑，去封装查询也很容易回答，因为A'也可以在这里返回一个随机值。也就是说，虽然查询 alt 应该通过首先计算 alt 来计算，使得 alt ，然后计算 alt ，但结果只是一个统一的值。

因此，A'可以简单地返回随机值，而无需执行中间计算。唯一的“陷阱”是A'必须确保其对H查询和Decaps查询的答案之间的一致性；也就是说，它必须确保对于任何 alt ，它保持 alt 。这是使用简单的簿记来处理的，并列出 alt ，它们跟踪A'在响应各自的oracle查询时给出的答案。我们现在给出细节。

算法A' Algorithm A':

算法以（N，e，c）作为输入。

初始化空列表。选择一个统一的并将（c，k）存储在中。
选择一个统一的位b∈ {0, 1}. 如果b=0，则设置如果b=1，则选择一个统一的。在<N、e>、c和上运行A。

当A发出一个查询 alt 时，按如下方式回答：

如果在表格的左侧中有某个k的条目，则返回k。
否则，设。如果在中有一个表格中的条目表示某些k，则返回k并将存储在中。
否则，选择统一的，返回k，并在中存储。

当A进行 alt 查询时，请按如下方式回答：

如果表格中的中有某个k的条目，则返回k。
否则，对于每个条目，检查，如果是，输出k。
否则，选择统一的，返回k，并在中存储。

3.在A的执行结束时，如果 alt 中有一个条目，其中 alt ，则返回r。

显然A'在多项式时间内运行，实验 alt 中A'作为子程序运行时， alt 的视图与实验 alt 中A的视图相同：给A的输入明显具有正确的分布，A的oracle查询的答案是一致的，所有H查询的响应都是一致和独立的。最后，A'在查询发生时准确地输出正确的解决方案。因此，相对于GenRSA，RSA问题的难度意味着Pr[Query]可以根据需要忽略不计。

值得注意的是，上述证明中使用的随机oracle模型（见第5.5.1节）的各种属性。首先，我们依赖于一个事实，即值H（r）是一致的，除非r被查询到H-即使H被查询到多个其他值 alt 。我们还隐式地使用可提取性来论证攻击者不能查询r到H；否则，我们可能会使用此攻击者来解决RSA问题。最后，证明依赖于可编程性，以模拟对手的解密oracle查询。