一种基于三次剩余的身份签名体制

摘要

本发明提供了一种基于三次剩余的身份签名体制，其中包括参数建立方法和设备、签名生成方法和设备、以及签名验证方法和设备，该参数建立方法包括：选取第一素数p和第二素数q；将第一素数p和第二素数q相乘，所得乘积作为第一参数N；选取第二参数a，使得所述第二参数a为模q的三次非剩余；计算第三参数η和第四参数λ；选取第一哈希函数h

说明书

技术领域

本发明涉及计算机安全领域，具体地，涉及一种用于基于身份的签名体制(简称为身份签名体制)的参数建立方法和设备、签名生成方法和设备以及签名验证方法和设备。

背景技术

公钥密码体制在现代信息社会中起着非常重要的作用。传统的公钥密码体制是基于证书的，需要证书认证机构(Certificate Authority，简称为CA)。传统的公钥密码体制存在着建立CA的开销巨大、公钥的更新步骤比较复杂、用户管理方面呆板等问题。因此，现代信息社会迫切需要发展基于无证书的公钥密码体制。目前，基于身份的密码体制就是基于无证书的公钥密码体制的一种，它的优点是不需要证书和证书管理，公钥更新极为方便，用户不需要事先注册。因而，基于身份的密码体制被普遍认为有广泛的应用前景。

目前，基于身份的密码体制有两个研究分支，第一个研究分支是利用配对技术的身份密码体制，第二个研究分支是利用其他非配对技术的身份密码体制。

第一个研究分支极为活跃，自从Boneh和Franklin提出第一个基于配对的身份密码体制以来，已经有将近400篇论文研究基于配对的身份密码体制。并且，IEEE还提出了基于配对的身份密码体制的标准IEEE1363.3。但是仅利用配对技术来构造一类公钥密码体制，是不可靠的，况且普通的配对运算(如Weil配对和Tate配对等)的计算量很大。

以下列出了有关基于配对技术的身份密码体制的一些参考文献，通过引用将它们并入于此，如同在本说明书中作了详尽描述：

Kenneth G.Paterson的论文“ID-based signatures from pairings onelliptic curves”，该论文发表于IEE Electronics Letters(2002年，38(18)，第1025-1026页)；

Florian H.的论文“Efficient identity based signature schemes basedon pairings”，该论文发表于Selected Areas in Cryptography(施普林格(Springer)出版，LNCS 2595卷，第310-324页)；

Paulo S.L.M.、Beonit L、Noel M.及Jacques Q.等人的论文“Efficientand provably secure identity-based signatures and signcryption frombilinear maps”，该论文发表于Asiacrypt 2005(施普林格(Springer)出版，LNCS 3788卷，第515-532页)；

Xun Y.等人的论文“An identity-based signature scheme from the weilpairing”，该论文发表于IEEE Communications Letters(2003年，7(3))；

Scott M.等人的论文“Implementing Cryptographic Pairings”，该论文发表于Pairing 2007(施普林格(Springer)出版，LNCS 4575卷，第177-135页)；

Scott M.等人的论文“Computing the Tate Pairing”，该论文发表于Ct-RSA 2005(施普林格(Springer)出版，LNCS 3376卷，第293-304页)。

第二个研究分支一直也广泛受到人们的关注，但是其构造难度比较大。目前已提出的基于非配对的身份签名体制数量很少，其中包括基于RSA的、基于离散对数的、基于二次剩余的等等。但是这些方案也存在着一些问题，诸如签名算法计算效率低(需要两次以上的模指数运算)、不能对其安全性(即选择消息和ID攻击安全)给出形式化证明等等。另外，这些方案不是真正的身份密码体制，其验证签名除了需要签名者的身份(ID)，还需要其他类似于公钥的信息，这些信息相当于基于证书的公钥密码体制中的公钥，需要进行认证。

以下列出了有关基于非配对技术的身份密码体制的一些参考文献，通过引用将它们并入于此，如同在本说明书中作了详尽描述：

Shamir A.等人的论文Identity-based cryptosystems and signatureschemes”，该论文发表于Crypto 1984(施普林格(Springer)出版，LNCS196卷，第47-53页)；

Lee W-B、Liao K-C等人的论文“Construction identity-basedcryptosystems for discrete logarithm based cryptosystem”，该论文发表于Journal of Network and Computer Applications(2004年，27，第191-199页)；

Chai Z、Cao Z及Dong X-L.等人的论文“Identity based signaturescheme based on quadratic residues”，该论文发表于Science in ChinaSeriers F：Information Sciences(2007年，50(3)，第373-380页)；以及

