密码学基础(七) - 公钥加密

公钥加密

在前面介绍密钥分发协议时提到过“中间人(Man-in-mid)攻击”的一种攻击方式，应对这种攻击方式的一种方式就是采用公钥加密：加密和解密使用不同的密钥，从而提高密钥分发的安全性。

公钥加密方案最主要的缺陷在于比一般的私钥加密方案慢 2 到 3 个数量级。

公钥加密的定义：

• Gen：以安全参数1ⁿ作为输入，然后输出一对密钥(pk, sk)，通常用pk表示公开密钥，sk表示私有密钥。并且假设pk 和 sk都至少有n比特长，n是公开的。
• Enc：以公开密钥 p_k 以及明文 m 作为输入，然后输出密文 c ，其中c := Enc_pk(m)
• Dec：以私有密钥 s_k 以及密文 c 作为输入，然后输出明文 m ，或者输出一条错误信息（允许以一个可忽略的概率出现解密错误）

由于加密体系的不同，所以公钥加密体系和私钥加密体系中用于检验消息完整性的手段也不同：公钥加密体系使用数字签名技术来进行消息完整性验证，并且能够实现身份验证；而私钥加密体系使用消息认证码来进行消息完整性验证，但是并不能实现身份认证。

公钥加密方案的被动攻击安全实验PubK^eav_A,Π(n)：

1. 运行Gen(1ⁿ)获得密钥(p_k, s_k)
2. 敌手A获取了公开密钥p_k，然后输出一对等长的明文m₁, m₂
3. 随机的选择一个比特b，然后生成一个密文c := Enc_pk(m_b)，并将其返回给敌手A
4. 敌手A输出一个比特b‘，如果b\' = b 则这个实验输出1；否则输出0.

与前面的私钥加密方案一样：如果存在一个可忽略函数对PPT上的所有敌手都有Pr[PubK^eav_A,Π(n)=1] ≤ 1/2 + negl(n)，则称这种方案具有窃听者存在下的不可区分性。或者说是在被动攻击下是安全的。

定理：如果一个公钥加密方案是被动攻击下是安全的，那么这中公钥加密方案也是CPA安全的。

因为加密所使用的公开密钥是公开的，所以被动攻击实验中相当于敌手可以访问加密预言机。

与私钥加密体系所不同的是，不管密钥长度有多长、明文空间有多小，公钥加密体系不可能实现完美保密。

定理：任何一个确定性算法的公钥加密方案都不是CPA安全的

考虑一个情形：一个教授使用确定性算法的公钥加密方案来加密学生的成绩，每个学生的成绩都在{A, B, C}中，那么窃听者通过加密所有可能的成绩，然后将得到的密文与结果进行比对，就可以快速得知每个学生的成绩到底是多少。

多明文加密

和前面的一样，允许敌手访问一个“Left-right”预言机：这个预言机以一对等长的明文m1, m0作为输入，然后计算c := Enc_pk(m_b)，并将其作为挑战密文发送给敌手

多明文下的CPA安全实验PubK^LR-cpa_A,Π(n)：

1. 运行Gen(1ⁿ)获得密钥(p_k, s_k)
2. 随机的选择一个比特b
3. 敌后获取了公开密钥p_k，并且允许访问预言机LR_pk,b(·, ·)
4. 然后敌手输出一个比特b\'
5. 如果b\' = b，则输出1；否则输出0

如果存在一个可忽略函数negl，对所有PPT上的敌手都有Pr[PubK^LR-cpa_A,Π(n)=1] ≤ 1/2 + negl(n)，则称这种加密方案在多名问下具有CPA安全性。

定理：如果一个公钥加密方案是CPA安全的，那么加密多明文也是具有CPA安全的

这个定理同时意味着如果一个公钥加密方案是CPA安全的，那么这个方案加密任意长度的明文也是CPA安全的。

选择密文攻击

公钥加密方案的CCA安全实验PubK^cca_A,Π(n)：

