随着密码技术的发展, 可证明安全概念已被广泛认可.在随机谕言机(random oracle, 简称RO)模型^[1]或者标准模型下具有自适应性选择密文攻击不可区分安全(indistinguishable security under adaptive chosen ciphertext attack, 简称IND-CCA2)^[2]普遍被认为是实用公钥加密方案应具备的性质之一.为了使一些高效的、确定性的加密方案具有IND-CCA2安全, 人们提出了很多将确定性加密方案改造成概率性加密方案的技术, 其中最著名的技术是Bellare等人于1994年^[3]提出的明文最优非对称填充(optimal asymmetric encryption padding, 简称OAEP)技术.

OAEP技术是一种基于Feistel网络算法的填充技术, 通常使用多个哈希函数来对加密前的消息进行随机化处理.最优非对称技术与任何安全陷门加密函数联合使用, 可构造一个不可区分安全^[4]的组合加密方案.

Bellare等人于1994年首次提出基于最优非对称填充技术与RSA^[5]加密方案的最优非对称加密填充方案(RSA-OAEP)^[3], 并声称基于理想的“Hash函数”, 该方案可以取得IND-CCA2安全(RO模型下).自RSA-OAEP提出以后, 出现了很多在安全和效率上的改进方案.按照安全证明所采用的模型, 这些方案可以分为两类.

· RO模型下的RSA-OAEP型方案

2001年, Shoup提出了Shoup攻击^[6], 进而证明了OAEP方案的安全性证明中存在漏洞, 并且提出能够广泛应用于各种确定性加密方案的OAEP增强版最优非对称填充加密方案(OAEP+)^[6].同年, Boneh提出了两个执行效率高的一轮OAEP (SAEP和SAEP+)^[7].2004年, Phan等人^[8]指出, 在应用方面, OAEP+, SAEP和SAEP+都具有一定的局限性, 并构造了一个安全性可以证明的明文填充加密方案, 称为三轮OAEP.该方案在当时是最优化的OAEP改进方案.2006年Cui等人^[9]在Phan等人工作的基础上, 把加密函数所需的随机串规定为$Hash(m||r)$, 使得改进后的三轮OAEP的安全性有所提高.2008年, 胡予濮等人指出, 当解密谕言机可以输出填充算法中的随机串, 即攻击者可以得到填充算法中的随机串时, 三轮OAEP是不安全的, 并构造了一个改进的三轮OAEP (OAEP3+)明文填充方案^[10].该方案从两个方面成功地修复了三轮OAEP加密方案的漏洞.2014年, 刘英莎等人指出, OAEP3+虽然在安全上有所提高, 但是带来了新的问题, 即在缩减密文尺寸方面不理想.同时, 他们构造了一个增强的OAEP3+明文填充方案(EAEP3++)^[11].该方案在保证安全性(RO模型下具有IND-CCA2安全)不变的基础上, 提高了方案的执行效率.

·标准模型下的RSA-OAEP型方案

2009年, Kiltz等人首次提出在标准模型下证明具有选择明文攻击语义不可区分安全(indistinguishable security under chosen plaintext attack, 简称IND-CPA)的实例化RSA-OAEP方案^[12].

2010年, Kiltz等人^[13]证明了在标准模型和假定的RSA难题强度下, 任何一个RSA-OAEP方案都不可能具有IND-CCA2安全性.

以上方案尽管很实用, 但是还存在以下3个方面的不足:

(1)绝大多数方案的安全性证明都是在RO模型下进行的, 因为RO模型下的安全论断是基于“理想”的Hash函数取得的, 所以不能作为加密方案实际安全的绝对证据.

(2)加密前对明文进行随机化处理时均采用最优非对称填充法, 该方法致使实际加密消息的长度比实际明文长度增加k比特位(k表示用于填充的随机数的长度), 只适用于短消息加密.由于实际加密的是填充后的消息, 所以实际加密信息的长度总是大于实际明文的长度, 无法做到两者相等.

(3)在标准模型下, 安全性证明只能取得IND-CPA级别.

本文基于配对函数编码构造了一个明文编码随机化加密方案.该方案在加密消息前, 先对消息进行配对函数编码, 并随机化配对函数编码序列, 然后再对被随机化处理后的配对数编码序列进行加密, 从而达到如下效果. (1)加密前对明文执行配对函数编码随机化操作, 实现了明文混淆, 这与OAEP技术在隐藏明文统计特性方面是等价的, 同时拓展了实际传送消息的长度.(2)通过对配对函数编码序列进行随机化, 然后加密这个随机化处理结果的途径, 获得了不可区分安全.(3)最后给出了本文方案安全性的规范证明:首先提出一个RSA难题的变体, 然后基于此难解性问题证明了本文方案在标准模型下具有IND-CCA2安全.

1 预备知识 1.1 OAEP

