30 第 34 卷数字签名是在认证授权及不可抵赖性中常用的一个密码原语. 当考虑签名方案的安全性时, 通常是指自适应选择消息攻击下存在性不可伪造 []. 多数不可伪造的签名方案是可延展的 [2], 即一个消 [3-4] 息存在多个合法签名. 然而, 有些实际应用需要更强的安全性强不可伪造 [5

Size: px

Start display at page:

Download "30 第 34 卷数字签名是在认证授权及不可抵赖性中常用的一个密码原语. 当考虑签名方案的安全性时, 通常是指自适应选择消息攻击下存在性不可伪造 []. 多数不可伪造的签名方案是可延展的 [2], 即一个消 [3-4] 息存在多个合法签名. 然而, 有些实际应用需要更强的安全性强不可伪造 [5"

忧贝
5 years ago
Views:

203 年 5 月 May203 第 34 卷第 3 期 Vol.34 No.3 doi:0.3969/j.isn.67-7775.203.03.02 标准模型下高效的强不可伪造短签名方案刘振华,2, 胡予濮 3 4, 张襄松 (. 西安电子科技大学数学系, 陕西西安 7007;2. 中国科学院信息工程研究所信息安全国家重点实验室, 北京 00093; 3.

1 203 年 5 月 May203 第 34 卷第 3 期 Vol.34 No.3 doi:0.3969/j.isn 标准模型下高效的强不可伪造短签名方案刘振华,2, 胡予濮 3 4, 张襄松 (. 西安电子科技大学数学系, 陕西西安 7007;2. 中国科学院信息工程研究所信息安全国家重点实验室, 北京 00093; 3. 西安电子科技大学通信工程学院, 陕西西安 7007;4. 西安工业大学理学院, 陕西西安 70032) 摘要 : 针对现有在标准模型下强不可伪造签名方案效率不高的问题, 提出了个新的高效签名方案. 利用椭圆曲线上的双线性对, 基于计算性 Difie Helman 数学困难问题假设, 证明新方案具有强存在性不可伪造. 在新方案中, 用户的公 / 私钥分别包含 6 个和个乘法循环群中的元素, 签名中含有 2 个群中的元素, 在签名阶段需要 3 个指数运算, 在验证阶段需要 2 个双线性对运算和个指数运算. 结果表明, 与现有的标准模型下强不可伪造签名方案相比, 新方案具有更短的公 / 私钥长度和签名长度, 降低了签名和验证阶段的计算耗时, 具有高效性, 适用于资源受限的环境. 关键词 : 数字签名 ; 哈希函数 ; 强不可伪造 ; 标准模型 ; 双线性对中图分类号 :TP309 文献标志码 :A 文章编号 : (203) Eficientandstronglyunforgeableshortsignaturescheme instandardmodel LiuZhenhua,2,HuYupu 3,ZhangXiangsong 4 (.DepartmentofMathematics,XidianUniversity,Xi an,shaanxi7007,china;2.statekeylaboratoryofinformationsecurity,institute ofinformationengineering,chineseacademyofsciences,beijing00093,china;3.schooloftelecommunicationandengineering,xidian University,Xi an,shaanxi7007,china;4.schoolofscience,xi antechnologicaluniversity,xi an,shaanxi70032,china) Abstract:Tosolvethelow eficiencyofexistingstronglyunforgeablesignatureschemesinstandard model,anew eficientsignatureschemewasproposed.basedonthecomputationaldifie Helman (CDH)hardproblemasumptionofbilinearpairingonelipticcurves,theproposedschemewasproved tobestronglyunforgeable.fortheproposedscheme,thepublickeycontainssixgroupelementswitha singlegroupelementofsecretkey,andthesignatureincludestwogroupelements.therearethreeexpo nentialcomputationsinthesigningalgorithm withoneexponentialandtwopairingcomputationsinthe verificationstage.theresultsshowthatcomparedwiththeexistingstronglyunforgeablesignatureschemes instandardmodel,thenewschemehasashorterlengthofpublic\secretkeyandsignaturewithdecreased computationtimeofsigningandverificationalgorithms.theproposedschemeissuitablefortheconstrai nedresourcecommunicationenvironmentswithhigheficiency. Keywords:digitalsignature;hashfunction;strongunforgeability;standardmodel;bilinearpairing 收稿日期 : 基金项目 : 国家自然科学基金资助项目 (600229,6735,032); 信息安全国家重点实验室开放基金资助项目 (GW ); 网络与数据安全四川省重点实验室开放基金资助项目 (DF ); 中央高校基本科研业务费资助项目 (K ); 陕西省教育厅科研计划项目 (2JK0852) 作者简介 : 刘振华 (978 ), 男, 河南潢川人, 博士, 副教授 (zh_liu@mail.xidian.edu.cn), 主要从事密码学与信息安全研究. 胡予濮 (955 ), 男, 河南濮阳人, 教授, 博士生导师 (yphu@mail.xidian.edu.cn), 主要从事密码学与信息安全研究.

2 30 第 34 卷数字签名是在认证授权及不可抵赖性中常用的一个密码原语. 当考虑签名方案的安全性时, 通常是指自适应选择消息攻击下存在性不可伪造 []. 多数不可伪造的签名方案是可延展的 [2], 即一个消 [3-4] 息存在多个合法签名. 然而, 有些实际应用需要更强的安全性强不可伪造 [5-7]. 目前已有的强不可伪造性的签名方案中, 文献 [8-9] 方案的安全性依赖随机预言机 ; 文献 [0-] 方案的安全性建立在强 -RSA 假设. 标准模型下可证明安全的密 [2,2] 码方案不借助于随机预言机假设, 避免了随机预言机模型下因使用哈希函数而在实际使用中可能出现的不安全因素. 最有效的标准模型下具有强不可伪造性的签名方案由文献 [3] 提出. 此后, 相继提出文献 [4-7] 方案, 然而这些方案的签名长度与计算代价都比文献 [3] 方案大得多. 文献 [8] 指出文献 [3] 方案的安全证明中用到的抗碰撞 (coli sionresistant,cr) 哈希函数, 可以用较弱的基于密钥的目标抗碰撞 (targetcolisionresistant,tcr) 哈希函数代替. 文中在文献 [3] 的基础上, 提出一个标准模型下强不可伪造的签名方案, 并对方案的安全性和有效性进行证明和对比分析. 预备知识本节将简要介绍与可证明安全的强不可伪造签名方案有关的基础知识, 分别是双线性对映射, 安全性归约中基于的困难问题假设和所要达到的安全目标. 双线性对映射定义令和 T 分别是 2 个大素数 p 阶乘法循环群, 双线性映射 e: T 满足下列条件 : ) 双线性性. 对任意的 u,v 和 a,b p, 有 e(u a,v b )=e(u,v) ab 成立. 2) 非退化性. 若 g 为群的生成元, 那么 e(g, g). 3) 可计算性. 对任意的 u,v, 映射 e(u,v) 在有效时间内可计算. 一个具体的双线性对映射可以参考文献 [9]. 2 ComputationalDifie Helman 困难问题定义 2 令是大素数 p 阶乘法循环群,g 为该群的一个生成元. 群上的 ComputationalDifie Helman(CDH) 困难问题为 : 给定 g,g a,g b, 计算 g ab, 其中随机选择 a,b p. 若有效时间内, 任意概率多项式时间算法的求解优势可忽略, 则称群上 CDH 困难问题假设成立. 3 强不可伪造签名安全模型一般地, 签名方案包含 3 个算法 : 密钥生成 (KeyGen) 算法, 签名 (Sign) 算法和验证 (Verify) 算法. 在自适应性选择消息攻击下强不可伪造性 (strongly existentialunforgeability underadaptively chosen mesageatacks,seu CMA) 可以由下面敌手与挑战者之间的游戏来定义 : 系统建立 (Setup): 挑战者运行密钥生成算法, 将所获得的公钥发送给敌手, 而自己保留私钥. 签名询问 (SignatureQueries): 敌手自适应地选择消息 M,M 2,,M q, 并向挑战者询问签名. 为了应答询问, 挑战者对消息 M i (i=,2,,q) 运行签名算法产生签名 σ i, 并将签名值 σ i 返回给敌手. 输出 (Output): 最后, 敌手决定停止询问, 并输出一对消息 - 签名 (M,σ ). 如果根据验证算法 σ 是 M 的有效签名, 且 (M,σ ) 不出现在询问阶段的消息 - 签名 {(M,σ ),(M 2,σ 2 ),, (M q,σ q )} 集合中, 则敌手赢得游戏. 我们定义敌手攻击签名方案的优势是敌手赢得上述游戏的概率. 定义 3 如果不存在进行至多 q 次签名询问, 在 t 时间内以至少 ε 优势赢得上述游戏的敌手, 则称签名方案是 (t,q,ε)- 强不可伪造的 (SEU CMA). 2 新签名方案改进 Waters 签名方案 [2], 设计一个标准模型下强不可伪造的签名方案. 令, T,g 和 e 如第节定义. 令 ={H k } 表示一类抗碰撞哈希函数 H k : {0,} {0,} n, 其中密钥 k. 假设 p>2 n 以便哈希函数输出结果可以看成 p 中的元素. 签名方案具体算法如下 : 密钥生成算法为了生成公钥, 首先随机选择 α p, 令 g =g α ; 然后随机选择 5 个元素 g 2,h,v, m 0,m ; 最后随机选择哈希密钥 k. 因此, 公钥 PK=(g,g,g 2,v,m 0,m,k), 私钥 SK=g 2. α 注意到私钥是个群元素, 而公钥包含 6 个群元素. 签名算法对消息 M {0,} 生成签名如下 : ) 随机选择一个元素 s p. 2) 令 σ =g s.