Jae C.C.和Jung H.C.等人的论文“An identity based signature fromgap diffie-hellman groups”，该论文发表于PKC 2003(施普林格(Springer)出版，LNCS 2567卷，第18-30页)。

发明内容

本发明的目的是提供一种用于基于身份的签名体制的参数建立方法和设备、签名生成方法和设备以及签名验证方法和设备，其中，不使用配对技术，其签名验证不依赖于需要认证的类似公钥的信息，且能够有效地提高签名和验证效率。

根据本发明的一个方面，提供了一种用于基于身份的签名体制的参数建立方法。该参数建立方法包括：选取第一素数p和第二素数q，使得所述第一素数p和所述第二素数q的二进制长度相同，并且满足pq≥2^k，p-1与3的最大公约数为1，以及q-1与3的最大公约数为3，其中，k是第一安全系数且为正整数；将所述第一素数p和所述第二素数q相乘，所得乘积作为第一参数N；选取第二参数a，使得所述第二参数a为模q的三次非剩余；利用下式来计算第三参数η和第四参数λ：η＝[(q-1)mod 9]/3，λ＝ηmod 2+1；选取第一哈希函数h₁()和第二哈希函数h₂()；以及利用下式来计算第五参数β和第六参数ξ：ξ＝a^ηβ mod q，其中，所述第一素数p、所述第二素数q、所述第三参数η、所述第四参数λ、所述第五参数β和所述第六参数ξ用作所述基于身份的签名体制中的第三方的秘密参数，而所述第一参数N、所述第一哈希函数h₁()、所述第二哈希函数h₂()以及所述第二参数a用作所述第三方的公开参数。

根据本发明的另一方面，提供了一种用于基于身份的签名体制的签名生成方法。该签名生成方法包括：从所述签名体制中的第三方获取第一公开参数N、第二哈希函数h₂()、以及签名者私钥g；利用从所获取的第一公开参数N来选取第一随机数r，使得r∈Z_N^＊，其中，Z_N^＊表示模N的循环群；根据所述第一随机数r利用下式来计算第二随机数t：t＝r³ mod N；利用所获取的签名者私钥g及第二哈希函数h₂()计算待发送的消息M的签名参数S，使得其中，t||M表示将所述第二随机数t与所述消息M二者转换成二进制值后串接在一起；以及生成所述消息M的签名，其中所述签名包括所述签名参数S和所述第二随机数t。

根据本发明的另一方面，提供了一种用于基于身份的签名体制的签名验证方法。该签名验证方法包括：从所述签名体制中的第三方获取第一公开参数N、第二公开参数a、第一哈希函数h₁()、以及第二哈希函数h₂()；接收附带签名的消息M，其中所述签名包括第一签名参数S和第二签名参数t；利用所获取的第一公开参数N、第二公开参数a、以及第一哈希函数h₁()，根据下式针对与所述签名相关联的签名者标识ID计算多个验证参数H_i中的一个或多个，其中i＝1，2，或3，H_i满足下式：H_i＝a^i-1h₁(ID)mod N；以及通过利用所获取的第二哈希函数h₂()计算所述第一签名参数S和所述第二签名参数t是否满足下式中的任一个：i＝1，2，或3来验证所述签名是否合法，其中，t||M表示将所述第二签名参数t与所述消息M二者转换成二进制值后串接在一起。

根据本发明的另一方面，提供了一种用于基于身份的签名体制的参数建立设备。该参数建立设备包括：素数选取装置，用于选取第一素数p和第二素数q，使得所述第一素数p和所述第二素数q的二进制长度相同，并且满足pq≥2^k，p-1与3的最大公约数为1，以及q-1与3的最大公约数为3，其中，k是第一安全系数且为正整数；乘法装置，用于将所述第一素数p和所述第二素数q相乘，其中，所得的乘积作为第一参数N；哈希函数选取装置，用于选取第一哈希函数h₁()和第二哈希函数h₂()；参数计算装置，用于计算第二参数a，使得所述第二参数a为模q的三次非剩余，用于利用下式来计算第三参数η和第四参数λ：η＝[(q-1)mod 9]/3，λ＝ηmod 2+1，还用于利用下式来计算第五参数β和第六参数ξ：ξ＝a^ηβmodq，其中，所述第一素数p、所述第二素数q、所述第三参数η、所述第四参数λ、所述第五参数β和所述第六参数ξ用作所述基于身份的签名体制中的第三方的秘密参数，而所述第一参数N、所述第一哈希函数h₁()、所述第二哈希函数h₂()以及所述第二参数a用作所述第三方的公开参数。

