前向安全数字签名

2024-06-15

前向安全数字签名（共7篇）

前向安全数字签名篇1

摘要：随着网络技术的不断发展, 前向安全数字签名引起了人们的广泛关注。本文以此为研究对象, 对前向安全数字签名的一般构建和解决方案进行研究。

关键词：前向安全,数字签名,方案

1997年Anderson提出了前向安全的概念, 前向安全思想的主要突破在于, 在密码学算法上设立了一种预防机制, 以减少由于密钥暴露而带来的危害。

一、前向安全数字签名的基本思想

把整个签名的有效时间分成T个时段, 在每个j (1≤j≤T) 时段内使用不同的签名密钥SKj产生签名, 在每个时段的最后, 签名者以一个单向的模式, 从当前时段j (1≤j≤T) 的密钥SKj得到一个新的下一个j+1 (1≤j+1≤T) 时段的密钥SKj+1, 并且安全地删除当前时段j (1≤j≤T) 的密钥SKj, 而用于验证的签名公钥PK在整个签名有效时间T内都保持不变。

二、前向安全数字签名的一般构建

前向安全数字签名方案的关键在于密钥进化和前向安全性, 这也是与一般的数字签名不同的特色所在。实际上, 这两点是相辅相成的。前者是后者的原因, 后者是前者的必然结论。前向安全数字签名方案的私钥随着时间的推移按时段不断进化更新, 而相应的公钥在整个签名周期内保持不变。

三、前向安全数字签名的几种解决方案

1、长公钥长秘密密钥方案:

系统建立时, 签名者重复执行密钥生成算法产生T个密钥对 ( (p1, s1) , (p2, s2) … (p T, s T) ) , 其中pi为签名的公开密钥, si为相应的签名秘密密钥 (i=1, 2, …, T) 。设密钥进化方案的公钥为PK= (p1, p2, …p T) 以及初始密钥SK0= (s0, s1, …, s T) , 其中s0为空串。当进入i时段, 签名者完全删除Ski-1, 则i时段的密钥为SKi= (s1, …, s T) , i时段消息m的签名为。对消息m的签名 (其中ξ=SGN (m, si) ) 的验证即检验VRFY (m, pi, ξ) =1是否成立。方案是前向安全的, 但是公钥和密钥的长度随着总时段数T线性地增长, 显然是不可取的。

2、短公钥长秘密密钥方案:

Anderson提出了以上方案的一个改进, 其结果为公钥很短, 但秘密密钥长度依然随着T线性增长。签名者同以上的方案一样首先产生T个密钥对 ( (p1, s1) , (p2, s2) , … (p T, s T) ) , 并产生一个附加的密钥对 (p, s) , 令σ=SGN (i||pi||s) (i=1, …, T) 即σ=SGN (i||pi) 是对时段i及第i个公钥pi的一个签名, 然后删除s。系统的公钥为p (短公钥) , 系统的初始密钥为SK0= (s0, σ0;si, σ1;…s T;σr) , 其中s0, σ0为空串。当进入i时段, 签名者完全删除si-1, σi-1, 则i时段的秘密密钥SKi= (si, σi;si+1, σi+1;…;s T, σT) , i时段消息m的签名为, 令ω=SGN (m, si) , 即消息m的签名为, 用si对应的公钥pi验证签名, 用p验证pi的签名σi, 要求检验VRFY (m, ω, pi) =1和VRFY (i||pi, p, σi) =1是否同时成立。这个方案和第一方案一样, 随着时间段的推移不断删除前一个阶段秘密密钥, 以此来获得前向安全性, 这类方案公钥的长度很小且与T无关, 但问题在于签名秘密密钥长度随总时段数T线性增长, 也是不可取的。

3、长签名方案:

通过使用证书链签名的公钥和私钥的长度都很短, 但是产生的签名却很长。签名者生成初始密钥对 (p0, s0) , 公钥p0, 密钥s0。在每个时段一个新密钥生成即刻删除旧密钥, 证书链被包含在签名中。具体地说:在1时段的开始, 签名者生成一个新的密钥对 (s1, p1) , 设σ1=SGN (1||p1||s0) , 然后删除s0, 第1时段的私钥为 (s1, p1, σ1) , 用s1对消息m的签名是<1, (SGN (m, s1) , p1, σ1) >, 令ω1=SGN (m, s1) , 即消息m的签名为, 用s1对应的公钥p1验证签名, 用p0验证p1的签名σ1, 为检验VRFY (m, ω1, p1) =1和VRFY (1||p1, p0, σ1) =1是否同时成立。重复以上过程, 当时段i≥2, 签名者拥有 ( (p1, σ1) , (p2, σ2) , … (pi-1, σi-1) ) 和前一个时段的密钥si-1, 生成一个新的密钥对 (pi, si) , 令σi=SGN (i||pi||si-1) 并删除si-1, 第i时段的私钥为 (si, pi, σi, pi-1, σi-1, …p1, σ1) 相当于一个证书链, 其作用是保证当前公钥pi的真实性。时段i消息m的签名为, 令ωi=SGN (m, si) , 即消息m的签名为, 用si对应的公钥pi验证签名, 用p0验证p1的签名σ1, 用p1验证p2的签名σ2, …, 用pi-1验证pi的签名σi, 检验VRFY (m, ωi, pi) =1, VRFY (1||p1, p0, σ1) =1, VRFY (1||p2, p1, σ2) =1, …, VRFY (1||pi, pi-1, σi) =1是否同时成立。此方案可得到前向安全性, 且签名的公钥和私钥的长度与总时段数T均无关。但是签名长度、验证时间随着T线性增长, 与T成正比, 也是不可取的。

随着网络和通信技术的飞速发展, 环保信息安全已经成为关系到国际民生的重大问题, 希望本文能为相关领域的研究提供借鉴。

参考文献

[1]阿力木江·艾沙:《一种强前向安全数字签名方案》[J].计算机工程与应用, 2008, (9) .[1]阿力木江·艾沙:《一种强前向安全数字签名方案》[J].计算机工程与应用, 2008, (9) .

[2]云翠兰:《基于前向安全签名体制的研究及其应用》[J].微计算机信息, 2008, (3) .[2]云翠兰:《基于前向安全签名体制的研究及其应用》[J].微计算机信息, 2008, (3) .

前向安全数字签名篇2

数字签名是一种以电子形式存储的消息签名的方法，是密码学的主要研究领域，在实际中广泛应用。它的安全性主要依赖于密钥的保密性，但目前的网络环境总是遭到各种攻击，几乎不可能完全保证密钥安全性。为了解决数字签名密钥泄露问题，Anderson[1]于1977年ACM CCS会议上提出前向安全数字签名FSS(Forward Secure Signature)的概念:即使当前签名密钥丢失，它仍然能够保证先前签名的安全有效性。随后，Bellar and Miner[2]设计了第一个前向安全数字签名方案，主要思想是将公钥生命周期分为T个时间段，每个时间段中相同的公钥对应着不同的私钥，利用目前的私钥可以计算出其后的私钥，但不能计算先前的私钥。即使目前的私钥泄露，攻击者仍无法伪造先前的数字签名。目前已经提出了多种前向安全数字签名方案[3,4,5,6]，国内关于这方面也取得很多研究进展[7,8,9,10]。基于身份的数字签名IBS(Identity Based Signature)由Shamir[11]首先提出，主要为了解决公钥基础设施PKI(Public Key Infrastructure)的密钥管理问题，验证者只需要利用签名者的身份信息，比如姓名和邮箱地址等，作为公钥验证签名的有效性，因此无需数字证书来认证签名者的身份和公钥。文献[12]提出一种类Schnorr轻量级基于身份的数字签名方案，文献[13]利用二次剩余构造了基于身份的数字签名方案，文献[14]在通用可组合安全性框架下证明了基于身份的数字签名方案的通用可组合安全性。结合前向安全和基于身份的数字签名方案，于是提出了基于身份的前向安全数字签名方案IBFSS(Identity Based Forward Secure Signature)[15,16,17]，旨在同时解决密钥管理以及密钥泄露的问题，具有重大的实际应用价值。

混沌系统由于其对初始值和参数的极端敏感性以及良好的伪随机特性，表现出与密码系统混淆和扩散的相似特征，为密码学发展提供了新的方向，成为密码学的重点研究领域，并且已经涌现了大量的基于混沌的密码算法[18]。2003年，Kocarev等人将实数域上的Chebyshev混沌映射用于公钥加密[19]。但由于实数域上的Chebyshev多项式具有周期特性，可用三角函数代换法进行攻击，因而该算法是不安全的[20,21]。于是Kocarev等将Chebyshev多项式的定义从实数域扩展到有限域[22]，设计了基于有限域Chebyshev多项式的Elgamal式公钥加密算法(Chebyshev-Elgamal)和RSA式公朗加密算法(Chebyshev-RSA)，极大地增强了算法的安全性。

本文基于Chebyshev公钥算法，构造了一个基于身份的前向安全数字签名方案。签名者只使用当前的私钥对信息进行签名，与先前密钥无关，并且利用密钥更新算法得到后继密钥，无需额外存储空间。验证者利用签名者身份信息，即可验证签名的有效性。分析表明，本文设计的基于身份的前向安全数字签名方案具有很高的安全性和良好的性能。现有的基于身份的前向安全数字签名方案非常少，本文主要的创新之处在于首次利用Chebyshev公钥算法设计了基于身份的前向安全数字签名方案，为其研究提供了新的思路。

