第3章
语义安全的公钥密码体制 
3.1 语义安全的RSA 加密方案 
3.1.1 RSA 加密算法
RSA 算法是1978年由Rivest、Shamir和Adleman提出的一种用数论构造的、也是
迄今为止理论上最为成熟完善的公钥密码体制,该体制已得到广泛的应用。它作为陷门
置换在1.3.1节中有过介绍,下面是算法的详细描述。
设GenPrime是大素数产生算法。
(1)密钥产生过程:
GenRSA(κ): 
p,q←GenPrime(κ); 
n=pq,φ(n)=(p-1)(q-1); 
选e,满足1<e<φ(n)且(φ(n),e)=1; 
计算d,满足de≡1(modφ(n)); 
pk=(n,e),sk=(n,d). 
(2)加密(其中|M|<log2n):
Epk(M ): 
CT=Me modn. 
(3)解密: 
Dsk(CT): 
M =CTd modn. 
下面证明RSA 算法中解密过程的正确性。
证明 由加密过程知CT≡Me(modn),所以
CTd ≡Med ≡Mkφ(n)+1(modn) 
下面分两种情况: 
(1)M 与n 互素。由欧拉定理: 
Mφ(n)≡1(modn),Mkφ(n)≡1(modn),Mkφ(n)+1≡M (modn)

第3章 语义安全的公钥密码体制 
即CTd ≡M (modn)。
(2)(M ,n)≠1。先看(M ,n)=1的含义,由于n=pq,所以(M ,n)=1意味着M 既
不是p 的倍数也不是q 的倍数。因此(M ,n)≠1意味着M 是p 的倍数或q 的倍数,不妨
设M =tp,其中t 为正整数。此时必有(M ,q)=1,否则M 也是q 的倍数,从而是pq 的
倍数,与M <n=pq 矛盾。
由(M ,q)=1及欧拉定理得Mφ(q)≡1(modq),所以Mkφ(q)≡1(modq),(Mkφ(q))φ(p) 
≡1(modq),Mkφ(n)≡1(modq),因此,存在整数r 使得Mkφ(n)=1+rq,两边同乘以M = 
tp 得Mkφ(n)+1=M +rtpq=M +rtn,即Mkφ(n)+1≡M (modn),所以CTd ≡M (modn)。
(证毕) 
如果消息M 是Zn* 中均匀随机的,用公开钥(n,e)对M 加密,则敌手不能恢复M 。然
而,如果敌手发起选择密文攻击,以上性质不再成立。例如敌手截获密文CT≡Me(mod 
n)后,选择随机数r←R Zn* ,计算密文CT'≡reCT(modn),将CT'给挑战者,获得CT'的
明文M'后,可由M ≡M'r-1(modn)恢复M ,这是因为
M'r-1≡(CT')dr-1≡(reMe)dr-1≡redMedr-1≡rMr-1≡M (modn) 
为使RSA 加密方案可抵抗敌手的选择明文攻击和选择密文攻击,需对其加以修改。
下面利用密钥封装机制及一次一密的单钥加密机制构造选择明文安全的RSA 加密方案, 
利用密钥封装机制及选择密文安全的单钥加密机制构造选择密文安全的RSA 加密方案。
3.1.2 密钥封装机制
密钥封装机制(KeyEncapsulationMechanism,KEM)是一个密码原语[18],其主要目
的是在通信的双方(发送方和接收方)之间安全地传递一个随机会话密钥。在实际应用
中,通信双方通常用对称加密算法加密要传输的消息,而用公钥加密算法加密对称加密算
法所用的秘密钥。密钥封装机制可以简化上述过程。会话密钥由发送方产生,并将其封
装于密文后发送给接收方;接收方对接收到的密文解封装,得到会话密钥。KEM 的模型
有以下3个算法: 
(1)密钥产生算法KeyGen(κ):输入安全参数κ,输出公开钥-秘密钥对(pk,sk)。
(2)封装算法Encap(pk):输入公开钥pk,输出一个密文C 和一个会话密钥K ,表示
为(C,K )=Encap(pk),称C 是对K 的封装。
(3)解封装算法Decap(sk,C):输入秘密钥sk和密文C,输出会话密钥K ,表示为
K =Decap(sk,C). 
【例3-1】 使用RSA 的KEM 方案。
(1)密钥产生算法KeyGen(κ)与RSA 方案相同。
(2)封装算法Encap(pk)如下:
Encap(pk): 
r←R [0,n-1]; 
C=re modn; 
K =KDF(r); 
输出C 和K . 
67