根据本发明的另一方面，提供了一种用于基于身份的签名体制的签名生成设备。该签名生成设备包括：获取装置，用于从所述签名体制中的第三方获取第一公开参数N、第二哈希函数h₂()、以及签名者私钥g；随机数选取装置，用于利用由所述获取装置获取的第一公开参数N来选取第一随机数r，使得r∈Z_N^＊，其中，Z_N^＊表示模N的循环群；随机数计算装置，用于根据所述第一随机数r利用下式来计算第二随机数t：t＝r³ modN；签名参数计算装置，用于利用由所述获取装置获取的签名者私钥g及第二哈希函数h₂()来计算待发送的消息M的签名参数S，使得其中，t||M表示将所述第二随机数t与所述消息M二者转换成二进制值后串接在一起；以及签名生成装置，用于生成所述消息M的签名，其中所述签名包括所述签名参数S和所述第二随机数t。

根据本发明的另一方面，提供了一种用于基于身份的签名体制的签名验证设备。该签名验证设备包括：公开参数获取装置，用于从所述签名体制中的第三方获取第一公开参数N、第二公开参数a、第一哈希函数h₁()、以及第二哈希函数h₂()；消息接收装置，用于接收附带签名的消息M，其中所述签名包括第一签名参数S和第二签名参数t；验证参数计算装置，用于利用由所述公开参数获取装置获取的第一公开参数N、第二公开参数a、以及第一哈希函数h₁()，针对与所述签名相关联的签名者标识ID计算多个验证参数H_i中的一个或多个，其中i＝1，2，或3，H_i满足下式：H_i＝a^i-1h₁(ID)modN；以及验证装置，用于通过利用由所述公开参数获取装置获取的第二哈希函数h₂()计算所述第一签名参数S和所述第二签名参数t是否满足下式中的任一个：i＝1，2，或3来验证所述签名是否合法，其中，t||M表示将所述第二签名参数t与所述消息M二者转换成二进制值后串接在一起。

附图说明

参照下面结合附图对本发明实施例的说明，会更加容易地理解本发明的以上和其它目的、特点和优点。附图中的部件只是为了示出本发明的原理。在附图中，相同的或类似的技术特征或部件将采用相同或类似的附图标记来表示。

图1是示出了可实现本发明的基于身份的签名体制的基本框架的示意图；

图2是示出了根据本发明的一个实施例的用于基于身份的签名体制的第三方参数建立方法的流程图；

图3示出了根据本发明的一个实施例的用于提取签名者私钥的方法的流程图；

图4是示出了用于计算图2所示方法中的第七参数H的一个示例性过程的图；

图5示出了根据本发明的一个实施例的签名生成方法的流程图；

图6示出了根据本发明一个实施例的验证签名方法的流程图；

图7是示出了根据本发明的一个实施例的用于实施图1所示方法的第三方参数建立设备的结构的示意性框图；

图8是示出了根据本发明的另一实施例的用于实施图2所示方法的参数建立设备的结构的示意性框图；

图9是示出了根据本发明的一个实施例的签名生成设备的结构的示意性框图；以及

图10是示出了根据本发明的一个实施例的签名验证设备的结构的示意性框图。

具体实施方式

下面参照附图来说明本发明的实施例。在本发明的一个附图或一种实施方式中描述的元素和特征可以与一个或更多个其它附图或实施方式中示出的元素和特征相结合。应当注意，为了清楚的目的，附图和说明中省略了与本发明无关的、本领域普通技术人员已知的部件和处理的表示和描述。

图1示出了可实现本发明的基于身份的签名体制的基本框架。如图1所示，可信第三方首先通过参数建立过程建立用于该签名体制的各种参数。这些参数包括公开参数和秘密参数。其中，公开参数是对外公开的，而秘密参数是不对外公开的。用户(包括签名者(即消息发送方)和验证方(即消息接收方))可以从该第三方获取其公开参数以便进行签名和验证。

当消息发送方(即签名者)要对待发送的消息签名时，首先要获得签名者私钥。签名者可以将自己的标识ID发送给第三方。由第三方通过私钥提取过程、根据所建立的秘密参数计算出与该签名者的标识对应的私钥，并反馈给签名者。因此，可信第三方亦可称为私钥生成者(Private KeyGenerator，简称为PKG)。

签名者利用从第三方获取的公开参数和私钥生成用于待发送的消息的签名，并将附带有签名的消息发送出去。消息的接收方(即验证方)在接收到该消息后，提取出签名，并根据与该消息相关联的签名者的标识和从第三方获取的的公开参数来验证签名是否合法。

