Software Engineering and Applications 软件工程与应用, 2012, 1, 43-46 http://dx.doi.org/10.12677/sea.2012.12008 Published Online December 2012 (http://www.hanspub.org/journal/sea.html) Analysis and Improvement of a Digital Signature Based on Conic Curve over Zn* Junxia Liu1, Xianwen Yang2 1Automatic Command Station, Henan Provincial Military Command, Zhengzhou 2Institute of Electronic Technology, PLA Information Engineering University, Zhengzhou Email: yxw200420042004@163.com Received: Oct. 10th, 2012; revised: Oct. 17th, 2012; accepted: Oct. 28th, 2012 Abstract: Under the analyses of an ElGamal digital signature scheme based on conic curve over Zn proposed by Yang Hui et al., this paper reveals that the secret key can be gained by the public key and the signature, so Yang et al.’s scheme is not security. An improved digital signature scheme is given, and it can resist the secret key gaining attack. Moreover, a multi-signature digital scheme is supplied based on the improved digital signature scheme. The multi- signature digital scheme has the advantage not to exchange many times among singers to get the same parameter, and therefore reduces the communication traffic. Keywords: Conic Curve; Discrete Logarithm; Digital Signature; Multiple Digital Signatures; Communication 对一个环 Zn上圆锥曲线数字签名的分析与改进* 刘军霞 1,杨先文 2 1河南省军区指挥自动化工作站,郑州 2解放军信息工程大学电子技术学院,郑州 Email: yxw200420042004@163.com 收稿日期:2012 年10 月10 日;修回日期:2012 年10 月17 日;录用日期:2012 年10 月28 日 摘 要:杨慧等人基于环 Zn上的圆锥曲线构造了一个 ElGamal 型数字签名方案,文章分析指出,该方案的私钥 可以从公钥和签名中恢复出来,因而该签名方案是不安全的。对杨慧等人的签名方案进行了改进,通过分析可 知改进方案能够抵抗密钥恢复攻击。基于改进数字签名方案构造了一个多重数字签名方案,该多重数字签名方 案无需进行多次交换数据以获得同一个参数,减少了通信量。 关键词:圆锥曲线;离散对数;数字签名;多重数字签名;通信 1. 引言 离散对数问题是公钥密码和数字签名中常用数 学难题之一,上世纪 90 年代提出的圆锥曲线应用于 公钥密码中,可以视其为有限域上离散对数问题的一 个推广。针对有限域 GF(p)上的圆锥曲线 Cp(a, b),1996 年张明志[1]首先引进Cp(a, b)上加法运算 ,并证明了 是一个有限加群。1998年,曹珍富[2]提 出了基于 GF(p)上的圆锥曲线公钥密码体制。2005 年, 孙琦等人[3]将有限域 GF(p)上的圆锥曲线的研究拓展 到环 Zn上,并在其上模拟了数字签名方案。 2007 年,杨慧等人[4]基于环 Zn上的圆锥曲线构造 了一个 ElGamal 数字签名方案,他们综合利用了大数 分解的困难性和有限群上计算离散对数问题的困难 性,试图增强该签名方案的安全性。本文分析指出, 该方案的私钥可以从一组签名消息对和公钥恢复出 来,因此,杨慧等人[4]的数字签名方案没有达到预期 ,, p Cab *基金项目:国家自然科学基金项目(61072047)。 Copyright © 2012 Hanspub 43 对一个环 Zn上圆锥曲线数字签名的分析与改进 的效果。对该签名方案进行了改进,改进后的方案可 抵抗本文关注的密钥恢复攻击,并利用改进方案提出 了一个多重数字签名方案[5]。与现有的ElGamal 广播 多重数字签名相比,本文方案在签名时无需签名者多 次数据交互获得同一参数,因而降低了通信代价。 本文剩下部分如下安排:第 2节介绍环 Zn上圆锥 曲线的基础知识;第3节对杨慧等人的签名方案进行 了分析与改进,改进方案能够抵抗密钥恢复攻击;第 4节基于改进后签名方案,提出了一个多重数字签名 方案,与现有的 ElGamal 多重数字签名方案相比,本 文多重签名方案在签名时无需多次交换数据,减少了 通信量;第 5节对改进后签名方案的安全性进行分析; 第6节结论。 2. 环Zn上的圆锥曲线 设Zn是模 n的剩余类环,定义 Zn上的圆锥曲线 Cn(a, b)为同余方程 modbx n 22 =xya (1) 在Zn上所有解(x, y)构成的集合,其中 n = pq,p, q 为两个不同的大素数,(a, n) = (b, n) = 1,a是模 p的 二次非剩余, b是模 q的二次非剩余,且p + 1= 2r,q + 1 = 2s,其中 r,s是素数,曲线的阶 Nn = 2rs。可以 对圆锥曲线 Cn(a, b)上的点定义一个加法运算 ,圆 锥曲线上点的集合在该加法作用构成一个有限交换 群,在此圆锥曲线上阶为Nn = 2rs 的点 G称为基点。 圆锥曲线上的离散对数问题定义为:由基点 G生成的 群 ,给定 1N G ,,2,SOGG ,n, M NS Gx , n Cab * n 满足 M = eN,则求出正整数 e是非常困难的[4]。该问题被普 遍认为是一个数学困难问题。 3. 杨慧等方案的分析与改进 3.1. 杨慧等签名方案 原方案由参数选取、签名过程和验证过程三部分 构成。 参数选取: 1) 设为曲线 上一点,其阶 为Nn = 2rs,称 G为Cn(a, b)的一个基点; , GG y 2) 设 N dZ为签名私钥,QG 为签名 验证公钥; dmodn * n 3) H(m)是对消息 m的一种安全 Hash 映射; 4) 随机选取一个整数 N kZ ,1 n kN ,且 ; 5) 公开 n, Nn, a, b, G, Q, k作为公钥,私钥为 d。 签名过程: 1) 计算 l,使得kl; 1mod n N 11 1 ,mod n kGx yxN ,; 2) 计算 =dmod n H 3) 计算 mlN ,如果 δ = 0, 则重新选择 k并返回步骤(1),否 则 将 (γ, δ)作为对消息 m的签名发送给收方B。 验证过程: B收到签名(γ, δ)后作如下验证 1) 取 12 mod n uukN , 12 modQuG n modmG n –1 ; 2) 计算Uu 。如果 U = (0, 0)则 拒绝这个签名,否则计算VH 。当且 仅当 U = V时,接受这个签名。 其签名验证证明请参考文献[4]。 3.2. 对杨慧等签名方案的分析 若攻击者能够截获一组消息签名对(m, γ, δ),则攻 击者可以运用 Fermat 小定理求逆法[6]计算出 γ模Nn 的逆元 =dmod n H 。根据签名过程 mlN 可得 –1 =mod n dHmk N (2) 因为明文 m的Hash 值H(m)和公钥 k已知,所以 通过式(2)可恢复私钥 d。因此,杨慧等人[4]提出的数 字签名方案是不安全的。 3.3. 对杨慧等签名方案的改进 原方案安全隐患的根源在于签名过程步骤(1)中l 的不合理选取。事实上,任何一种与公钥有关又未基 于数学难题的选取,都不能保证计算复杂度足够大, 从而也就不能保证方案的安全性。为避免攻击者对私 钥进行恢复,本文对原方案改进如下。 改进方案由参数选取、签名过程、验证过程和签 名验证证明四部分构成。 参数选取: 1) 设 , GG Gxy n 为曲线 Cn(a, b)上一点,其阶为 Nn = 2rs,称 G为Cn(a, b)的一个基点; 2) 设 N dZ为签名私钥, 121 dmod,d modQGnQ Qn为签名验证公钥; 3) H(m)是对消息m的一种安全 Hash映射; Copyright © 2012 Hanspub 44 对一个环 Zn上圆锥曲线数字签名的分析与改进 45 ,1 mod ii QdG n, 4) 随机选取一个整数 n N kZ,且 ,1 n kN ; Copyright © 2012 Hanspub 5) 公开 n, Nn, a, b, G, Q1, Q2, k作为公钥,私钥为 d。 签名过程: 1) 计算 , 11 ,kGx y 1mod n x N ddmodn ; 2) 计算 H mN ,如果 δ = 0, 则重新选择 k并返回步骤(1),否 则 将 (γ, δ)作为对消息 m的签名发送给收方B。 验证过程: B收到签名(γ, δ)后作如下验证 1) 取u1 = γ,u2 = δ; 2) 计算 moduG n 1modmQ n 12 Q 2 Uu 。如果 U = (0, 0) 则拒绝这个签名,否则计算VH。当 且仅当 U = V时,接受这个签名。 签名验证证明: 12 22 1 22 mod dd dd d mod UuQ uGnQ QHm G GHm G dHm GnHm 1 mod dmod mod mod G n n n Q n 1modmQ n 1,2, ,k * n iN dZ 一个私钥,满足条件 ,2,1 mod iii QdQn ,1,2 ij Qj ,其 中为签名公钥,G 为选定圆锥曲线上的基点。UC为消息的收集人,UV 为签名验证人。 收集人与签名人相互验证: ,, ,, mod , iji Cjijij TdQn xy , 1) 每个 Ui计算 ,, mod ij ijn VH 当且仅当 U = V时,接受这个签名。 4. 基于改进方案的多重签名方案 由于数字签名的完整性、不可否认性等特点,数 字签名代替手写签名已经被信息社会逐渐接受。然 而,在许多情况下,一份文件需要多个人进行签名。 作为第 3节改进签名方案的应用,本节提出基于环 Zn 上的圆锥曲线多重数字签名方案,该方案由参数选 取、收集人与签名人相互验证[7]、签名过程、验证过 程、签名验证证明五部分组成。 参数选取: 选择 Zn上的圆锥曲线 Cn(a, b),满足条件同上, 设共有 k个签名人Ui,每个签名者拥有 i x N ,i ,将 j 发给 UC; 2) UC计算 , ,, ,, mod , ijCijijij RdQ nxy ,, mod ij ijn x N ,,ij ij ,若 ** ,,, mod , iCijijij DdQn xy ,则 Ui合法,否则 不合法; 3) UC计算 , * ,, mod ij ijn x N ,ij ,将 发给 Ui; 4) Ui计算 , ** ** ,, ,, mod , iji Cjijij EdQ nxy ** ,, mod ij ijn x N ,,ij ij ,若 ,则 UC合法,否则不 合法。 签名过程: 1) 消息发起人 UI将消息m发给每个签名人 Ui 和消息收集人 UC; 2) Ui选择随机数 11 iin kkN 12 mod kn N 12 ,, , k ,利用 3.3小 节签名过程生成签名(γi, δi),并将其发送给消息收集人 UC; 3) UC利用 3.3小节验证过程验证每个(γi, δi),当 都正确时,计算。若 δ = 0 则要求每个签名人重签,否则将 11,1 2,1,1 mod k QQ n 作为对 消息 m的签名发给验证人 UV。 验证过程: UV首先计算 QQ ,进 而计算: 1modUHmQ n, 1 1,222,2,2mod kk VQ QQn , modWG n , 若三者有为(0, 0),则拒绝该签名;若 modWVnU 成立,则接受该签名,否则拒绝。 签名验证证明: 1,22 2,2,2 21 1,222,2,2 22 111 1 2,1,11 mod mod mod mod mod mod mod kk iii kk kkk iii iii iii k WVnGQQQn mdGQQQn dH mdGdGndH mGn 1 1 k i dH 1, H mQH mQHmQnH mQnU 对一个环 Zn上圆锥曲线数字签名的分析与改进 所以若WV 成立,则接受该签名。 modn U mod n 由签名过程知,签名人把签名直接发给消息收集 人就已完成签名,而同类ElGamal 型签名方案需要签 名人两次发给消息收集人才能完成签名[7,8]。因此,该 签名方案减少了通信量。 5. 改进方案的安全性分析 下面对改进的签名方案进行安全性分析: 1) 若攻击者能够截获一个消息签名对(m, γ, δ), 那么根据签名过程 –d H mdN 0mod n 可得二 次同余方程 2 dd H mN (3) 其中 Nn = 2rs 是一个大整数。由数论知识可得,在仅 已知 Nn而未知其分解的情况下,由式(3)求解 d是一 个困难问题[9]。换言之,攻击者“几乎不可能”通过 消息签名对(m, γ, δ)恢复出私钥 d。因此,改进方案能 够抵抗密钥恢复攻击; 2) 为防止签名重放攻击,可在消息签名过程中设 立时间标志,验证过程中对时间标志进行验证,若发 现时间标志无效,则拒绝该签名; 3) 就目前而言,如果攻击者欲伪造一个有效的签 名(γ, δ),需要求解的问题难度不低于求解基于环 Zn 上圆锥曲线上的离散对数的难度。因此,改进签名方 案能抵抗此类的伪造攻击; 4) 安全运行的前提是确保私钥d不能泄漏,否则 攻击者将很容易地伪造签名值,其后果往往是灾难性 的。为减少私钥 d被盗的损失,可在改进签名方案的 基础上加入前向安全机制[10]。 此外,圆锥曲线上的多重数字签名方案是在改进 签名方案的基础上建立起来的,故与基于改进签名方 案具有相同的安全性。 6. 结论 本文根据环 Zn上的圆锥曲线公钥密码体制,改进 了杨慧的数字签名方案,其安全性基于大数分解的困 难性和环 Zn上圆锥曲线 Cn(a, b)的离散对数问题。作 为改进签名方案的应用,提出了一个多重数字签名方 案。最后,改进签名方案的安全性分析表明改进方案 能抵抗密钥恢复攻击,并对其它安全指标也进行了说 明。作为下一步研究工作,我们将在本文研究基础上 实现其他数字签名方案(如代理签名、群签名和盲签 名)。 参考文献 (References) [1] 张明志. 用圆锥曲线分解整数[J]. 四川大学学报(自然科学 版), 1996, 33(4): 356-359. [2] 曹珍富. 基于有限域 FP上圆锥曲线的公钥密码系统[A]. 密码 学新进展——Chinacrypt’98[C]. 北京: 科学出版社, 1998: 45- 49. [3] 孙琦, 朱文余, 王标 . 环Zn上圆锥曲线和公钥密码协议[J]. 四川大学学报(自然科学版), 2005, 42(3): 471-478. [4] 杨慧, 肖国镇. 基于环 Zn上圆锥曲线的 ElGamal 数字签名方 案[J]. 计算机科学, 2007, 34(6): 98-100. [5] T. C. Wu, S. L. Chou and T. S. Wu. Two-based multisignature protocols for sequential and broadcasting architectures. Co mpute r Communications, 1996, 19(9): 851-856. [6] A. J. Menezes, P. C. Oorschot and S. A. Vanstone. 胡磊, 王鹏, 译. 应用密码学手册[M]. 北京: 电子工业出版社, 2005: 56- 64. [7] 王晓明. 一种多重数字签名方案的安全方案[J]. 南开大学学 报(自然科学版), 2003, 36(1): 33-38. [8] 杜海涛, 张青坡, 钮心忻等. 一个新的离散对数有序多重签 名方案[J]. 计算机工程与应用, 2007, 43(2): 148-150. [9] 潘承洞, 潘承彪. 初等数论[M]. 北京: 北京大学出版社, 2001: 157-176. [10] 杨洁, 钱海峰, 李志斌. 一种具有强前向安全性的代理签名 方案[J]. 计算机工程, 2008, 34(17): 162-166. Copyright © 2012 Hanspub 46 |