OAEP是一种将消息随机化的填充技术, 主要由两个Hash函数$({H_1},{H_2})$构成Feistel网络.该网络的输入为明文m, 随机数r以及为验证消息而填充的“0”冗余串, 如图 1所示.设$\ell $是RSA方案中模n的长度, 先选定两个参数k₀与k₁(k₀是填充“0”冗余串的长度, k₁是填充随机数r的长度), 然后根据k₀与k₁确定长度为$\ell - {k_0} - {k_1}$的消息m, H₁是输出为$\ell - {k_1}$长的Hash函数, H₂是输出为k₀长的Hash函数.

OAEP具体填充操作如下:

(1)在长度为$\ell - {k_0} - {k_1}$的消息m后填充k₀个“0”:$m||\overbrace {0...0}^{{k_0}}.$

(2)计算:

$X = (m||\overbrace {0...0}^{{k_0}}) \oplus {H_1}(r).$

(3)计算:

$Y = r \oplus {H_2}((m||\overbrace {0...0}^{{k_0}}) \oplus {H_1}(r)).$

(4)输出:$X||Y$, 其中X位于图 1的左半部分, Y位于图 1的右半部分.

1.2 配对函数^[14]

配对函数是原始递归函数, 定义如下:

$z = \langle x,y\rangle = {2^x}(2y + 1) - 1$

其中, x, y与z都是大于等于0的整数, 并且$\langle x,y\rangle $中x和y是有序的.该运算是良定的^[14], 即整数z与$\langle x,y\rangle $是一一对应的.

1.3 RSA算法

RSA^[5]加密系统由密钥生成、加密和解密这3种随机算法组成.

(1)密钥生成.选择两个大素数p和q, 计算$n = pq,\phi (n) = (p - 1)(q - 1).$任选$e \ge 3$且满足$gcd(\phi (n),e) = 1$作为公钥, 用$ed \equiv 1(\bmod {\rm{ }}\phi (n))$计算一个d作为私钥.

(2)加密.消息发送方计算:

$c = {m^e}(\bmod {\rm{ }}n),m \in Z_n^*.$

(3)解密.消息接收方计算:

$m = {c^d}(\bmod {\rm{ }}n).$

1.4 可证明安全相关定义 1.4.1 不可区分性安全游戏^[15-17]

设${\cal E}$为任意一个公钥加密方案, ${\cal A}$为任意一个概率多项式时间的敌手, 安全证明用到的两个不可区分性安全游戏IND-CPA和IND-CCA2^{[15, 16]}分别被定义如下:

1) IND-CPA游戏$Game_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(k)$

(1)初始化.挑战者生成加密系统${\cal E}{\rm{,}}$并将系统公钥${K_{{\rm{Pub}}}}$发送给敌手${\cal A}{\rm{.}}$

(2)获取密文.${\cal A}$可以获取足够多的自己选择的消息对应的密文.

(3)挑战.${\cal A}$输出两个相同长度的明文m₀和m₁挑战者随机选择$b \in \{ 0,1\} ,$然后输出一个挑战密文${c^ * } = En{c_{_{{K_{{\rm{Pub}}}}}}}({m_b}),$并将c^*发送给${\cal A}{\rm{.}}$

(4)猜测.${\cal A}$输出一个对b的猜测${b^\prime } \in \{ 0,1\} ,$若$b = {b^\prime },$则输出1(${\cal A}$赢得游戏); 否则输出0.

令$Adv_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(k)$为${\cal A}$赢得游戏$Game_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(k)$的优势, 如果存在一个可忽略的函数$\delta {\rm{,}}$满足:

$Adv_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(k) = \left| {\Pr [Game_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(k) = 1] - \frac{1}{2}} \right| \le \delta (k),$

则方案${\cal E}$在选择明文攻击下具有不可区分安全.

2) IND-CCA2游戏$Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(k)$

(1)初始化.挑战者生成加密系统${\cal E}{\rm{,}}$并将系统公钥${K_{{\rm{Pub}}}}$发送给敌手${\cal A}{\rm{.}}$

(2)问询.${\cal A}$向挑战者发起对密文c的解密问询(可多次(设为i次), 且第i次问询可以依赖于前i-1次的问询), 挑战者用$De{c_{{K_{{\rm{Pri}}}}}}(c)$响应${\cal A}$的问询(问询可发生在挑战前和挑战后).

(3)挑战.${\cal A}$输出两个相同长度的明文m₀和m₁挑战者随机选择$b \in \{ 0,1\} ,$然后输出一个挑战密文${c^ * } = En{c_{_{{K_{{\rm{Pub}}}}}}}({m_b}),$并将c^*发送给${\cal A}{\rm{.}}$

(4)猜测.${\cal A}$输出一个对b的猜测${b^\prime } \in \{ 0,1\} ,$若$b = {b^\prime },$则输出1(${\cal A}$赢得游戏); 否则输出0.

令$Adv_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(k)$为${\cal A}$赢得游戏$Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(k)$的优势, 如果存在一个可忽略的函数$\delta ,$满足:

$Adv_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(k) = \left| {\Pr [Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(k) = 1] - \frac{1}{2}} \right| \le \delta (k),$

则方案${\cal E}$在自适应选择密文攻击下具有不可区分安全.

1.4.2 视图(view)

视图:一个协议参与方在协议特定步骤中的公共输入、自己的秘密输入和随机带及其收到的所有消息.