下文结合附图来描述基于上述框架实现的根据本发明实施例的第三方参数建立方法和设备、签名生成方法和设备以及签名验证方法和设备。

图2是示出了根据本发明的一个实施例的用于基于身份的签名体制的第三方参数建立方法的流程图。下面参照该附图来描述该第三方参数建立方法。

如图2所示，在步骤201，选取两个素数p和q(下文中分别称为第一素数和第二素数)。这两个素数满足以下条件：(1)二者的二进制长度相同，(2)pq≥2^k，(3)p-1与3的最大公约数为1，且q-1与3的最大公约数为3，即gcd(3，p-1)＝1，gcd(3，q-1)＝3。其中，k是安全系数(下文中称为第一安全系数)且为正整数。

在步骤203，将第一素数p和第二素数q相乘，所得乘积作为第一参数N。

在步骤205，选取第二参数a，使得第二参数a为模q的三次非剩余。

在步骤207，按照下式计算第三参数η和第四参数λ：

η＝[(q-1)mod 9]/3，λ＝η mod 2+1。

在步骤209，任意选取两个哈希函数h₁()和h₂()(下文中分别称为第一哈希函数和第二哈希函数)。

在一个示例中，第一哈希函数h₁()优选为将任意长度的{0，1}序列映射成模N的循环群Z_N^＊上的元素的哈希函数，而第二哈希函数h₂()优选为将任意长度的{0，1}序列映射成l比特的消息摘要的哈希函数，即这两个哈希函数满足下式：h₁()：{0，1}^*→Z_N^*，h₂()：{0，1}^*→{0，1}^l。其中，Z_N^＊表示模N的循环群，l为另一安全参数(称为第二安全系数)且为正整数。当然，这里给出的哈希函数的例子是示例性的，而非限制性的，本领域的普通技术人员应理解，任意适当的哈希函数均可适用，本发明并不限于所述示例。

在步骤211，按照下式计算第五参数β和第六参数ξ：

$\beta =\frac{q-1}{3},$ξ＝a^ηβ modq。

利用上述方法，即可建立用于可信第三方的参数。其中，可信第三方的秘密参数为(p，q，β，ξ，η，λ)，公开参数为(N，h₁()，h₂()，a)。

在一个示例中，第一安全系数k的二进制长度优选大于或等于1024比特，而第二安全系数l的二进制长度优选大于或等于160比特。当然，这里给出的安全系数的例子是示例性的，而非限制性的。本领域的普通技术人员可以根据实际的安全要求而采用其他数值。任意适当的安全系数均可适用，本发明并不限于所述示例。

图3示出了根据本发明的一个实施例的用于生成签名者私钥的方法。该私钥生成方法由可信第三方基于根据图2所示的方法而建立的第三方参数而执行。

如图3所示，在步骤301，从签名者接收签名者标识ID。

在步骤303，将所接收的签名者标识ID凑成模N(即前述第一参数)的三次剩余，所得结果作为参数H(下文中称为第七参数)。

在步骤305，计算第七参数H的三次根，所得结果作为与签名者标识ID对应的签名者私钥g。

在一个示例中，可以利用下式来计算签名者私钥g：

g³＝H mod N

在一个更优选的示例中，还可以利用下式来计算签名者私钥g：

$g=H^{\frac{2^{\eta -1}(p-1)(q-1)-3}{9}}\mathrm{mod}N,$

该方法更加快捷有效。

当然，这里给出的根据第七参数来计算签名者私钥的方法是示例性的，而非限制性的。在本发明的精神和范围内，本领域的普通技术人员可以对上述计算方法进行修改和变更。本发明并不限于所述示例。

最后，在步骤307，将所得到的签名者私钥g反馈给签名者。

图4示出了用于计算所述第七参数H的具体示例。

如图4所示，在步骤401，针对签名者标识ID利用下式计算第八参数ω：

ω＝h₁(ID)^λ·βmod q。

在步骤403，根据第八参数ω数计算第九参数c，使得：当ω＝1时第九参数c等于0，当ω＝ξ时第九参数c等于1，当ω＝ξ²时第九参数c等于2，即满足下式：

$c=\left(\begin{array}{cc}0,& \omega =1\\ 1,& \omega =\xi \\ 2,& \omega ={\xi }^2\end{array}\right).$

在步骤405，根据第九参数c来计算第七参数H，使得第七参数H满足下式：

H＝a^ch₁(ID)mod N。

当然，这里给出的计算第七参数H的方法是示例性的，而非限制性的。在本发明的精神和范围内，本领域的普通技术人员可以对上述计算方法进行修改和变更。本发明并不限于所述示例。

