具有强前向安全性的动态门限签名方案

程亚歌，胡明生，公 备，王利朋，徐二锋

1.郑州师范学院 信息科学与技术学院，郑州450044

2.北京工业大学 计算机学院，北京100124

1 引言

在如今互联网处于爆炸式发展时期，它在给人们带来便利的同时，也存在着隐私泄露、信息被篡改的事实。网络的飞速发展促使了数字签名技术的广泛应用，然而数字签名技术存在的最大挑战来自于私钥泄露带来的签名被篡改、伪造导致的信息失实的严重后果。在这样的大背景下前向安全的思想应运而生。

1997 年Anderson[1]首次在欧洲的密码学大会上提出前向安全的概念，其核心思想在于密钥的更新。在此基础上，Bellare和Miner[2]于1999年基于One-Schnorr和Fiat-Shamir 认证方案，提出了前向安全性理论，并首次通过算法实现了前向安全的数字签名方案。1997 年Anderson 对前向安全方案进行总结提出了两种安全性[3]：前向安全性和后向安全性。2001 年Mike Burmester 等人提出了强前向安全性的定义[4]，即一个签名体制在当前密钥泄露时，不会对在此之前和之后的签名造成影响。它的提出极大地提升了签名效率，不必因每次密钥泄露就重新构建新的密钥系统。强前向安全的这一特性极大地提高了签名系统的安全性，因此在近20 年的签名方案研究历程中被众多国内外研究者追捧。

鉴于强前向安全性对于数字签名安全性的重要性，国内外学者致力于这一方面已做了大量的工作。文献[5]提出了一种前向安全数字签名方案的分析及改进，该方案借助单向散列链技术，对刘亚丽等人方案进行了改进，使方案满足后向安全。文献[6]引入反向安全监测，采用哈希链技术，使方案满足了后向安全性，但并没有对密钥泄露之后采取措施，且方案耗时较长。文献[7]提出一种强前向安全的数字签名方案，该方案基于Guillou-Quisquater 签名体制和Rabin 密码体制，并引入双密钥，在签名生成过程中需要计算杂凑函数、双密钥等其他信息，计算复杂。文献[8]提出基于离散对数的双向安全签名方案，该方案引入正向和逆向的密钥算法，同时利用哈希进行盲化，设计简单，效率较高，但该方案不能抵抗共谋攻击。文献[9]利用哈希链和秘密共享技术相结合，提出前后向安全的群签名方案，该方案需要群管理员对成员进行统一管理，权利过于集中，容易造成系统拥塞，效率低等问题。

文献[10]提出一个前向和后向安全的数字签名方案，该方案基于强RSA假设，在密钥演化过程中加入后向元素，使方案满足前后向安全，但该方案在密钥生成和更新阶段计算量较大处理速度较慢。文献[11]基于双线性对算法，将双私钥更新方法与环签名有效地结合，提出了可验证的强前向安全的环签名方案，方案在签名及验证过程中均需双线性对计算，使得签名效率较低。文献[12]提出一种前向后向安全的数字签名方案，该方案利用多变量公钥密码理论和零知识证明技术构造了基于身份识别的改进模型的密钥更新算法，方案需计算大量多项式，而多项式阶数较高导致计算复杂度高、效率低。文献[13]提出了一种基于WEB的数字签名方案，该方案采用基于证据与证据相结合的检测方法，保证了信息的安全性和完整性，但该方案构造复杂，算法执行效率低。以上方案均满足前后向安全，但在执行效率方面有待提高。

文献[14]提出了基于可验证随机数的前后向安全群签名方案，方案需可信管理中心，缺乏成员对群管理中心的反向监督机制，管理中心很容易成为整个签名系统的安全隐患。文献[15]提出了一种具有双向安全性的基于身份的短签名方案，该方案算法简单，但没有考虑成员加入和退出问题。文献[16]提出了基于中国剩余定理的签名方案，该方案无需可信中心，解决了成员撤销问题，但该方案不满足后向安全。为解决以上问题，本文在已有研究的基础上，提出一种具有强前向安全性的动态门限签名方案。方案基于中国剩余定理，无需可信中心，避免了可信中心权威欺诈等行为，定期更新成员私钥，使方案满足强前向安全性，同时解决了成员加入和退出等问题。

2 背景知识

2.1 前向安全性介绍

前向安全性理论[2]是指将整个签名时间划分为T个周期，在整个签名时间内公钥持续保持不变，成员私钥则随着签名周期的递进不断更新，在每个周期内使用成员当前周期的私钥产生签名。当某个周期内某成员私钥泄露时，由于私钥的动态更新，恶意攻击者无法利用当前周期的私钥修改该周期之前的签名信息，即当前周期私钥对前期签名无效，因此在当前周期之前产生的签名是安全有效的。前向安全性保证了前期签名信息的安全。