3 第 3 期刘振华等 : 标准模型下高效的强不可伪造短签名方案 3 3) 计算 h H k (M σ ) {0,} n, 将 h 看作 p 中的元素. 4) 检查 σ 的 χ- 坐标的最右边比特值 γ {0, }. 5) 计算 σ 2 g2(m α γ v h ) s, 输出签名 (σ,σ 2 ). 验证算法如下 : 对消息 M 的签名 σ=(σ,σ 2 ) 验证 ) 计算珘 h H k (M σ ), 将珘 h 看作 p 的元素. 2) 检查 σ 的 χ- 坐标的最右边比特值 γ {0, }. 珘 3) 检查 e(σ 2,g)=e(σ,m γ v h ) e(g,g 2 ) 是否成立. 如果成立, 那么就接受消息 M 的签名 σ, 否则拒绝. 3 安全性证明定理如果是 (t,ε/2)- 抗碰撞的, 或者上的 (t,ε/4)-cdh 假设成立, 那么上述的签名方案是 (t,q,ε)- 强不可伪造的. 证明假设存在敌手能攻破上述方案 (t,q, ε)- 强不可伪造性, 下面证明将存在一个模拟器, 能解决上的 (t,ε/2)-cdh 假设, 或者能够找到哈希函数的 (t,ε/2)- 碰撞. 可以将公开参数 PK=(g,g,g 2,v,m 0,m,k) 发给敌手. 敌手可以询问消息 M,M 2,,M q 的签名, 获取消息 M i 对应的签名 σ i =(σ i,,σ i,2 ), 其中 i=,2,,q. 对 i=,2,,q, 令 h i =H k (M i σ i, ). 假设 (M,σ =(σ,σ 2 )) 是伪造的消息 - 签名对, 令 h =H k (M σ ). 将敌手的伪造分成下面两类 : 类型 Ⅰ 伪造 : 存在 i {,2,,q}, 使 h =h i. 类型 Ⅱ 伪造 : 任意 i {,2,,q}, 总有 h h i. 一个成功的敌手必须输出类型 Ⅰ 或者类型 Ⅱ 伪造. 我们将证明类型 Ⅰ 伪造能够用来找到的碰撞 ; 类型 Ⅱ 伪造能够解决计算 Difie Helman 困难假设. 挑战者扮演模拟器的角色, 在模拟开始时扔枚硬币来猜测敌手产生伪造的类型, 并建立相应的模拟. 两种模拟都是完美的. 首先从类型 Ⅰ 伪造开始. 类型 Ⅰ 伪造 : 假设是类型 Ⅰ 敌手, 它攻破新签名方案的 (t,q,ε)- 强不可伪造性. 将构造个模拟器算法, 它以 (t,ε) 找到哈希函数的个碰撞. 算法获得个随机密钥 k. 模拟器的目标是输出一对消息 ( 珚 m, 珚 m 2 ), 使得珚 m 珚 m 2 且 H k ( 珚 m )=H k ( 珚 m 2 ). 执行如下的操作 : 系统建立 : 算法置 k k, 并根据新方案产生公私钥. 将生成的公钥 PK =(g,g,g 2,v,m 0,m, k) 发送给敌手, 并秘密保存私钥 SK. 签名询问 : 敌手自适应地询问 q 个消息 M, M 2,,M q 的签名, 模拟器对消息 M i 运行新签名方案的签名算法, 并返回签名值 σ i =(σ i,,σ i,2 ) 给, 其中 i=,2,,q. 输出 : 输出一个伪造 (M,σ =(σ,σ 2 )) 满足 (M,σ ) {(M,σ ),(M 2,σ 2 ),,(M q, σ q )}, 且存在 i {,2,,q} 使得 h =h i. 具体地, h =h i 意味着 H k (M σ )=H k (M i σ i, ). 模拟器输出哈希函数 H k 的一对碰撞 (M σ,m i σ i, ). 只要敌手能产生个类型 Ⅰ 伪造, 模拟器就能成功找到 H k 的一对碰撞. 由于 h =h i, 也即 H k (M σ )=H k (M i σ i, ), 接下来只需要表明 M σ M i σ i,. 采用反证法证明. 如果有 M σ =M i σ i,, 则有 s =s i,γ =γ i, 从而有 σ i,2 = g2(m α γi v h i ) s i =g 2(m α γ v h =σ 2, 也即存在个 i {,2,,q} 使 (M,σ )=(M i,σ i ) 成立, 这与已知 (M,σ ) {(M,σ ),(M 2,σ 2 ),,(M q,σ q )} 矛盾. 因此,M σ M i σ i,. 下面分析挑战者成功的概率. 如果敌手成功攻破新方案, 则挑战者能找到了哈希函数 H k 的一对碰撞 (M σ,m i σ i, ). 由于敌手成功的概率是 ε, 模拟器没有中断, 选择类型 Ⅰ 的概率是 /2, 所以挑战者成功的概率是 ε/2. 类型 Ⅱ 伪造 : 假设是类型 Ⅱ 敌手, 它攻破新签名方案的 (t,q,ε)- 强不可伪造性. 我们将构造一个模拟器算法, 它解决 (t,ε)- 计算 Difie Hel man 困难假设. 给定元素 g α,g β, 模拟器的目标是计算 g αβ. 执行如下的操作 : 系统建立 : 算法置 g =g α,g 2 =g β, 选择 4 个元素 a,b,c,t p, 令 m 0 =g a,m =g 2g t b, 和 v=g c. 返回公开参数 PK=(g,g,g 2,v,m 0,m,k) 给敌手. 此时不知道私钥 g αβ. 签名询问 : 敌手自适应地询问 q 个消息 M, M 2,,M q 的签名, 虽然模拟器不知道私钥 g αβ, 但仍能模拟 M i 的有效签名值 σ i =(σ i,,σ i,2 ) 并返回给, 其中 i=,2,,q, 操作如下 : ) 随机选择一个 s p, 并计算 σ i, =g - t g s =g s-α t.