1.4.3 抗碰撞的哈希函数族^[17]

令H_F为若干个Hash函数组成的哈希函数族, 任取一个$H{\rm{(}} \cdot {\rm{)}} \in {H_F},$如果对于任意的多项式时间内的敌手都无法找到一个不同于x的y满足$H(x) = H(y),$则称哈希函数族H_F是抗碰撞的哈希函数族.

2 基于配对函数的明文编码随机化加密方案 2.1 方案介绍

本文基于配对函数和RSA设计了一个明文编码随机化加密方案.该方案由密钥生成、配对函数编码、加密、解密和消息恢复这5种随机算法组成.我们将其记为

${\cal E}(Gen,Encode,Enc,Dec,Rec).$

Gen.输入安全参数“1ⁿ”, 和RSA一样生成密钥对$(e,N)$和$(d,N),$发布公钥$(e,N),$保留私钥$(d,N).$

Encode.消息发送方用配对函数将明文M进行编码:$M = {2^x}(2y + 1) - 1 = \langle x,y\rangle ,$得到明文M的配对函数编码序列$\langle x,y\rangle .$

Enc.消息发送方按照如下的方式进行加密, 则密文为$C = ({C_1},{C_2},{\alpha _v}).$

(1)随机选择一个长度为$\ell (\ell \in {Z_n})$的$r \in {Z_n},$并与$\min (x,y)$执行操作:

${R_{{\rm{Op}}}} = r \oplus \min (x,y),{\rm{ }}{R_{{\rm{Xor}}}} = {R_{{\rm{Op}}}}\left\| r \right\|h,{\rm{ }}{R_{{\rm{Xor}}}} < N,$