1. 运行Gen(1ⁿ)获得密钥(p_k, s_k)
2. 敌手获得公钥，并且能够访问解密预言机Dec_sk(·)，然后输出一堆长度相等的明文m₀, m₁
3. 随机的选择一个比特b，然后计算密文c := Enc_pk(m_b)，并且 c 返回给敌手
4. A在获得了挑战密文后仍然能够访问解密预言机，但是不能查询挑战密文。最终敌手输出一个比特b’
5. 如果b\' = b，则输出1；否则输出0

如果存在一个可忽略函数negl，对所有PPT上的敌手都有Pr[PubK^cca_A,Π(n)=1] ≤ 1/2 + negl(n)，则称这种加密方案具有CCA安全性。

同样的，如果一个公钥加密方案是CCA安全的，那么加密多明文也是具有CCA安全的

混合加密

私钥加密方案相对与公钥加密方案来说效率更高，但是安全性比较低

公钥加密方案有更好的安全性，但是加密的效率比较低

而混合加密同时弥补了这两种加密体系的缺陷：使用公钥加密方案加密明文，然后使用私钥加密方案加密私钥加密的密钥。

图示如下：

发送方选择一个随机的密钥 k，然后使用公钥加密方案加密 k 从而分享 k。 接收者使用其 私有密钥 sk 解密出 k ，然后使用私钥加密方案解密(密钥为 k )来恢复原始消息。 

尽管使用了私钥加密方案作为组件，但这是一个成熟的公钥加密方案(发送方和接收方事先不共享任何秘密密钥)。也就是说可以将混合加密看作是公钥加密。

密钥封装方案的形式化定义KEM(Gen, Encaps, Decaps)：

• Gen：密钥生成算法，以安全参数1ⁿ作为输入，然后输出一个公开密钥和私有密钥(p_k, s_k)，假设p_k 和 s_k 的长度至少为n，并且能够从 p_k 和 s_k 中推断出 n 的大小。
• Encaps：密钥封装算法，以安全参数1ⁿ以及公开密钥 p_k 作为输入，然后输出一个密文 c 以及一个密钥k ∈ {0, 1}^l(n)，其中 l 是密钥长度。通常记为(c, k)←Encaps_pk(1ⁿ)
• Decaps：密钥解封装算法，以私有密钥sk以及密文c作为输入，然后输出一个密钥或者一条错误信息。通常记为 k := Decaps_sk(c)

有了密钥封装方案后，可以给出混合加密方案的形式化定义Π^hy=(Gen^hy, Enc^hy, Dec^hy)：设Π=(Gen, Encaps, Decaps)是一个密钥长度为 n 的密钥分装方案，Π‘=(Gen\', Enc\', Dec\')为一个私钥加密方案：

• Gen^hy：以安全参数1ⁿ作为输入，然后运行Gen(1ⁿ)，将得到的公开密钥和私有密钥(p_k, s_k)作为输出
• Enc^hy：以一个公开密钥 p_k 和一条消息 m∈{0, 1}* 作为输入：

1. 计算(c, k) ← Encaps_pk(1ⁿ)
2. 计算c\' ← Enc\'_k(m)
3. 输出密文(c, c\')

• Dec^hy：以一个私有密钥 s_k以及密文(c, c\')作为输入：

1. 计算k := Decaps_sk(c)
2. 计算m := Dec\'_k(c\')

密钥封装方案的CPA安全实验KEM^cpa_A,Π(n)：

1. 运行Gen(1ⁿ)获得密钥(p_k, s_k)，然后运行Encaps_pk(1ⁿ)生成(c, k)，其中k∈{0, 1}ⁿ
2. 随机的选择一个比特b，如果b=0，则令k^{^} = k；如果b=1，则随机的选择一个k^{^}∈{0, 1}ⁿ
3. 将(pk, c, k^{^})发送给敌手A，然后敌手输出一个比特b\'。如果b’=b，则这个实验输出1；否则输出0。

敌手可以访问Encaps_pk(1ⁿ)，因为公钥是公开的。

如果存在一个可忽略函数negl，对所有PPT上的敌手都有Pr[KEM^cpa_A,Π(n)=1] ≤ 1/2 + negl(n)，则称这个密钥封装方案是CPA安全的。

定理：如果Π是一个CPA安全的密钥封装方案，Π’是在被动攻击下具有安全性的私钥加密方案，则Π^hy是一个CPA安全的加密方案。

证明.

假设任意一个PPT上的敌手Ahy，正在进行PubK^eav_A^hy,Π^hy(n)实验，

想要证明Πhy是CPA安全的，那么就需要证明存在一个可忽略函数negl，使得Pr[PubK^eav_A^hy,Π^hy(n)] ≤ 1/2 + negl(n)

通过安全实验的定义可以得出：Pr[PubK^eav_A^hy,Π^hy(n)] = 1/2 (Pr[A^hy(p_k, Encaps⁽¹⁾_pk(1ⁿ), Enc\'_k(m₀))=0] + Pr[A^hy(p_k, Encaps⁽¹⁾_pk(1ⁿ), Enc\'_k(m₁))=1] )，其中Encaps⁽¹⁾p_k(1ⁿ)表示由Encaps生成的密文，而 k 则是由Encaps生成的密钥

假设有一个敌手A₁，正在进行KEM^cpa_A1,Π(n)实验：A₁接收到(pk, c, k^)，运行A^hy(p_k)来获取两条明文m₀, m₁，然后计算c\' := Enc\'_k^(m₀)，然后将<c, c\'>返回给敌手A^hy，然后将A^hy输出的一个比特b\'作为自己的输出

那么就有：

Pr[A₁ outputs 0 | b=0] = Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₀))=0]；Pr[A₁ outputs 1 | b=1] = Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₀))=1]，其中 k 是由Encaps生成的密钥，而 k\' 则是一个长度为 n 的随机二进制串