图5示出了根据本发明的一个实施例的签名生成方法。该方法利用根据图2所示的方法建立的可信第三方的公开参数及根据图3所示的方法生成的签名者私钥。假设待发送的消息用M来表示，下面参考附图5来描述用于为该消息生成签名的过程。

如图5所示，作为该方法的预备步骤，在步骤S501，从可信第三方获取公开参数(具体地说，第一公开参数N和第二哈希函数h₂())以及签名者私钥g。

在步骤503，根据第一公开参数N来选取一个小随机数r(下文中称为第一随机数)。可选地，该第一随机数满足：r∈Z_N^＊。其中，Z_N^＊表示模N的循环群。

在步骤505，根据第一随机数r来计算大随机数t(下文中称为第二随机数)。例如，第二随机数t满足下式：t＝r³ mod N。

在步骤507，根据上述两个随机数r和t、利用签名者私钥g及第二哈希函数h₂()计算消息M的签名参数S。签名参数S满足下式：其中，t||M表示将第二随机数t与消息M二者转换成二进制值后串接在一起。

最后，在步骤509，生成消息M的签名，其中该签名包括作为第一签名参数的签名参数S和作为第二签名参数的第二随机数t。

上述的签名生成方法仅需一次模指运算，大大减小了计算复杂度。

在上述的签名生成方法中，签名者私钥对应于签名者ID，是第三方根据上述私钥提取方法而生成的。在此不再一一赘述。

在上述的签名生成方法中，第一公开参数N是可信第三方的公开参数。N＝p×q，p和q为二进制长度相同的两个素数，并且满足pq≥2^k，p-1与3的最大公约数为1，以及q-1与3的最大公约数为3。k是第一安全系数且为正整数。

在上述的签名生成方法中，第二哈希函数h₂()也是从第三方获取的公开参数。在一个示例中，h₂()为将任意长度的{0，1}序列映射成l比特的消息摘要的哈希函数。l为第二安全参数且为正整数。当然，这里给出的哈希函数的例子是示例性的，而非限制性的，本领域的普通技术人员应理解，任意适当的哈希函数均可适用，本发明并不限于所述示例。

在一个示例中，第一安全系数k的二进制长度优选大于或等于1024比特，而第二安全系数l的二进制长度优选大于或等于160比特。当然，这里给出的安全系数的例子是示例性的，而非限制性的。本领域的普通技术人员可以根据实际的安全要求而采用其他数值。任意适当的安全系数均可适用，本发明并不限于所述示例。

图6示出了根据本发明一个实施例的用于验证签名的方法。下面参考图6来描述对该签名进行验证的过程。

如图6所示，作为该方法的预备步骤，在步骤601，从可信第三方获取第一公开参数N、第二公开参数a、第一哈希函数h₁()、以及第二哈希函数h₂()。

在步骤603，接收附带签名的消息M，其中该签名包括第一签名参数S和第二签名参数t。

在步骤605，利用从可信第三方获取的第一公开参数N、第二公开参数a、以及第一哈希函数h₁()，针对与所接收到的消息M对应的签名者标识ID来计算多个验证参数H_i中的一个或多个，其中i＝1，2，或3。H_i满足下式：H_i＝a^i-1h₁(ID)mod N。

具体地，第一验证参数H₁、第二验证参数H₂、第三验证参数H₃分别满足下式：

H₁＝h₁(ID)mod N，H₂＝a·h₁(ID)mod N，H₃＝a²·h₁(ID)mod N。

在步骤607，利用从第三方获取的第二哈希函数h₂()计算第一签名参数S和第二签名参数t是否满足下式中的任一个：

$S^3{H_i}^{h_2\left(t\right|\left|M\right)}=t,$i＝1，2，3，

其中，t||M表示将第二签名参数t与消息M二者转换成二进制值后串接在一起，

只要满足上述三个等式中的任一个，则可确定所述签名是合法的。如果三个等式均不成立，则可确定所述签名是不合法的。

上述的签名验证方法仅需两次模指运算，并且仅依赖于签名者的身份(ID)，而不依赖于需要认证的类似公钥的信息。

在一个示例中，N＝p×q，p和q为二进制长度相同的两个素数，并且满足pq≥2^k，p-1与3的最大公约数为1，以及q-1与3的最大公约数为3。k是第一安全系数且为正整数。

在一个示例中，第一哈希函数h₁()为将任意长度的{0，1}序列映射成模N的循环群Z_N^＊上的元素的哈希函数，h₂()为将任意长度的{0，1}序列映射成l比特的消息摘要的哈希函数。l为第二安全参数且为正整数。当然，这里给出的哈希函数的例子是示例性的，而非限制性的，本领域的普通技术人员应理解，任意适当的哈希函数均可适用，本发明并不限于所述示例。