其中, “‖”是串联符; $h \in \{ 0,1\} ,$是标识符; $h = \left\{ {\begin{array}{*{20}{l}} {1,}&{\min (x,y) = x}\\ {0,}&{\min (x,y) = y} \end{array}} \right..$

(2)计算:

${C_1} = R_{{\rm{Xor}}}^e\left( {\bmod {\rm{ }}N} \right).$

(3)计算:

${C_2} = x + y.$

(4)计算:

${\alpha _v} = H(r,{C_1},{C_2}),$

其中, $H( \cdot )$为抗碰撞的Hash函数.

Dec.消息接收方接收到密文后, 按如下步骤进行解密, 从而得到明文M的配对数编码序列:$\langle x,y\rangle .$

(1)先对C₁做d次幂运算, 然后将该幂运算结果模N

${C_1}^d\left( {\bmod {\rm{ }}N} \right) = {R_{{\rm{Xor}}}}.$

(2)对${R_{{\rm{Xor}}}}$做解除联接操作:从低位算起, 第1位为h第2位~第$\ell + 1$位是随机数r其余位是$\min (x,y) \oplus r$ (即${R_{{\rm{Op}}}}$).

(3)验证:${\alpha _v}\mathop = \limits^? H(r,{C_1},{C_2}),$如果相等, 则继续执行步骤(4);否则返回停止符号“$ \bot $”.

(4)计算:

${R_{{\rm{Op}}}} \oplus r = \min (x,y).$

(5)计算:

${C_2} - \min (x,y) = \left\{ {\begin{array}{*{20}{l}} {y,}&{x < y}\\ {x,}&{y \le x} \end{array}} \right..$

Rec.用得到的$\langle x,y\rangle $和配对函数解码方法恢复明文:

$M = \langle x,y\rangle = {2^x}(2y + 1) - 1.$

2.2 解密正确性验证

对于解密运算中的步骤(1):

${C_1}^d\left( {\bmod {\rm{ }}N} \right) = {(R_{{\rm{Xor}}}^e)^d}{\rm{ }}\left( {\bmod {\rm{ }}N} \right) = R_{{\rm{Xor}}}^{ed \equiv 1{\rm{ }}\left( {\bmod \varphi (N)} \right)}{\rm{ }}\left( {\bmod {\rm{ }}N} \right) = {R_{{\rm{Xor}}}}.$

对于解密运算中的步骤(2):

做解除联接操作, 得到${R_{{\rm{Op}}}}$(即$\min (x,y) \oplus r$), r与h

对于解密运算中的步骤(3):

计算$H(r,{C_1},{C_2}),$并验证:${\alpha _v}\mathop = \limits^? H(r,{C_1},{C_2}),$如果相等, 则继续执行步骤(4);否则返回停止符号“$ \bot $”.

对于解密运算中的步骤(4):

如果步骤(3)中${\alpha _v} = H(r,{C_1},{C_2}),$则计算:

${R_{{\rm{Op}}}} \oplus r = (\min (x,y) \oplus r) \oplus r = \min (x,y).$

对于解密运算中的步骤(5):

根据${C_2} - \min (x,y)$以及步骤(2)中得到的h, 计算x与y的值, 从而得到一个配对数序列:$\langle x,y\rangle .$因为配对函数具有良定性, 所以明文M可以唯一地对应于一个配对数序列$\langle x,y\rangle ;$反之, 一个配对数序列$\langle x,y\rangle $唯一对应于1个明文.因此, 用所得到的配对数序列$\langle x,y\rangle $可以正确地恢复明文:

$M = \langle x,y\rangle = {2^x}(2y + 1) - 1.$

3 RSA问题的变形问题

本节给出RSA问题的变形问题, 称为RSA选择异或判定性问题.

3.1 问题描述

设${R_{{\rm{Xor}}}}$为加密算法(Enc)中步骤(1)定义的参数.简单来讲, RSA选择异或判定性问题就是区分给定的两个数$\Re $和$\Re '$(已知两个中的一个是$R_{{\rm{Xor}}}^e$的模N剩余, 另一个是从Z_N上随机选择的)中哪一个是$R_{{\rm{Xor}}}^e(\bmod {\rm{ }}N)$, 哪一个是从Z_N上随机选择的.其严格定义如下:设D为区分算法, ${D_{{\rm{Ran}}}}$与${D_{{\rm{Xor}}}}$为两个分布:

$\begin{align} &{{D}_{\text{Ran}}}=\{(n,\omega )=(N,\Re )|n\leftarrow N,\omega \xleftarrow{R}\Re \in {{Z}_{N}}\}, \\ &{{D}_{\text{Xor}}}=\{(n,\omega )=(N,R_{\text{Xor}}^{e}(\bmod \text{ }N))|n\leftarrow N,\omega \leftarrow R_{\text{Xor}}^{e}(\bmod \text{ }N)\}. \\ \end{align}$

随机选择一个分布$(n,\omega ) \in \{ {D_{{\rm{Ran}}}},{D_{{\rm{Xor}}}}\} $发送给D, D对其进行区分:如果D断定$(n,\omega )$来自分布${D_{{\rm{Ran}}}},$则输出$D(n,\omega ) = {D_{{\rm{Ran}}}};$如果D断定$(n,\omega )$来自分布${D_{{\rm{Xor}}}},$则输出$D(n,\omega ) = {D_{{\rm{Xor}}}}.$设$Adv(D)$为区分算法D能够区分出分布${D_{{\rm{Ran}}}}$与${D_{{\rm{Xor}}}}$的优势, 定义为

$Adv(D) = \left| {\Pr [D(n,\omega ) = {D_{{\rm{Ran}}}}] - \Pr [D(n,\omega ) = {D_{{\rm{Xor}}}}]} \right|.$

如果对于任意的概率多项式时间区分算法D, 都有:

$Adv(D) \le \delta (n),$

其中$\delta (n)$是一个可忽略的函数, 则称RSA选择异或判定性问题是困难的.

3.2 问题描述难解性

关于RSA选择异或判定性问题的困难性, 有下面的定理.

定理1. RSA选择异或判定性问题是困难的, 即${D_{{\rm{Ran}}}}$与${D_{{\rm{Xor}}}}$是多项式时间不可区分的.

为了证明定理1, 我们需要下面的定理.

定理2^[18].如果总体$X = {\{ {X_n}\} _{n \in N}}$与$Y = {\{ Y\} _{n \in N}}$是多项式时间不可区分的, 对于任意的多项式时间算法A, 总体上A(X)与A(Y)也是多项式时间不可区分的.

定理1的证明:独立随机地选择$r,\Re \in {Z_N},$则$r,\Re $是计算不可区分的, 因为它们是来自同一分布Z_N的两次独立采样.如果用r做运算${R_{{\rm{Op}}}} = \min (x,y) \oplus {r_n}$与${R_{{\rm{Xor}}}} = {R_{{\rm{Op}}}}\left\| {{r_n}} \right\|h$后, 再用RSA加密算法对${R_{{\rm{Xor}}}}$加密:$\Re ' = {({R_{{\rm{Xor}}}})^e}{\rm{ }}\bmod N$, 那么得到的密文$\Re '$与r是计算不可区分的.因为用r计算$\Re '$的全部计算可以在多项式时间内完成, 如果用这个过程可以区分$\Re '$与r, 那么实现这个过程的算法就可以作为区分器来区分$r,\Re ,$而这与$r,\Re $是计算不可区分的事实相矛盾.

显然, 上述过程可视作$\Re $与$\Re '$在同一分布Z_N上的两次独立采样, 经$n \in N$次这样的采样过程, 按照如下构造方式得到分布${D_{{\rm{Ran}}}}$与${D_{{\rm{Xor}}}}$:

$\begin{align} &{{D}_{\text{Ran}}}=\{(n,\omega )=(N,\Re )|n\leftarrow N,\omega \xleftarrow{R}\Re \in {{Z}_{N}}\}, \\ &{{D}_{\text{Xor}}}=\{(n,\omega )=(N,R_{\text{Xor}}^{e}(\bmod \text{ }N))|n\leftarrow N,\omega \leftarrow R_{\text{Xor}}^{e}(\bmod \text{ }N)\}, \\ \end{align}$

那么${D_{{\rm{Ran}}}}$与${D_{{\rm{Xor}}}}$自然也是多项式时间计算不可区分的.

从而有:

$Adv(D) = \left| {\Pr [D(n,\omega ) = {D_{{\rm{Ran}}}}] - \Pr [D(n,\omega ) = {D_{{\rm{Xor}}}}]} \right| \le \delta (n).$

因此, RSA选择异或判定性问题是困难的.

4 安全性证明

本文的证明思路是先证明方案具有IND-CPA安全后再证明其具有IND-CCA2安全.这样做的原因有两个:

(1)具有IND-CPA安全是本文方案具有IND-CCA2安全的一个必要条件, 或者归约基础.

(2)本文方案的安全基于一个新的RSA变形问题, 称为RSA选择加随机因子判定性问题.

4.1 IND-CPA安全性

定理3.如果RSA选择异或判定性问题是困难的, 则方案${\cal E}$具有IND-CPA安全, 即语义安全.

证明:规定选择异或判定性问题的挑战者按如下方式工作:

(1)运行RSA密钥生成算法产生密钥对$(N,e).$

(2)用配对函数将明文M进行编码:$M = {2^x}(2y + 1) - 1 = \langle x,y\rangle ,$得到明文M的配对函数编码序列$\langle x,y\rangle .$

(3)随机选择一个$r \in {Z_n}$与$\min (x,y)$做异或运算得到${R_{{\rm{Op}}}},$并做链接运算得到${R_{{\rm{Xor}}}}.$

(4)随机选择$d \in \{ 0,1\} .$

(5)如果d=0, 则令$T = {R_{{\rm{Xor}}}};$如果d=1则置$T = \Re .$

(6)将$(e,N,(N,\omega ),T)$发送给攻击者.

设${\cal E}(Gen,Encode,Enc,Dec,Rec)$是我们设计的加密方案, ${\cal A}$是一个攻击${\cal E}$的多项式时间算法, ${\cal A}$在IND-CPA游戏中的获胜优势为$\delta {\rm{.}}$按照如下方式设计一个解决RSA选择异或判定性问题的算法${\cal B}{\rm{.}}$

算法${\cal B}{\rm{.}}$

1.从RSA选择异或判定性问题挑战者那里接收到$(e,N,(n,\omega ),T).$

2.令${K_{{\rm{Pub}}}} = (e,N).$

3.将系统安全参数1ⁿ和公钥pk发给${\cal A}{\rm{.}}$

4.接收来自${\cal A}$的消息M₀与M₁

5.随机选择$b \in \{ 0,1\} {\rm{.}}$

6.用配对函数将明文M_b进行编码:${M_b} = {2^{{x_b}}}(2{y_b} + 1) - 1 = \langle {x_b},{y_b}\rangle ,$得到明文M_b的配对函数编码序列$\langle {x_b},{y_b}\rangle {\rm{.}}$

7.随机选择一个$r \in {Z_n},$与$\min ({x_b},{y_b})$做异或运算得到${R_{b{\rm{Op}}}},$并做链接运算得到${R_{b{\rm{Xor}}}}{\rm{.}}$

8.设${C_1} = (e,N,T \cdot R_{b{\rm{Xor}}}^{e - 1}(\bmod {\rm{ }}N)),$并将C₁发送给${\cal A}{\rm{.}}$

9.令$b' \in \{ 0,1\} $为算法${\cal A}$对b的猜测结果;

10.输出d'(如果$b = b',$则置$d' = 0;$如果$b \ne b',$则置$d' = 1$).

多项式时间算法${\cal B}$赢得RSA选择异或判定性安全游戏的概率为

$\begin{array}{c} {\rm{Pr}}\left[ {d = d'} \right] = {\rm{Pr}}[d = 0]{\rm{Pr}}[d = d'|d = 0] + {\rm{Pr}}[d = 1]{\rm{Pr}}[d = d'|d = 1]\\ = \frac{1}{2}\Pr [d' = 0|d = 0] + \frac{1}{2}\Pr [d' = 1|d = 1]\\ = \frac{1}{2}\Pr [b = b'|d = 0] + \frac{1}{2}\Pr [b \ne b'|d = 1] \end{array}$

(1)

当d=0时, RSA选择异或判定性问题挑战者置$T = {R_{{\rm{Xor}}}}.$此时, 算法${\cal B}$提交给算法${\cal A}$的视图与实际中${\cal A}$攻击${\cal E}$的IND-CPA游戏中的视图相同.因此, 当d=0时, $b = b'$的概率等于多项式时间算法${\cal A}$赢得攻击${\cal E}$的IND-CPA游戏的概率, 即

$\Pr [b = b'|d = 0] = \frac{1}{2} + \delta $

(2)

当d=1时, RSA选择异或判定性问题挑战者置$T = \Re .$由$\Re $在Z_n上是均匀分布的, 可得出$\Re \cdot R_{{\rm{Xor}}}^{e - 1}\left( {\bmod {\rm{ }}N} \right)$在Z_n上也是均匀分布的, 又因为$\Re $与M₀, M₁和b是相互独立的.进而可得出:随机变量e, $R_{{\rm{Xor}}}^e\left( {\bmod {\rm{ }}N} \right),$$\Re \cdot R_{b{\rm{Xor}}}^{e - 1}\left( {\bmod {\rm{ }}N} \right)$和b也是相互独立的.因此, 公钥${K_{{\rm{Pub}}}}$和密文C₂并没有泄露任何关于b的信息, 所以由算法${\cal A}$输出的猜测结果b'与b必定相互独立.又因为b=0和b=1的概率各为$\frac{1}{2},$因此有:

$\Pr [b \ne b'|d = 1] = \frac{1}{2}$

(3)

由式(1)~式(3)得:

$\begin{array}{c} \Pr \left[ {d = d'} \right] = \frac{1}{2}\left( {\frac{1}{2} + \delta } \right) + \frac{1}{2} \times \frac{1}{2}\\ = \frac{1}{2} + \frac{1}{2}\delta , \end{array}$

因此, 算法${\cal B}$赢得RSA选择异或判定性安全游戏的优势为

$\left| {\Pr \left[ {d = d'} \right] - \frac{1}{2}} \right| = \left( {\frac{1}{2} + \frac{1}{2}\delta } \right) - \frac{1}{2} = \frac{\delta }{2}.$

由RSA选择异或判定性问题假设可知, 算法${\cal B}$只能以可忽略的优势赢得RSA选择异或判定性安全游戏, 所以$\frac{\delta }{2}$是个可忽略值.这蕴含着$\delta $也是可忽略的.因此, 算法${\cal A}$只能以可忽略的优势$\delta $赢得攻击${\cal E}$的IND-CPA游戏.

4.2 IND-CCA2安全性

定理4.如果${\cal E}$是IND-CPA安全的加密方案, 并且${\cal E}$选用的Hash函数$H( \cdot )$是抗碰撞的, 则${\cal E}$是一个IND-CCA2安全的加密方案.

证明:证明思路:因为$H( \cdot )$是抗碰撞的, 所以${\alpha _v} = H(r,{C_1},{C_2})$可视为$(r,{C_1},{C_2})$的唯一验证码.从而挑战者对于敌手提交的所有解密询问的回答方式为:如果是先前从挑战者那里获得的密文, 则返回此密文对应的消息M; 否则, 挑战者的正确响应是返回终止符“$ \bot $”.此时解密问询对敌手没有任何帮助, 因此, 方案${\cal E}$的安全就归约到其IND-CPA安全.然后证明如果方案${\cal E}$不具有IND-CCA2安全, 那么它一定也不具有IND-CPA安全.这是因为挑战者从敌手收到的解密问询如果不是先前从挑战者手里得到的密文, 那么它将返回终止符“$ \bot $”, 所以挑战者无需为了响应敌手提交的解密问询而进行解密运算.

设算法${\cal A}$是一个对方案${\cal E}$进行IND-CCA2的概率多项式时间敌手; 设$ValidQuery$为敌手在IND-CCA2游戏中问询挑战者事件, 即敌手${\cal A}$提交给挑战者的解密问询$({C_1},{C_2},{\alpha _v})$不是先前从挑战者手里(或通过加密系统正常加密)得到的密文, 而是按照如下方式生成的:

方式(1)$\left\{ \begin{array}{l} ① 截取某一密文C = ({C_1},{C_2},{\alpha _v})的部分密文{C_1},{C_2}\\ ② 随机选择一个r' \in {Z_n}计算{\rm{:}}{{\alpha '}_v} = H(r',{C_1},{C_2})\\ ③ 返回密文{\rm{:}}C' = ({C_1},{C_2},\alpha ') \end{array} \right.,$

方式(2)$\left\{ \begin{array}{l} ① 随机选择两个{{C'}_1},{{C'}_2} \in {Z_n}\\ ② 随机选择一个r' \in {Z_n}计算{\rm{:}}{{\alpha '}_v} = H(r',{{C'}_1},{{C'}_2})\\ ③ 返回密文{\rm{:}}C' = ({{C'}_1},{{C'}_2},\alpha ') \end{array} \right.,$

所以有:

$\Pr [Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n) = 1] \le {\rm{Pr}}\left[ {ValidQuery} \right] + {\rm{Pr}}[Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n) = 1 \wedge \overline {ValidQuery} ]$

成立.

如果下面两个断言成立, 那么定理4成立.下面将给出两个断言及证明.

断言1. $\Pr \left[ {ValidQuery} \right]$是可忽略的.

证明:直观上, 如果事件$ValidQuery$发生, 敌手就成功地伪造了给定消息$(r,{C_1},{C_2})$的唯一验证码, 即$H(r',{C_1},{C_2}) = H(r,{C_1},{C_2}).$因为Hash函数$H( \cdot )$是抗碰撞的, 所以敌手想要成功地伪造给定消息$(r,{C_1},{C_2})$的验证码, 除非发生以下情形:敌手在构造密文时, 自己选择的随机数$r' \in {Z_n}$恰好等于挑战者输出挑战密文时挑战者选择的随机数$r \in {Z_n}.$而这种情形发生的概率只有$1/q(n),$其中, q(n)为敌手问询挑战者次数的多项式时间上界.因n很大, 所以$1/q(n),$是一个可忽略的值.

于是得出结论:$\Pr [ValidQuery]$是可忽略的.也就是说, 存在一个可忽略的函数$\delta '(n),$满足:

$\Pr [ValidQuery] \le \delta '(n).$

断言2.存在一个可忽略的函数$\delta (n),$满足:

$\Pr \left[ {Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n) = 1 \wedge \overline {ValidQuery} } \right] \le \frac{1}{2} + \delta (n).$

设${\cal A}$是IND-CCA2游戏中任意一个概率多项式时间敌手.假定${{\cal A}_{\cal E}}$是对方案${\cal E}$实施CPA攻击的敌手.现用${{\cal A}_{\cal E}}$模拟${\cal A}$的挑战者, 并规定${\cal A}$除了向挑战者提交解密问询以外, 还可以向挑战者提交加密问询.

敌手${{\cal A}_{\cal E}}$按照如下方式工作:

1)敌手${{\cal A}_{\cal E}}$输入系统安全参数1ⁿ随机选择公钥对$(e,N) \leftarrow {\{ 0,1\} ^n}{\rm{.}}$

2)用公钥对$(e,N)$及RSA系统模拟${\cal A}$的挑战者.唤醒(调用) CCA2敌手${\cal A}$.当敌手${\cal A}$用M作为加密问询时, 按如下方式回答问询:

(a)用配对函数对M进行编码得到序列$\langle x,y\rangle {\rm{.}}$

(b)随机选择一个$r \in {Z_n},$计算:

${R_{{\rm{Op}}}} = \min (x,y) \oplus r{\rm{.}}$

(c)做联接运算:

${R_{{\rm{Op}}}}\left\| r \right\|h{\rm{.}}$

(d)计算:

${C_1} = R_{{\rm{Xor}}}^e\left( {\bmod {\rm{ }}N} \right){\rm{.}}$

(e)计算:

${C_2} = x + y{\rm{.}}$

(f)计算:${\alpha _v} = H(r,{C_1},{C_2}),$并将$({C_1},{C_2},{\alpha _v})$发给敌手${\cal A}{\rm{.}}$

3)当敌手${\cal A}$提交解密问询$({C_1},{C_2},{\alpha _v})$时, 按照如下方式进行应答:

如果$({C_1},{C_2},{\alpha _v})$是先前对M加密问询的应答, 则返回对应的M否则, 输出“$ \bot $”(解密问询可以发生在挑战前和挑战后).

4)当敌手${\cal A}$输出两个等长的密文M₀和M₁时, 按照步骤2)计算一个密文$({C_{1b}},{C_2}_b,{\alpha _v}),$并将$({C_{1b}},{C_2}_b,{\alpha _v})$发给敌手${\cal A}{\rm{.}}$

5)敌手${\cal A}$输出一个比特$b' \in \{ 0,1\} .$

注意到, 敌手${{\cal A}_{\cal E}}$在模拟敌手${\cal A}$的挑战者时根本就不需要额外的解密能力来应对${\cal A}$的解密问询, 这是因为它和敌手${\cal A}$的挑战者一样, 把除了先前从挑战者那里得到的关于M的加密问询和已经提交的解密问询以外的任何新的解密问询$({C_1},{C_2},{\alpha _v})$都视为无效问询.因为当$ValidQuery$事件未发生时, 敌手${\cal A}$的挑战者对任何解密问询的正确应答应为“$ \bot $”, 所以${\cal A}$作为${{\cal A}_{\cal E}}$子进程, 它所见的内容的概率分布与在IND-CCA2游戏中所见内容的概率分布是相同的, 即

$\Pr \left[ {Game_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(n) = 1 \wedge \overline {ValidQuery} } \right] = \Pr \left[ {Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n) = 1 \wedge \overline {ValidQuery} } \right],$

这就蕴含着:

$\begin{array}{c} \Pr \left[ {Game_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(n) = 1} \right] \ge \Pr \left[ {Game_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(n) = 1 \wedge \overline {ValidQuery} } \right]\\ = \Pr \left[ {Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n) = 1 \wedge \overline {ValidQuery} } \right]. \end{array}$

因为前面已经证明方案${\cal E}$具有IND-CPA安全, 所以存在一个可忽略的函数$\delta (n),$满足:

$\Pr [Game_{{\cal A},{\cal E}}^{{\rm{ind - cpa}}}(n) = 1] \le \frac{1}{2} + \delta (n).$

因此得到:

$\Pr \left[ {Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n) = 1 \wedge \overline {ValidQuery} } \right] \le \frac{1}{2} + \delta (n).$

由综上所述可得:

$\begin{array}{c} Adv_{{\cal A},{\cal E}}^{{\rm{cca}}2}(n) = \left| {\Pr [Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n)] = 1] - \frac{1}{2}{\rm{ }}} \right|\\ \le \left| {\Pr \left[ {ValidQuery} \right] + \Pr [Game_{{\cal A},{\cal E}}^{{\rm{ind - cca}}2}(n) = 1 \wedge \overline {ValidQuery} ] - \frac{1}{2}} \right|\\ = \left| {\delta '(n) + \left( {\frac{1}{2} + \delta (n)} \right) - \frac{1}{2}} \right|\\ = \delta '(n) + \delta (n). \end{array}$

因为前面已经证明$\delta '(n)$与$\delta (n)$都是可忽略的, 所以$Adv_{{\cal A},{\cal E}}^{{\rm{cca}}2}(n)$也是可忽略的.因此, 敌手${\cal A}$只能以可忽略的优势赢得攻击${\cal E}$的IND-CCA2游戏.

5 性能分析

本节给出方案效能分析, 具体如下.

1.效率方面.一方面, 由于本文方案对明文混淆不再需要Hash函数运算, 只需配对数编码运算, 而编码运算可以在预处理阶段进行, 另一方面, 本文方案不需要填充$k = {k_0} + {k_1}$比特的冗余, 因此提高了加密方案的执行效率.

2.协商签名模与加密模的大小.在电子商务中, 使用RSA型加密系统的用户为了节约开销, 在很多情况下需要使用与签名相结合的加密方案(通信双方传递的是一个既签名又加密的消息), 这样的方案称为签密, 由Zheng^[19]提出.但因各个用户使用的模不同, 具体应用中需要事先协商签名模与加密模的大小关系.采用OAEP, OAEP3+和EAEP3+这3种类型的签密方案依然需要额外协商签名模与加密模的大小顺序, 而本文签密方案却不需要, 原因如下:假设使用本文方案的用户Alice的公钥为$({N_A},{e_A}),$私钥为${d_A};$用户Bob的公钥为$({N_B},{e_B}),$私钥为${d_B},$其他参数同第2节.在使用OAEP, OAEP3+和EAEP3+方案时, 若Bob想发送一个既签名又加密的消息m给Alice, 则需要按照如下方式进行:

1) Bob先利用明文填充技术对消息m进行填充, 得到m'