密码学中的可证明安全性(第2版) 
其中KDF称为密钥导出函数,例如可取为密码哈希函数。
(3)解封装算法Decap(sk,C)如下: 
Decap(sk,C): 
r=Cd modn; 
K =KDF(r). 
密钥封装中的适应性选择密文安全的概念,除了挑战密文不是对两个等长的消息加
密外,其他均与加密方案类似。在挑战阶段,挑战者选取β←R {0,1},并且将挑战密文C* 
和一个比特串K * 发送给敌手。其中K * 如下产生:如果β=1,K * 是用密文C* 封装的
会话密钥;如果β=0,K * 取为随机比特串。敌手进行适应性的解封装询问(除了挑战密
文C* ),输出对β 的猜测β'。
称上述交互为KEM-CCA2游戏。敌手A的优势定义为
AdvKEM A (κ)= Pr[β'=β]-12 
如果对PPT的A,AdvKEM A (κ)是可忽略的,则称KEM 方案是KEM-CCA2安全的。
3.1.3 RSA 问题和RSA 假设
RSA 问题:已知大整数n,e,y←R Zn* ,满足1<e<φ(n)且(φ(n),e)=1,计算y1/e 
modn。
RSA 假设:没有概率多项式时间的算法以不可忽略的概率解决RSA 问题。
可将e 视为加密密钥,y 视为某个消息x 的密文,即xe modn=y,而1e
为解密密钥。
求y1/e modn 就是对y 的解密,因此RSA 假设成立。
3.1.4 选择明文安全的RSA 加密方案
设GenRSA 是RSA 加密方案的密钥产生算法,它的输入为κ,输出为模数n(为两个
κ 比特素数的乘积)、整数e、d 满足ed≡1(modφ(n))。又设H :{0,1}2κ→{0,1}.(κ)是一
个哈希函数,其中.(κ)是一个任意的多项式。
加密方案Π(称为RSA-CPA 方案)如下: 
(1)密钥产生过程: 
KeyGen(κ): 
(n,e,d)←GenRSA(κ); 
pk=(n,e),sk=(n,d). 
(2)加密过程(其中M ∈{0,1}.(κ)): 
Epk(M ): 
r←R Zn* ; 
输出(re modn,H (r)..M ). 
(3)解密过程(其中C=(C1,C2)): 
68

第3章 语义安全的公钥密码体制 
Dsk(C): 
r=Cd1 
modn; 
输出H (r)..C2. 
解密过程的正确性显然。
上述过程中H (r)是封装的密钥,C1=re modn 是对H (r)的封装。解密时,先由C1 
导出封装的密钥,再对C2 解密。
在对该方案进行安全性分析时,将其中的哈希函数视为谕言机,称为哈希函数随机谕
言机,简称为随机谕言机(randomoracle)。随机谕言机是2.2节介绍的谕言机的一种,可
把它视为一个魔盒,对用户(包括敌手)来说,魔盒内部的工作原理及状态都是未知的。用
户能够与这个魔盒交互,方式是向魔盒输入一个比特串x,魔盒输出比特串y(对用户来
说y 是均匀分布的)。这一过程称为用户向随机谕言机的询问。
因为这种哈希函数的工作原理及内部状态是未知的,因此不能用通常的公开哈希函
数。在安全性的归约证明中(见图1-7),敌手A需要哈希函数值时,只能由敌手B为他产
生。之所以以这种方式使用哈希函数,是因为B要把要攻击的困难问题嵌入哈希函数值
中。这种安全性称为随机谕言机模型下的安全性。如果不把哈希函数当作随机谕言机, 
则安全性称为标准模型下的安全性,如3.2 节的Paillier公钥密码系统和3.3 节的
Cramer-Shoup密码系统。
定理3-1 设H 是一个随机谕言机,如果与GenRSA 相关的RSA 问题是困难的,则
RSA-CPA 方案Π是IND-CPA 安全的。
具体来说,假设存在一个IND-CPA 敌手A以ε(κ)的优势攻破RSA-CPA 方案Π,那
么一定存在一个敌手B至少以
AdvRSA B (κ)≥2ε(κ) 
的优势解决RSA 问题。
证明 Π的IND-CPA 游戏如下: 
ExpRSA-CPA 
Π,A (κ): 
(n,e,d)←GenRSA(κ); 
pk=(n,e),sk=(n,d); 
H ←R {H :{0,1}2κ→{0,1}.(κ)}; 
(M0,M1)←AH (·)(pk),其中|M0|=|M1|=.(κ); 
β←R {0,1},r←R Zn* ,C* =(re modn,H (r)..Mβ); 
β'←AH (·)(pk,C* ); 
如果β'=β,则返回1;否则返回0. 
其中,{H :{0,1}2κ→{0,1}.(κ)}表示{0,1}2κ到{0,1}.(κ)的哈希函数族。A右肩上的H (·) 
表示敌手对H (·)的询问。敌手的优势定义为安全参数κ 的函数: 
AdvRΠS,AA-CPA(κ)= Pr[ExpRSA-CPA 
Π,A (κ)=1]-12 
下面证明RSA-CPA 方案可归约到RSA 假设。
69

密码学中的可证明安全性(第2版) 
敌手B已知(n,e,c^1),以A(攻击RSA-CPA 方案)作为子程序,进行如下过程,目标是
计算r^≡(c^1)1e 
(modn)。
(1)选取一个随机串h^←R {0,1}.(κ)作为对H (r^)的猜测值(但是实际上B并不知道
r^)。将公开钥(n,e)给A。
(2)H 询问。B建立一个表Hlist(初始为空),元素类型为(xi,hi),A在任何时候都能
发出对Hlist的询问,B做如下应答(设询问为x): 
. 如果x 已经在Hlist中,则以(x,h)中的h 应答。
. 如果xe≡c^1(modn),以h^应答,将(x,h^)存入表Hlist中,并记下r^=x(嵌入了困
难问题)。
. 其他情况下随机选择h←R {0,1}.(κ),以h 应答,并将(x,h)存入表Hlist中。
(3)挑战。A输出两个要挑战的消息M0 和M1,B随机选择β←R {0,1},并令c^2= 
h^..Mβ,将(c^1,c^2)给A作为密文。
(4)A输出猜测β'。若β'=β 以概率12
+ε(κ) .
è .
.
. ÷ 
,B知道Hlist中以一定概率存在(r^, 
h^),输出第(2)步记下的r^=x。
设H表示事件:在模拟中A发出H (r^)询问,即H (r^)出现在Hlist中。
以上归约过程如图3-1所示。
图3-1 RSA-CPA方案到RSA假设的归约
断言3-1 在以上模拟攻击中,B的模拟是完备的。
证明 在以上模拟中,A的视图与其在真实攻击中的视图是同分布的。这是因为
(1)A的H 询问中的每一个都是用随机值应答的。而在A对Π 的真实攻击中,A得
到的是H 的函数值,由于假定H 是随机谕言机,所以A得到的H 的函数值是均匀的。
(2)h^..Mβ 对A来说为h^对Mβ 做一次一密加密。由h^ 的随机性,h^..Mβ 对A来说
是随机的。
所以两种视图不可区分。
(断言3-1证毕) 
断言3-2 在以上模拟攻击中Pr[H]≥2ε。
70

第3章 语义安全的公钥密码体制 
证明 显然有Pr[ExpRSA-CPA 
Π,A (κ)=1|..H]=12
。又由A在真实攻击中的定义知A的
优势大于或等于ε,因此A在模拟攻击中的优势也为Pr[ExpRSA-CPA 
Π,A (κ)=1]-12
≥ε。 
Pr[ExpRSA-CPA 
Π,A (κ)=1] 
=Pr[ExpRSA-CPA 
Π,A (κ)=1|..H]Pr[..H]+Pr[ExpRSA-CPA 
Π,A (κ)=1|H]Pr[H] 
≤Pr[ExpRSA-CPA 
Π,A (κ)=1|..H]Pr[..H]+Pr[H] 
=12
Pr[..H]+Pr[H] 
=12
(1-Pr[H])+Pr[H] 
=12
+12
Pr[H] 
又知
Pr[ExpRSA-CPA 
Π,A (κ)=1]≥Pr[ExpRSA-CPA 
Π,A (κ)=1|..H]Pr[..H] 
=12
(1-Pr[H])=12
-12
Pr[H] 
所以ε≤ Pr[ExpCPA Π,A (κ)=1]-12
≤12
Pr[H] 
即模拟攻击中Pr[H]≥2ε。
(断言3-2证毕) 
由以上两个断言,在上述模拟过程中r^以至少2ε 的概率出现在Hlist中。若H发生, 
则B在第(2)步可找到x 满足xe=c^1 modn,即x≡r^≡(c^1)1e 
(modn)。所以B成功的概
率与H发生的概率相同。
(定理3-1证毕) 
定理3-1的证明采用的是倒逼法,即A的攻击成功(β'=β),则倒逼出r^可能出现在
Hlist中,将其总结为定理3-2。
定理3-2(倒逼定理) 在随机谕言机模型下IND-CPA 安全(IND-CCA 安全)的加密
方案中,设敌手攻击方案的优势为ε,则敌手必以2ε 的概率对挑战密文做随机谕言机
询问。定
理3-1已证明Π是IND-CPA 安全的,然而它不是IND-CCA 安全的。敌手已知密
文CT=(C1,C2),构造CT'=(C1,C2..M'),给解密谕言机,收到的解密结果为M″= 
M ..M',再由M″..M'即获得CT对应的明文M 。
3.1.5 选择密文安全的RSA 加密方案
因为单钥加密方案效率高于公钥加密方案,且选择密文安全的单钥加密方案的构造
较容易,所以本节利用密钥封装机制和选择密文安全的单钥加密方案构造选择密文安全
的公钥加密方案。
71

密码学中的可证明安全性(第2版) 
单钥加密方案Π=(PrivGen,Enc,Dec)的选择密文安全性由以下IND-CCA 游戏
刻画: 
ExpPriv-Π,ACCA(κ): 
kpriv←PrivGen(κ); 
(M0,M1)←AEnckpriv(·),Deckpriv
(·),其中|M0|=|M1|=.(κ); 
β←R {0,1},C* =Enckpriv(Mβ); 
β'←AEnckpriv(·),Deckpriv,≠C* (·)(C* ); 
如果β'=β,则返回1;否则返回0. 
其中,Deckpriv,≠C* (·)表示敌手对Deckpriv(·)做除了C* 以外的解密询问。敌手的优势可
定义为安全参数κ 的函数: 
AdvPriv-CCA Π,A (κ)= Pr[ExpPriv-CCA Π,A (κ)=1]-12 
单钥加密方案Π的安全性定义与定义2-1、定义2-5、定义2-6类似。
设GenRSA 及H 如前,Π=(PrivGen,Enc,Dec)是一个密钥长度为κ、消息长度为
.(κ)的IND-CCA 安全的单钥加密方案。
选择密文安全的RSA 加密方案Π'=(KeyGen,E,D)(称为RSA-CCA 方案)构造
如下:
(1)密钥产生过程: 
KeyGen(κ): 
(n,e,d)←GenRSA(κ); 
pk=(n,e),sk=(n,d). 
(2)加密过程(其中M ∈{0,1}.(κ)): 
Epk(M ): 
r←R Zn* ; 
h=H (r); 
输出(re modn,Ench(M )). 
(3)解密过程(其中C=(C1,C2)): 
Dsk(C): 
r=Cd1 
modn; 
h=H (r); 
输出Dech(C2). 
定理3-3 设H 是随机谕言机,如果与GenRSA 相关的RSA 问题是困难的,且Π是
IND-CCA 安全的,则RSA-CCA 方案Π'是IND-CCA 安全的。
具体来说,假设存在一个IND-CCA 敌手A以ε(κ)的优势攻破RSA-CCA 方案Π',那
么一定存在一个敌手B至少以
AdvRSA B (κ)≥2ε(κ) 
的优势解决RSA 问题。
72

第3章 语义安全的公钥密码体制 
证明 仍然采用倒逼法。
Π'的IND-CCA 游戏如下: 
ExpRSA-Π',ACCA(κ): 
(n,e,d)←GenRSA(κ); 
pk=(n,e),sk=(n,d); 
H ←R {H :{0,1}2κ→{0,1}.(κ)}; 
(M0,M1)←ADsk(·),H (·)(pk),其中|M0|=|M1|=.(κ); 
β←R {0,1},r←R Zn* ,C* =(re modn,EncH (r)(Mβ)); 
β'←ADsk,≠C* (·),H (·)(pk,C* ); 
如果β'=β,则返回1;否则返回0. 
其中,Dsk,≠C* (·)表示敌手对Dsk(·)做除了C* 以外的解密询问。敌手的优势定义为安
全参数κ 的函数: 
AdvRSA-CCA Π',A (κ)= Pr[ExpRSA-CCA Π',A (κ)=1]-12 
下面证明RSA-CCA 方案可归约到RSA 问题。
敌手B已知(n,e,c^1),以A(攻击RSA-CCA 方案Π')作为子程序,执行以下过程(在
图3-1中,将RSA-CPA 改为RSA-CCA),目标是计算r^≡(c^1)1e 
(modn)。
(1)选取一个随机串h^←R {0,1}.(κ)作为对H (r^)的猜测(但实际上B并不知道r^)。将
公开钥pk=(n,e)给A。
(2)H 询问。B建立一个Hlist,元素类型为三元组(r,c1,h),初始值为(*,c^1,h^),其
中*表示该分量的值目前未知(嵌入了困难问题)。A在任何时候都能对Hlist发出询问。
设A的询问是r,B计算c1≡re(modn)并做如下应答: 
. 如果Hlist中有一项(r,c1,h),则以h 应答。
. 如果Hlist中有一项(*,c1,h),则以h 应答并在Hlist中以(r,c1,h)替换(*,c1, 
h)。
. 其他情况下,选取一个随机数h←R {0,1}n ,以h 应答并在Hlist中存储(r,c1,h)。
(3)解密询问。A向B发起询问(c-1,c-2)时,B如下应答: 
. 如果Hlist中有一项,其第二元素为c-1(即该项为(r-,c-1,h- 
),其中r-e≡c-1(modn), 
或者为(*,c-1,h- 
)),则以Dech- (c-2)应答。
. 否则,选取一个随机数h- 
←R {0,1}n ,以Dech- (c-2)应答,并在Hlist中存储(*,c-1, 
h- 
)。
(4)挑战。A输出消息M0,M1∈{0,1}.(k)。B随机选取β←R {0,1},计算^c2=Enc^h 
(Mβ)。以(c^1,c^2)应答A。继续应答A的H 询问和解密询问(A不能询问(c^1,c^2))。
(5)猜测。A输出猜测β'。若β'=β 以概率12
+ε(κ) .
è .
.
. ÷ 
,B知道Hlist中以一定概率存
在(r^,c^1,h^),检查Hlist,找到(r^,c^1,h^)后,输出r^。
73

