公平的基于身份的有向签名方案

书书书 云南大学学报 (自然科学版)，2011，33 (6):658 ～ 661 CN 53 －1045 /N ISSN 0258 －7971 Journal of Yunnan University http:/ /www． yndxxb． ynu． edu． cn 公平的基于身份的有向签名 * ? 王大星1，朱鹤鸣1，滕济凯2 (1．滁州学院 数学科学学院，安徽 滁州 239000;2．中国科学院 软件研究所，北京 100190) 摘要:为了保护签名接收者的隐私，有向签名方案要求签名的验证必须得到接收者或签名者的合作．利用 椭圆曲线上双线性映射的基于身份的密码体制，提出了一个公平的基于身份的有向签名方案．当签名者与验证 者发生争议时，在二者的协助下，可信第三方能够进行公开验证签名．结果的分析表明，所提方案与同类方案相 比签名长度更短并且通信代价更小． 关键词:基于身份的密码体制;有向签名;双线性映射;公平性 中图分类号:TP 309 文献标识码:A 文章编号:0258 － 7971(2011)06 － 0658 － 04 在现代网络通信系统中，数字签名技术在数据完整性检验、身份鉴别、身份证明、防否认等方面独特的 功能和实际用途，尤其是在一些特殊行业，比如金融、商业、军事等有着广泛的应用．普通的数字签名中，任 何人只要获得签名者的公钥，就可以验证被签发的文件有效性［1］．然而，对于一些私人或公司的保密文件 的签名，如果也可以肆意传播和验证，定会造成不良后果甚至灾难．从另一个角度看，有些签名文件也许包 含有汇款单、工资单、遗传病史等，这些对签名接收者是很敏感的．也就是说，这些签名最好只允许由接收 者本人直接验证． 为了解决上述问题，有向签名方案［2］被提出． 这种签名的特点是签名者以自己的私钥及指定接收者 的公钥产生对消息的签名，接收者以自己的私钥及签名者的公钥来验证．近几年来，基于身份的公钥密码 体系［3 － 5］引起了许多研究者的兴趣．基于身份的密码系统的主要优点是减少证书管理开销．使用基于身份 的密码系统，不需要保存每个用户的公钥证书．系统中每个用户都有 1 个身份，用户的公钥可以由任何人 根据其身份信息计算出来，而私钥则由可信中心统一生成． 作者提出了一个公平的基于身份的有向签名算法，该算法建立在 Hess 的签名方案［4］基础之上．当签 名者与验证者发生争议时，可以由可信第三方出面调停，以达到公平性的效果．由于利用了双线性映射及 基于身份的密码体系，本文所提方案与同类方案［6 － 7］相比签名长度更短并且通信成本更小． 1 准备工作 本节我们简要介绍一些背景知识和模型说明，以满足后文新方案的建立． 1． 1 双线性对和密码学困难问题 设 G1，G2 为两个阶均为大素数 q的群．其中 G1 是一个加法循环群，G2 是一个乘法循环群．设 p是 G1 的任意一个生成元．假设离散对数问题(DLP)在 G1 和 G2 中都是困难的．映 射 e:G1 × G1 → G2 是密码学中的双线性对． 定义 1 椭圆曲线离散对数问题(ECDLP) :给定 1条定义于有限域 Fq 上的椭圆曲线 E和 E上的 2点 P，Q∈ E(Fq)寻找一整数 x，使在 E中有 xP = Q; 定义 2 计算性 Diffie － Hellman问题(CDHP) :已知 P，aP，bP，cP，其中 a，b∈ Z*q ，计算 abP．到目前 * 收稿日期:2011 － 04 － 19 基金项目:国家自然科学基金重点项目资助(90604036) ;安徽省高校省级自然科学研究项目资助(KJ2011Z277) ;滁州学院科研基金 资助项目资助(2010kj009B)． 作者简介:王大星(1980 －) ，男，安徽人，硕士，讲师，主要从事密码学与信息安全方面的研究． 为止，上述 2 个问题都没有多项式时间的有效算法可以解决; 定义 3 可判别 Diffie － Hellman问题(DDHP) :给定(P，aP，bP，cP) ，a，b，c∈ Z*q ，如果有 c = ab成 立，则称(P，aP，bP，cP)为有效 Diffie － Hellman元组． 1． 2 Hess签名方案简介 下面我们来简单介绍 Hess签名过程． 系统的建立:密钥生成中心(PKG)随机选取 s ∈RZ * q 作为它的主密钥，并计算它的全局公钥 PPub = sP． PKG同时选择两个密码学上的哈希函数 H1:{0，1} * → G*1 ，h:{0，1} * × G2→ Z * q ．然后，PKG将主密钥 s秘密保存，公布系统参数 params〈G1，G2，e，P，PPub，H1，h〉． 密钥提取:假定签名者的身份信息是 ID，PKG为签名者计算私钥 dID = sQID，其中 QID = H1(ID)为签 名者的公钥． 签名:要签发一条消息M∈{0，1}* ，签名者任选P1∈G * 1 ，k∈Z * q 然后计算R = e(P1，P) k，V = h(M， R) ，U = VdID + kP1 ．消息 M的签名是 σ = (U，V)∈ G1 × Z * q ． 验证:验证者计算 R = e(U，P)e(QID，－ PPub) y ．当且仅当 V = h(M，R)时接受签名． 1． 3 新签名方案的模型说明 一个公平的基于身份的有向签名模型由算法集〈Setup，Extract，Sign， DVerify，TVerify〉组成，下面我们给出它们的定义． 系统初始化(Setup) :密钥生成中心(PKG)生成系统参数 Params 和主密钥 x． 主密钥是秘密保存的， 而系统参数 Params是公开的，并且将会输入到以下所有的算法． 密钥提取(Extract) :给定一个用户的身份信息 ID和主密钥 x，PKG为用户计算私钥 dID，并通过安全的 信道发送给该用户． 签名的生成(Sign) :输入签名者的身份信息 IDs，验证者的身份信息 IDv，消息 M和私钥 dID，为指定验 证者 IDv生成关于消息 M的签名 σ． 有向验证(DVerify) :输入 IDs，IDv，私钥 dID，消息M和签名 σ，该算法验证 σ的有效性．如果输出 1表 示签名有效，输出 0 表示签名无效． 可信方验证(TVerify) :输入 IDs，IDv，消息M和签名σ．可信第三方(TTP)在 IDs和 IDv的协助下验证 σ的有效性．如果输出 1 表示签名有效，输出 0 表示签名无效． 2 基于身份的数字签名的安全模型 2． 1 随机预言机模型 密码学上的 Hash函数能保障数据的完整性． Hash 函数通常用来构造数据的短 “指纹”;一旦数据改变，指纹就不再正确． 即使数据被存储在不安全的地方，通过重新计算数据的指纹并 验证是否改变，就能够检测数据的完整性［8］． 1993 年，Bellare和 Rogaway 引入随机预言机模型(Random Oracle Model)［9－10］，提供了一个理想的 Hash函数数学模型．记 X表示所有消息的集合，Y表示所有的消息摘要组成的有限集，令 F(x，y)为所有从 X 到 Y的函数集合．在这个模型中，随机从F(x，y)中选出一个Hash函数 h:X→ Y，我们仅允许预言器访问函数 h．这意味着不会给出一个公式或者算法来计算函数 h的值．因此，计算 h(x)的惟一方法是询问预言器．这 可以想象为在一本巨大的关于随机数的书中查询 h(x)的值，对于每一个，有一个完全随机的值 h(x)与之 对应．作为在随机预言模型假定下的结果，下面的独立性质是显然的: 定理 1 假定 h∈ F(x，y)是随机选择的，令 X0 X，假定当且仅当 x∈ X0时，h(x) (通过 h的随机预言 器)被确定．那么，对所有的 x∈ X \X0 和 y∈ Y，有 Pr［h(x)= y］ = 1 /M． 在定理 1 中，概率 Pr［h(x)= y］实际上是对任意的 x∈ X0 计算所有的函数 h，得出指定值的条件概 率．该定理是随机预言模型中关于问题复杂性证明中所要用到的关键性质［11－12］． 2． 2 基于身份的数字签名安全性定义 定义 4 (基于身份的数字签名的安全性定义)如果不存在这样的敌手，在概率多项式时间以一个不 容忽略的优势在以下游戏中获胜，那么这样一个基于身份的数字签名在适应性选择消息和身份的攻击下 是存在性不可伪造的． 956第 6 期 王大星等:公平的基于身份的有向签名方案 (1)挑战者 C首先执行 setup算法，生成系统参数 params和系统私钥 s，然后将 params发给敌手 A． (2)敌手 A进行下面的预言机查询: ① Hash询问:对 A的每条 Hash值的查询，算法 C都返回相应的值给 A; ② 私钥解析询问:A可以根据自己的需要向挑战者 C询问用户 ID的私钥，C运行 Key Extract算法产 生私钥 dID，并将 dID 发送给 A; ③ 签名询问:A根据自己的需要向挑战者 C询问身份 ID关于任意消息 m的签名，挑战者 C运行 sign 算法生成相应的签名 σ并返还给 A． (3)A生成1个身份 ID* (ID* 的私钥没有泄露)的消息 /签名对M* ，σ* ，如果满足下面的条件，就表 明 A在该游戏中获胜． ① Verify(params，ID* ，M* ，σ* )= 1; ② ID* 从未提交给私钥解析预言机; ③ (ID* ，M* )从未提交给签名预言机． 3 公平的基于身份的有向签名方案 下面我们以 Hess签名方案为基础，利用双线性对构造一种公平的基于身份的有向签名方案． 具体描 述如下: 3． 1 系统初始化(Setup) 密钥生成中心 PKG随机选择 x∈RZ * q 作为其主密钥，并计算全局公钥 PPub = xP． 然后，PKG选择安全的哈希函数H1，H2，h．其中，H1，H2:{0，1} * →G*1 ，h:{0，1} * × G2→Z * q ．双线性映 射 e:G1 × G1→ G2，其中 G1，G2分别为阶为素数 q的加法群和乘法群，P是 G1的一个生成元．系统参数集为 params〈G1，G2，e，P，PPub，H1，h〉． 3． 2 密钥提取(Key Extract) 给定一个用户的身份 ID∈{0，1}* ． PKG计算 QID = H1(ID)∈ G1，然后 计算用户的私钥 dID = xQID ∈ G1 ． 3． 3 签名的生成(Sign) 为了给一个指定的验证者 IDv生成关于身份 IDs的有向签名，我们按如下步骤 进行: Step1:签名者随机选择 P1 ∈RG * 1 ，r1，k∈ Z * q ． Step2:计算 U = e(P1P) k，L = r1QIDs ． Step3:计算 V = h(H，U) ，这里 H = H2(IDs，IDv，M，U，e(dIDs，r1QIDv) )． Step4:计算 W = VdIDs + kP1 ． 最后得到消息 M的签名即为 σ = (V，W，L)． 3． 4 有向验证(DVerify) 对于一个声称是消息M的关于身份 IDs的签名 σ = (V，M，L) ，验证者 IDv用 他的私钥验证．方法如下: Step1:计算 U' = e(W，P)·e(QIDs，－ PPub) v ． Step2:计算 H = H2(IDs，IDv，M，U'，e(dIDv，L) )． 如果 V = h(H，U') ，则接受签名;否则就断定签名无效，拒绝接受． 3． 5 可信方验证(TVerify) 当签名者与验证者发生争议时，对于上述一个有向签名方案，可信第三方 (TTP)可以解决争议． TTP在 IDs和 IDv的协助下获得辅助信息 A = e(dIDv，L)= e(dIDs r1QIDv) ，TTP计算 U' = e(W，P)·e(QIDs，－ PPub) v 和 H = H2(IDs，IDv，M，U'，A)．当 V = h(H，U')时接受签名，否则拒绝． 4 新方案的分析 下面我们对方案的正确性、安全性和效率方面作一些分析． 4． 1 正确性分析 下面我们证明有向验证(DVerify)算法的正确性，而可信方验证(TVerify)正确性的 证明类似．从上述签名的过程和验证的过程知，我们只需证明 U' = U即可． U' = e(W，P)·e(QIDs，－ PPub) v = e(VdIDs + kP1，P)·e(QIDs，－ PPub) v = 066 云南大学学报(自然科学版) 第 33 卷 e(VdIDs，P)·e(kP1，P)·e(QIDs，－ PPub) v = e(dIDs，P) v·e(P1，P) k·e(QIDs，－ PPub) v = e(QIDs，－ PPub) v·e(P1，P) k·e(QIDs，－ PPub) v = U． 4． 2 安全性分析 从签名算法的过程知道，任何一个攻击者包括指定的接收者 IDv 都不能假冒签名者 IDs伪造签名，因为 IDv不能够从 U' 恢复出签名 σ．另一方面，只有指定的接收者 IDv利用自己的私钥 dIDv 才能计算出 e(dIDv，L) ，从而计算出H．因此，其他用户要验证该签名是不可行的．也即伪造签名相当于计算 G1 或 G2 上的离散对数问题．由于本方案基于 Hess签名方案的，所以在随机预言模型下，其安全性等价于 双线性 Diffe － Hellman问题．更详细的证明过程可以参考文献［6］，这里不再赘述． 4． 3 效率分析 下面我们来分析我们提出的签名方案的效率，并将其与目前较好的方案，即文献［6 － 7］作比较． 我们只考虑双线性对的计算，而其它的计算(如点加点乘运算)相对于双线性对的计算量很 小，这里不作考虑．记 Pa(即 Pairing)表示需要计算双线性对的次数．文献［6］中的签名长度为 3 G1 ，签 名阶段只需作 1 次双线性对运算，而有向验证和公开验证的计算量分别为为 4 次和 3 次双线性对运算．文 献［7］的签名长度为 4 G1 ，有向验证和公开验证的计算量都比文献［6］大．通过比较发现，我们的方案在 验证阶段计算量较小，并且签名的长度也较短．具体如下表 1 所示． 表 1 几种同类方案的效率对比 Tab． 1 Efficiency compaison of several similar programs 方案 签名长度 签名计算量 有向验证计算量 公开验证计算量 文献［6］ 3 G1 1Pa 4Pa 3Pa 文献［7］ 4 G1 1Pa 5Pa 5Pa 本文方案 2 G1 + Z * q 2Pa 3Pa 2Pa 5 结束语 因为有向签名具有不可否认性和有向验证性，所以，当被签发的消息或文件含有个人或商业的敏感信 息时，有向签名可以解决此类问题．本文中，我们提出了一种公平的基于身份的有向签名，这种签名只有指 定的接收者才能验证，而且不需要验证签名的公钥证书．另外，在签名者与验证者发生争议时，可以由可信 第三方出面调停和公开验证．通过与同类方案相比较，我们的签名的计算量较小且签名长度较短，在随机 预言模型下，其安全性等价于双线性 Diffe － Hellman 问题．因此，从接收者权利的保护及通信效率等方面 来看，该方案具有广阔的应用空间． 参考文献: ［1］ 孙超亮．代理重签名研究［D］．上海:上海交通大学，2008． ［2］ 张彰，王培春．基于离散对数的有向签名方案及其应用［J］．西安电子科技大学学报，2002，29(4) :510-512． ［3］ 杜红珍．数字签名技术的若干问题研究［D］．北京:北京邮电大学，2009． ［4］ 王永兴．基于身份的有向签名［J］．榆林学院学报，2005，5(5) :1-3． ［5］ HESS F． Efficient identity based signature schemes based on pairings，Selected Areas in cryptography［C］． SAC 2002，Springer － Verlag，2003:310-324． ［6］ SUN X，LI Jian-hua，CHEN Gong-liang，et al． Identity － Based Directed Signature Scheme from Bilinear Pairings［EB /OL］ ［2011 － 04 － 17］． http:/ /eprint． iacr． org /2008 /305． ［7］ ZHANG J，YANG Y，NIU Xin-xin． Efficient provable secure ID － Based directed signature scheme without random oracle［C］． Proceedings of the 6th International Symposium on Neural Networks:Advances in Neural Networks，LNCS，Vol． 5553，Springer － Verlag，2009:318-327． (下转第 666 页) 166第 6 期 王大星等:公平的基于身份的有向签名方案 A study of proton － air inelastic cross section at the energy region of 1 － 100 TeV by applying cosmic ray LAN Xiao-gang1，XU Bin2 (1． School of Physics and Electronic Information，China West Normal University，Nanchong 637002，China; 2． School of Science，Hubei University of Technology，Wuhan 430068，China) Abstract:We have proposed a numerical simulation of extensive air shower (EAS)of cosmic ray at high al- titudes，combined with the response of detector array to ascertain the selection criteria and efficiency of directly arrived protons． We have measured the proton － air inelastic cross section at the energy region of 1 － 100 TeV by analyzing the probability of directly arrived protons． Additionally，the total proton － proton cross section at the en- ergy region of 1 － 100 TeV has been calculated by applying Glauber theory． Key words:extensive air shower of cosmic ray;proton － air inelastic cross section;Glauber theory;total pro- ton － proton cross section ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ (上接第 661 页) ［8］ BELLARE M，ROGAWAY P． The exact security of digital signatures—how to sign with RSA and Rabin［C］/ / In Advances in Cryptology － EuroeryPt’96 ． LNCS1070，1996:257-273． ［9］ BELLARE M，NAMPREMPRE C，NEVEN G． Security proofs for identity － based identification and signature schemes［C］/ / Advances in Cryptology － EUROCRYPT’04，LNCS 3027，Springer － Verlag，2004:268-286． ［10］ LAGUILLAUMIE F，PAILLIER P，VERGNAUD D． Universally convertible directed signatures［C］/ /Advances in Cryptology － ASIACRYPT’05，LNCS 3788，Springer － Verlag，2005:682-701． ［11］ LU R，CAO Z． A directed signature scheme based on RSA assumption［J］． International Journal of Network Security，2006，2 (3) :182-421． ［12］ LU R，LIN X，CAO Z，et al． New (t，n)threshold directed signature scheme with provable security［J］． Information Sci- ences，2008，178(3) :756-765． Directed signature scheme based on identity with Fairness WANG Da-xing1，ZHU He-ming1，TENG Ji-kai2 (1． College of Mathematical Sciences，Chuzhou University，Chuzhou 239012，China; 2． Institute of Software，Chinese Academy of Sciences，Beijing 100190，China) Abstract:In order to protect the privacy of the signature receiver in applications，directed signature schemes have the property that the signature can be verified only with the help of the signature receiver of the signer． A di- rected signature scheme based on identity with fairness is proposed by bilinear maps on elliptic curve cryptosys- tem based on identity． When the signer and the verifier disputes，trusted third party can check the signature valid- ity with the help of the signer or the designated verifier as well． It is shown our scheme is more efficient and shor- ter in size than the existing directed signature schemes． Key words:identity － based cryptography;directed signature;bilinear map;fairness 666 云南大学学报(自然科学版) 第 33 卷