前向安全性理论具体实施过程如下：

（1）Pi( )i=1,2,…,n 将整个签名的有效期划分为T 个周期[ 0,T ]。

（2）在整个签名时间内公钥PK 不变，私钥SK 随着时间周期的递进而动态更新。

（3）在第j 个周期时，成员Pi( )i=1,2,…,n 计算SKij=h( S Ki(j-1))，其中h 是一个单向函数。

（4）Pi计算出SKij后立即删除SKi(j-1)。这样即使有某攻击者获得了成员Pi第j 个周期的私钥SKi(j-1)，也不能获得该周期之前的私钥SKi0,SKi1,…,SKi(j-1)的任何信息。私钥更新示意图如图1所示。

图1 私钥更新示意图

强前向安全性[4]是指一个签名体制当前密钥的泄露不会对之前和之后的签名产生影响。主要包含两方面的安全[3]：（1）前向安全，是指当前周期的密钥泄露，对在此周期之前完成的签名信息不会产生威胁，即保证前期签名信息的安全。（2）后向安全，是指当前周期的密钥泄露，对在此周期之后即将生成的密钥信息没有影响，他人无法根据当前密钥伪造之后周期的密钥信息，也无法伪造签名，即保证未来周期的成员密钥及签名信息安全。

2.2 Asmuth-Bloom秘密共享方案

Asmuth-Bloom 秘 密 共 享 方 案[17]，是 由Asmuth 和Bloom 在1983 年时提出，方案主要包含以下三个步骤：初始化、秘密分发及秘密恢复。具体执行过程如下：

（1）初始化。假设DC 是秘密分发者，P={P1,P2,…,Pn}是n 个成员组成的集合，门限值为t ，需要共享的秘密为S。秘密分发者DC 选择大素数q( )q ＞S ，以及严格递增正整数序列d={ }d1,d2,…,dn，且q、d必须满足如下条件：

（2）秘密分发。秘密分发者DC 随机选择整数A，使 其 满 足：；并计算：z=S+Aq，zi=z mod di(i=1,2,…,n) ，然后将( )zi，di发送给Pi(i=1,2,…,n)，作为Pi的秘密份额。

（3）秘密恢复。任意成员可以通过相互之间交换秘密份额恢复秘密S。任意选取t 个成员作为恢复秘密的一组成员，成员之间通过相互交换秘密后，任意成员Qi都可以建立如下同余方程组来恢复秘密：

z ≡zimod di

根据中国剩余定理，该方程组有且只有唯一解：

这里：

因此，可求出S=z-Aq，也即S=z mod q。

2.3 离散对数难题

本文所涉及的难题为离散对数难题，是指给定有限域GF( p )，当模p 有原根时，设g 为模的一个原根（即有限循环群的生成元），任给元素y ∈，求解唯一的x，满足1 ≤x ＜p-1，使得：称为以p 为模，以g 为底y 的离散对数。

这里对于已知的g 和y 要求解出唯一的x 属于离散对数难题。

3 本文方案

本文基于中国剩余定理提出了一种具有强前向安全性的动态门限签名方案。本文方案无需可信中心，在保持组公钥和组私钥不变的前提下，定期更新成员私钥，使其具有强前向安全性，且允许成员加入和退出。

具有强前向安全性的门限签名方案架构图如图2所示。

如图2所示，具有强前向安全的动态门限签名包括：产生签名、私钥更新、成员加入和撤销三个方面的内容。

3.1 产生签名

为方便理解，对本文定义符号解释如表1所示。

图2 强前向安全门限签名方案架构图

表1 符号说明

（1）系统初始化。Q={ }

Q1,Q2,…,Qn是n 个成员的集合，p 和q 是两个大素数，满足,d={d1,d2,…,dn}是一组严格单调递增的正整数序列，q 和d 满足Asmuth-Bloom 秘密共享方案，t 为门限值，有限域GF( p )上的生成元为g ，待签名消息为M ，为最小的t 个di之积，公开n,t,g,p,q,d 以及N 。

（2）产生秘密份额。成员Qi随机选取子秘密α0i和整数，满足如下条件：

成员Qi为其他成员计算秘密份额：

（3）Qi计算验证信息。

（4）产生成员私钥及组密钥。Qj收到其他t-1 个成员发送来的秘密份额，根据其广播的消息验证收到消息的正确性，以确保信息未被篡改：