2) Bob用自己的签名密钥对消息m'进行签密, 得到的签名为$s = {m'^{{d_B}}}{\rm{ }}\bmod {\rm{ }}{N_B}.$

3)然后再用Alice的公钥对s加密, 得到$c = {s^{{e_A}}}{\rm{ }}\bmod {\rm{ }}{N_A}.$

4) Alice收到密文c后, 先解密, 然后验证签名.

5)还原消息m.

注意到Bob计算密文时需要在模N_B运算结果的基础上再进行模N_A运算, 如果不事先协商签名模N_B与加密模N_A的大小关系, Alice解密后的结果不能通过签名验证的情形就会以$|{N_B} - {N_A}|/{N_B}$的概率发生^[20].

在使用本文方案时, 若Bob想发送一个既签名又加密的消息m给Alice, 则需要按照如下方式进行:

1) Bob按照第2.1节的方法对消息m执行配对数编码随机化.

2) Bob用Alice的公钥$({N_A},{e_A})$加密明文配对数编码随机化后的${R_{{\rm{Xor}}}}$:

$c = R_{{\rm{Xor}}}^{{e_A}}(\bmod {\rm{ }}{N_A}).$

3) Bob用自己的私钥和通用Hash函数H计算签名:

${s_1} = {(x + y)^{{d_B}}}{\rm{ }}\bmod {\rm{ }}{N_B},{s_2} = H(x,y,r).$

