论文部分内容阅读
摘要:电子商务的安全性随着电子商务的发展越来越重要。椭圆曲线数字签名是用来保证电子商务安全的技术,在实现身份认证、数据完整性和不可抵赖性等功能方面都有重要作用。椭圆曲线密码体制提供了最高的位安全强度,椭圆曲线数字签名为电子商务安全问题提供一个新的参考。
关键词:ECDLP;数字签名;ECDSA;离散对数
中图分类号:TP311 文献表示码:A文章编号:1009-3044(2010)11-2824-02
Application of ECDSA in the E-Business
LIU Zhi-ping
(Modern Education Technology Centre, Heze University, Heze 274015, China)
Abstract: With the rapid development of E-Business, the security of E-Business looks increasingly important. Signature scheme based on the elliptic curve cryptosystem (ECDSA) is the important technology, and plays an important role in realizing the functions of identification anthentication and data integrity. Elliptic curve cryptosystem provides the highest strength-per-bit. ECDSA provides a new reference for the security of d E-Business.
Key words: ECDLP; digital signature; ECDSA; discrete logarithm
1 椭圆曲线密码体制
椭圆曲线密码是基于椭圆曲线的一种公钥体制。由于基于有限乘法群在离散对数问题的密码体系受到威胁,人们提出了能否用其它有限群来代替有限乘法群。1985年,Neil Koblitz和Victor Miller分别独立提出了以椭圆曲线上的有理点构成的Abel群为背景结构、基于椭圆曲线密码离散对数问题的椭圆曲线密码体制,使用椭圆曲线有限群来代替有限乘法群。利用有限域上椭圆曲线的点构成的Abel群离散对数难解性,实现加密、解密和数字签名,构建椭圆曲线密码体制。椭圆曲线密码体制(ECC)是目前的一个研究热点[1]。椭圆曲线有理点群的结构使得密码体制的参数选择更加灵活,安全性更高。
1.1 椭圆曲线数学定义
椭圆曲线是由维尔斯特拉斯(Weiertrass)方程:
y2 a1xy a3y=x3 a2x2 a4x a6
所确定的平面曲线E。椭圆曲线E上点P(x1,y1)和Q(x2,y2),连接点P和Q交曲线E于另一点,过该点作平行于纵坐标轴的直线与曲线E相交于点R(x3,y3),则R为P和Q两点之和,记为R = P Q,这就是椭圆曲线的加法运算。曲线E上任一点自加,记为2P = P P。对于k个相同点的相加,即P P ... P,可表示为kP,称为点乘或数乘。
1.2 椭圆曲线离散对数问题(ECDLP)
椭圆曲线离散对数的困难性是椭圆曲线密码方案安全性的基础,目前还没有有效的算法解决此问题.。根据椭圆曲线点乘的运算法则,给定有限域上的椭圆曲线E,基点P的阶为n,点Q∈E,寻找一个整数k∈[0, n-1],使得Q=kP。整数k称为Q的基于P的离散对数,该类问题即为椭圆曲线离散对数问题,记为ECDLP。求解ECDLP问题最简单的方法是穷举法,计算P,2P,3P . . . 一直计算得到Q。穷举法运算时间最坏为n步,平均为n/2步,只需要通过选取n足够大的椭圆曲线,穷举法就不可能实现。另外还有Shanks的小步大步算法,该算法预先计算并存储P的倍数,选取整数a,计算Q-aP,Q-2aP,Q-3aP,. . . ,一直到Q-iaP在预存的P的倍数表中出现。已知的最好的攻击方法是Pollard-ρ算法和Pohilg-Hellman算法相结合,该方法把ECDLP问题进行分解,分解之后的ECDLP问题比较容易解决。如果n含有大素数因子,或者n本身就是大素数,该算法计算也是指数级的。
2 椭圆曲线数字签名
2.1 数字签名概念
在现实生活中,签名代表着一个人的身份和许可。在电子商务中,电子信息可以被任意复制和修改,无法直接应用于身份的鉴别,必须运用其它手段对电子信息进行处理,这就是数字签名。如果要满足电子商务安全的需要,数字签名须满足以下要求:1) 签名算法本身是安全的;2) 签名者在对电子信息签名后不能否认自己所做的签名;3) 签名接收者能够验证签名的所属;4) 其他任何人不能伪造签名者的签名;5) 交易双方如果对签名的真假有争议时,第三方能够解决争议。只有满足这些条件,电子商务各方才能有信心参与电子交易,提高效率。
公钥加密算法一个用途是加密,另一个用途就是数字签名。公钥加密算法有两个密钥,一个是公钥,可以对外公开,不要求保密;另一个是私钥,私钥要求保密,不能泄露,且通过公钥不能推算出私钥。公钥与私钥是对应的,由公钥加密的只能是由私钥解开。数字签名是交易一方利用私钥对信息进行加密,交易另一方使用对方公开的公钥进行解密,如果能成功解开,则该信息是对方所发送。由于私钥不公开,只能私钥所有人持有,所以也不能否认自己发送的信息。
2.2 椭圆曲线数字签名
电子商务中常用的公钥加密算法是RSA,对电子信息进行数字签名也是用RSA。由于椭圆曲线密码系统的密钥短、速度快的优势,采用椭圆曲线密码系统的也越来越多。在椭圆曲线密码系统中,数字签名算法为椭圆曲线数字签名算法(ECDSA) [2]。该算法公布椭圆曲线的各个参数,包括有限域的阶、椭圆曲线上的基点、基点的阶及椭圆曲线的各个系数等,另外还包括摘要算法。
假设椭圆曲线基点为G (x1, y1)。交易方A发送给交易方B签名信息时,椭圆曲线数字签名如下[3]:
A生成签名:
1)选择随机整数k [1,n-1];
2)计算R=kG (x1, y1);
3)计算r=Rx mod n (Rx是R的横坐标),若r=0,则返回(1);
4)计算信息摘要e;
5)计算s=k-1(e rd) mod n,d为A的私钥,若s=0,则返回(1);
6)(r, s)是信息的签名,A把签名传送给B。
B收到签名(r,s)后,验证签名:
1)验证r和s 是否为[1,n-1]内的正整数;
2)计算信息摘要e;
3)取得A的公钥Q;
4)计算w=s-1 mod n;
5)计算u=ew mod n;
6)计算v=rw mod n;
7)计算T=uG vQ;
8)如果T=O,拒绝签名;否则计算v=Tx mod n (Tx是T的横坐标);
9)当v=r时,接受签名。
3 总结
随着我国推进电子商务力度的加强和网络的飞速发展,电子商务已成为一种趋势,其安全性问题越来越受到人们的关注。作为已知公钥密码体制中最高安全强度的ECC克服了以往公钥系统速度慢的缺陷,能在32位的PC机上快速实现。ECC是密码学界普遍看好的、有望取代RSA,成为下一代通用的公钥密码体制。ECDSA是由IEEE工作组和ANSI X9组织开发的快速签名方案。32位的ECDSA算法的签名安全强度相当于1024位的RSA。将ECDSA算法应用于电子商务身份认证系统中,可以有效的提高身份认证的安全性和可靠性,ECDSA也必将是数字签名技术今后的应用热点和技术主流。
参考文献:
[1] 徐秋亮,李大兴.椭圆曲线密码体制[J].计算机研究与发展,1999(11):1281-1288.
[2] 孙家泽,张荣.椭圆曲线数字签名软件设计与实现[J].西安邮电学院学报,2008(9).
[3] 罗涛,易波.关于椭圆曲线数字签名算法研究[J].计算机工程与应用,2003(29).
关键词:ECDLP;数字签名;ECDSA;离散对数
中图分类号:TP311 文献表示码:A文章编号:1009-3044(2010)11-2824-02
Application of ECDSA in the E-Business
LIU Zhi-ping
(Modern Education Technology Centre, Heze University, Heze 274015, China)
Abstract: With the rapid development of E-Business, the security of E-Business looks increasingly important. Signature scheme based on the elliptic curve cryptosystem (ECDSA) is the important technology, and plays an important role in realizing the functions of identification anthentication and data integrity. Elliptic curve cryptosystem provides the highest strength-per-bit. ECDSA provides a new reference for the security of d E-Business.
Key words: ECDLP; digital signature; ECDSA; discrete logarithm
1 椭圆曲线密码体制
椭圆曲线密码是基于椭圆曲线的一种公钥体制。由于基于有限乘法群在离散对数问题的密码体系受到威胁,人们提出了能否用其它有限群来代替有限乘法群。1985年,Neil Koblitz和Victor Miller分别独立提出了以椭圆曲线上的有理点构成的Abel群为背景结构、基于椭圆曲线密码离散对数问题的椭圆曲线密码体制,使用椭圆曲线有限群来代替有限乘法群。利用有限域上椭圆曲线的点构成的Abel群离散对数难解性,实现加密、解密和数字签名,构建椭圆曲线密码体制。椭圆曲线密码体制(ECC)是目前的一个研究热点[1]。椭圆曲线有理点群的结构使得密码体制的参数选择更加灵活,安全性更高。
1.1 椭圆曲线数学定义
椭圆曲线是由维尔斯特拉斯(Weiertrass)方程:
y2 a1xy a3y=x3 a2x2 a4x a6
所确定的平面曲线E。椭圆曲线E上点P(x1,y1)和Q(x2,y2),连接点P和Q交曲线E于另一点,过该点作平行于纵坐标轴的直线与曲线E相交于点R(x3,y3),则R为P和Q两点之和,记为R = P Q,这就是椭圆曲线的加法运算。曲线E上任一点自加,记为2P = P P。对于k个相同点的相加,即P P ... P,可表示为kP,称为点乘或数乘。
1.2 椭圆曲线离散对数问题(ECDLP)
椭圆曲线离散对数的困难性是椭圆曲线密码方案安全性的基础,目前还没有有效的算法解决此问题.。根据椭圆曲线点乘的运算法则,给定有限域上的椭圆曲线E,基点P的阶为n,点Q∈E,寻找一个整数k∈[0, n-1],使得Q=kP。整数k称为Q的基于P的离散对数,该类问题即为椭圆曲线离散对数问题,记为ECDLP。求解ECDLP问题最简单的方法是穷举法,计算P,2P,3P . . . 一直计算得到Q。穷举法运算时间最坏为n步,平均为n/2步,只需要通过选取n足够大的椭圆曲线,穷举法就不可能实现。另外还有Shanks的小步大步算法,该算法预先计算并存储P的倍数,选取整数a,计算Q-aP,Q-2aP,Q-3aP,. . . ,一直到Q-iaP在预存的P的倍数表中出现。已知的最好的攻击方法是Pollard-ρ算法和Pohilg-Hellman算法相结合,该方法把ECDLP问题进行分解,分解之后的ECDLP问题比较容易解决。如果n含有大素数因子,或者n本身就是大素数,该算法计算也是指数级的。
2 椭圆曲线数字签名
2.1 数字签名概念
在现实生活中,签名代表着一个人的身份和许可。在电子商务中,电子信息可以被任意复制和修改,无法直接应用于身份的鉴别,必须运用其它手段对电子信息进行处理,这就是数字签名。如果要满足电子商务安全的需要,数字签名须满足以下要求:1) 签名算法本身是安全的;2) 签名者在对电子信息签名后不能否认自己所做的签名;3) 签名接收者能够验证签名的所属;4) 其他任何人不能伪造签名者的签名;5) 交易双方如果对签名的真假有争议时,第三方能够解决争议。只有满足这些条件,电子商务各方才能有信心参与电子交易,提高效率。
公钥加密算法一个用途是加密,另一个用途就是数字签名。公钥加密算法有两个密钥,一个是公钥,可以对外公开,不要求保密;另一个是私钥,私钥要求保密,不能泄露,且通过公钥不能推算出私钥。公钥与私钥是对应的,由公钥加密的只能是由私钥解开。数字签名是交易一方利用私钥对信息进行加密,交易另一方使用对方公开的公钥进行解密,如果能成功解开,则该信息是对方所发送。由于私钥不公开,只能私钥所有人持有,所以也不能否认自己发送的信息。
2.2 椭圆曲线数字签名
电子商务中常用的公钥加密算法是RSA,对电子信息进行数字签名也是用RSA。由于椭圆曲线密码系统的密钥短、速度快的优势,采用椭圆曲线密码系统的也越来越多。在椭圆曲线密码系统中,数字签名算法为椭圆曲线数字签名算法(ECDSA) [2]。该算法公布椭圆曲线的各个参数,包括有限域的阶、椭圆曲线上的基点、基点的阶及椭圆曲线的各个系数等,另外还包括摘要算法。
假设椭圆曲线基点为G (x1, y1)。交易方A发送给交易方B签名信息时,椭圆曲线数字签名如下[3]:
A生成签名:
1)选择随机整数k [1,n-1];
2)计算R=kG (x1, y1);
3)计算r=Rx mod n (Rx是R的横坐标),若r=0,则返回(1);
4)计算信息摘要e;
5)计算s=k-1(e rd) mod n,d为A的私钥,若s=0,则返回(1);
6)(r, s)是信息的签名,A把签名传送给B。
B收到签名(r,s)后,验证签名:
1)验证r和s 是否为[1,n-1]内的正整数;
2)计算信息摘要e;
3)取得A的公钥Q;
4)计算w=s-1 mod n;
5)计算u=ew mod n;
6)计算v=rw mod n;
7)计算T=uG vQ;
8)如果T=O,拒绝签名;否则计算v=Tx mod n (Tx是T的横坐标);
9)当v=r时,接受签名。
3 总结
随着我国推进电子商务力度的加强和网络的飞速发展,电子商务已成为一种趋势,其安全性问题越来越受到人们的关注。作为已知公钥密码体制中最高安全强度的ECC克服了以往公钥系统速度慢的缺陷,能在32位的PC机上快速实现。ECC是密码学界普遍看好的、有望取代RSA,成为下一代通用的公钥密码体制。ECDSA是由IEEE工作组和ANSI X9组织开发的快速签名方案。32位的ECDSA算法的签名安全强度相当于1024位的RSA。将ECDSA算法应用于电子商务身份认证系统中,可以有效的提高身份认证的安全性和可靠性,ECDSA也必将是数字签名技术今后的应用热点和技术主流。
参考文献:
[1] 徐秋亮,李大兴.椭圆曲线密码体制[J].计算机研究与发展,1999(11):1281-1288.
[2] 孙家泽,张荣.椭圆曲线数字签名软件设计与实现[J].西安邮电学院学报,2008(9).
[3] 罗涛,易波.关于椭圆曲线数字签名算法研究[J].计算机工程与应用,2003(29).