如果上述两个等式成立，则证明收到的消息正确未被篡改，此时Qj计算个人私钥：

则成员Qj的个人公钥为：

根据每个成员选取的子秘密α0

i ，产生组私钥：

则组公钥为：

（5）产生签名。任意t 个成员协作产生签名。首先由每个成员产生部分签名，然后由t 个部分签名合成消息M 的签名。每个成员Qi选取随机数xi∈Zp，计算：

广播信息gxi，Qj收到zi后，计算：

Qi计算部分签名R0i：

（6）合成签名。签名合成者收到t 个成员的部分签名后，合成签名R：

3.2 私钥更新

成员私钥生成后，攻击者只要有足够时间便可窃取该成员私钥信息，进而获得t 个成员私钥，并伪造签名，这种攻击机制称为移动攻击。为了防止移动攻击，成员需要定期更新自己的私钥。私钥的更新必须确保之前的签名仍然有效，因此必须保证更新过程不更改组公钥信息。

私钥更新确保即使攻击者获得了T 时刻的成员私钥，也无法获得T-1 时刻的私钥，而且也不能伪造T+1时刻的私钥，使得攻击者即使知晓了T 时刻的成员私钥，也无法修改之前的签名，更不能伪造之后的签名。本文方案提出的私钥更新机制具有强前向安全性，能够有效抵御移动攻击，具有较高的安全性。

设更新周期为T ，则详细的更新算法步骤如下：

（1）成员Qi随机选取整数，满足初始条件。

（2）成员Qi计算更新因子：

（3）成员Qi计算验证信息

（4）成员Qj收到Qi发送的信息，以及，根据广播信息，由以下两个等式验证ωTi和的正确性：

（5）Qj在T-2 时段的私钥为，则T 时段的私钥为：

更新产生的新私钥，仍然可以按照签名过程进行签名和验证。更新过程中组公钥不变，因此更新前的签名依然有效。

3.3 成员加入和撤销

3.3.1 成员加入

当有新成员加入时，任意t 个老成员相互协作产生伪私钥，并发送给新成员，新成员收到t 份伪私钥后计算自己的私钥。假设某一时刻有新成员Qn+1加入，其加入过程的算法如下：

（1）选择模数dn+1。新成员Qn+1选取模数dn+1并公开，使其满足Asmuth-Bloom秘密共享方案。

（2）计算伪私钥。任意t 个老成员协助新加入成员Qn+1计算伪私钥。 Qi随机选取t 个随机数λij∈Zp，并将λij发送给Qj，Qj收到λij后由以下等式计算λ'j：

然后由每个老成员Qj计算伪私钥：

并将H'j发送给Qn+1。

（3）新成员计算自己的私钥。当Qn+1收到来自其他t 个老成员的伪私钥H'i后，计算自己的私钥：

在这个过程中组公钥、组私钥以及其他成员的私钥均未发生变化，因此，对整个签名过程没有任何影响。

3.3.2 成员撤销

成员的撤销必须遵循在保持组公钥和组私钥不变的前提下，重新构建其余成员的秘密份额，并更新其私钥，使被删除成员的秘密份额及私钥无效，从而无法参与后期的签名过程。在后期的更新以及签名阶段，其他成员不再接受被删除成员分发的信息，也不再为被删除成员分发信息。假设在第T 个周期有成员Qk决定离开，其他n-1 个成员重新构建自己的秘密份额：

（1）成员Qi( i ≠k )随机选取，并为其他n-2 个成员计算秘密份额：

（2）Qi计算并验证信息。根据收到的其他成员发送的秘密份额和广播信息，Qi计算验证收到的来自其他成员发送的信息的正确性。

（3）其他成员计算自己的新私钥。Qj收到ωT′i和φT′ij后，由以下验证信息其正确性：

若等式成立，则Qj重新计算自己的新私钥：

至此，其他n-1 个成员的私钥已重新构建，对于要撤销的成员Qk不再执行此过程，其秘密份额失效，成员Qk被删除。

在现有的大多数门限签名方案中，只考虑了成员加入，没有考虑成员退出问题，允许成员退出的算法，大都依赖可信中心，由可信中心直接删除，不能排除可信中心权威欺诈的可能性。本文方案在没有可信中心的前提下，确保成员退出时组公钥、组私钥保持不变，仍可用于签名及验证，降低了系统更新代价。

4 方案分析

4.1 正确性分析

定理1 成员Qj收到其他成员Qi( i=1,2,…,n,i ≠j )发送的子秘密和整数时，鉴别信息来源的真实性，确保信息未被篡改，即证明验证等式（7）成立。

