Page 267 - 《软件学报》2021年第9期

康步荣 等:抗随机数后门攻击的密码算法 2891

EwH)和 RSA-DOAEP 算法(RSA-deterministic optimal asymmetric encryption padding,简称 RSA-DOAEP).下面我
们将对 EwH 算法和 RSA-DOAEP 算法分别进行讨论.简单来说,EwH 算法是先对用户的公钥、明文消息做一次
Hash 操作,将 Hash 值作为一个安全公钥加密算法的随机数,并利用该公钥加密算法生成最终密文.下面我们给
出具体的 EwH 加密算法.为方便描述,我们将 EwH 算法记为 EwH=(EwH.K,EwH.E,EwH.D),将任一安全公钥密
*
*
*
码算法记为 PKE=(PKE.K,PKE.E,PKE.D),哈希函数记为 H:{0,1} ×{0,1} →{0,1} .
k
k
• 密钥生成算法 EwH.K(1 ):输入安全参数 k,该算法运行算法 PKE.K(1 )→(pk,sk),输出公私钥对(pk,sk);
• 加密算法 EwH.E(pk,x):输入公钥 pk 和要加密的消息 x,先计算 H(pk,x)→R,再运行算法 PKE.E(pk,x,
R)→y,输出密文 y;
• 解密算法 EwH.D(y,pk,sk):输入私钥 sk、公钥 pk 和密文 y,先计算 PKE.D(sk,y)→x,H(pk,x)→R,再判断等
式 PKE.E(pk,x,R)=y 是否成立:若成立,输出 x;否则,输出⊥.
在文献[19]中,Bellare 等人也同时分析了确定性公钥加密算法的安全性,给出了 PRIV(privacy,简称 PRIV)
安全性的定义.PRIV 安全性要求一个攻击者,已知一个明文向量所对应的确定性加密算法的密文,只要这个明
文向量的每个分量有高的最小熵,则该攻击者不能在多项式时间内以不可忽略的概率猜出任何关于原明文的
部分信息(部分信息不依赖于加密时所用的公钥).证明结果表明:如果公钥加密算法 PKE=(PKE.K,PKE.E,
PKE.D)是 IND-CPA 安全的,则上述 EwH 确定性加密算法满足 PRIV 安全性.
RSA-DOAEP 算法是在 RSA-OAEP 算法对应的确定性算法,该算法先对明文消息进行填充,之后做 3 次
Feistel 计算,最后做一次 RSA 算法来生成相应的密文.RSA-DOAEP 加密算法由 3 个基本算法组成,为方便描述,
我们将其记为 RSA-DOAEP=(RSA-DOAEP.K,RSA-DOAEP.E,RSA-DOAEP.D).该算法有两个基础参数:k 0 ,k 1 >0,他
们之间满足关系 n>2k 0 和 n≥k 1 .这里,n 表示明文长度.算法的明文空间为 max(k 1 ,2k 0 +1),RSA 算法的模数为 N=k 1 .
0 k
,
HH 2 :{0,1} × * {0,1} → * {0,1} , :{0,1}R * × {0,1} → * {0,1} n− 0 k 表示哈希函数.算法描述中,我们用 s[i…j]表示字符串 s
1
的第 i 到第 j 个比特.RSA-DOAEP 算法的具体描述如下.
k
• 密钥生成算法 RSA-DOAEP.K(1 ):输入安全参数 k,算法输出 RSA 算法的公私钥对 pk=(N,e),sk=(N,d);
• 加密算法 RSA-DOAEP.E((N,e),x):输入明文消息 x 和公钥 pk=(N,e),计算 x l ←x[1…k 0 ],x r ←x[k 0 +1…n],
s 0 ←H 1 ((N,e),x r )⊕x l ,t 0 ←R((N,e),s 0 )⊕x r ,s 1 ←H 2 ((N,e),t 0 )⊕s 0 ,x 1 ←(s 1 ||t 0 )[1…n−k 1 ],x 2 ←(s 1 ||t 0 )[n−k 1 +1…n],
y ← x 1 || ( mod )x e 2 N ,输出密文 y;
• 解密算法 RSA-DOAEP.D((N,d),y):计算 x 1 ←y[1…n−k 1 ],y 1 ←y[n−k 1 +1…n], x ← x 1 || (y 1 e mod )N ,s 1 ←
x[1…k 0 ],t 0 ←x[k 0 +1…n],s 0 ←H 2 ((N,e),t 0 )⊕s 1 ,x r ←R((N,e),s 0 )⊕t 0 ,x l ←H 1 ((N,e),x r )⊕s 0 ,输出明文 x l ||x r .
证明结果表明,上述确定性加密算法 RSA-DOAEP 是 PRIV 安全性.
关于确定性加密算法的研究还有一些其他的研究结果,例如在文献[20]中,Boldyreva 等人在文献[19]的基
础上继续研究了确定性公钥加密算法的设计及安全性定义,他们发现了确定性公钥加密和有损限门函数之间
的联系.他们利用有损限门函数,给出了在标准模型下满足 PRIV-CPA 安全性(即,在 PRIV 安全性的基础上允许
攻击者进行加密预言机询问)的确定性公钥加密算法的一般性构造思想.为了更好地描述该算法,他们提出了一
个新的密码原语,隐藏全域哈希模式的确定性公钥加密算法(deterministic encryption with hidden universal-Hash
mode,简称 DEHUHM);其次,他们将该 PRIV-CPA 安全的算法构造进行了扩展,给出了 PRIV-CCA 安全的确定性
加密算法的一般性构造.另外,文献中还基于抗目标碰撞哈希函数、DDH 困难问题给出了两个具体的确定性加
密算法实例.
2.2 RtD算法
Bellare 等人在文献[18]中介绍了对冲公钥密码算法 RtD,RtD 基本思想是:对消息 m 先用一个概率性加密算
法进行加密,输出密文 C′,再用一个确定性加密算法对 C′进行加密,输出最终密文 C.同时,他们定义了一个新的
对冲公钥加密算法的安全性质,即选择分布攻击下的不可区分性(indistinguishability under chosen-distribution
attacks,简称 IND-CDA).在被加密的明文消息和相应随机数的联合分布是高熵的条件下,一个对冲公钥加密算