在一个示例中，第一安全系数k的二进制长度优选大于或等于1024比特，而第二安全系数l的二进制长度优选大于或等于160比特。当然，这里给出的安全系数的例子是示例性的，而非限制性的。本领域的普通技术人员可以根据实际的安全要求而采用其他数值。任意适当的安全系数均可适用，本发明并不限于所述示例。

应该理解，上述的所有例子均是示例性的，而非限制性的。在本发明的精神和范围内，本领域的普通技术人员可以对上述方法和/或步骤进行修改和变更。本发明并不限于所述的各个示例。

为了更好地理解本发明，下面以具体的参数为例来示例性地描述图1中所示的用于建立第三方参数的过程、用于生成签名者私钥的过程、用于生成签名的过程以及用于验证签名的过程。

1.第三方参数建立

首先，选择两个素数，使得p＝5，q＝7，可以计算，所选取的两个参数分别满足：gcd(3，p-1)＝1，gcd(3，q-1)＝3。

然后，计算第一参数N，即N＝5×7＝35。

然后，选取模7(q)的三次非剩余2，得到第二参数a。

然后，计算第三参数η和第四参数λ，具体地，

η＝[(q-1)mod 9]/3＝2，λ＝η mod 2+1＝1。

然后，选取两个哈希函数，例如h₁()：{0，1}^*→Z₃₅^*，h₂()：{0，1}^*→{0，1}^l，并计算第五参数β和第六参数ξ，具体地，ξ＝2^2×2 mod 7＝2。

这样，即可得到可信第三方的秘密参数(p＝2，q＝7，β＝2，ξ＝2，η＝2，λ＝1)以及公开参数(N＝14，h₁()，h₂()，a＝2)。

2.签名者私钥提取

假设签名者标识ID＝23，则第一哈希函数h₁(23)＝3。因此，根据前述等式可计算得到第八参数ω＝3^1×2 mod 7＝2及第九参数c＝1。根据第八参数和第九参数可计算得到第七参数H＝2·3 mod 35＝6。

这样，即可计算出与签名者ID 23对应的私钥g：

$g=6^{\frac{2^1(5-1)(7-1)-3}{9}}\mathrm{mod}35=6^5\mathrm{mod}35=6.$

3.签名生成

假设待发送的消息为5，即二进制101。下面描述如何生成针对该消息的签名。首先，选择第一随机数r＝2(2∈Z₃₅^*)。然后根据该第一随机数可计算得到第二随机数t＝2³ mod 35＝8。第二随机数8的二进制表示为1000，而8与5串接得到1000101，即十进制的69。假设h₂(69)＝1，则可计算得到第一签名参数

因此，消息5的签名为(12，8)。

4.签名验证

当接收到附带有上述签名的消息时，对上述签名进行验证。首先，计算三个验证参数，即H₁＝3 mod 35＝3，H₂＝2·3 mod 35＝6，H₃＝2²·3 mod 35＝12。对于i＝1，2，3，分别检验是否成立。当其中任一个等式成立时，即可断定签名是合法的。在这个示例中，i＝1时，等式成立。因此，可以验证这个签名是合法的。

应该理解，上述示例中虽然给出了具体的参数，但这些参数均是示例性的，而非限制性的。在本发明的精神和范围内，本领域的普通技术人员可以根据实际需求对上述参数进行修改和变更。本发明并不限于所述示例。

图7示出了根据本发明的一个实施例的用于实施图2所示方法的第三方参数建立设备。

如图7所示，该参数建立设备700可以包括素数选取装置701、乘法装置703、哈希函数选取装置705以及参数计算装置707。

素数选取装置701可以被配置用于选取第一素数p和第二素数q。与上述方法实施例相同，第一素数p和第二素数q的二进制长度相同，并且满足pq≥2^k，p-1与3的最大公约数为1，以及q-1与3的最大公约数为3。其中，k是第一安全系数，为正整数。

乘法装置703可以被配置用于将第一素数p和第二素数q相乘，所得的乘积作为第一参数N。

哈希函数选取装置705可以被配置用于选取第一哈希函数h₁()和第二哈希函数h₂()。第一哈希函数h₁()和第二哈希函数h₂()可以是任选的。在一个示例中，第一哈希函数h₁()优选为将任意长度的{0，1}序列映射成模N的循环群Z_N^＊上的元素的哈希函数，而第二哈希函数h₂()优选为将任意长度的{0，1}序列映射成l比特的消息摘要的哈希函数，即这两个哈希函数满足下式：h₁()：{0，1}^*→Z_N^*，h₂()：{0，1}^*→{0，1}^l。其中，Z_N^＊表示模N的循环群，l为另一安全参数(称为第二安全系数)且为正整数。