1 预备知识

本节将介绍所涉及到一些基础知识，包括基于身份的前向安全数字签名算法和Chebyshev公钥算法，如下所示:

1.1 基于身份的前向安全数字签名

基于身份的前向安全数字签名(IBFSS)方案主要分为四个阶段:IBFSS=(IBFSS.setup,IBFSS.update,IBFSS.sign,IBFSS.verify)，如下所示:

(1)IBFSS.setup:密钥生成算法，根据输入的安全参数k和一个周期内的时段数T，生成所需要的公共参数和主密钥。签名者身份信息ID∈{0,1}*，连接ID和T，得到id=ID‖T。将id作为签名者公钥，并根据主密钥计算初始的私钥SK0。

(2)IBFSS.update:密钥更新算法，在当前的时间段i<T时，根据当前的私钥SKi，计算下一时段的私钥SKi+1。

(3)IBFSS.sign:数字签名算法，根据当前私钥SKi和待签名消息m，计算消息的签名Sign。

(4)IBFSS.verify:签名验证算法，根据签名者身份信息id和消息m的签名Sign进行验证，以判定签名是否有效。

1.2 Chebyshev混沌映射

下面介绍Chebysehv混沌映射以及离散对数难题DLP(Discrete Logarithm Problem)和Diffie-Hellman难题DHP(Diffie-Hellman Problem)基本概念。

定义1 n为一个正整数，x∈[-1,1],n阶Chebyshev多项式Tn(x):[-1,1]→[-1,1]定义如下:

它同时可以通过以下递归关系定义:

其中T0(x)=1 and T1(x)=x。

前3项Chebyshev多项式为:

Chebyshev多项式具有两项重要性质:半群属性和混沌属性。

(1)半群属性

其中r和s是正整数，x∈[-1,1]。

(2)混沌属性

当n>1时，Chebyshev多项式具有不变密度分布和正的李雅普诺夫指数λ=lnn>0，表明其混沌属性。

为了增强其安全性，Kocarev等[22]将Chebyshev多项式的定义从实数域扩展到有限域，如下所示:

其中n≥2,P是一个大素数，可以得到:

定义2离散对数难题是指(DLP):给定y，寻找整数s，使其满足Ts(x)=y。

定义3 Diffie-Hellman难题(DHP):给定Tr(x)和Ts(x)，计算Trs(x)。

Chebyshev公钥算法基于DLP和DHP难题，它们被认为是NP难题。

1.3 Chebyshev公钥密码算法

在文献[22]中，Kocarev等将Chebyshev多项式的定义从实数域扩展到有限域，设计了基于有限域Chebyshev多项式的Elgamal类型公钥加密算法和RSA类型公钥加密算法(ChebyshevRSA)。本文需要结合使用两种类型的公钥算法，下面分别予以介绍:

1)Elgamal类型公钥算法

(1)密钥生成:生成一个随机大整数N,x和s，并且x<N,s<N，计算A=Ts(x)mod N。则所得的公钥为(x,N,A)，私钥为s。

(2)消息加密:发送方首先把需要加密的消息转换成整数m(1<m<N)，选择一个随机数r,r<N。根据公钥(x,N,A)，计算B=Tr(x)mod N,X=mTr(A)mod N，然后将密文消息c=(B,X)发送给接收者。

(3)消息解密:接收到密文消息c后，解密者利用私钥s计算C=Ts(B)mod N，恢复出明文消息m=XC-1(mod N)。

2)RSA类型公钥算法

(1)密钥生成:生成两个不同大随机数p和q，计算N=pq和=(p2-1)(q2-1);选择一个随机数e，使得1<e<，并且gcd(e，)=1;计算整数d,1<d<，并且ed≡1(mod);生成的公钥即为(N,e)，私钥为d。

(2)消息加密:发送方把需要加密的消息转换成整数m(1<m<N)，根据公钥(N,e)，计算密文c=Te(m)(mod N)，并发给接收者。

(3)消息解密:收到密文c后，接收者利用私钥d计算m=Td(c)(mod N)，得到所发送的明文消息。

2 基于身份的前向安全数字签名方案

本方案的构造结合基于Chebyshev混沌映射的Elgamal类型和RSA类型公钥加密算法:Elgamal类型算法用来构建基于身份的公钥加钥算法，RSA类型算法则用来构建前向安全数字签名方案。如前面所述，它分为以下四个阶段:

1)密钥生成阶段(IBFSS.setup)

(1)生成两个不同的随机大素数p和q，它们应具有相同的位数。计算N=pq和=(p2-1)(q2-1);

(2)确定一个周期内时间段数T，选择T+1个随机整数ei(0≤i≤T)，使得1<ei<，并且gcd(ei，)=1。计算相应的整数di(0≤i≤T)，使得1<di<，并且eidi=1(mod)。计算d'i=Tei(di+1)(bmod N),e'i=Tdi(ei+1)(mod N),0≤i≤T-1;

(3)令id=ID‖T,ID为签名者身份信息和T为时间段数，构建单向Hash函数H:{0,1}*→P,P是一个集合P={x x∈Z,1<x<N}。

签名者公共参数为PP=(H,N)，公钥即为签名者的身份信息id，私钥为(e0,d0,e'i,d'i(0≤i≤T-1))。

2)密钥更新(IBFSS.update)

(1)如果0≤i≤T-1，计算

(2)如果i=T，重新运行密钥生成算法，初始化系统。

3)签名算法(IBFSS.sign)

(1)对于消息m，计算Hash函数h=H(m)。计算

(2)计算s=H(id)，选择一个随机整数r∈P，计算sig2=Tr(h)mod P和sig3=ei·Ts(Tr(h))mod N;

(3)签名消息即为Sign=(m,sig1,sig2,sig3)。

4)验证算法(IBFSS.verify)

(1)根据签名消息Sign，公共参数PP和公钥id，验证者计算h=H(m),s=H(id)。并由h和s，计算e'i=sig3·(Ts(Tr(h)))-1mod N;

(2)验证Te'i(s)(mod N)=H(m)。若两者相等，则表示签名有效，否则说明签名无效。

3 安全性分析

(1)算法安全性

本方案的安全性主要基于大整数因子分解难题和基于Chebyshev离散对数难题。

大整数分解问题是数论中一个重要的难题，在密码学中被广泛应用。RSA,Rabin,Blum Blum Shub等密码系统安全性主要依赖于大整数因子分解难题。该问题是极其重要的，也是许多数学家一直研究的问题。本方案中N=pq,N是公开参数，p和q是秘密参数，用来计算私钥ei和di(0≤i≤T)。基于大数数因子分解难题，不存在能在多项式时间内有效算法将N分解得到p和q，因而保证了私钥的安全性。

由前面可知，Chebyshev离散对数难题(DLP)可以表述为:给定x和y，寻找整数s，使其满足Ts(x)=y。基于Chebyshev的Elgamal类型公钥算法安全性主要基于该离散对数难题，它被认为是一个NP问题。本方案密钥更新过程中，，假设当前密钥ei+1和di+1泄露，基于该离散对数难题，攻击者无法计算前一时间段ei和di密钥，因此保证了算法的前向安全性。

(2)参数选择安全性

Chebyshev公钥算法的安全性取决于Chebyshev混沌多项式序列的性质，而Chebyshev多项式Tr(x)mod N的性质由参数x和N共同决定。下面讨论这些参数的选择对Chebyshev多项式序列以及对该密码体制的安全性的影响，并给出一些参数选择的原则。

为了增加分解的难度，N的值应该足够大，因此p和q应取较大的值，两者应该具有相同的位数，但值不能过于接近。x的取值也需要足够大。当时x=0,Tr(0)(mod N)=1,0,-1,0，周期为4;当x=1,Tr(1)(mod N)=1，周期为1;当x=N-1,Tr(N-1)(mod N)=1,p-1，周期为2。由于Tr(x)mod N的周期性，的选择应该避免这样一些特殊的取值。在基于Chebyshev的Elgamal类型算法中，需要选择一个随机数r,r<N。根据公钥(x,N,A),A=Ts(x)mod N，计算B=Tr(x)mod N,X=mTr(A)mod N，在随机选取r的过程中，需要保证(Tr(A))-1mod N存在，否则无法进行解密。

4 性能分析

本方案效率主要受高阶Chebyshev多项式的函数值计算影响，它不能利用递归数列直接计算，否则算法效率非常低。有两种快速计算的方法，分别如下:

第一种方法利用Cheyshev多项式的半群性质[19]，设它的阶数为:

则，因此需要{{迭代Chebyshev映射的次数就变为:次[19]。例如假设s=234516远小于，则只需要迭代(2-1)×34+(5-1)×16=98次，极大提高了计算效率，但是这该方法并不能对任意的s作简化计算，不是通用的计算方法。

第二种是计算Cheyshev多项式的一种通用快速算法，它需要将递归公式写成如下矩阵乘积形式[22]:

从上式可知，Tn(x)的计算转化为矩阵幂的计算，然后把n表示成二进制的形式，计算复杂度为O(logn)。文献[23]利用Cayley-Hamilton定理，提出了特征多项式方法，比矩阵幂算法效率高。文献[24]对矩阵幂算法和特征多项式算法进行了优化，并提出了新的矩阵特征值算法，进一步提升其计算效率。

下面根据文献[25]中的方法，通过一个签名周期内时间段数T分别对密钥生成、密钥更新、签名算法和验证算法的复杂度计算。将本文所提出的方案和现有的前向安全数字签名方案[25]、基于身份的前向安全数字签名方案[16]比较，如表1所示。

从表中可以看出，本方案在密钥生成阶段计算相对复杂，但在密钥更新、签名和验证阶段的效率有一定的优势，具有潜在的应用价值。

5 结语

前向安全数字签名篇3

针对以上的问题和传输中的泄漏, 专家们提出了不同的方式去降低系统密钥被泄露的机会。1997年Anderson针对以上问题提出了前向安全概念, 前向安全概念主要是对密钥有效期分时段, 通过单向模式的每个时段是最后签名者, 在当前时段, 密钥对下个时段得到密钥, 并对不使用的密钥进行安全删除。公钥在整个密钥周期里不变, 通过这种方式保证了泄漏密钥时段签名有效性。

签名密钥进化是通过前向安全数字签名实现的。初期用户通过注册得到一个证书, 获得初始密钥SK0与公钥。针对有效期划分T个时段, 记1, 2, 3, ……, T。公钥PK有效期内是固定, 通过时段不段密钥更新。i时段密钥为SKi。i时段得到SKi=f (SKi-1) , f为单向函数, 获得SKi后, 马上删除SKi-1。在i时段, 攻破系统获得密钥SKi, 不能得到SKi-1, SKi-2, ……, SK0, 因为这些密钥通过单向函数已经被删除。签名秘密密钥进化如下:

当前向安全方案不断发展和实践, 通过通常签名Miner, Bellare对安全定义进行了扩展, 得出前向安全正式概念, 从此有了许多前向安全的数字签名方案如[1,2,3,4,5]被陆续提出[1,2,3,4,5]。最近, 徐光宝等[6]提出了一种强前向安全的数字签名方案, 本文通过对该方案的分析指出该方案的验证过程存在错误, 并对验证过程做了修改, 使真正的签名能通过验证。

1 文献[6]方案介绍

基于Guillou-Quisquater设计强前向安全的数字签名。整个方案分成初始签名密钥生成、签名密钥的更新、签名生成、及签名验证4个部分。假定签名者是Alice, 签名接收者是Bob, 有效期分T个时段。在每个签名时段Alice有2个私钥。

1.1 签名密钥生成

签名密钥生成过程如下:

第一, Alice进行随机取2个素数p和q, 满足条件p≡q≡3 mod 4, 得出n=pq, 选取2个整数和, 使它们满足如下条件:

gcd (v, (p-1) (q-1) ) =1, gcd (w, (p-1) (q-1) ) =1

第二, Alice随机选取2个私钥x, z∈RZn*, 计算公开密钥:

第三, Alice计算:

并将它们分别加密保存。

第四, Alice公开{n, y1, y2, v, w}。

1.2 签名密钥的更新

令x0=x mod n, 第i (1≤i≤T) 个签名时段, Alice一方面根据等式xi=xi2-1, 计算第i阶段的第一私钥xi, 同时永久删除xi-1;另一方面对zi解密第i时段私钥。

1.3 签名生成

假设m是待签名, i (1≤i≤T) 签名时段为例, Alice生成签名步骤如下:

第一, 随机选2个整数k, r∈RZn*, 得出:

第二, 计算杂凑值:e=H (m‖Q‖i) , 使之满足1≤e

第三, 计算s1=kxiemod n, s2=rziemod n。

Alice把 (m, s1, s2, e, i) 签名数据给验证者Bob。

1.4 签名验证

验证者Bob接收到Alice的签名数据后, 进行验证步骤如下:

第一, 计算

第二, 计算出e'=H (m‖Q'‖i) 。

第三, 验证等式e=e'是否成立, 成立签名有效, 否则签名无效。

2 对文献[6]的分析

通过对文献[6]的分析发现其验证部分存在错误, 即使是签名者Alice的真实签名, 接收者Bob也不能验证该签名是真实的。

设m为待签名消息, 签名者Alice在第i时段执行1.3节步骤, 获得对m签名 (m, s1, s2, e, i) , 不能通过1.4节验证得到。

具体证明如下:

所以有

e'=H (m‖Q'‖i) , 而

又因为

所以有

故即便是签名者Alice真正的签名, 也不能通过验证, 该签名方案是错误的。

3 对文献[6]验证部分的改进

下面通过对文献[6]的验证部分进行改进, 使真正的签名能通过验证, 证明其有效。具体验证过程如下:

第一, 计算

第二, 计算出e=H (m‖Q‖i) 。

第三, 验证等式e=e'是否成立, 成立签名有效, 否则签名无效。

4 修改方案正确性及安全分析

4.1 正确性分析

设m'为待签名, 签名者Alice对1.3节签名步骤进行操作, 获得签名数据, 通过验证步骤如下。

具体证明如下:

所以有

4.2 方案的安全性分析

文献[6]给出了方案的安全性分析及前向安全和后向安全的分析, 指出了该方案本身是安全的, 同时具有前向安全和后向安全的特性, 由于本文所做的只是在验证部分对原方案作了修改, 所以改进方案具有前后向安全特点。

5 结语

本文针对强前向安全数字签名进行了分析, 发现其验证部分存在错误, 导致正确的签名不能通过验证, 并对该方案的验证部分做了改进, 使其具有验证的功能, 并对签名的安全性做了说明。

参考文献

[1]邓宇乔.前向安全的盲代理重签名方案[J].计算机工程与应用, 2011, 47 (16) :97—100.

[2]万世昌, 程丽红, 张珍.前向安全的混合代理多重签名方案[J].计算机工程与应用, 2011, 47 (12) :80—83.

[3]芦殿军, 张秉儒, 赵海兴.基于多项式秘密共享的前向安全门限签名方案[J].通信学报, 2009, 30 (1) :45—49.

[4]于嘉, 孔凡玉, 郝蓉, 等.一个基于双线性映射的前向安全门限签名方案的标注[J].计算机研究与发展, 2010, 47 (4) :605—612.

[5]刘亚丽, 秦小麟, 殷新春, 等.基于模m的n方根的前向安全数字签名方案的分析与改进[J].通信学报, 2010, 31 (6) :82—87.

实用的前向安全门限重签名方案篇4

1 前向安全的门限数字签名方案

1.1 初始化阶段

1.1.1 选择循环子群

密钥分发中心首先选择n=P1P2=(2qp1'+1)(2qp2'+1)和一个阶为q的循环子群,g∈QRn(即gq=1mod n),QRn为模n的平方剩余集合,且p1=p2=3mod 4,其中p1,p2,p1',p2',q都为安全的大素数,然后选择一对整数(e,d),分别作为基于合数n的RSA公私钥,h()为一个安全的单向散列函数。

1.1.2 系统选择t-1阶秘密多项式

最后,公布(n,q,g,h,Y)。

1.1.3 秘密分量的分发

设A={u1,u2,…,ul}是群组t个成员,其身份标示IDi。对每个群组成员,密钥分发中心通过秘密信道把σi发送给每个ui作为成员秘密分量。

1.1.4 密钥的更新

将群组签名整个有效期分为T个时间段,从第一个时间段开始,群组成员根据前一时间段的密钥计算出目前时间段的密钥。

式(1)中,σi,j表示成员ui的第j时间段密钥,σi,j-1表示成员ui的第j-1时间段密钥,初始密钥σi,j=σi;j=1,2,…,T。更新完成后,销毁前一周期密钥σi,j-1。

1.2门限重签名的产生

1.2.1 部分签名产生

设群组集合A中t各成员B={u1,u2,…,ut}相对消息M产生代表群组的门限重签名,B中成员一起执行下列操作:

每个ui(i=1,2,3,…,t)选择一个随机数βi,计算:

然后,每个ui把{P,si,zi}发送给群签名合成者。

1.2.2 门限重签名的产生

群组签名合成者计算:

最后,{j,P,Z,S}为消息M的门限签名,j为第j个签名时间段。

1.2.3 门限签名的验证

任何验证者都能通过计算下式验证{j,P,Z,S}就是消息M的门限重签名。

2 方案安全性分析

2.1{j,P,Z,S}是有效的前向安全门限签名

证明:为了证明{j,P,Z,S}是有效的前向安全门限签名,则需要证明式(6)成立。

根据式(3)、式(4)和式(5)得:

根据式(5)和上式得:

则{j,p,Z,S}是有效的前向安全门限签名。

2.2 方案具有前向安全的特性

方案的前向安全是基于强RSA假定。

强RSA假定已知n和,n为两个大素数的乘积,则找出一个,且满足y=xβmod n(β>1)是一个非常困难的问题。