而Π是CPA安全的密钥封装方案，则：

等式1：Pr[KEM^cpa_A1,Π(n)=1]

= 1/2(Pr[A₁ outputs 0 | b=0] + Pr[A₁ outputs 1 | b=1])

= 1/2(Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₀))=0] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₀))=1]) ≤ 1/2 + negl(n)

假设有一个敌手A‘，正在进行PrivK^eav_A\',Π’(n)实验：A‘运行Gen(1ⁿ)获得密钥(p_k, s_k)，然后计算c := Encaps⁽¹⁾_pk(1ⁿ)，再运行A^hy(p_k)来获取两条明文m₀, m₁，然后将这两条明文作为自己的输出，最后返回一个挑战密文c\'，将<c, c\'>发送给A^hy，将A^hy的输出的一个比特b\'作为自己的输出，则：

Pr[A’ outputs 0 | b=0] = Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k‘(m₀))=0]；Pr[A’ outputs 1 | b=1] = Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₁))=1]，这里的两个密钥都为k‘，因为k’对于Ahy来说是随机的。

而Π\'是在被动攻击下安全的私钥加密方案，则：

等式2：Pr[PrivK^eav_A,Π\'(n)=1]

= 1/2(Pr[A\' outputs 0 | b=0] + Pr[A\' outputs 1 | b=1])

= 1/2(Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k‘(m₀))=0] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₁))=1]) ≤ 1/2 + negl(n)

假设有一个敌手A₂，和A₁一样，不过在加密的时候加密的是m1，则可以直接由等式1得到：

等式3：Pr[KEM^cpa_A2,Π(n)=1]

= 1/2(Pr[A₂ outputs 0 | b=0] + Pr[A₂ outputs 1 | b=1])

= 1/2(Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₁))=1] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₁))=0]) ≤ 1/2 + negl(n)

将上面三个等式相加可以得到：

1/2(Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k‘(m₀))=0] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₁))=1]

+ Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₀))=0] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₀))=1]

+ Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₁))=1] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₁))=0]) ≤ 3/2 + negl(n)

而 Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₁))=0] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₁))=1] = 1同时，Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k’(m₀))=1] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k‘(m₀))=0] = 1

即：1/2(Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₀))=0] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₁))=1] +1 ) ≤ 3/2 + negl(n)