当然，这里给出的哈希函数的例子是示例性的，而非限制性的，本领域的普通技术人员应理解，任意适当的哈希函数均可适用，本发明并不限于所述示例。

参数计算装置707可以被配置用于计算第二参数a。所述第二参数a为模q的三次非剩余。参数计算装置707还可以被配置用于计算第三参数η、第四参数λ、第五参数β和第六参数ξ。

计算所得的第三参数η、第四参数λ满足下式：

η＝[(q-1)mod 9]/3，λ＝η mod 2+1。

计算所得的第五参数β和第六参数ξ满足下式：

$\beta =\frac{q-1}{3},$ξ＝a^ηβmodq，

利用上述设备，即可建立用于可信第三方的参数。其中，可信第三方的秘密参数为(p，q，β，ξ，η，λ)，公开参数为(N，h₁()，h₂()，a)。

在一个示例中，第一安全系数k的二进制长度优选大于或等于1024比特，而第二安全系数l的二进制长度优选大于或等于160比特。当然，这里给出的安全系数的例子是示例性的，而非限制性的。本领域的普通技术人员可以根据实际的安全要求而采用其他数值。任意适当的安全系数均可适用，本发明并不限于所述示例。

图8示出了根据本发明另一实施例的参数建立设备800。参数建立设备800可以包括素数选取装置801、乘法装置803、哈希函数选取装置805以及参数计算装置807。与图7所示的实施例的不同之处在于，参数建立设备800还可以包括用于实施图3所示方法的签名者私钥生成装置809。

签名者私钥生成装置809可以被配置用于通过将签名者标识ID凑成模N的三次剩余来计算第七参数H，并计算所述第七参数H的三次根以得到与所述签名者标识ID对应的签名者私钥g。

第三方参数建立设备700和800使用与前述方法实施例相同的方法来建立第三方参数，这里不再一一赘述。另外，签名者私钥生成装置805计算第七参数以及签名者私钥g的方法也可与前述的各方法实施例相同，这里也不再一一赘述。

图9示出了根据本发明的一个实施例的签名生成设备900。所述签名生成设备900可以实施例如图5所示的签名生成方法。

如图9所示，签名生成设备900可以包括获取装置901、随机数选取装置903、随机数计算装置905、签名参数计算装置907以及签名生成装置909。

获取装置901可以被配置用于从可信第三方获取公开参数(具体地说，第一公开参数N和第二哈希函数h₂())以及签名者私钥g。

随机数选取装置903可以被配置用于利用从所示签名体制的第三方获取的第一公开参数N来选取第一随机数r，使得r∈Z_N^＊。其中，Z_N^＊表示模N的循环群。

随机数计算装置905可以被配置用于根据所述第一随机数r来计算第二随机数t。其中，第二随机数t满足：t＝r³ mod N，。

签名参数计算装置907可以被配置用于利用从所述第三方获取的签名者私钥g及第二哈希函数h₂()来计算待发送的消息M的签名参数S。其中，签名参数S满足其中，t||M表示将第二随机数t与消息M二者转换成二进制值后串接在一起。

签名生成装置909可以被配置用于生成消息M的签名，其中该签名包括作为第一签名参数的签名参数S和作为第二签名参数的第二随机数t。

上述的签名生成设备在执行签名生成过程时仅需一次模指运算，大大减小了计算复杂度。

上述的签名生成设备所使用的签名者私钥对应于签名者ID，是第三方(签名者私钥提取装置)利用前述私钥提取方法而生成的。在此不再一一赘述。

上述的签名生成设备所使用的第一公开参数N是可信第三方的公开参数。N＝p×q，p和q为二进制长度相同的两个素数，并且满足pq≥2^k，p-1与3的最大公约数为1，以及q-1与3的最大公约数为3。k是第一安全系数且为正整数。

上述的签名生成设备所使用的第二哈希函数h₂()也是从第三方获取的公开参数。在一个示例中，h₂()为将任意长度的{0，1}序列映射成l比特的消息摘要的哈希函数。l为第二安全参数且为正整数。当然，这里给出的哈希函数的例子是示例性的，而非限制性的，本领域的普通技术人员应理解，任意适当的哈希函数均可适用，本发明并不限于所述示例。