如果攻击者已获得群组签名者ui的第j时间段密钥σi,j,企图通过n计算第j时间段密钥σi,j-1,这是一个强RSA假定问题,所以攻击者无法通过σij计算出σi,j-1,也就无法伪造第k周期签名(k

2.3 方案能抵抗伪造攻击

非法用户企图通过式(4)和式(5)求S',这将面临大整数分解和单向散列函数求逆的问题。少于t个合法的参与者不能代表群组进行有效签名,t个成员无法获得系统秘密参数,任何一组成员不可以假冒另一组成员对消息生成有效的门限签名,而事后不负任何责任。这是由Shamir的秘密共享方案的安全性来保证的。

2.4 方案具有实用性

方案将求(Lagrange相关系数)通过计完成,在不知道RSA秘密参数(p-1)(q-1)的情况系不用求逆计算,因为整除P,这样的设计将方案具有实用性。

3 结束语

就日前已有的前向安全门限数字签名存在理论错误的缺陷,提出一种新的实用的前向安全门限重数字签名方案。降低门限签名者密钥泄漏造成的损失,将群组成员密钥按时间段进行更新,群组公钥保持不变。即使第k时间段的签名密钥被泄露,攻击者无法推出第k-1时间段的签名密钥,也无法伪造第k时间段之前的签名。前向安全的门限签名为签名密钥提供了强大的保护,使签名密钥被泄露所造成的损失降到最小。基于强RSA的假设,证明方案可抵抗非法签名者的伪造攻击和具有前向安全性和实用性。

参考文献

[1] Desmedt Y,Frankel Y.Threshold cryptosystems.In:Brassard G,ed. Advances in Cryptology——CRYPTO' 89 Proceedings Lecture Notes in Computer Science 435 Berlin:Springer Verlag,1990:307-315

[2] Anderson R..Invited lecture.In:Proceedings of the 4th ACM Conference on Computer and Communications Security,Zurich,Switzerland, 1997:1-7

[3]于佳.标准模型下的前向安全多重签名:安全模型和构造.软件学报,2010;21(11):2910-2923

[4]张明武.密文匿名的高效前向安全短签密方案,北京邮电大学学报,2010;33(4):131-135

[5]米军利,张建中.前向安全的门限签名方案.计算机工程与应用,2009;45(1):124-125

[6]程曦,戚文峰.一种向前安全的门限代理签名方案.信息工程大学学报,2006;4(7):314-318

前向安全数字签名篇5

代理签名是指原始签名者可以将他的签名权力授权给代理签名者,之后代理签名者就可以代表原始签名者进行签名,当验证者验证一个代理签名的同时,还需要验证原始签名者的授权协议。代理签名的思想最早出现于1991年,1993年Neuman讨论问题时也提到了代理签名的概念。1996年Mambo等[1]第一次系统地阐述了代理的概念,根据授权方式对代理签名作了分类,并给出了一个部分授权代理签名方案,为代理签名的研究奠定了基础。

前向安全的概念最早是由Anderson首先提出的[2],Bellare和Miner第一次给出了前向安全签名的正式定义,并基于A.Fiat和A.Shamir的签名方案[3]给出了两个前向签名方案[4]。其基本思想是把一对公钥和私钥的有效期分为若干个时间段,用于验证签名的公钥保持不变,而私钥是由单向函数和前一时间段的私钥产生。这样,每一时间段的签名私钥都互不相同,并且每一次签名后都把上一次的密钥删除,使得攻击者即使窃取到当前时间段的私钥也无法伪造过去时间段里的签名,从而减少密钥泄露带来的威胁。

目前提出的前向安全的签名方案主要分为两类:一类是通过修改一些特别的方案来得到的。如Bellare和Miner[5]的方案是基于大整数分解难题,它是根据Fiat-Shamir[6]方案构造的;Abdalla和Reyzin[7]的方案也是基于大整数分解难题,它是根据2t-th根的方案[8]构造的;王晓明等人的WCF方案[9]是基于强RSA假设的。第二类是提出一个一般模型,它可以把一般的签名方案转化成前向安全的签名方案。

双线性对对函数表现出良好的密码学特性,目前这方面已经引起的众多的关注。本文利用双线性对,构造了一种具有前向安全特性的代理签名方案。

2预备知识

2.1双线性对

双线性对是指两个循环群之间相对的线性映射关系。设G1是一个加法群,阶是大素数q。G2是一个乘法群,也以q为阶。双线性映射e:G1×G1→G2满足如下特性:

(2) 非退化性:存在P,Q∈G1,使得e(P,Q)≠1;

(3)可计算性:对所有的P,Q∈G1,存在一个有效的算法计算e(P,Q)。

2.2GDH群

假设G是一个椭圆曲线上的q阶的加法群,q为大素数。以下是几个基于G的困难问题:

(1)离散对数问题(DLP):给定G中两个元素P和Q,计算整数n,满足Q=nP。

(2)判定Diffie-Hellman问题(DDHP):对a,b,c∈Z*q,给定P,aP,bP,cP,判断c=abmodq是否成立。

(3)计算Diffie-Hellman问题(CDHP):对a,b,c∈Z*q,给定P,aP,bP,计算abP。

当群G上的DDHP是容易的,而CDHP是困难时,称群G为Gap Diffie-Hellman(GDH)群。这样的群可以在有限域的超椭圆曲线上找到。利用椭圆曲线上的Weil配对或Tate配对可以构造满足以上条件的双线性映射。

2.3前向安全的数字签名方案

一个前向安全数字签名方案是一个密钥进化数字签名方案。一个密钥进化数字签名方案非常相似于一个标准的数字签名方案。在一个标准的数字签名方案中,有密钥更新算法、签名算法和验证算法。在前向安全的数字签名方案的整个生命期中,公钥不改变,验证算法和标准签名方案的验证算法类似。

前向安全数字签名的形式化定义:

一个前向安全数字签名由四部分算法组成:FSIG=(FSIGkeygen, FSIGkeyupdate, FSIGsign, FSIGverify)。

(1)FSIGkeygen:密钥生成算法:输入一个安全参数k,时段总数T,输出初始公钥和私钥。

(2) FSIGkeyupdate密钥更新算法:输入当前时段的私钥SKi-1,返回下一时段的私钥。

(3)FSIGsign签名生成算法:输入一个当前时段j私钥SKj和要被签名的消息m,输出(j,sign),表示j时段消息m的签名。

(4)FSIGverify签名验证算法:输入公钥PK,消息m和签名(j,sign),如果(j,sign)是有效的签名,则返回1;否则返回0。

3基于双线性对的前向安全代理签名方案

3.1系统初始化:

给定安全参数k,G是一个以P为生成元的阶为素数q的GDH群,而I是阶为素数q的乘法群;e∶G×G→I是一个双线性对映射。选取hash函数H1∶{0,1}*→G,H2∶{0,1}*×G→Z*q,h∶{0,1}*→Z*q,并且输出公共系统参数{G,I,q,e,P}。

3.2密钥生成:

给定系统参数k,算法生成原始签名者A和代理签名者B的公私钥对。原始签名者A的公私钥对为(eA,dA),其中eA=dAP;代理签名者B的公私钥对为(eB,dB),其中eB=dBP。

3.3双线性配对代理签名权指定:

1.产生代理权:

原始签名者A首先生成一个授权委托证书mw,它详细描述了原始签名者对代理签名者的授权关系,包含A和B的身份信息、A对B的代理签名授权、代理签名时限等。然后A计算S′=dAH1(mw,IDA,IDB),并通过安全信道秘密地发送给代理签名者B。

2.验证代理权:

代理签名者B收到S′后,验证e(S′,P)=e(H1(mw,IDA,IDB),eA)是否成立,若成立,则接受此代理权,转到(3);否则,B拒绝接受代理权或者要求A重新传送新的S′。

3.代理密钥生成:

B接受代理权后,随即选取r0∈Z*q,计算R0=r0h(o)dundefined

S0=dundefined(S′+r0h(0)),(R0,S0)为代理签名者B的初始代理签名密钥。

4.代理密钥更新:

签名进入第时段,代理签名者B用i-1第时段的代理签名密钥(Ri-1,Si-1)计算第时段的代理签名私钥:

首先,代理签名者B随机选取ri∈Z*q,计算:

计算完成之后立即删除ri,Ri-1,Si-1;而(Ri,Si)即为代理签名者B在第i时段的代理签名密钥。

3.4代理签名生成:

代理签名者B利用第时段的代理签名密钥(Ri,Si)对消息的签名过程如下:

1.令T=Ri;

2.随机选取rp∈Z*q,计算U=rpeB,V=rpP+H2(m,U)S;

代理签名者B对消息的代理签名为(i,mW,T,U,V)。

3.5代理签名验证:

代理签名的接收者收到B对消息的代理签名(i,mw,T,U,V)后,验证:

e(V,eB)=e(U,P)e(H1H2,eA)e(H2T,eB)是否成立。方程中H1是H1(mw,IDA,IDB)的缩写,H2是H2(m,U)的缩写,在本章的以下部分都将沿用这个缩写。若成立则认可签名有效,否则认为无效。

3.6签名方案的正确性分析:

方案的正确性可由以下算式获得:

4方案的性能分析

4.1效率分析

Zhang等的基于双线性对的代理签名方案[10]是一个公认的比较好的方案,将本方案与之在效率上进行比较,得到如下结果(见表1)。可以看到,在代理签名生成阶段本方案比Zhang等的方案少了一个配对函数,多了一次群G中的乘法运算。而计算配对函数是最耗费时间的,与计算配对函数相比,计算群G中乘法运算的工作量要小的多,因此总的来说,本文的方案在效率上有了一定的提高。

4.2特性分析

本方案的安全性是基于GDH群中CDH问题难解的基础上的,满足代理签名的安全性质。

1.强不可伪造性:因为选取的G是GDH群,在G上的CDH问题是难解的,所以任何人在不知道原始签名者A私钥dA的情况下,不能够生成S′来伪造代理签名;同时,攻击者也不能冒充代理签名者B对消息m伪造代理签名,因为他没有原始签名者A给的S′,也就无法生成代理密钥(Ri,Si)。

2.可区分性:因为完整有效的代理签名中有授权证书mw,而且签名验证的过程中同时出现了原始签名者A的公钥eA、代理签名者B的公钥eB和证书mw,有效的区分了签名权和代理权。

3. 强不可抵赖性:对消息m完整有效的签名(i,mw,T,U,V)中包含了授权证书mw,并且在验证过程中用到mw、原始签名者和代理签名者的公钥,而代理签名者B不能更改mw,故代理签名者B一旦产生了代理签名,他就不能够否认所产生的签名,具有强抗抵赖性。

4. 身份证实性(可识别性):原始签名者A可以通过验证方程来确定代理签名者的身份是B,也就是说原始签名者可以根据此有效的代理签名确定出相应的代理签名者的身份,具有身份证实性。

5. 密钥依赖性:代理签名密钥(Ri,Si)是由原始签名者A的秘密密钥dA生成的S′产生的,所以方案具备了密钥依赖性。

6. 可注销性:授权委托证书mw指出签名的权限和时限,只允许代理签名者在一定时间内拥有代理签名的能力,代理密钥只在规定的时间内有效。

7. 可验证性:任何验证签名的人都可以验证代理签名是否有效,并且根据有效的代理签名中的授权证书mw能够确认原始签名者认同了这份签名消息。

8. 前向安全性:

在代理密钥更新过程中,代理签名者可以通过随机选取来进行代理密钥更新,这个随机数的选取不会受时间周期的影响,与总的时间周期无关,代理密钥可以不受时间周期数量的限制,无限的更新下去。也就是说,方案的安全参数与总的时间周期数量无关,可以在保证代理签名者私钥长度和公钥保持不变的条件下无限制的进行代理私钥更新。

假定攻击者获得了代理签名者B在第时段的代理签名密钥(Ri,Si),要想获得第j(j

5结束语

前向安全数字签名篇6

关键词：盲签名,离散对数,二次剩余,前向安全,盲性

0引言

随着现代信息技术和计算机网络的广泛应用与普及,人们对信息的安全提出了越来越高的要求,其中数字签名就是一种实现网络信息安全的重要手段,它在保证传输信息的保密性、完整性和不可抵赖性,实现发送者的身份认证等方面都有着广泛的应用。

1982年,Chuam[1]首次提出盲签名的概念,实现了不可跟踪的支付系统,即电子现金。盲签名是一种特殊的数字签名技术,它可以使消息拥有者在不被签名者看到所签消息的具体内容的情况下获得合法签名。一种简单的实现方法是消息拥有者和签名者进行如下交互:消息拥有者先利用盲因子将消息盲化,签名者对盲化后的消息签名,消息拥有者施行脱盲变换,最终获得原始消息的签名。在盲签名产生过程中,签名者不知道所签消息的具体内容,也无法将自己保留的中间结果与最终公布的签名联系起来进而跟踪消息拥有者。这种特性称为盲性,它使得盲签名能有效地保护用户的隐私,被广泛应用到需要保护个人隐私的场合,例如电子现金、电子选举等领域。

一般来说,一个密码体制的安全性应该仅仅依赖于密钥的安全性,这就是著名的Kerckhoff原则。根据Kerckhoff原则,密钥的泄露会使整个密码体制立刻变得不再安全。1997年,Anderson[2]首次提出前向安全的概念,有效地减轻了密钥泄露所带来的安全隐患。1999年,Bellare和Miner首次给出了前向安全数字签名的正式定义[3]。随后,前向安全技术被大量运用到各种具有特殊性质的数字签名中。前向安全的基本思想是通过在公钥密码体制中引入密钥演化算法,使得私钥随着时段的推进而不断更新,而公钥保持不变。这样,即使对手拥有当前时段的密钥,也不能伪造之前各时段的数字签名,保证了之前各时段所产生的签名的合法性,减少了由密钥泄露所带来的损失。

将盲签名和前向安全特性相结合,就产生了前向安全盲签名。2003年,Duc等人[4]基于强RSA假设提出了第一个前向安全盲签名方案。2005年,Lai等人[5]基于Koyama主密钥方案[6]提出了一个新的前向安全盲签名方案,方案中,各个时段的密钥需要预先设置和存储,增加了存储开销和泄露风险。Chow等人[7] 运用树结构构造方法提出了一个基于双线性映射和GDH问题的前向安全盲签名方案,但结构设计过于复杂。

本文在基于离散对数和二次剩余计算难题提出了一个前向安全盲签名方案,并对新方案进行了安全和效率分析。分析表明,新方案满足不可伪造性、盲性和前向安全性,且具有较高的计算效率。

1预备知识

1.1前向安全盲签名

前向安全数字签名的基本思想是把签名的整个有效时间划分成若干个时段,在不同时段内使用不断更新的签名密钥生成签名,却保持验证公钥在整个有效时间内不变,同时要求由某一时段的密钥无法计算出之前各时段的密钥,也无法生成之前各时段的签名。在每个时段的最后一个签名产生以后,以一个单向模式产生下一时段的签名密钥,即从时段j-1的密钥SKj-1生成时段j的密钥SKj,并且删除SKj-1。

一个前向安全盲签名方案包括以下四个算法[4]:

(1) 密钥生成算法是一个概率多项式时间算法。输入安全参数k和时间周期数T等,输出系统参数params、公钥PK和初始私钥SK0。

(2) 密钥更新算法是一个确定性或概率算法。输入前一时段的密钥SKj-1,输出当前时段的私钥SKj。

(3) 盲签名发布协议是一个用户与签名者之间通过交互方式产生盲签名的协议。签名者是一个概率图灵机,使用当前时段的密钥SKj与用户进行交互,为用户提供消息M的盲签名。用户也是一个概率图灵机,输入消息M和公钥PK,并与签名者进行交互。在签名完成后,输出时段j、消息M及签名sig(M)。(j,sig(M))即为最终盲签名。

(4) 签名验证算法是一个确定性算法,输入公钥PK,消息M和签名(j,sig(M)),输出验证通过与否的0/1判断。用A4纸,页边距上下左右已经设置好,请不要改动。

1.2相关数学难题

(1) 离散对数难题

设p是一个大素数,g是Z $_{p}^{*}$ 的生成元。给定y∈Z $_{p}^{*}$ ,求解x(1<x<p-1),使y=gxmodp成立是困难的。

(2) 二次剩余计算难题

在不知道n的具体分解的情况下,求满足y=x2modn的x是困难的。二次剩余计算难题等价于大数分解问题。

2方案描述

2.1密钥生成

系统选取大素数p(p≥2512);g∈Z $_{p}^{*}$ 是Z $_{p}^{*}$ 的生成元。选择安全的哈希函数H:{0,1}*→Z $_{p}^{*}$ 。

将签名的整个有效时间划分为T 个时段:1,2,…,T,只有在T个时段内,签名者对消息的签名才是有效的。

随机选取初始私钥s0(1<s0<p-1),计算公钥Y = gs2T0,公开(H,p,g,T,Y)。

2.2密钥更新

签名者根据前一时段的密钥更新得到当前时段的密钥。设当前时段为j,签名者按以下步骤更新密钥:

1) 若j>T,则sj设为空串,算法终止;

2) 若1≤j≤T,则计算j周期的密钥sj=s $_{j - 1}^{2}$ mod(p-1),并删除sj-1。