1/2(Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₀))=0] + Pr[A^hy(p_k, Encaps_pk⁽¹⁾(1ⁿ), Enc\'_k(m₁))=1] ) ≤ 1/2 + negl(n)

Pr[PubK^eav_A^hy,Π^hy(n)] ≤ 1/2 + negl(n)

密钥封装方案的CCA安全实验KEM^cca_A,Π(n)：

1. 运行Gen(1ⁿ)获得密钥(p_k, s_k)，然后运行Encaps_pk(1ⁿ)生成(c, k)，其中k∈{0, 1}ⁿ
2. 随机的选择一个比特b，如果b=0，则令k^{^} = k；如果b=1，则随机的选择一个k^{^}∈{0, 1}ⁿ
3. 将(pk, c, k^{^})发送给敌手A，同时敌手A能够访问解封装预言机Decapssk(·)，但是不能用这个预言机直接查询c。
4. 敌手输出一个比特b\'。如果b’=b，则这个实验输出1；否则输出0。

如果存在一个可忽略函数negl，对所有PPT上的敌手都有Pr[KEM^cca_A,Π(n)=1] ≤ 1/2 + negl(n)，则称这个密钥封装方案是CCA安全的。

定理：如果Π是一个CCA安全的密钥封装方案，Π‘是一个CCA安全的私钥加密方案，则Π^hy也是CCA安全的加密方案。

基于DDH/CDH困难问题假设的加密方案

CDH困难问题假设：给定(G, q, g, g^x, g^y)，很难计算出g^xy，形式化表示为：Pr[A(G, q, g,g^x, g^y) = g^xy]≤negl(n)

DDH困难问题假设：给定(G, q, g, g^x, g^y, g^xy)以及(G, q, g, g^x, g^y, g^z)，很难区分这两个六元组，形式化表示为：|Pr[D(G, q, g, g^x, g^y, g^xy)=1] - Pr[D(G, q, g, g^x, g^y, g^z)=1]| ≤ negl(n)

这个体系的加密方案是由Thar El Gamal在1985年通过观察Diffie Hellman密钥交换协议演变而来的，他发现Diffie Hellman密钥交换协议可以是用于公钥加密。

引理：设G是一个有限群，设m是G中任意一个元素。那么以一个均匀的概率在G中选择一个 k 并且令k\' := k · m，那么 k\' 的分布也是均匀的。换句话说，对于任意的g G，有Pr[k·m=g] = 1/|G|。

而这个概率取决于在G中均匀概率选择的 k。

回顾Diffie Hellman密钥交换协议：

而El Gamal公钥加密方案的构造就是在Diffie Hellman密钥交换协议上做了一点改动：

基于CDH/DDH困难问题假设的公钥加密方案：设ς为以1ⁿ为输入的多项式时间算法，输出一个循环群G的描述，它的阶(|q|=n)以及一个生成元g。则可以定义一个公钥加密方案如下：

• Gen：输入安全参数1ⁿ，然后运行ς(1ⁿ)获得(G, q, g)，然后概率均匀的选择一个x ∈ Z_q，然后计算h := g^x。输出公钥<G, q, g, h>，输出私钥<G, q, g, x>。明文空间是G。
• Enc：输入一个公钥pk = <G, q, g, h>以及一个明文m ∈ G，然后概率均匀的选择一个y ∈ Z_q，然后输出密文<g^y, h^y·m>
• Dec：输入一个私钥sk = <G, q, g, x>以及一个密文<c₁, c₂>，然后输出明文m := c₂/c₁^x

正确性验证：Dec(Enc(m)) = c₂ / c₁^x = (h^y·m) / c₁^x = (g^xy·m) / g^yx = m

实例：设q=83，p = 2q+1 = 167，令G为模p二次剩余的群。由于G的阶是素数，所以除了 1 以外的所有元素能够作为生成元，不妨令g = 2² = 4 mod 167

发送方选择一个密钥37 ∈ Z₈₃

pk = <p, q, g, h> = <167, 83, 4, [437 mod 167]> = <167, 83, 4, 76>

sk = <p, q, g, x> = <167, 83, 4, 37>

现在假设加密一条消息m = 65，则其加解密过程如下：

定理：如果DDH问题相对于 ς 是困难的，那么El Gamal公钥加密方案是CPA安全的

证明.

构造一个公钥加密方案Π\'，与Π的区别在于概率均匀的选择y, z ∈ Z_q，然后输出密文<g^y, g^z·m>

由前面的引理可知，g^z·m仍然服从均匀分布的，则

Pr[PubK^eav_A,Π\'(n)=1] = 1/2

假设有一个PPT上的算法试图解决DDH问题，D获得输入<G, q, g, h₁, h₂, h₃>，

1. 令pk = <G, q, g, h₁>，然后运行A(pk)，获得两条消息m₀, m₁ ∈G
2. 概率均匀的选择一个比特b，然后令c₁ := h₂，c₂ := h₃·m_b
3. 返回密文<c₁, c₂>给敌手A，然后获得一个比特b\'。如果b\' = b则输出1；否则输出0。

如果h₃ = g^z，则Pr[D(G, q, g, g^x, g^y, g^z)=1] = Pr[PubK^eav_A,Π‘(n)=1] = 1/2

如果h₃ = g^xy，则Pr[D(G, q, g, g^x, g^y, g^xy)=1] = Pr[PubK^eav_A,Π(n)=1]

而negl(n) ≥ |Pr[D(G, q, g, g^x, g^y, g^z)=1] - Pr[D(G, q, g, g^x, g^y, g^xy)=1]| = |1/2 - Pr[PubK^eav_A,Π(n)=1]|

Pr[PubK^eav_A,Π(n)=1] = 1/2 + negl(n)

所以Π是CPA安全的公钥加密方案

El Gamal实例中的问题：

1. 共享公共参数：在实践中，这些参数(如G、q、G)被生成并“一次性固定”，然后由多个接收者共享，这是常见且安全的。而这与RSA的情况相反。
2. 群的选择：群的阶q通常被选为素数。
3. 消息空间：El - Gamal加密方案的一个不便之处是，消息空间是群G，而不是指定长度的位字符串。

基于DDH困难问题假设的密钥封装方案：

• Gen：输入安全参数1n，然后运行ς(1ⁿ)并获得(G, q, g)，概率均匀的选择一个x ∈ Z_q，令h := h^x。同时确定一个函数H：G→{0, 1}^l(n)，公钥为<G, q, g, h, H>而私钥为<G, q, g ,x>
• Encpas：输入公钥pk = <G, q, g, h, H>，然后概率均匀的选择一个y ∈ Z_q，最后输出密文g^y以及密钥H(h^y)
• Decaps：输入私钥sk = <G, q, g, x>以及密文c ∈ G，输出密钥H(c^x)

函数H的选择有两种：
常规的函数：选择一个常规的函数H: G→{0, 1}^l(n)意味着对于每个可能的密钥k {0, 1}^l(n)，映射到k的群G中的元素的个数相近似相等的，形式化的表示为2^l·|Pr[H(g)=k]-2^-l| ≤ negl(n)

带密钥的函数：第二种选择就是令H是一个带密钥的函数，其中的密钥是包含在接收者公钥中的，并且如果H是一个不依赖于任何随机预言机的哈希函数。

定理：如果DDH问题相对于ς是困难的，那么上面所构造的密钥封装方案是CPA安全的。

定理：如果DDH问题相对于ς是困难的，并且将H改为一个随机预言机，那么上面所构造的密钥封装方案是CPA安全的。

gap-CDH困难问题假设：即使给敌手一个能够解决DDH问题预言机，CDH问题仍然是难以解决的

定理：如果gap-CDH相对于ς是困难的，并且将H改位一个随机预言机，那么上面所构造的密钥封装方案是CCA安全的。

DHIES/ECIES：设ΠE = (Enc\', Dec\')是一个私钥加密方案，ΠM = (Mac, Vrfy)是一个消息认证码。则可以构造出一个公钥加密方案如下：

• Gen：输入安全参数1ⁿ，然后运行ς(1ⁿ)获得(G, q, g)，概率均匀的选择一个x ∈ Z_q。令h := g^x，同时确定一个函数H：G→{0, 1}²ⁿ，那么公钥就是<G, q, g, h, H>，私钥为<G, q, g, x, H>
• Enc：输入公钥pk = <G, q, g, h, H>以及一条明文m，概率均匀的选择一个y ∈ Z_q 并令k_E||k_M := H(h^y)，然后计算c\' ← Enc\'_kE(m)，最后输出密文<g^y, c\', Mac_kM(c\')>
• Dec：输入私钥sk = <G, q, g, x, H>以及一条密文<c, c\', t>，如果c不在群G内则输出一个错误信息；然后计算k_E || k_M := H(c^x)，如果Vrfy_kM(c\', t) ≠ 1，也输出一条错误信息；否则，输出m = Dec\'_kE(c\')

推论：如果ΠE是一个CPA安全的私钥加密方案，并且ΠM是一个强的MAC。如果gap-CDH问题相对于ς是困难的，并且H是随机预言机，那么上面所构造的加密方案是CCA安全的。

RSA加密方案

尽管基于RSA的公钥加密方案目前被广泛传播，但是目前也在逐步减少使用RSA，并转向依赖椭圆曲线组的基于CDH/DDH困难问题假设的加密方案，因为基于RSA的方案需要更长的密钥长度。

RSA假设：给定一个模数N，以及一个整数 e>0，以及一个元素y ∈ Z*_N，然后计算y^1/e mod N；给定N，e，y，找到一个满足x^e = y mod N的x

RSA实验RSA-inv_{A, GenRSA}(n)：

1. 运行GenRSA(1ⁿ)获得(N, e, d)
2. 选择一个y←Z*_N
3. 敌手A获得输入N, e, y，然后输出一个x ∈ Z*_N
4. 如果y = x^e mod N，则这个实验的输出就是1；否则输出0

定义：如果对PPT上的敌手A都存在一个可忽略函数negl，满足Pr[RSA-inv_{A, GenRSA}(n)=1] ≤ negl(n)，则称RSA问题相对于GenRSA是困难的。

RSA密钥生成算法GenRSA：

输入：安全参数1ⁿ

输出：N, e, d(其中模数N是两个n比特长的素数的乘积，并且整数e, d满足ed = 1 mod φ(N) )，具体算法过程如下：

1. (N, p, q)←GenModulus(1ⁿ)
2. φ(N) := (p-1)(q-1)
3. 选择 e > 1 满足 e与φ(N)互素
4. 计算d := [e-1 mod φ(N)]
5. 返回N, e, d

普通RSA加密方案：设存在一个上文提到的GenRSA算法，则可以构造一个公钥加密方案如下：

• Gen：输入安全参数1ⁿ，运行GenRSA(1ⁿ)获得N, e, d，公钥为<N, e>而私钥为<N, d>
• Enc：输入一个公钥pk = <N, e>以及一条明文m ∈ Z*_N，计算密文c := [m^e mod N]
• Dec：输入一个私钥sk = <N, d>以及一条密文c  ∈ Z*_N，计算明文m := [c^d mod N]

正确性验证：c^d = (m^e)^d = m^ed = m^xφ(N)+1 = m mod N

不过这种普通的RSA加密方案并不安全，从发明到现在二十多年，已经发现各种不同的针对RSA加密的攻击方法，如：使用小的e加密短消息m、加密部分已知明文、加密相关明文、发送同一条明文给多个接收者等。

CPA安全的RSA加密方案

CPA安全的KEM

用lsb(x)表示x的最低位的比特

RSA问题的硬核谓词实验RSA-lsb_A,GenRSA(1ⁿ)：

1. 运行GenRSA(1ⁿ)获得(N, e, d)
2. 概率均匀的选择一个x ∈ Z*_N然后计算y := [x^e mod N]
3. 敌手A获得N, e, y，然后输出一个比特b
4. 如果lsb(x) = b则这个实验输出1；否则输出0.

定义：如果对所有PPT上的敌手A都存在一个可忽略函数negl，使得Pr[RSA-lsbA,GenRSA(n)=1] ≤ 1/2 + negl(n)，则称这个RSA问题相对于GenRSA是困难的

RSA硬核谓词加密单比特加密方案：设GenRSA还是前面所提到的，则可以构造一个公钥加密方案如下：

• Gen：输入安全参数1ⁿ，运行GenRSA(1ⁿ)获得(N, e, d)，然后输出公钥pk=<N, e>，输出私钥sk = <N, d>
• Enc：输入一个公钥pk = <N, e>以及一条明文m ∈ {0, 1}，概率均匀的选择一个r ∈ Z*_N，并且使 r 满足lsb(r) = m，输出密文c = [r^e mod N]
• Dec：输入一个私钥sk = <N, d>以及一条密文c，计算r := [c^d mod N]，输出明文m = lsb(r)

定理：如果RSA问题相对于GenRSA是困难的，那么上面所构造的加密方案是CPA安全的

证明.

设A是一个PPT上的敌手，不失一般性，可以令PubKeavA,Π(n)实验中的m0 = 0， m1 = 1；

则Pr[PubK^eav_A,Π(n)=1] = 1/2 (Pr[A(N, e, c)=0 | b=0] + Pr[A(N, e, c)=1 | b=1])

考虑实验RSA-lsb_A,GenRSA(1ⁿ)，由定义可知：Pr[RSA-lsb_A,GenRSA(n)=1] = Pr[A(N,e,[r^e mod N])=lsb(r)]，其中 r 在Z*N中均匀分布

而Pr[lsb(r)=1] = Pr[lsb(r)=0] = 1/2，所以有：Pr[RSA-lsb_A,GenRSA(n)=1] = 1/2(Pr[A(N, e, [r^e mod N])=0 | lsb(r)=0] + Pr[A(N, e, [r^e mod N]=1) | lsb(r)=1])

因为lsb(r)=m，所以有：Pr[PubK^eav_A,Π(n)=1] = Pr[RSA-lsb_A,GenRSA(n)=1] ≤ 1/2 + negl(n)

所以此方案是CPA安全的

使用上面所构造的加密方案构造一个密钥长度为 n 的密钥封装方案：

• 最简单的方法：使用上面加密一比特的加密方案逐比特的加密密钥 k 的 n 的比特
• 最佳的方法：发送方使用RSA置换

基于RSA置换的密钥封装方案：设存在一个GenRSA，则可以构造一个密钥封装方案KEM如下：

• Gen：输入安全参数1ⁿ，运行GenRSA(1ⁿ)获得(N, e, d)，然后计算d\' := [dⁿ mod Φ(N)]，输出公钥pk = <N, e>，输出私钥sk =<N, d\'>
• Encaps：输入公钥pk = <N, e>以及安全参数1ⁿ，概率均匀的选择一个c₁ ∈ Z*_N，对i = 1, ..., n，依次执行下列操作：

1. 计算k_i := lsb(c_i)
2. 计算c_i+1 := [c_i^e mod N]
3. 最终输出密文c := c_n+1，以及密钥k = k₁||k₂...||k_n

• Decaps：输入私钥sk = <N, d\'>以及一个密文c，计算c₁ := [c^d\' mod N]，然后对i = 1, ..., n，依次执行下列操作：

1. 计算k_i = lsb(c_i)
2. 计算c_i+1 := [c_i^e mod N]
3. 最终输出密钥k = k₁||k₂...||k_n

其原理示意图如下：

定理：如果RSA问题相对于GenRSA是困难的，那么上面所构造的加密方案是CPA安全的

基于RSA置换的密钥封装方案的效率：具体地说，假设n = 128, RSA模N为2048位长，公开指数e为3，这样幂e模N的求幂可以用两个模乘法计算。所以，加密需要2n = 256个模块乘法。解密可以通过一个完整的模幂运算(大约花费1.5·2048 = 3072个模乘法)加上一个额外的256个模乘法来完成。因此，解密的成本仅比普通RSA加密方案低8%左右。相比之下，加密要比普通RSA花费更高的成本，但在很多应用中解密时间更重要。

RSA-OAEP

前面所介绍的基于RSA问题的加密方案安全性都是比较弱的，比如普通的RSA加密方案是具有密文可延展性的

而RSA-OAEP是具有更高安全性的一种基于RSA困难问题假设的加密方案，其主要思想是将明文m转换成一个Z_N*中的一个元素m^，然后令密文c := m^^e mod N

设l(n), k₀(n), k₁(n)是三个返回值为整数的函数，其中k₀(n), k₁(n) = Θ(n)，并且k₀(n)+k₁(n)比由GenRSA(1ⁿ)生成的模N的最小比特长度

先确定一个n，然后令l = l(n), k₀ = k₀(n)以及k₁ = k₁(n)

明文m ∈ {0,1}^l，如果将m转换成一个正整数，则由于l, k₀, k₁的约束条件，m<N

加密过程还需要两个建立于相互独立的随机预言机上的哈希函数，G: {0, 1}^k0 → {0, 1}^l+k1，H：{0, 1}^l+k1 → {0, 1}^k0

RSA-OAEP加密方案：设存在一个GenRSA，l(n), k₀(n), k₁(n)是三个返回值为整数的函数，其中k₀(n), k₁(n) = Θ(n)，并且k₀(n)+k₁(n)比由GenRSA(1ⁿ)生成的模N的最小比特长度，G和H是两个建立于相互独立的随机预言机上的哈希函数，G: {0, 1}^k0 → {0, 1}^l+k1，H：{0, 1}^l+k1 → {0, 1}^k0，则可以构造一个公钥加密方案如下：

• Gen：输入安全参数1ⁿ，运行GenRSA(1ⁿ)获取(N, e, d)，则公钥为(N, e)，私钥为(N, d)
• Enc：输入公钥(N, e)以及一条明文m ∈ {0, 1}^l，令m\' = m||0^k1，然后概率均匀的选择一个r ∈ {0, 1}^k0，然后计算s := m\' ⊕ G(r)，t := r ⊕ H(s)，令m^ := s||t，输出密文c := m^^e mod N
• Dec：输入私钥(N, d)以及一条密文c ∈ Z_N*，计算m^ = c^d mod N，如果|m^| > l + k0 + k1，则输出一个错误，否则将m^裁剪为 s||t，其中s∈{0, 1}^l+k1，t∈{0, 1}^k0，然后计算r := H(s) ⊕ t 以及m\' := G(r) ⊕ s，如果m\'最低的k1位不全是0，则输出一个错误，否则输出m 为m\'的最高的 l 位。

RSA-OAEP在实际的应用中被指定为PKCS #1 v2.0

RSA-OAEP的CPA安全性：

在加密过程中，发送方会计算m\' := m||0^k1，s := m’⊕G(r)，t := r⊕H(s)，其中r是随机的，密文c := (s||t)^e mod N

如果敌手从来没有查询过G(r)，那么G(r)对于敌手来说就是随机的，因此，如果敌手没有查询过G(r)，那么就不会泄露任何关于明文的信息。

然而在密文中 r 被H所掩盖，如果敌手不查询H的话，那他就不知道任何关于 r 的信息。

所以敌手如果想要从密文中获取任何关于明文的信息，他首先需要查询H(s)，也就需要从密文中获取s的值，而密文(s||t)e mod N，所以在概率多项式的时间内，敌手没法从(s||t)e mod N中计算出s

故而RSA-OAEP是CPA安全的

RSA-OAEP的CCA安全性：

敌手对解密预言机每一次查询都必然是这两种情况：要么解密一个由某个明文m加密得到的c；要么直接解密一个随机构造的密文c，而返回一个错误

之所以会有这样的结果是因为接收方在解密的时候会检查m\'的最低的k1位是否全为0；如果敌手不是通过加密某些明文来构造密文c的，那么能够解密出某个明文的概率是可以可忽略的

故而RSA-OAEP是CCA安全的