4) Alice在收到密文后, 先进行解密:

${c^{{d_A}}}\left( {\bmod {\rm{ }}{N_A}} \right) = {R_{{\rm{Xor}}}},$

得到r, 进而得到x或者y

5) Alice验证签名:

$s_1^{{e_B}}\left( {\bmod {\rm{ }}{N_B}} \right) = (x + y)$

根据步骤4)与步骤5)得到的结果计算x, y与r, 验证$H(x,y,r)\mathop = \limits^? {s_2},$如果相等, 则Alice恢复明文:m=2^x(2y+1)-1;否则, 输出“$ \bot $”.

Bob在签名计算和加密计算时不需要在模N_B运算的基础上再做模N_A运算, 自然就不需要考虑协商模N_B与N_A的大小问题.

3.性能对比.设RSA加密方案的模长度为2 048位, 用于填充的随机数的长度k₀=150位, 验证消息时填充“0”冗余串长度为k₁=136位.表 1是OAEP, OAEP3+和EAEP3+这3种类型的加密方案, 以及本文方案在时间复杂度(用哈希运算的次数和RSA运算次数来体现)、空间复杂度(用可加密的最大明文来体现)、安全级别、安全证明模型, 以及当签名与加密结合使用时是否需要额外协商签名模与加密模的大小方面的对比(见表 1).

6 结论

本文采用配对函数编码构造了一个新的RSA型加密方案.该方案与OAEP, OAEP+, OAEP3+和EAEP3+相比, 一方面, 不需要Hash运算就可以隐藏明文的统计特性, 并且相对于EAEP3+, 每2 048比特密文所对应的明文长度至少增加了150比特位, 提高了加密方案效率; 另一方面, 本方案安全性提高明显, 可以在标准模型下达到IND-CCA2安全.此外本文还提出了一个新的RSA变形问题, 称作RSA选择异或判定性问题.