证明等式（7）成立，则证明该信息真实可信，其他成员接受Qi发送的信息。

定理2 成员Qj收到其他n-1 个成员发来的秘密份额后，鉴别秘密份额的真实性，确保秘密份额来源可信且未被篡改，即证明验证等式（8）成立。

证明 由式（5）、（6），可得：

原式得证，等式（8）成立，则证明成员Qj收到的其他成员发送的秘密份额真实可信，接受此信息。

如果成员Qi提供了真实的信息，则式（7）、（8）一定成立。反之，如果验证结果表明等式不成立，则说明成员没有提供真实的信息，则该成员不可信，不接受此成员发送的信息。

定理3 由部分签名式（11）合成的最终签名式（12），需由签名验证公式（13）验证签名是否成立，即证明等式（13）成立。

证明 由式（3）和（9），成员私钥为：

令：

则：

根据中国剩余定理，解如下同余方程组：

可得唯一解：

因此：

令：

则：

当t ＞2 时，根据文献[18]可知：

由式（11）、（12）有：

因此：

则有：

故有：

经验证，等式（13）成立，则证明签名信息真实有效，由部分签名合成的最终签名为有效签名，接受该签名。

定理4 私钥动态更新后，新私钥可以通过3.1 节产生签名过程产生签名，且该签名依然能够通过签名验证等式（13）的验证，即证明由新私钥产生的签名有效。

证明

令：

则：

根据中国剩余定理解同余式方程组：

得唯一解：

令：

则：

由式（1）、（2）和（14）可知：

由文献[18]可知，当t ＞2 时有：

根据式（12）、（13）有：

由式（21）有：

所以，有：

经验证等式（13）成立，故由更新后的新私钥产生的签名有效。

定理5 在新成员加入时，由老成员协作为新加入成员产生的新私钥式（17），需由原私钥式（15）验证新成员私钥的有效性。

证明

定理6 当有成员退出时，其他成员更新自己的私钥，更新后的新私钥式（19）依然有效，即验证公式（19）成立。

成员退出时，其他成员更新自己的私钥，即将退出成员不再执行此过程，整个过程类似于更新过程。证明过程同定理4，在此不再展开。

4.2 安全性分析

本文设计的具有强前向安全性的( )t,n 动态门限签名方案，攻击者即使窃取了某一周期的私钥也无法伪造在此之前和之后的所有签名。根据中国剩余定理，至少需要t 个同余方程组才能求解方程组，因此只有达到门限值即t 个成员联合才能完成签名，少于t 个成员的联合攻击属于无效攻击。

4.2.1 前向安全性分析

假设某攻击者窃取了第T 周期成员Qj的私钥HTj=试图计算，则攻击者必须先计算，而：

所以有：则攻击者需要在有限时间内，即第T 周期内同时获得所有成员前T 个周期的随机数以及所有成员的初始秘密份额，而是有成员秘密选取的攻击者不可能获得，成员初始秘密份额中的随机数由成员秘密选取并保存攻击者也不可能知晓。

因此，攻击者无法根据T 时段的私钥计算得到T周期之前的成员私钥，方案具有前向安全性。

4.2.2 后向安全性分析

若攻击者想由T 时段的私钥伪造T 时间段之后的成员私钥也是不能实现的。由成员私钥可知，攻击者若要由当前私钥伪造T周期之后的私钥，假设攻击者要伪造第T+1 周期的私钥则攻击者必须先计算和，而由上一段的分析可知，攻击者不可能在有效时间内计算得到T 周期之前的私钥，因此攻击者无法获得，同时由上一段的分析，攻击者也无法通过计算得到成员T+1 周期的秘密份额

因此，攻击者不可能获得第T+1 周期的私钥，不可能伪造T+1 周期之后的所有成员私钥。故攻击者不能在有限的周期内获得当前周期之后的成员私钥，即方案具有后向安全性。

4.2.3 不可伪造性分析

不可伪造性是指任意恶意攻击者以及合法成员均不能伪造其他成员生成签名信息。本文方案具有强前向安全性的门限签名，无需可信中心，成员协作产生签名，可以有效地避免可信中心的权威欺诈等问题。为方便下文描述，假设恶意攻击者为Q'i，合法成员为Qi。

若恶意攻击者Q'i 想替代合法成员Qi伪造成员秘密选取的秘密数。则恶意攻击者Q'i随机选取秘密数并保存，由于所以，在计算组私钥的过程中必然会有=SKT，由于每个成员均保存了一份，当组成员发现成员Q'