2.3盲签名发布

在j时段,签名者和用户进行如下交互产生消息m的盲签名:

(1) 承诺(Promise)

签名者选择随机数k(1<k<p-1),计算R′=gkmodp,并将(R′,j)发送给用户;

(2) 盲化(Blind)

用户收到(R′,j)后,随机选择盲化因子α,β,γ (1<α,β,γ<p-1),计算:

R=R′αgβYγmodp

e=H(R‖m‖j)

e′=α-1(e-j-1γ)mod(p-1)

并发送e′给签名者。

(3) 签名(Sign)

签名者收到e′后,计算:

s′=k-je′s $_{j}^{2^{Τ - j}}$ mod(p-1)

将s′发送给用户。

(4) 去盲(Umblind)

用户收到s′后,计算:

s=αs′+βmod(p-1)

则消息m的签名为sig(m)=(j,R,s)。

2.4 签名验证

接收者收到盲签名(m,j,(R,s))后,首先判断盲签名是否在签名者的签名有效期内生成,即j是否小于等于T。若j>T则签名无效;若1≤j≤T,验证:

R=Yjegsmodp

其中e=H(R‖m‖j),如果等式成立,签名sig(m)=(j,e,s)有效,否则,签名无效。

3安全性分析

3.1有效性

由于:

Yjegsmodp=Yjegαs′+βmodp=Yjegα(k-je′s2T-jj)+βmod

$\begin{array}{l} p = \\ Y^{j e} (g^{k})^{α} (g^{s_{j}^{2^{Τ - j}}})^{- α j e^{'}} g^{β} m o d p = Y^{j e} R^{'}^{α} g^{β} Y^{- α j α^{- 1} (e - j^{- 1} γ)} m o d p = \\ Y^{j e} R^{'}^{α} g^{β} Y^{γ - j e} m o d p = R^{α} g^{β} Y^{γ} m o d p = R m o d p \end{array}$

说明盲签名(m,j,(R,s))是一个有效的签名。

3.2不可伪造性

定理1 在随机预言模型和离散对数问题困难的假设下,所提前向安全盲签名方案对自适应选择消息攻击是存在性不可伪造的。

证明假设存在一个攻击者A以不可忽略的概率成功伪造部分盲签名,下面构造一个算法B解决离散对数问题。

对于给定的Z $_{p}^{*}$ 的生成元g和数y∈Z $_{p}^{*}$ ,为了能够计算x(1<x<p-1)满足y=gxmodp,算法B模拟挑战者与攻击者A进行交互,回答攻击者A的HZ随机预言询问和签名询问。具体交互过程如下:

系统设置:算法B生成系统公共参数params=(H,p,g,T,Y)发送给攻击者A,其中验证公钥设置为Y=y,即用x模拟s $_{0}^{2^{Τ}}$ 。

H询问:A至多可以做qH次H询问,B通过维护列表H-list响应A的H询问。A关于(Ri,mi,ji)(1≤i≤qH)的每一次询问,B首先检查列表H-list:

1) 如果在列表H-list中已经存在项(Ri,mi,ji,ei),B将ei返回给A作为(Ri,mi,ji)的H哈希值。

2) 否则,也就是A从来没做过(Ri,mi,ji)的H询问。这时,B随机选取ei∈RZ $_{q}^{*}$ ,将(Ri,mi,ji,ei)添加到列表H-list,并将H(Ri,mi,ji)=ei返回给A。

签名询问:A至多可以做qS次签名询问。关于A对消息m在时间段j的签名询问,B随机选取e,s(1<e,s<p-1),令R=Yjegsmodp,将(R,m,j,e)加到列表H-list。B将sig(m)=(j,R,s)返回给A。

输出:如果算法B没有终止,则A在没有做过(m*,j*)的签名询问的条件下,以一个不可忽略的概率对输入消息(m*,j*)Z输出一个有效签名sig(m*)=(j*,R,s)。根据Forking引理[12],通过对A哈希重放,B可以获得对消息(m*,j*)Z的两个有效签名(m*,j*,k,R,e1,s1)和(m*,j*,k,R,e2,s2),其中e1≠e2。因为有效签名满足R=Yjegsmodp,其中e=H(R‖m‖j),所以:

R=Yj*e1gs1modp,R=Yj*e2gs2modp

于是:

Yj*e1gs1=Yj*e2gs2modp

将Y = gs0 2T带入,得:

gs0 2Tj*e1 + s1 = gs0 2Tj*e2 + s2 modp

即

s0 2Tj*e1 + s1 = s0 2Tj*e2 + s2 mod(p-1)

所以

s0 2T = (j*)-1(e1 -e2 )-1(s2 -s1 )mod(p-1)

最终,B可以输出x=s $_{0}^{2^{Τ}}$ Z作为离散对数问题的解。

所以,在离散对数问题困难的假设下,所提前向安全盲签名方案对自适应选择消息攻击是存在性不可伪造的。

3.3盲性

首先,签名者在盲签名发布协议的执行过程中无法获得所签消息的任何相关信息。签名者在整个签名过程中只能获得数据(k,R′,e′,s′),其中R′,j由自己随机生成,s′是对e′的签名,而e′是用户经过盲化变换和哈希函数变换对原始消息m作用后的数据。在不知道盲化因子α,β,γ和哈希函数求逆困难的情况下,签名者得不到消息m的任何相关信息。

其次,在同一时段内,签名者无法将公布的签名与自己保留的中间结果建立联系,即签名者无法追踪消息的拥有者。事实上,给定一个有效签名(m,j,(e,s))和任一组第j时段的盲签名发布过程中签名者保留下来的中间变量(k,R′,e′,s′),签名者无法通过:

计算出3个随机数α,β,γ。因此,签名者无法确定公布的盲签名(m,j,(e,s))是由自己保留的哪一组中间结果(j,k,R′,e′,s′)生成的签名。

但是,前向安全盲签名方案的盲性也是有局限的。由于盲签名(m,j,(e,s))中含有时段编号j,如果恶意的签名者在每一时段只对一个消息签名,并记录下用户信息,则签名者就可以根据j追踪到消息的拥有者。

3.4前向安全性

在二次剩余求解困难的假设下,所提方案具有前向安全性。

假设攻击者获取了第j时段的密钥sj,试图通过等式sj=s $_{j - 1}^{2}$ mod(p-1)获得前一时段的密钥sj-1不可行,因为在不知道p-1的分解的情况下求解二次剩余是困难的。由方案的不可伪造性,攻击者在不知道密钥sj-1的情况下试图直接伪造第j-1时段的盲签名也是不可行的。

4性能分析

令TE、TI和TM分别表示一次模幂、模逆和模乘运算所需的时间。将新方案与Duc等人[4]方案、刘亚丽等人[8]方案和张席等人[9]方案在计算效率上进行比较,如表1所示,其中三个方案在密钥更新阶段计算量相同,都为TM,没有列出。可以看出本文方案比另三个方案减少模幂运算,计算效率更高。

5结语

基于离散对数和二次剩余计算难题设计了一个高效的前向安全盲签名方案,证明了其正确性并进行了安全和性能分析。新方案在随机预言机模型下是自适应选择消息攻击下存在不可伪造的,其安全性能够归约于离散对数困难假定;其前向安全性依赖于计算二次剩余的困难性。与目前已有的基于离散对数的前向安全盲签名方案相比,所提方案效率较高。

参考文献

[1]Chaum D.Blind signatures for untraceable payments[C]//Advancesin Cryptology-Crypto'82.New York:Plenum Press,1983:199-203.

[2]Anderson R.Two remarks on public-key cryptology[C]//Proceedingsof 4th ACM computer and Communications Security.New York:ACMPress,1997:151-160.

[3]Bellare M,Miner S.A Forward-Secure Digital Signature Scheme[C]//Advances in Cryptology-CRYPTO'99.LNCS 1666,Berlin:Springer-Verlag,1999:431-448.

[4]Duc D N,Cheon J H,Kim K.A Forward-secure Blind SignatureScheme Based on the Strong RSA assumption[C]//Proceedings of 5thInter-national Conference on Information and Communications Securi-ty.LNCS 2836,New York:Springer-Verlag,2003:11-21.

[5]Lai Y P,Chang C C.A Simple Forward Secure Blind SignatureScheme Based on Master Keys and Blind Signatures[C]//Proceedingsof 19th International Conference on Advanced Information Networkingand Applications(AINA'05).Washington DC:IEEE CS,2005:139-144.

[6]Koyama K.A Master Key for the RSA Public Key Cryptosys-tem[J].IEICE Transactions on Information and Systems,1982,J65-D(2):163-170.

[7]Chow S S M,Hui L C K,Yiu S M,et al.Forward-secure multisigna-ture and blind signature schemes[J].Applied Mathematics and Com-puta-tion,2005,168(2):895-908.

[8]刘亚丽,殷新春,孟纯煜.一种基于EIGamal体制的前向安全强盲签名方案[J].微电子学与计算机,2007,24(10):95-98.

前向安全数字签名篇7

密钥泄露问题是数字签名的主要问题之一,密钥泄露给数字签名带来的损失是致命的。针对密钥泄露问题,基于如何减少密钥泄露带来损失的目的,1997年,Anderson R首次提出了前向安全的概念[1]。前向安全的本质是对数字签名风险的控制,能有效地减少密钥泄露带来的损失,自然而然很快成为了信息安全领域研究的热点。环签名的概念[2]是在2001年的亚密会上,由Rivest,Shamir和Tauman在如何匿名泄漏秘密的背景下正式提出来了的。

因为环签名具有无条件匿名性这一特殊性质,使得其被深入研究。2005年,Joseph K Liu针对环签名的密钥泄漏问题,首次将前向安全特性和环签名结合,提出了前向安全的环签名和密钥封装的环签名。最近的研究表明,一部分前向安全数字签名密钥具有前向安全性,而签名并不真正具有前向安全性,并找到了不具备前向安全的根本原因是真正用于签名的私钥不是更新的私钥,而是一个常量私钥。如2009年,王玲玲等人提出标准模型下基于双线性对的前向安全环签名方案[3],2011年黄明军等人就指出其不具有前向安全性并给出了改进方案[4]。