密码学中的可证明安全性(第2版) 
设H表示事件:在模拟中A发出H (r^)询问,即H (r^)出现在Hlist中。
断言3-3 在以上模拟过程中,B的模拟是完备的。
证明 在以上模拟中,A的视图与其在真实攻击中的视图是同分布的。这是因为
(1)A的H 询问中的每一个都是用随机值应答的。
(2)B对A的解密询问的应答是有效的。B对(c-1,c-2)的应答为Dech- (c-2),根据Hlist的
构造,h-
对应的r- 满足r-e≡c-1(modn)及h- 
=H (r-),因而Dech- (c-2)是有效的。
所以两种视图不可区分。
(断言3-3证毕) 
由定理3-2,在上述模拟过程中r^以至少2ε 的概率出现在Hlist中,B在第(5)步逐一
检查Hlist中的元素,所以B成功的概率等于H的概率。
(定理3-3证毕) 
3.2 Paillier公钥密码系统 
3.1节介绍的方案,其安全性证明是在随机谕言机模型下进行的,即把其中的哈希函
数看成随机谕言机。但这种证明不能排除敌手可能不针对方案所基于的困难性问题而攻
击方案,或者不通过找出哈希函数的某种缺陷而攻击方案。本节和3.3节介绍的Paillier 
公钥密码系统[19]和Cramer-Shoup公钥密码系统[20]的安全性证明不使用随机谕言机模
型,这种证明模型称为标准模型。
Paillier公钥密码系统基于合数幂剩余类问题,即构造在模数取为n2 的剩余类上,其
中n=pq,p、q 为两个大素数。
设CP是一类问题集合,如果CP中的任一实例可在多项式时间内归约到另一实例或
另外多个实例,就称CP是随机自归约的。CP中问题的平均复杂度和最坏情况下的复杂
度相同(相差多项式因子)。
3.2.1 合数幂剩余类的判定
定义3-1 设n=pq,p、q 为两个大素数,对z←R Zn*2 ,如果存在y∈Zn*2 ,使得z≡yn 
(modn2),则z 称为模n2 的n 次剩余,y 称为z 的根。
引理3-1 
(1)n 次剩余构成的集合C 是Zn*2 的一个阶为φ(n)的乘法子群。
(2)每一个n 次剩余z 有n 个根,其中只有一个严格小于n。
(3)单位元1的n 次根为(1+n)t≡1+tn(modn2)(t=0,1,…,n-1)。
(4)对任一w ∈Zn*2 ,wnλ≡1(modn2),其中λ 是n 的卡米歇尔函数λ(n)的简写。
证明
(1)设z1,z2∈C,则存在y1,y2∈Z* n2 ,使得z1≡yn1
(modn2),z2≡yn2
(modn2)。因
为y2-1∈Zn*2 ,y1y2-1∈Zn*2 ,所以z1z2-1≡(y1y2-1)n (modn2)∈C,所以C 是Zn*2 的子群。
又设y(y<n)是z≡yn (modn2)的解,那么y+tn(t=0,1,…,n-1)都是z≡yn (mod 
74

第3章 语义安全的公钥密码体制 
n2)的解,这是因为
(y+tn)n =yn +nyn-1tn=yn +yn-1tn2≡yn(modn2)≡z 
所以C 中每一元素有n 个根, 
|C|=1n
Z* n2 =1n
φ(n2)=1n
n2 1-1p
.
è .
.
. ÷ 
1-1q
.
è .
.
. ÷ 
=(p-1)(q-1)=φ(n) 
(2)在(1)的证明中已得。
(3)易证(1+tn)n =1+tn2+…≡1(modn2)。
(4)因为wλ≡1(modn),wλ=1+tn,t 为某个整数。
wnλ=(1+tn)n =1+tn2+…≡1(modn2) 
(引理3-1证毕) 
合数幂剩余类的判定问题是指区分模n2 的n 次剩余与n 次非剩余,用CR[n]表示。
CR[n]是随机自归约的:设z1 ≡yn1
(modn2),z2 ≡yn2
(modn2),那么z2 ≡ 
(y2y1-1)nz1(modn2)。所以,如果z1 是n 次剩余,则z2 也是n 次剩余,即任意两个实例
都是多项式等价的。
与素数剩余类的判定类似,判定合数幂剩余类也是困难的。
假设 CR[n]是困难的。
这个假设称为判定合数幂剩余类假设(DecisionalCompositeResiduosityAssumption, 
DCRA)。由于随机自归约性,DCRA的有效性仅依赖于n 的选择。
3.2.2 合数幂剩余类的计算
设g∈Zn*2 ,ψg 是如下定义的整型值函数: 
Zn ×Zn*aZn*2 
(x,y)agx ·yn modn2 { 
引理3-2 如果g 的阶是n 的非零倍,则ψg 是双射。
证明 因为|Zn ×Zn*|=|Zn*2|=nφ(n),所以只需证明ψg 是单射。
假设gx1yn1 
≡gx2yn2
(modn2),那么gx2-x1 (y2/y1 )n ≡1(modn2),两边同时取λ 次
方,由引理3-1(4)得gλ(x2-x1)≡1(modn2),因此有ordn2g|λ(x2-x1),进而n|λ(x2- 
x1)。又知,当n=pq 时,(λ,n)=1,所以n|(x2-x1)。因为x1,x2∈Zn ,|x2-x1|<n, 
所以x1=x2。gx2-x1 (y2/y1 )n ≡1(modn2)变为(y2/y1 )n ≡1(modn2)。又由引理3-1 
(3),模n2 下单位元1的根在Zn* 上是唯一的,为1,所以在Zn* 上,y2/y1=1,即y1=y2。
综上,ψg 是双射。
(引理3-2证毕) 
设Bα.Zn*2 表示阶为nα 的元素构成的集合,B 表示Bα 的并集,其中α=1,2,…,λ。
定义3-2 设g∈B,对于w∈Zn*2 ,如果存在y∈Zn* 使得ψg (x,y)=w,则称x∈Zn 为
w 关于g 的n 次剩余,记作[[w ]]g 。
引理3-3 
(1)[[w ]]g =0当且仅当w 是模n2 的n 次剩余。
(2)对任意w1,w2∈Zn*2 ,有[[w1w2]]g ≡[[w1]]g +[[w2]]g (modn)。即,对于任
75

密码学中的可证明安全性(第2版) 
意的g∈B,函数w a[[w ]]g 是从(Zn*2 ,×)到(Zn ,+)的同态。
证明很简单,略去。
已知w ∈Zn*2 ,求[[w ]]g ,称为基为g 的n 次剩余类问题,表示为Class[n,g]。
引理3-4 Class[n,g]关于w ∈Zn*2 是随机自归约的。
证明 对于Class[n,g]的任一实例w ∈Zn*2 ,在Zn 上均匀随机选取α、β (β.Zn* 的概
率是可忽略的),构造w'≡wgαβn(modn2),就将w ∈Zn*2 转换为另一实例w'∈Zn*2 ,求出
[[w']]g 后,可计算出[[w ]]g =[[w']]g -α modn。
(引理3-4证毕) 
引理3-5 Class[n,g]关于g∈B 是随机自归约的,即,对任意g1,g2∈B,Class[n, 
g1]≡Class[n,g2],其中P1≡P2表示问题P1 和P2 在多项式时间内等价。
证明 已知w ∈Z* n2 ,g2 ∈B,存在y1 ∈Z* n ,使得w =g[[w]]g2 2 yn1
。同理,对于g1, 
g2∈B,存在y2∈Z* n ,g2=g[[g2]]g1 1 yn2
。得w =g1[[w]]g2[[g2]]g1 (y2[[w]]g2y1)n ,即
[[w ]]g1 ≡ [[w ]]g2[[g2]]g1modn (3-1) 
即由[[w ]]g2 
可求[[w ]]g1 ,所以Class[n,g1].Class[n,g2]。
再由[[g1]]g1 =1,将w =g1 代入式(3-1),得[[g1]]g2[[g2]]g1 ≡1(modn),即
[[g1]]g2 =[[g2]]-1 g1 
[[w ]]g2 ≡[[w ]]g1[[g1]]g2 ≡[[w ]]g1[[g2]]-1 g1 (modn) 
所以Class[n,g2].Class[n,g1] 
(引理3-5证毕) 
引理3-5说明Class[n,g]的复杂性与g 无关,因此可将它看成仅依赖于n 的计算
问题。定
义3-3 称Class[n]问题为计算合数幂剩余类问题,即已知w ∈Zn*2 ,g∈B,计算
[[w ]]g 。
设Sn ={u<n2|u≡1(modn)},在其上定义函数L 如下: 
对任一u∈Sn ,L(u)=u-1 n 
显然函数L 是良定的。
引理3-6 对任一w ∈Zn*2 ,L(wλ modn2)≡λ[[w ]]1+n(modn)。
证明 因为1+n∈B,所以存在唯一的(a,b)∈Zn ×Zn* ,使得w =(1+n)abn mod 
n2,即a=[[w ]]1+n 。由引理3-1(4),bnλ ≡1(modn2),所以wλ =(1+n)aλbnλ ≡1+aλn 
(modn2),L(wλ modn2)=λa≡λ[[w ]]1+n(modn)。
(引理3-6证毕) 
定理3-4 Class[n].Fact[n]。
证明 因为[[g]]1+n ≡ [[1+n]]-1 g (modn)是可逆的,所以由引理3-6 可知
L(gλ modn2)≡λ[[g]]1+n(modn)可逆。已知n 的因子分解可求λ 的值。因此,对于任
意的g∈B 和w ∈Zn*2 ,可以计算
L(wλ modn2) 
L(gλ modn2)=
λ[[w ]]1+n 
λ [[g]]1+n 
= [[w ]]1+n 
[[g]]1+n ≡ [[w ]]g (modn) (3-2) 
76

第3章 语义安全的公钥密码体制 
其中最后一步由式(3-1)获得。
(定理3-4证毕) 
用RSA[n,e]表示求模n 的e 次根,即已知w ≡ye(modn),求y。
定理3-5 Class[n].RSA[n,n]。
证明 由引理3-5可知,Class[n,g]关于g∈B 是随机自归约的,且1+n∈B,因此, 
只需证明Class[n,1+n].RSA[n,n]。
假设敌手A能解RSA[n,n]问题,对于给定的w ∈Zn*2 ,A的目标是求x∈Zn 使得w = 
(1+n)xyn modn2。由(1+n)x =1modn,得w ≡yn modn,A由此可求出y,进一步由
下式可求出x: 
w 
yn =(1+n)x ≡1+xn(modn2) 
(定理3-5证毕) 
定理3-6 设D-Class[n]是与Class[n]相关的判定问题,即已知w ∈Zn*2 ,g∈B 和
x∈Zn ,判定x 是否等于[[w ]]g ,那么下面的关系成立: 
CR[n]≡D-Class[n].Class[n] 
证明 因为验证解比计算解容易,D-Class[n].Class[n]显然。
下面证明CR[n]≡D-Class[n]。
“.”:已知w ∈Zn*2 、g∈B 和x∈Zn ,要判断x 是否等于[[w ]]g ,即判断x 是否满足
w ≡gxyn(modn2),改为判断wg-x ≡yn(modn2),即判断wg-x modn2 是否为模n2 下
的n 次剩余。所以敌手A若能解CR[n]问题,就能解D-Class[n]问题。
“.”,即证明:若敌手A能解D-Class[n]问题,则能够判定w 是否为n 次剩余。
任取g∈B,将(g,w ,x=0)给A,A能解D-Class[n]问题,即能判断是否[[w ]]g = 
x=0。如果是,w 是n 次剩余;否则,w 不是n 次剩余。
(定理3-6证毕) 
表3-1是以上各问题的小结。
表3-1 与合数幂相关的困难问题
问 题描 述
Fact[n] 分解n 
RSA[n,e] 已知w ≡ye(modn),求y 
Class[n] 已知w ≡gxyn (modn2),求x 
D-Class[n] 已知w ∈Zn*2 、g∈B 和x∈Zn ,判定x 是否等于[[w ]]g 
CR[n] 对w ∈Zn*2 ,判断是否存在y∈Zn*2 ,使得w ≡yn modn2 
它们之间的归约关系为
CR[n]≡D-Class[n].Class[n].RSA[n,n].Fact[n] 
其中,除了在CR[n]和D-Class[n]之间存在等价关系外,其他问题之间是否存在等价关
系还存在质疑。
77

密码学中的可证明安全性(第2版) 
假设 不存在求解合数幂剩余类问题的概率多项式时间算法,即Class[n]是困难
问题。这
一假设称为计算合数剩余类假设(ComputationalCompositeResiduosityAssumption, 
CCRA)。它的随机自归约性意味着CCRA的有效性仅依赖于n 的选择。显然,假如DCRA 
是正确的,那么CCRA也是正确的;但是反过来,仍然是一个公开问题。
3.2.3 基于合数幂剩余类问题的概率加密方案
以下加密方案简称为Paillier方案1。
(1)密钥产生过程:
KeyGen(κ): 
n=pq; 
g←RB 满足(L(gλ modn2),n)=1; 
pk=(n,g),sk=(p,q)(或sk=λ). 
(2)加密过程(其中M <n):
Epk(M ): 
r←R {1,2,…,n}; 
输出gMrn modn2. 
(3)解密过程(其中CT<n2): 
Dsk(CT): 
L(CTλ modn2) 
L(gλ modn2)≡M (modn). 
Paillier方案1的正确性由定理3-4证明过程中的式(3-2)给出。加密函数用λ(等价
于n 的因子)作为陷门的陷门函数,其单向性是基于Class[n]是困难的。
定理3-7 Paillier方案1是单向的当且仅当Class[n]是困难的。
证明 Paillier方案1中由密文计算明文即是Class[n]问题。
定理3-8 Paillier方案1是语义安全的当且仅当CR[n]是困难的。
证明 充分性采用反证法。假设M0、M1 是两个已知消息,C* 是其中一个(设为Mβ) 
的密文,即C* ≡gMβrn (modn2),因此C*g-Mβ ≡rn (modn2)是n 次剩余,而C*g-M1-β ≡ 
gMβ-M1-βrn(modn2)是n 次非剩余。因此敌手能够区分C* 对应哪个消息,就能区分n 次剩
余和n 次非剩余,与CR[n]是困难的矛盾。
必要性的证明类似。
(定理3-8证毕) 
3.2.4 基于合数幂剩余类问题的单向陷门置换
以下方案是Zn*2aZn*2 的单向陷门置换,简称为Paillier方案2。
(1)密钥产生过程:Paillier方案2的密钥产生过程与Paillier方案1相同。
(2)加密过程(其中M <n2): 
78

第3章 语义安全的公钥密码体制 
Epk(M ): 
M =M1+nM2; 
输出gM1Mn2 
modn2. 
其中,M =M1+nM2 是将M 分成两部分:M1 和M2(例如可用欧几里得除法)。
(3)解密过程(其中CT<n2): 
Dsk(CT): 
M1≡L(CTλ modn2) 
L(gλ modn2)(modn); 
c'≡CTg-M1(modn); 
M2≡(c')n-1modλ(modn); 
返回M =M1+nM2. 
方案的正确性:解密过程中的第1步得到M1≡M (modn),第2步恢复出Mn2
(mod 
n),第3步是公开钥为e=n 的RSA 解密,最后一步重组得到原始M 。
Paillier方案2为置换是由于ψg 是双射。置换的陷门是n 的因子。
定理3-9 Paillier方案2是单向的当且仅当RSA[n,n]是困难的。
证明 充分性的证明是将RSA[n,n]归约到Paillier方案2,即,若RSA[n,n]是可
解的,则Paillier方案2是可求逆的。若敌手A可解RSA[n,n]问题,则可解Class[n]问
题,A由CT≡gM1Mn2
(modn2)能得出M1 及CT gM1 ≡Mn2
(modn2)。因为RSA[n,n]可解, 
A由Mn2 
modn2 可得M2。
必要性的证明是将Paillier方案2归约到RSA[n,n]。即,若Paillier方案2是可求
逆的,则RSA[n,n]是可解的。设敌手A已知w ≡yn0
(modn),其目标是求y0。又设A可
求Paillier方案2的逆,即A可求出x、y 及a、b,使得w ≡gxyn (modn2)及1+n≡gabn 
(modn2)。若x0 是n 的倍数,则(1+n)x0 =1+x0n≡1(modn2)。
w =yn0
=(1+n)x0yn0
=(gabn)x0yn0
=gax0 (bx0y0)n 
≡gax0modn (gax0divnbx0y0)n(modn2) 
其中第四个等式由ax0=(ax0divn)n+ax0(modn)得到,div表示整除。
因为ψg 是双射,所以ax0 modn=x,gax0divnbx0y0=y。
x0=x(a-1 modn),y0=y(gax0divnbx0)-1 
即A已求出y0。
(定理3-9证毕) 
注意,由ψg 的定义,Paillier方案2要求M2∈Zn* 。若M2.Zn* ,即M2 与n 不互素, 
可能会导致M2≡0(modn),得密文为0;或者由M2 的因子可能会分解n。因此Paillier 
方案2不能用来加密长度小于n 的短消息。
数字签名:用h:N a{0,1}κ.Zn*2 表示哈希函数,可以得到如下的数字签名方案。
给定消息M ,签名者计算签名(s1,s2)为
79

密码学中的可证明安全性(第2版) 
s1≡L(h(M )λ modn2) 
L(gλ modn2) (modn),s2≡(h(M )g-s1)1/n modλ(modn) 
验证者检查h(M )≡? 
gs1sn2 
modn2。
推论(定理3-9的推论) 在随机谕言机模型中,如果RSA[n,n]是困难的,那么该签
名方案在适应性选择消息攻击下是存在性不可伪造的。
3.2.5 Paillier 密码系统的性质
Paillier密码系统除了具有随机自归约性外,还有如下两个性质。
1. 加法同态性
加密函数M agMrn modn2 在Zn 上具有加同态。即,对任意M1,M2∈Zn ,任意k∈ 
N ,以下等式成立: 
D (E(M1)E(M2)modn2)≡M1+M2(modn) 
D (E(M )kmodn2)≡kM (modn) 
D (E(M1)gM2modn2)≡M1+M2(modn) 
D (E (M1)M2modn2) 
D (E(M2)M1modn2)}≡M1M2(modn) 
这些性质在电子选举、门限加密方案、数字水印、秘密共享方案及安全的多方计算等
领域有重要应用。
2. 重加密
已知一个公钥加密方案(E,D ),重加密RE(re-encryption)是指已知(E,D )的一个密
文CT,在不改变CT对应的明文的前提下,将CT变为另一密文CT',表示为
CT'=RE(CT,r,pk) 
其中pk是公开钥,r 是随机数。
Paillier密码系统满足这一性质。
对任一M ∈Zn 和r∈N ,E(M )=E(M )E(0)≡E(M )rn (modn2)。因此D (E (M ) 
rn modn2)≡M (modn)。 
3.3 Cramer-Shoup密码系统 
3.3.1 Cramer-Shoup 密码系统的基本机制
设G是阶为大素数q 的群,g1、g2 为G的生成元,明文消息是群G的元素,使用单向哈
希函数将任意长度的字符映射到Zq中的元素。Cramer-Shoup密码系统(记为Π)如下: 
(1)密钥产生过程(其中H是哈希函数集合): 
80

第3章 语义安全的公钥密码体制 
KeyGen(κ): 
g1,g2←R G; 
x1,x2,y1,y2,z1,z2←R Zq; 
c=gx11gx22 ,d=gy11gy22 ,h=gz11gz22 ; 
H ←R H; 
sk=(x1,x2,y1,y2,z1,z2),pk=(g1,g2,c,d,h,H ). 
(2)加密过程(其中M ∈G): 
Epk(M ): 
r←R Zq; 
u1=gr1
,u2=gr2
,e=hrM ,α=H (u1,u2,e),v=crdrα; 
输出(u1,u2,e,v). 
(3)解密过程:D 
sk(u1,u2,e,v): 
α=H (u1,u2,e); 
如果ux1+y1α 
1 ux2+y2α 
2 ≠v,返回⊥;否则返回e 
uz11uz22 
. 
方案的正确性: 
由u1=gr1
,u2=gr2
可知ux11ux22 =gr1x1gr2x2 =cr,uy11uy22 =dr。所以
ux1+y1α 
1 ux2+y2α 
2 =ux11ux22 (uy11uy22)α=crdrα=v 
验证等式成立。又因为uz11uz22 =hr,所以e 
uz11uz22 =e 
hr =M 。
在该方案中,明文是群G中的元素,限制了方案的应用范围。如果允许明文是任意长
的比特串,则该方案的应用范围更广。
3.3.2 Cramer-Shoup 密码系统的安全性证明
设g2=gw
1 ,则h=gz11+wz2 =gz'
1。解密时uz11uz22 =gr1z1gr2z2 =gr1(z1+wz2)=hr。所以加
密过程中的(u1,e)是以秘密钥z'=z1+wz2 和公开钥h=gz'1
的ElGamal加密算法对消
息M 进行的加密。由2.1.5节知,在DDH 假设下ElGamal加密算法是IND-CPA 安全
的,所以Cramer-Shoup密码系统也是IND-CPA 安全的。密文中的(u2,v)则用于数据的
完整性检验,以防止敌手的延展攻击,因而获得了IND-CCA2的安全性。安全性的具体
分析如下。
该方案的安全性基于2.1节介绍的Diffie-Hellman判定性假设(简称为DDH 假设)。
DDH 假设的另一种描述如下。没有多项式时间的算法能够区分以下两个分布: 
. 随机四元组R=(g1,g2,u1,u2)∈G4。
. DH 四元组D =(g1,g2,u1,u2)∈G4,其中u1=gr1
,u2=gr2
,r←R Zq。
设RDH是R 构成的集合,PDH是D 构成的集合。
定理3-10 设哈希函数H 是防碰撞的,群G上的DDH 假设成立,则Cramer-Shoup
81

密码学中的可证明安全性(第2版) 
密码系统Π是IND-CCA2安全的。
具体来说,假设存在一个IND-CCA2敌手A以ε(κ)的优势攻破Cramer-Shoup密码
系统Π,那么一定存在一个敌手B以
AdvDDH B (κ)=12
ε(κ) 
的优势解决DDH 假设。
证明 下面证明Cramer-Shoup密码系统可归约到DDH 假设。
设敌手B已知四元组T =(g1,g2,u1,u2)∈G4,以A(攻击Cramer-Shoup密码系统) 
作为子程序,目标是判断T ∈RDH还是T ∈PDH。过程如下: 
ExpCS-CCAΠ,A 2(T): 
x1,x2,y1,y2,z1,z2←R Zq,H ←R H; 
c=gx11gx22 ,d=gy11gy22 ,h=gz11gz22 ; 
sk=(x1,x2,y1,y2,z1,z2),pk=(g1,g2,c,d,h,H ); 
(M0,M1)←ADsk(·)(pk),其中|M0|=|M1|; 
β←R {0,1},e=uz11uz22Mβ,α=H (u1,u2,e),v=ux1+y1α 
1 ux2+y2α 
2 ;/嵌入了困难问题 
C* =(u1,u2,e,v); 
β'←ADsk,≠C* (·)(pk,C* ); 
如果β'=β,则返回1;否则返回0. 
其中,Dsk,≠C* (·)表示敌手对Dsk(·)询问除了C* 外的密文。如果ExpCΠS,-ACCA2(T )=1,B 
认为T ∈PDH;如果ExpCΠS,-ACCA2(T)=0,B认为T ∈RDH。
A的优势定义为安全参数κ 的函数: 
AdvCS-CCA2 Π,A (κ)= Pr[β'=β]-12 
B的优势定义为
AdvDDH B (κ)= Pr[ExpCS-CCA2 Π,A (T)=1]-12 
显然AdvDDH B (κ)=AdvCΠS,-ACCA2(κ) 
断言3-4 如果(g1,g2,u1,u2)∈PDH,则B的模拟是完备的。
证明 若(g1,g2,u1,u2)∈PDH,则有
u1=gr1,u2=gr2 
ux11ux22 =cr,uy11uy22 =dr,uz11uz22 =hr 
所以B对任意消息M 以(g1,g2,c,d,h,H )为公开钥加密得到e=Mhr,v=crdrα,以(x1, 
x2,y1,y2,z1,z2)为秘密钥可正确解密,B的模拟是完备的。
(断言3-4证毕) 
断言3-5 如果(g1,g2,u1,u2)∈RDH,则A在上述模拟中的优势为0。
证明 该断言由以下两个断言得到。
断言3-5' 当(g1,g2,u1,u2)∈RDH时,B以不可忽略的概率拒绝A在解密询问时询
问的所有无效密文。
82

第3章 语义安全的公钥密码体制 
证明 考虑秘密钥(x1,x2,y1,y2)∈Z4q,假设敌手A此时有无限的计算能力,可求
logg1c、logg1d 以及logg1v,那么A可根据公开钥(g1,g2,c,d,h,H )和挑战密文(u1,u2, 
e,v)建立如下方程组: 
logg1c=x1+wx2 
logg1d=y1+wy2 
logg1v=r1x1+wr2x2+αr1y1+αwr2y2 
ì
.
í
.. 
.. 
(3-3) 
(3-4) 
(3-5) 
其中w =logg1g2。
假设A询问了一个无效密文(u'1
,u'2
,e',v')≠(u1,u2,e,v),这里u'1 
=gr'1 1 ,u'2 
=gr2'2 , 
r'1 
≠r'2
,α'=H (u'1
,u'2
,e')。
下面分3种情况讨论。
(1)(u'1
,u'2
,e')=(u1,u2,e)。此时α'=α,必有v'≠v,因此B将拒绝无效密文。
(2)(u'1
,u'2
,e')≠(u1,u2,e),且α'=α。此时与哈希函数的抗碰撞性矛盾。
(3)(u'1
,u'2
,e')≠(u1,u2,e),且α'≠α。此时B若接受无效密文,A就可以建立另一
方程: 
logg1v'=r'1
x1 +wr'2
x2 +αr'1
y1 +αwr'2
y2 (3-6) 
因为
det 
1 w 0 0 
0 0 1 w 
r1 wr2 αr1 αwr2 
r'1
wr'2
α'r'1
α'wr'2 
.
è
..... 
.
.
÷÷÷÷÷
=w2(r2-r1)(r'2 
-r'1
)(α-α')≠0 
所以式(3-3)~式(3-6)组成的方程组有唯一解,即A可求出秘密钥(x1,x2,y1,y2)。
因此,即使A有无限的计算能力,A询问无效的密文使得B接受的概率仍然是可忽
略的。
(断言3-5'证毕) 
断言3-5″ 若在模拟过程中B拒绝所有的无效密文,则A的优势为0。
证明 考虑秘密钥(z1,z2)∈Z2q,A可根据公开钥(g1,g2,c,d,h,H )建立关于(z1, 
z2)的方程(仍然假定A有无限的计算能力): 
logg1h =z1 +wz2 (3-7) 
如果B仅解密有效密文(u'1,u'2,e',v'),则由于(u'1
)z1 (u'2
)z2 =gr1'z1gr2'z2 =hr',A通过
(u'1
,u'2
,e',v')得到的方程r'logg1h=r'z1+r'wz2 仍是式(3-7),因此没有得到关于(z1, 
z2)的更多信息。
在B输出的挑战密文(u1,u2,e,v)中,有e=γMβ,其中γ=uz11uz22 ,A由此建立的方
程为
logg1γ =r(z1 +wz2) (3-8) 
式(3-7)和式(3-8)有4个未知量(z1,z2,r,γ),对A来说没有获得γ 的任何信息,γ 保持
均匀分布。换句话说,e=γMβ 是用γ 对Mβ 所做的一次一密加密,A猜测β 是完全随机的。
(断言3-5″证毕)(断言3-5证毕)
83

密码学中的可证明安全性(第2版) 
设D和R分别表示事件(g1,g2,u1,u2)∈PDH和(g1,g2,u1,u2)∈RDH。
由A的优势及断言3-4、断言3-5得
Pr[β'=β|D]-12
=ε(κ),Pr[β'=β|R]-12
=0 
所以
Pr[β'=β]=Pr[D]Pr[β'=β|D]+Pr[R]Pr[β'=β|R] 
=12 
12
±ε(κ) .
è .
.
. ÷ 
+12
=12
±12
ε(κ) 
AdvCS-CCA2 Π,A (κ)= Pr[β'=β]-12
=12
ε(κ) 
得B的优势为
AdvDDH B (κ)=12
ε(κ) 
(定理3-10证毕) 
3.4 RSA-FDH 签名方案 
3.4.1 RSA 签名方案
签名方案的定义见定义2-8,其语义安全性见定义3-4。
定义3-4 对于一个签名方案(SigGen,Sign,Vrfy),如果对任何多项式有界时间的敌
手A在以下实验中的优势是可忽略的(其中A可多项式有界次访问签名谕言机
Signsk(·)): 
ExpSEiUgF,A (κ): 
(vk,sk)←SigGen(κ); 
(M ,σ)←ASignsk(·)(vk); 
设Q 表示A访问签名谕言机Signsk(·)的消息集合; 
如果Vrfyvk(M ,σ)=1且M .Q,返回1;否则返回0. 
则称该签名方案为在适应性选择消息攻击下具有存在性不可伪造性(Existential 
UnforgeabilityAgainstAdaptiveChosen MessagesAttacks,EUF-CMA),简称为EUFCMA 
安全。
A的优势定义为
AdvSEiUgF,A (κ)=|Pr[ExpSEiUgF,A (κ)=1]| 
定义2-9的方案是一次性强签名方案,其中A对签名谕言机Signsk(·)只能访问一
次,且A即使得到一个消息-签名对,也不能伪造这个消息的另一个签名。
RSA 作为加密算法见3.1.1节。RSA 用于签名算法的方案如下。
(1)密钥产生过程: 
84

第3章 语义安全的公钥密码体制 
GenRSA(κ): 
p,q←GenPrime(κ); 
n=pq,φ(n)=(p-1)(q-1); 
选e,满足1<e<φ(n)且(φ(n),e)=1; 
计算d,满足de≡1(modφ(n)); 
pk=(n,e),sk=(n,d). 
(2)签名过程: 
Signsk(M ): 
σ=Md modn. 
(3)验证过程: 
Vrfypk(M ,σ): 
如果σe=M modn,返回1;否则返回0. 
但RSA 签名体制不是EUF-CMA 安全的,它的EUF游戏如下。
(1)初始阶段。挑战者产生系统的密钥对pk=(e,n),sk=(d,n),将pk发送给敌手
A,但将sk保密。
(2)签名询问。A执行以下的多项式q=q(κ)有界次适应性询问。
A提交Mi,其中某个M.=reM ,挑战者计算si≡Md
i (modn)(i=1,2,…,q)并返回
给A。
(3)输出。A输出(M ,σ)=(M ,s./r),因为s.≡(reM )d ≡rMd (modn),所以s./r≡ 
Md (modn),即为M 的签名。M 不出现在签名询问阶段且Vrfypk(M ,σ)=1。
3.4.2 RSA-FDH 签名方案的描述
RSA 签名方案中使用模指数运算,如果哈希函数的输出比特长度和模数的比特长度
相等,则称该哈希函数为全域哈希函数(FullDomainHash,FDH)。使用全域哈希函数
的RSA 签名方案(简称RSA-FDH 签名方案)在适应性选择消息攻击下具有存在性不可
伪造性,即为EUF-CMA 安全的。
方案(记为Π)如下: 
设GenRSA 如前,函数H :{0,1}* →{0,1}2κ,κ 为安全参数。
(1)密钥产生过程: 
SignGen(κ): 
(n,e,d)←GenRSA(κ); 
pk=(n,e); 
sk=(n,d). 
(2)签名过程(其中M ∈{0,1}* ): 
Signsk(M ): 
h=H (M ); 
输出σ=hd modn. 
85