4 32 第 34 卷如果 σ i, 的 χ- 坐标的最右边比特是, 那么计算 h i =H k (M i σ i, ), 否则重新选择不同的 s p 使 σ i, 满足上述条件. 这样的 s 总是可以找到的, 因为每次选择使得 σ i, 最右边比特是的概率是 2. g α 2 2) 计算 σ i,2 =g -b+ch t (m v h i ) s. σ i,2 的正确性如下 :σ i,2 =g -b+ch i t (m v h i g -α 2 g - b+ch i t ( )(m v h i g 2(g α 2g t b+ch i g α 2(g t 2g b g ch i g α 2(m v h i g α 2(m v h i ) s-α t. 3) 返回签名值 σ i =(g s,g α 2(m v h i ) s ), 其中 s =s- α t. 输出 : 输出一个伪造 (M,σ =(σ,σ 2 )) 满足 (M,σ ) {(M,σ ),(M 2,σ 2 ),,(M q, σ q )}, 且对任意的 i {,2,,q} 都有 h h i. 如果 σ 的 χ- 坐标的最右边比特是 0, 则继续进行, 否则模拟器终止. 如果不终止, 则此时 m 0 =g a. 算法可以计算 σ σ a+ch 2 = gα 2(m 0 v h (g s 2(m 0 v h ) a+ch = gα (g s ) a (g s ) ch = g2(m α 0 v h (g a (g c ) h =g 2=g α αβ. 这意味着模拟器计算出 CDH 困难问题假设的个实例. 下面分析挑战者成功的概率. 如果敌手成功攻破新方案, 则挑战者能计算出 CDH 困难问题假设的一个实例. 由于敌手成功伪造签名的概率是 ε, 模拟器不中断的概率是 2, 选择伪造类型 Ⅱ 的概率是 2, 所以挑战者成功计算 CDH 困难问 ε 题实例的概率是 4. 4 效率分析在新方案中, 用户私钥包含个群元素, 公钥包含 6 个群元素 ; 签名算法需要 3 次指数运算和 2 次乘法运算, 签名值包含 2 个群元素 ; 验证算法需要 2 次双线性对运算, 次指数运算和次乘 [3,8] 法运算. 与已知的强不可伪造签名算法相比, 新方案具有较大优势, 详见表. 表中表示元素长度,E 表示次指数运算时间,P 表示次双线性对运算时间,n 为哈希输出的长度. 表效率比较方案公私钥签名签名验证长度长度代价代价文献 [3] (n+6) 2 + p 4E 2P+2E 文献 [8] (n+4) 2 + p 5E 2P+3E 文中 7 2 3E 2P+E 5 结论 ) 提出了个强不可伪造的签名方案, 在标准模型下其安全性依赖计算 Difie Helman 困难问题假设. 2) 与现有的方案相比, 文中方案缩短了公 / 私钥长度和签名长度, 降低了签名和验证算法的时间, 提高了效率. 新方案更适用于资源受限的环境. 参考文献 (References) [] GoldwaserS,MicaliS,RivestRL.Adigitalsignature schemesecureagainstadaptivechosen mesagesatacks [J].SIAM JournalonComputing,988,7(2): [2] WatersB.Eficientidentity based encryption without randomoracles[c] ProcedingsoftheAdvancesin Cryptology EUROCRYPT Berlin: Springer Ver lag,2005:4-27. [3] AnJH,DodisY,RabinT.Onthesecurityofjointsig natureandencryption[c] ProcedingsoftheAdvances incryptology EUROCRYPT2002.Berlin:Springer Ver lag,2002: [4] SelviSSD,VivekSS,VinayagamurthyD,etal.ID basedsigncryptionschemeinstandardmodel[c] Procedingsofthe6thInternationalConferenceonPro vablesecurity ProvSec202.Berlin:Springer Verlag, 202: [5] ParkH,Lim S,YieI,etal.Strongunforgeabilityin groupsignatureschemes[j].computerstandards&in terfaces,2009,3(4): [6] ZhangJianhong,LiuXue.AneficientstrongID based signatureschemewithunforgeability[c] Procedings ofthe200fifthinternationalconferenceonfrontierof ComputerScienceand Technology. Piscataway:IEEE ComputerSociety,200: [7] VivekSS,SelviSSD,BalasubramanianG,etal.

5 第 3 期刘振华等 : 标准模型下高效的强不可伪造短签名方案 33 Stronglyunforgeableproxyre signatureschemesinthe standardmodel[eb/ol].[ ].htp: eprint.iacr.org/202/080.pdf,202. [8] BelareM,RogawayP.Theexactsecurityofdigitalsig natures:howtosignwithrsaandrabin[c] Pro cedingsoftheadvancesin Cryptology EUROCRYPT 996.Berlin:Springer Verlag,996: [9] BonehD,LynnB,Shacham H.Shortsignaturesfrom theweilpairing[j].journalofcryptology,2004,7 (4): [0] CramerR,ShoupV.Signatureschemesbasedonthe strongrsaasumption[j].acmtransactionsoninfor mationandsystemsecurity,2000,3(3):6-85. [] GennaroR,HaleviS,RabinT.Securehash and sign signatureswithouttherandomoracle[c] Procedings oftheadvancesincryptology EUROCRYPT999.Ber lin:springer Verlag,999: [2] 祁正华, 杨庚, 任勋益, 等. 标准模型下基于身份的多接收者签密方案 [J]. 江苏大学学报 : 自然科学版, 20,32(5): QiZhenghua,YangGeng,RenXunyi,etal.AnID based signcryption scheme formultiple receiversin standardmodel[j].journalofjiangsuuniversity:na turalscienceedition,20,32(5): (in Chinese) [3] BonehD,ShenE,WatersB.Stronglyunforgeablesig naturesbasedoncomputationaldifie Helman[C] Procedingsofthe9thInternationalConferenceonTheory andpracticeofpublic keycryptography.berlin:sprin ger Verlag,2006: [4] HuangQ,WongDS,LiJ,etal.Generictransforma tionfromweaklytostronglyunforgeablesignatures[j]. JournalofComputerScienceandTechnology,2008,23 (2): [5] SteinfeldR,PieprzykJ,WangHX.Howtostrengthen anyweaklyunforgeablesignatureintoastronglyunfor geablesignature[c] ProcedingsoftheCryptogra phers TrackattheRSAConference.Berlin:Springer Verlag,2007: [6] LiuJK,AuMH,SusiloW,etal.Shortgenerictrans formationtostronglyunforgeablesignatureinthestan dardmodel[c] Procedingsofthe5thEuropean Symposium onresearchincomputersecurity.berlin: Springer Verlag,200:68-8. [7] TeranishiI,OyamaT,OgataW.Generalconversionfor obtaining strongly existentialy unforgeable signatures [C] Procedingsofthe7thInternationalConferenceon Cryptologyin India. Berlin: Springer Verlag, 2006: [8] MatsudaT,AtrapadungN,HanaokaG,etal.Astrong lyunforgeablesignatureunderthecdhasumptionwith outcolisionresistanthashfunction[j].ieicetransac tionsoninformationandsystems,2008,e9-d(5): [9] BonehD,FranklinM.Identity basedencryptionfrom theweilpairing[c] ProcedingsoftheAdvancesin Cryptology.Berlin:Springer Verlag,200: ( 责任编辑梁家峰 )

% %! # % & ( ) % # + # # % # # & & % ( #,. %

!!! # #! # % & % %! # % & ( ) % # + # # % # # & & % ( #,. % , ( /0 ) %, + ( 1 ( 2 ) + %, ( 3, ( 123 % & # %, &% % #, % ( ) + & &% & ( & 4 ( & # 4 % #, #, ( ) + % 4 % & &, & & # / / % %, &% ! # #! # # #