前向安全数字签名通过更新私钥,将时间戳j嵌入到数字签名算法中,从而使得签名具有了前向安全性,但是却存在着另一个隐患:假设前向安全数字签名用于第j时段签名的私钥泄露了,那么攻击者就可以伪造第j时段及其以后任何时段的签名,因为私钥的泄露并不会被签名者及时发现,签名者也就无法采取相应的安全措施,并且攻击者在得到第j时段签名的私钥后,可以和签名者保持同样的私钥更新,这样整个签名体制就都暴露在攻击者的攻击之下,这种损失也是非常巨大的。由于前向安全数字签名无法保证数字签名的后向安全性,针对这个问题,早在2001年,Burmester M等人提出了强前向安全的概念[5]。

目前已有的强前向安全数字签名方案还不多,如2006年张波等人给出了一个强前向安全的代理签名方案[6]。2008年,阿力木江.艾莎等人在Abdalla M等的前向安全签名方案[7]的基础上,借助于单向散列链的单向性,构造了一种强前向安全数字签名方案[8]。因此对强前向安全数字签名的研究是非常具有实际意义的,本文在一个前向安全环签名算法的基础上,通过增加一个私钥,该私钥的更新是用来保证后向安全的,然后将具有前向安全的私钥和具有后向安全的私钥同时与环签名有效地结合,从而构造出了可验证的具有强前向安全性的环签名方案。

1可验证的强前向安全环签名方案

设环中有n个成员U={U1,U2,…,Un}(Ui对应身份为IDi)。

1) 系统设置算法SET-BP:

定义群G1为加法循环群,G2为乘法循环群(阶数均为素数N),双线性对e:G1×G1→G2,P是G1的生成元,选择单向哈希函数:

H:{0,1}*×{0,1}*×{0,1}*×{0,1}*×{0,1}*×G2→Z*N

签名密钥的有效期分为T个时段,计算g={P,P},发布系统公共参数{e,P,g,H,T}。

2) 初始密钥生成算法IKG-BP:

用户Ui任选xi,0,yi,0∈Z $_{Ν}^{*}$ ,计算:

Pi,1=x $_{i, 0}^{2^{Τ}}$ PmodN Pi,2=y $_{i, 0}^{2^{Τ}}$ PmodN

用户Ui初始私钥对为SKi,0=(xi,0,yi,0),相应公钥对为PKi=(Pi,1,Pi,2)。

3) 密钥进化算法KE-BP:系统在第j(1≤j≤T)时段,用户Ui使用初始私钥对SKi,0=(xi,0,yi,0),计算:

xi,j=x $_{i, 0}^{2^{j}}$ modN yi,j=y $_{i, 0}^{2^{Τ - j}}$ modN

生成第j时段的私钥对为SKi,j=(xi,j,yi,j),公钥对保持不变为PKi=(Pi,1,Pi,2)。

4) 环签名算法SIG-BP:

用户Us希望代表群体对消息m进行签名,系统进行到第j时段,用户Us执行如下操作:

a) 对于i∈{1,…,n}/s,选择秘密随机数ri∈Z $_{Ν}^{*}$ ,计算:

Ri=grimodN

b) 选择秘密随机数k,rs,μ∈Z $_{Ν}^{*}$ ,计算:

ω1=xs,jkμmodN ω2=ys,jkμmodN

$\begin{array}{l} h_{i} = Η (m ∥ ω_{1} ∥ ω_{2} ∥ Ι D_{i} ∥ Ρ Κ_{i} ∥ R_{i}) m o d Ν i \in {1, \dots, n} s \\ R_{s} = g^{r_{s}} \prod_{i \in {1, \dots, n} s} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{- h_{i}} m o d Ν \end{array}$

若Rs=1G2或Rs=Ri(s≠i),只需重新选择rs避免冲突。

c) 计算:

$\begin{array}{l} h_{s} = Η (m ∥ ω_{1} ∥ ω_{2} ∥ Ι D_{s} ∥ Ρ Κ_{s} ∥ R_{s}) m o d Ν \\ v = [\sum_{i = 1}^{n} r_{i} + (k^{- 2^{Τ - j} μ} + k^{- 2^{j} μ}) h_{s}] m o d Ν \end{array}$

d) 输出关于消息m的环签名:σ={ω1,ω2,v,R1,R2,…,Rn,j}。

5) 签名验证算法VER-BP:

接收方收到关于消息m的环签名σ={ω1,ω2,v,R1,R2,…,Rn,j},根据公钥集PK={PK1,PK2,…,PKn},执行下列算法:

a) 计算公式:

hi=H(m‖ω1‖ω2‖IDi‖PKi‖Ri)modN i∈{1,…,n}

b) 对签名进行验证,计算等式:

$\prod_{i = 1}^{n} R_{i} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{h_{i}} m o d Ν = g^{v} m o d Ν$

若等式成立则接受签名,否则拒绝。

6) 签名者验证算法:

签名者Us将自己当初选择的秘密随机数rs发送给验证者并告诉验证者自己为用户Us,验证者收到参数后,根据环签名σ={ω1,ω2,v,R1,R2,…,Rn,j},在公钥集PK={PK1,PK2,…,PKn}找到用户Us的公钥PKs,执行下列算法:

a) 计算公式:

hs=H(m‖ω1‖ω2‖IDs‖PKs‖Rs)modN

b) 对签名者进行验证,计算等式:

$[e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{s, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{s, 2})^{h_{s}}] g^{r_{s}} \prod_{i \in {1, \dots, n} s} R_{i} m o d Ν = g^{v} m o d Ν$

若等式成立,根据哈希函数的抗碰撞攻击性质可知,hs有唯一的IDs与其对应,因此验证者就可确定身份为IDs用户为真实签名者,否则,签名者为冒充者。

2安全性分析

1) 正确性

$\begin{array}{l} \prod_{i = 1}^{n} R_{i} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{h_{i}} m o d Ν \\ = [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{s, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{s, 2})]^{h_{s}} \prod_{i = 1}^{n} e (Ρ, Ρ)^{r_{i}} m o d Ν \\ = e ([\sum_{i = 1}^{n} r_{i} + (k^{- 2^{Τ - j} μ} + k^{- 2^{j} μ}) h_{s}] Ρ, Ρ) m o d Ν \\ = e (v Ρ, Ρ) m o d Ν \\ = g^{v} m o d Ν \end{array}$

2) 强前向安全性

因为私钥xs,j=x $_{s, j - 1}^{2}$ modN具有前向安全性,另一个私钥ys,j=y $_{s, j + 1}^{2}$ modN具有后向安全性,私钥对SKi,j={xi,j,yi,j}具有强前向安全性,只要将具有强前向安全性的私钥对SKi,j={xi,j,yi,j}真正和环签名结合起来,就可以保证环签名方案具有强前向安全性。从公式ω1=xs,jkμmodN和ω2=ys,jkμmodN中可以看出本方案的实际签名私钥不是常量,而是随时段j不断更新的私钥对SKs,j={xs,j,ys,j},从公式 $v = [\sum_{i = 1}^{n} r_{i} + (k^{- 2^{Τ - j} μ} + k^{- 2^{j} μ}) h_{s}] m o d Ν$ 中可以发现时段j的信息被加入到签名中,说明私钥对SKi,j={xi,j,yi,j}的演进和环签名真正结合起来,因此本方案具有强前向安全性,强前向安全性是基于模平方剩余难题的。

3) 无条件匿名性

从本方案的环签名σ={ω1,ω2,v,R1,R2,…,Rn,j}来看,任何成员的地位是一样的,无法确定具体签名人。从环签名算法来看,对于i∈{1,…,n}s, 在公式Ri=grimodN中,因为ri是随机选取的,所以Ri是随机的。而公式ω1=xs,jkμmodN中的ω1和公式ω2=ys,jkμmodN中的ω2均与随机数μ相关,公式 $R_{s} = g^{r_{s}} \prod_{i \in {1, \dots, n} s} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{- h_{i}} m o d Ν$ 中的Rs和随机数rs相关,公式 $v = [\sum_{i = 1}^{n} r_{i} + (k^{- 2^{Τ - j} μ} + k^{- 2^{j} μ}) h_{s}] m o d Ν$ 中的v和随机数μ相关,因此ω1,ω2,Rs,v可以看作是随机的,攻击者得不到签名者Us的任何信息,猜对真正签名者的概率为1/n,本方案满足无条件匿名性。

4) 可验证性

签名者Us向验证者提交参数rs,实际上是将环签名σ={ω1,ω2,v,R1,R2,…,Rn,j}转化成签名为σ′={ω1,ω2,v,R1,…,rs,…,Rn,j},公钥为PKs的个人签名。

假设攻击者为用户Uk(k∈{1,…,n},k≠s)(或知道用户Uk的一切信息),想将Us的环签名σ={ω1,ω2,v,R1,R2,…,Rn,j}据为己有,则攻击者选择一个随机值rk∈Z $_{Ν}^{*}$ 发送给验证者,并告诉验证者自己为用户Us,验证者收到参数后,根据Us的环签名σ={ω1,ω2,v,R1,R2,…,Rn,j},在公钥集PK={PK1,PK2,…,PKn}找到用户Us的公钥PKs,执行下列算法:

a) 计算公式:

hs=H(m‖ω1‖ω2‖IDs‖PKs‖Rs)modN

b) 计算等式:

$[e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{s, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{s, 2})^{h_{s}}] g^{r_{s}} \prod_{i \in {1, \dots, n} s} R_{i}^{- 1} m o d Ν = g^{v} m o d Ν$

要使得上述等式成立,攻击者选择的随机值rk必须满足等式:

$g^{r_{k}} = e (v Ρ, Ρ) [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{s, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{s, 2})]^{- h_{s}} \prod_{i \in {1, \dots, n} s} R_{i}^{- 1} m o d Ν$

而参数{v,ω1,ω2,Ri(i∈{1,…,n}s),PKs,hs}都已经相应确定,要求出满足条件的rk是基于一般离散对数困难问题的。因此新方案具有可验证性,任何攻击者想将环签名据为己有是不可行的。

5) 不可伪造性

下面通过一个定理,来证明改进方案可抵抗自适应选择消息攻击下的存在性伪造。

定理1 在随机预言机模型下,设A是自适应选择消息和身份攻击下的超级攻击者,如果在时间t内,至多做qU次生成用户询问,qH次H询问,qPK次公钥询问,qSK次私钥询问,qσ次签名询问后,能以不可忽略的概率ε攻破改进后的方案,那么存在一个算法B,在时间t′≤2(t+qUtU+qHtH+qPKtPK+qSKtSK+qσtσ)内解决DL问题,其中tU、tH、tPK、tSK、tσ分别表示一次生成用户询问、H询问、公钥询问、私钥询问和签名询问所用的时间。

证明令B是加法循环群G1上的DL问题解决者,给定一个DL问题的随机实例(P,X=bPmodN),B的目标是计算出b。A的攻击的目标身份是ID*,最终他能在时间t内,以不可忽略的概率ε,伪造出关于消息m的合法环签名σ={ω1,ω2,v,R1,R2,…,Rn,j}。下面将证明B可利用A的能力,在t′时间内以不可忽略的概率ε′解决给定的DL问题。

建立系统参数:B把系统参数{e,P,g,H,T}发送给A。

攻击:B把哈希函数H作为随机预言机,A可以作生成用户询问、哈希H询问、公钥询问、私钥询问和签名询问,假设A的询问都是不同的。模拟机询问如下:

生成用户询问:B保持一个列表L1={IDi,SKi,0=(xi,0,yi,0)},初始为空,设IDi是A的第i次询问。当收到A的生成用户询问,B判断IDi=ID*是否成立,若IDi=ID*,则终止,若IDi≠ID*,则查表L1,若IDi在表L1中,则返回相应的(IDi,SKi,0=(xi,0,yi,0))给A,否则随机选择xi,0,yi,0∈Z $_{Ν}^{*}$ (xi,0,yi,0以前未出现在表L1中),返回(IDi,SKi,0=(xi,0,yi,0))给A并将其添加到表L1中(i∈{1,2,…,qU})。

私钥询问:假设当前前向安全环签名时段为第j时段,B保持一个列表L2={IDi,SKi,j=(xi,j,yi,j)},初始为空。当收到A的私钥询问,B判断IDi=ID*是否成立,若IDi=ID*,则终止,若IDi≠ID*,则查表L2,若IDi在表L2中,则返回相应的{IDi,SKi,j=(xi,j,yi,j)}给A,否则查表L1,得到相应的SKi,0=(xi,0,yi,0),计算xi,j=x $_{i, 0}^{2^{j}}$ modN,yi,j=y $_{i, 0}^{2^{Τ - j}}$ modN,返回{IDi,SKi,j=(xi,j,yi,j)}给A并将其添加到表L2中。

公钥询问:B保持一个列表L3={IDi,PKi=(Pi,1,Pi,2)},初始为空。当收到A的公钥询问,B判断IDi=ID*是否成立,若IDi=ID*,则令PKID*=(PID*,1,PID*,2),其中PID*,1=PID*,2=X=aPmodN,将(ID*,PKID*=(PID*,1,PID*,2))返回给A并将其添加到表L3中,若IDi≠ID*,B查表L1获得相应的SKi,0=(xi,0,yi,0),计算Pi,1=x $_{i, 0}^{2^{Τ}}$ PmodN,Pi,2=y $_{i, 0}^{2^{Τ}}$ PmodN,返回(IDi,PKi=(Pi,1,Pi,2))给A,并将其添加到表L3中。

H询问:B保持一个列表L4={IDi,hi},初始为空。当收到A的H询问,B查表L4,若IDi在表L4中,返回相应的hi给A,否则,随机选择hi∈Z $_{Ν}^{*}$ (hi以前未出现在表L4中),返回(IDi,hi)给A,并将其添加到表L4中。

签名询问:当B收到A的签名询问时,B先从表L3中获得成员的公钥,接下来按如下步骤回答:

a) 任选s∈{1,2,…,n},对任意的i∈{1,2,…,n}s,随机选取ri∈Z $_{Ν}^{*}$ ,计算公式:

Ri=grimodN

任选ω1,ω2∈Z $_{Ν}^{*}$ ,计算公式:

hi=H(m‖ω1‖ω2‖IDi‖PKi‖Ri)modN(i∈{1,…,n}s)

b) 任选v,hs∈Z $_{Ν}^{*}$ ,计算:

$R_{s} = e ((v - \sum_{i \in {1, \dots, n} s} r_{i}) Ρ, Ρ) \prod_{i = 1}^{n} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{- h_{i}}$

若Rs=1G2或Rs=Ri(s≠i),只需重新选择v避免冲突。计算公式:

hs=H(m‖ω1‖ω2‖IDs‖PKs‖Rs)modN

c) 输出环签名σ={ω1,ω2,v,R1,R2,…,Rn,j}。

伪造:A能在t′时间内以不可忽略的概率ε′输出用户身份为ID*,关于消息m的有效环签名σ={ω1,ω2,v,R1,R2,…,Rn,j},由分叉引理可知,A能够生成消息m另一个有效环签名σ′={ω1,ω2,v′,R1,R2,…,Rn,j}。

设PKs=PKID*=(PID*,1,PID*,2)=(bPmodN,bPmodN),其中hi=h′i(i∈{1,…,n}s),hs≠h′s。这样就得到了两个有效的环签名验证等式:

gv′mod $Ν = \prod_{i = 1}^{n} R_{i} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{h_{i} ´} m o d Ν$

由第一个环签名验证等式可得:

$\begin{array}{l} g^{v} m o d Ν = R_{s} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{Ι D^{*}, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{Ι D^{*}, 2})]^{h_{s}} \times \\ \sum_{i \in {1, \dots, n} s} R_{i} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{h_{i}} m o d Ν \end{array}$

由第二个环签名验证等式可得:

$\begin{array}{l} g^{v^{'}} m o d Ν = R_{s} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{Ι D^{*}, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{Ι D^{*}, 2})]^{h^{'}_{s}} \times \\ \sum_{i \in {1, \dots, n} s} R_{i} [e (ω_{1}^{- 2^{Τ - j}} Ρ, Ρ_{i, 1}) e (ω_{2}^{- 2^{j}} Ρ, Ρ_{i, 2})]^{h_{i} ´} m o d Ν \end{array}$

将上面两个公式两边相除得:

这样B利用A就求出了椭圆曲线上DL问题的一个解,出现矛盾。由此得出该方案在随机预言机模型下可抵抗敌手A的自适应选择消息攻击下的存在性伪造。

3结语

基于强前向安全性的思想,通过增加一个私钥,该私钥的更新是后向安全的,然后将具有前向安全的私钥和具有后向安全的私钥同时与环签名有效地结合,提出了一个可验证的具有强前向安全性的环签名方案。该签名的效率还有待进一步提高,下一阶段的研究重点是优化环签名算法,将强前向安全性与高效的环签名算法结合,从而构造出更高效和安全的可验证的前向安全环签名方案。

参考文献

[1]Anderson R.Two remarks on public key cryptology[R].Invited lec-ture,ACM-CCS’97,1997.

[2]Rivest R L,Shamir A,Tauman Y.How to leak a secret[C]//Ad-vances in Cryptology-Asiacrypt 2001,LNCS:Berlin,2001:552-565.

[3]王玲玲,张国印,马春光.标准模型下基于双线性对的前向安全环签名方案[J].电子与信息学报,2009,31(2):448-452.

[4]黄明军,杜伟章.一种改进的前向安全环签名方案[J].计算机工程,2011,37(24):106-108.

[5]Burmester M,Chrissikopoulos V.Strong forward security[C]//IFIP-SEC2001 Conference.Kluwer Academics Publishers,2001:109-119.

[6]张波,徐秋亮.一个强前向安全的代理签名方案[J].计算机工程与应用,2006,42(9):109-110.

[7]Abdalla M,Reyzin L.New forward-secure digital signature scheme[C]//Advances in Cryptology-CRYPTO’99,1999:431-448.

【前向安全数字签名】推荐阅读：

前向安全05-19

数字档案安全07-16

数字档案信息安全08-08