在一个示例中，第一安全系数k的二进制长度优选大于或等于1024比特，而第二安全系数l的二进制长度优选大于或等于160比特。当然，这里给出的安全系数的例子是示例性的，而非限制性的。本领域的普通技术人员可以根据实际的安全要求而采用其他数值。任意适当的安全系数均可适用，本发明并不限于所述示例。

图10示出了根据本发明的一个实施例的签名验证设备1000。所述签名验证设备1000可以实施例如图6所示的签名验证方法。

如图10所示，签名验证设备1000可以包括公开参数获取装置1001、消息接收装置1003、验证参数计算装置1005以及验证装置1007。

公开参数获取装置1001可以被配置用于从可信第三方获取第一公开参数N、第二公开参数a、第一哈希函数h₁()、以及第二哈希函数h₂()。

消息接收装置1003可以被配置用于接收附带签名的消息M，其中该签名包括第一签名参数S和第二签名参数t。

验证参数计算装置1005可以被配置用于利用从可信第三方获取的第一参数N、第二参数a、以及第一哈希函数h₁()来计算多个验证参数H_i中的一个或多个，其中i＝1，2，或3。H_i满足下式：H_i＝a^i-1h₁(ID)mod N。

具体地，第一验证参数H₁、第二验证参数H₂、第三验证参数H₃应分别满足下列等式：

H₁＝h₁(ID)mod N，H₂＝a·h₁(ID)mod N，H₃＝a²·h₁(ID)mod N。

验证装置1002可以被配置用于通过利用从所述第三方获取的第二哈希函数h₂()来计算包括在接收到的消息M的签名中的第一签名参数S和第二签名参数t是否满足下式中的任一个：其中，i＝1，2，3，t||M表示将第二签名参数t与消息M二者转换成二进制值后串接在一起。

如果上述三个等式中的任一个成立，则所述签名合法。如果三个等式均不成立，则所述签名不合法。

在一个示例中，N＝p×q，p和q为二进制长度相同的两个素数，并且满足pq≥2^k，p-1与3的最大公约数为1，以及q-1与3的最大公约数为3。k是第一安全系数且为正整数。

在一个示例中，第一哈希函数h₁()为将任意长度的{0，1}序列映射成模N的循环群Z_N^＊上的元素的哈希函数，h₂()为将任意长度的{0，1}序列映射成l比特的消息摘要的哈希函数。l为第二安全参数且为正整数。当然，这里给出的哈希函数的例子是示例性的，而非限制性的，本领域的普通技术人员应理解，任意适当的哈希函数均可适用，本发明并不限于所述示例。

在一个示例中，第一安全系数k的二进制长度优选大于或等于1024比特，而第二安全系数l的二进制长度优选大于或等于160比特。当然，这里给出的安全系数的例子是示例性的，而非限制性的。本领域的普通技术人员可以根据实际的安全要求而采用其他数值。任意适当的安全系数均可适用，本发明并不限于所述示例。

应该理解，上述的所有例子均是示例性的，而非限制性的。在本发明的精神和范围内，本领域的普通技术人员可以对上述方法和/或步骤进行修改和变更。本发明并不限于所述的各个示例。

上述装置中各个组成部件、单元和子单元可通过软件、硬件或其组合的方式进行配置。配置可使用的具体手段或方式为本领域技术人员所熟知，在此不再赘述。

容易理解，包含上述本发明的实施例的设备和/或装置的签名体制或系统也应该被认为落入本发明的保护范围内。

本发明还提出一种存储有机器可读取的指令代码的程序产品。所述指令代码由机器读取并执行时，可执行上述根据本发明实施例的方法。

相应地，用于承载上述存储有机器可读取的指令代码的程序产品的存储介质也包括在本发明的公开中。所述存储介质包括但不限于软盘、光盘、磁光盘、存储卡、存储棒等等。

在上面对本发明具体实施例的描述中，针对一种实施方式描述和/或示出的特征可以以相同或类似的方式在一个或更多个其它实施方式中使用，与其它实施方式中的特征相组合，或替代其它实施方式中的特征。

应该强调，术语“包括/包含”在本文使用时指特征、要素、步骤或组件的存在，但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。

此外，本发明的方法不限于按照说明书中描述的时间顺序来执行，也可以按照其他的时间顺序地、并行地或独立地执行。因此，本说明书中描述的方法的执行顺序不对本发明的技术范围构成限制。

尽管上面已经通过对本发明的具体实施例的描述对本发明进行了披露，但是，应该理解，本领域的技术人员可在所附权利要求的精神和范围内设计对本发明的各种修改、改进或者等同物。这些修改、改进或者等同物也应当被认为包括在本发明的保护范围内。