i 发送的信息有误，则不接受其发送的信息，Q'i无法参与到签名算法系统中，因此攻击者Q'i 无法伪造成员Qi的秘密信息。

若恶意攻击者想通过伪造秘密份额从而伪造成员私钥，由于秘密份额q mod dj，在验证阶段当其他成员收到Q'

另外，恶意攻击者Q'i 可能截获其他n-1 个成员发送的信息，想通过计算成员私钥，由于每个成员各自保留了攻击者无法获得。而攻击者可能截获和，试图通过和计算出和从而得到，然而通过和求解和是离散对数难题，攻击者无法通过求解得到。

由以上分析可知，本文方案具有不可伪造性。

5 性能分析

5.1 效率分析

本文设计的具有强前向安全性的动态门限签名方案，其计算难度等价于求解离散对数难题。

为方便描述，本文定义符号表示不同运算的计算复杂度，如表2。表3 是本文方案与文献[7，10-11]的计算复杂度对比表。计算复杂度分为时间复杂度和空间复杂度，本文主要从时间复杂度层面展开分析。以上方案中涉及的运算主要有双线性对、Hash 运算、模幂运算、模逆运算、模乘运算、模加和模减等。鉴于模加、模减与模乘法运算与其他运算相比计算量较小可忽略不计，因此不予进行分析。

本文将在签名生成、签名验证和密钥更新三个阶段展开，对本文方案和文献[7，10-11]在时间计算复杂度上进行对比分析。其对比结果如表3所示。

表3是本文基于中国剩余定理的强前向签名算法，与其他具有强前向安全的签名算法时间计算复杂度对比结果。以上方案都具有强前向安全性，通过对比发现，本文方案的时间计算复杂度明显低于其他几个方案。

文献[7]引入双密钥，在签名生成过程中需要计算杂凑函数、双密钥等信息，从而增加了时间消耗，计算成本较高。

文献[10]基于强RSA假设，在方案中引入伪随机函数：种子seed和Hash函数来生成素数，在私钥演化过程中私钥由两部分的乘积组成，需要分别计算部分私钥然后合成私钥，这个过程大大增加了时间开销，计算复杂度较高。

文献[11]利用双线性对性质构造了前后向安全的签名算法，方案在产生签名算法时引入双线性对运算和哈希计算，在验证过程需经两次双线性运算进行验证，大大增加了系统计算量，执行效率较低。

上述几个方案中涉及的算法为：e、m、u、r 、h，在相同操作系统下运行一万次得到这四个算法的时间计算复杂度大小顺序为：e ＞m ＞u ＞h ＞r，也即双线性对计算复杂度最高，接下来依次为模幂计算、模逆计算、哈希计算和模乘运算。本文方案主要涉及模幂、模逆和模乘运算。

由表3 可知，文献[10]在这三个阶段的计算复杂度都高于本文方案。文献[7]和文献[11]在更新阶段优于本文，但是在签名生成和验证阶段的计算复杂度均高于本文方案。文献[7]需哈希运算和大量模幂运算，使得执行效率较低。文献[11]基于双线性对运算，而双线性对运算的计算复杂度明显高于模幂和模逆运算。

由以上分析，显然本文方案所涉及的运算较其他几个方案算法更简单，计算复杂度更低、效率更高。

5.2 仿真实验

该仿真实验的环境为：64位Window 10操作系统，MyEclipse2015 系统，CPU 为英特尔酷睿i5-8300H 处理器，主频2.3 GHz，内存8 GB。将本文方案与文献[11]在签名生成和验证阶段的时间开销进行仿真实验。结果显示如图3。

由图3 可知，本文方案和文献[11]随着成员数n 的增加耗时均成上升趋势，这是因为整个签名过程与成员n 成正相关的关系。从实验数据看，文献[11]较本文方案耗时更多，这是由于文献[11]在签名生成和验证阶段均需进行双线性对运算，该运算计算复杂度相对较高。

由图4 可知，本文效率与方案[11]相比提升了80%左右，很大程度上降低了签名系统时间开销，执行效率较高。

表2 时间复杂度表示符号

表3 签名方案计算复杂度对比

图3 成员数n 与时间开销关系图

图4 验证效率与成员数n 的关系图

6 结语

本文设计的具有强前向安全的动态门限签名方案，无可信中心，由集合内部成员相互协作产生部分签名并合成签名，同时实现了成员之间相互验证功能。在组公钥不变的前提下解决了成员加入和退出问题。周期性更新成员私钥，使其具有强前向安全性。方案基于中国剩余定理与其他方案相比具有计算量小、效率高的优点。