论文部分内容阅读
摘 要: 基于Ellipse曲线的密码体制是最近发展起来的安全性能较好的一种体制,在一定程度上代表着公钥密码体制的发展方向。本文阐述了Ellipse曲线的基础,密钥对的生成,ECIES加解密方案,以及ECDSA签名验证方案。
关键词: Ellipse曲线公钥密码 密钥对 ECIES加密方案 ECDSA签名
前言
目前影响最大的三类公钥密码是RSA公钥密码、ElGamal公钥密码和Ellipse曲线公钥密码,前者是在20世纪70年代中期提出的,其安全性依赖于大整数的因子分解的困难性,而后两者的安全性分别依赖于有限域和椭圆曲线离散对数的难度。Ellipse曲线公钥密码是1985年由Koblitz(美国华盛顿大学)和Victor Miller(IBM)提出来的,它具有一些其它公钥密码无法比拟的优势,如密钥短、占用带宽、存储空间少,单位密钥安全性高等,越来越受到人们的关注,有着广阔的应用前景。
1.Ellipse曲线基础
Ellipse曲线指的是由威尔斯特拉斯(Weierstrass)方程:
y+axy+ay=x+ax+ax+a(1)
所确定的平面曲线。
常用于密码系统的基于有限域GF(p)上的椭圆曲线是由方程:
y≡x+ax+b(mod p)(2)
所确定的,外加一个无穷远点o,它并不在Ellipse曲线上,表示为o=(x,+∞)。其中a、b、x、y均在GF(p)上取值,且有4a+27b≠0,p是大于3的素数。
在等式
mp=p+p+…+p=Q(3)
中,已知m和点P求Q比较容易,反之已知Q和点p求m却是很难的,这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计出来的。
2.密钥对的生成
Ellipse曲线密钥对与参数组D=(q,FR,S,a,b,P,n,h)中的一系列参数相关。在由P生成的群{P}上随机选择点Q作为公钥。相应的私钥是d=logQ。要生成密钥对的实体A必须保证参数组是合法的。参数组和公钥间的关系必须能被所有随后可能用到A的公钥的通信实体所检验。
输入:参数组D=(q,FR,S,a,b,P,n,h)。
输出:公钥Q,私钥d。
1)选择d∈[1,n-1]。
2)计算Q=dp。
3)返回(Q,d)。
从公钥Q计算私钥d的问题显然就是椭圆曲线离散对数问题。至关重要的是参数组D的选择要使得椭圆曲线离散对数问题不可求解。
3.ECIES加密方案
椭圆曲线加密方案(ECIES)由Bellare和Rogaway提出,是ElGamal公钥加密方案的一种变体。在ECIEC中,使用Diffie-Hellman共享秘密来产生两个对称密钥k和k。密钥k用于对称密钥密码中加密明文,而用于对得出的密文进行认证。
3.1 ECIES加密
输入:参数组D=(q,FR,S,a,b,P,n,h),公钥Q,明文m。
输出:密文(R,C,t)。
1)计算k∈[1,n-1]。
2)计算R=kP和Z=hkQ。若Z=+∞则跳至第一步。
3)(k,k)←KDF(x,R),其中x是Z的x坐标。
4)计算C=E(m)和t=MACC。
5)返回(R,C,t)。
其中KDF是由杂凑函数H构成的密钥导出函数。若需要生成一个长度为l比特的密钥,则将KDF(S)定义为杂凑值H(S,i)的级联,其中i是计数器,当每个杂凑函数得出结果后增一,直到产生l比特的杂凑值为止。E是对称密钥加密方案中的加密函数,而AES、D则是解密函数。MAC是消息认证码算法。
3.2 ECIES解密
输入:参数组D=(q,FR,S,a,b,P,n,h),私钥d,密文(R,C,t)。
输出:明文m或者拒绝该密文。
1)对R进行嵌入的公钥确认。若确认失败,则返回(“拒绝该密文”)。
2)计算Z=hkR。若Z=+∞则返回(“拒绝该密文”)。
3)(k,k)←KDF(x,R),其中x是Z的x坐标。
4)计算t′=MAC(C)。若t′≠t,则返回(“拒绝该密文”)。
5)计算m=D(c)。
6)返回(m)。
解密工作的证明:若密文(R,C,t)确实是由合法的加密者加密明文m产生的,则
hkR=hd(kP)=hk(dP)=hkQ,
于是解密者同加密者计算出同样的密钥(R,R),接受该密文并解密出m。
4.ECDSA签名
椭圆曲线签名算法(ECDSA)是数字签名算法(DSA)的椭圆曲线版本。
4.1 ECDSA签名的生成
输入:参数组D=(q,FR,S,a,b,P,n,h),私钥d,消息m。
输出:签名(r,s)。
1)选择k∈[1,n-1]。
2)计算kP=(x,y)并将x转换为整数。
3)计算r=mod n。若r=0,则跳至第一步。
4)计算e=H(m)。
5)计算s=k(e+dr)mod n。若s=0,则跳至第一步。
6)返回(r,s)。
其中H表示一个密码杂凑函数,其输出长度不超过n比特。
4.2 ECDSA签名的验证
输入:参数组D=(q,FR,S,a,b,P,n,h),公钥Q,消息m,签名(r,s)。
输出:判断签名是否合法。
1)检验r和s是否是区间[1,n-1]内的整数。若任何一个检验失败,则返回(“拒绝该签名”)。
2)计算e=H(m)。
3)计算w=smod n。
4)计算u=ew mod n和u=rw mod n。
5)计算X=uP+uQ。
6)若X=+∞,则返回(“拒绝该签名”)。
7)将X的x坐标x转换为整数;计算v=mod n。
8)若v=r,则返回(“接受该签名”);否则,返回(“拒绝该签名”)。
签名验证工作的证明:若一条消息的签名(r,s)确实是由合法的签名者生成的,则s≡k(e+dr)(mod n),
重新整理可得k≡s(e+dr)≡se+srd≡we+wrd≡u+ud(mod n),
于是X=uP+uQ=(u+ud)P=kP,因此v=r即为所需。
数字签名的加密解密过程和秘密密钥的加密解密过程都使用公开密钥体系。数字签名使用的是发送方的密钥对,发送方用自己的私有密钥进行加密,接收方用发送方的公开密钥进行解密。在实用过程中,通常一个用户拥有两个密钥对,一个密钥对用来对数字签名进行加密解密,一个密钥对用来对秘密密钥进行加密解密。这种方式提供了更高的安全性。加密钥匙是公开的,密钥的分配和管理就很简单,而且能够很容易地实现数字签名。
5.结语
Ellipse加密算法作为一种密码系统,它比RSA,DSA具有更高的安全强度,Ellipse加密算法只有亚指数时间算法。其由于所需要的密钥较短、计算量小、处理速度快及占用存储空间小等优点,正广泛应用于电子商务、电子政务等领域之中,Ellipse加密算法取代RSA和DSA是个必然的趋势。如何高效地实现椭圆曲线密码系统是当前密码学研究的热点,它必将有着广阔而实际的应用前景。
参考文献:
[1][加]Darrel Hankerson著.张焕国等译.椭圆曲线密码学导论[M].北京:电子工业出版社,2005.
[2][德]Andreas Enge著.吴铤,董军武等译.椭圆曲线及其在密码学中的应用——导引[M].北京:科学出版社,2007.
[3]滕艳平.基于非对称密钥体制Ellipse曲线加密算法的应用研究[D].吉林大学,2007.
[4]宋金秀,杨秋翔.椭圆曲线密码体制的研究与探讨[J].山西农业大学学报,2008,28,(2).
[5]宋国琴.椭圆曲线密码体制ECC[J].电脑开发与应用,2008,21,(8).
[6]张楠,张建华,吴兵,陈建英,傅春常.基于椭圆曲线密码体制的数字签名[J].西安民族大学学报,2007,33,(1).
关键词: Ellipse曲线公钥密码 密钥对 ECIES加密方案 ECDSA签名
前言
目前影响最大的三类公钥密码是RSA公钥密码、ElGamal公钥密码和Ellipse曲线公钥密码,前者是在20世纪70年代中期提出的,其安全性依赖于大整数的因子分解的困难性,而后两者的安全性分别依赖于有限域和椭圆曲线离散对数的难度。Ellipse曲线公钥密码是1985年由Koblitz(美国华盛顿大学)和Victor Miller(IBM)提出来的,它具有一些其它公钥密码无法比拟的优势,如密钥短、占用带宽、存储空间少,单位密钥安全性高等,越来越受到人们的关注,有着广阔的应用前景。
1.Ellipse曲线基础
Ellipse曲线指的是由威尔斯特拉斯(Weierstrass)方程:
y+axy+ay=x+ax+ax+a(1)
所确定的平面曲线。
常用于密码系统的基于有限域GF(p)上的椭圆曲线是由方程:
y≡x+ax+b(mod p)(2)
所确定的,外加一个无穷远点o,它并不在Ellipse曲线上,表示为o=(x,+∞)。其中a、b、x、y均在GF(p)上取值,且有4a+27b≠0,p是大于3的素数。
在等式
mp=p+p+…+p=Q(3)
中,已知m和点P求Q比较容易,反之已知Q和点p求m却是很难的,这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计出来的。
2.密钥对的生成
Ellipse曲线密钥对与参数组D=(q,FR,S,a,b,P,n,h)中的一系列参数相关。在由P生成的群{P}上随机选择点Q作为公钥。相应的私钥是d=logQ。要生成密钥对的实体A必须保证参数组是合法的。参数组和公钥间的关系必须能被所有随后可能用到A的公钥的通信实体所检验。
输入:参数组D=(q,FR,S,a,b,P,n,h)。
输出:公钥Q,私钥d。
1)选择d∈[1,n-1]。
2)计算Q=dp。
3)返回(Q,d)。
从公钥Q计算私钥d的问题显然就是椭圆曲线离散对数问题。至关重要的是参数组D的选择要使得椭圆曲线离散对数问题不可求解。
3.ECIES加密方案
椭圆曲线加密方案(ECIES)由Bellare和Rogaway提出,是ElGamal公钥加密方案的一种变体。在ECIEC中,使用Diffie-Hellman共享秘密来产生两个对称密钥k和k。密钥k用于对称密钥密码中加密明文,而用于对得出的密文进行认证。
3.1 ECIES加密
输入:参数组D=(q,FR,S,a,b,P,n,h),公钥Q,明文m。
输出:密文(R,C,t)。
1)计算k∈[1,n-1]。
2)计算R=kP和Z=hkQ。若Z=+∞则跳至第一步。
3)(k,k)←KDF(x,R),其中x是Z的x坐标。
4)计算C=E(m)和t=MACC。
5)返回(R,C,t)。
其中KDF是由杂凑函数H构成的密钥导出函数。若需要生成一个长度为l比特的密钥,则将KDF(S)定义为杂凑值H(S,i)的级联,其中i是计数器,当每个杂凑函数得出结果后增一,直到产生l比特的杂凑值为止。E是对称密钥加密方案中的加密函数,而AES、D则是解密函数。MAC是消息认证码算法。
3.2 ECIES解密
输入:参数组D=(q,FR,S,a,b,P,n,h),私钥d,密文(R,C,t)。
输出:明文m或者拒绝该密文。
1)对R进行嵌入的公钥确认。若确认失败,则返回(“拒绝该密文”)。
2)计算Z=hkR。若Z=+∞则返回(“拒绝该密文”)。
3)(k,k)←KDF(x,R),其中x是Z的x坐标。
4)计算t′=MAC(C)。若t′≠t,则返回(“拒绝该密文”)。
5)计算m=D(c)。
6)返回(m)。
解密工作的证明:若密文(R,C,t)确实是由合法的加密者加密明文m产生的,则
hkR=hd(kP)=hk(dP)=hkQ,
于是解密者同加密者计算出同样的密钥(R,R),接受该密文并解密出m。
4.ECDSA签名
椭圆曲线签名算法(ECDSA)是数字签名算法(DSA)的椭圆曲线版本。
4.1 ECDSA签名的生成
输入:参数组D=(q,FR,S,a,b,P,n,h),私钥d,消息m。
输出:签名(r,s)。
1)选择k∈[1,n-1]。
2)计算kP=(x,y)并将x转换为整数。
3)计算r=mod n。若r=0,则跳至第一步。
4)计算e=H(m)。
5)计算s=k(e+dr)mod n。若s=0,则跳至第一步。
6)返回(r,s)。
其中H表示一个密码杂凑函数,其输出长度不超过n比特。
4.2 ECDSA签名的验证
输入:参数组D=(q,FR,S,a,b,P,n,h),公钥Q,消息m,签名(r,s)。
输出:判断签名是否合法。
1)检验r和s是否是区间[1,n-1]内的整数。若任何一个检验失败,则返回(“拒绝该签名”)。
2)计算e=H(m)。
3)计算w=smod n。
4)计算u=ew mod n和u=rw mod n。
5)计算X=uP+uQ。
6)若X=+∞,则返回(“拒绝该签名”)。
7)将X的x坐标x转换为整数;计算v=mod n。
8)若v=r,则返回(“接受该签名”);否则,返回(“拒绝该签名”)。
签名验证工作的证明:若一条消息的签名(r,s)确实是由合法的签名者生成的,则s≡k(e+dr)(mod n),
重新整理可得k≡s(e+dr)≡se+srd≡we+wrd≡u+ud(mod n),
于是X=uP+uQ=(u+ud)P=kP,因此v=r即为所需。
数字签名的加密解密过程和秘密密钥的加密解密过程都使用公开密钥体系。数字签名使用的是发送方的密钥对,发送方用自己的私有密钥进行加密,接收方用发送方的公开密钥进行解密。在实用过程中,通常一个用户拥有两个密钥对,一个密钥对用来对数字签名进行加密解密,一个密钥对用来对秘密密钥进行加密解密。这种方式提供了更高的安全性。加密钥匙是公开的,密钥的分配和管理就很简单,而且能够很容易地实现数字签名。
5.结语
Ellipse加密算法作为一种密码系统,它比RSA,DSA具有更高的安全强度,Ellipse加密算法只有亚指数时间算法。其由于所需要的密钥较短、计算量小、处理速度快及占用存储空间小等优点,正广泛应用于电子商务、电子政务等领域之中,Ellipse加密算法取代RSA和DSA是个必然的趋势。如何高效地实现椭圆曲线密码系统是当前密码学研究的热点,它必将有着广阔而实际的应用前景。
参考文献:
[1][加]Darrel Hankerson著.张焕国等译.椭圆曲线密码学导论[M].北京:电子工业出版社,2005.
[2][德]Andreas Enge著.吴铤,董军武等译.椭圆曲线及其在密码学中的应用——导引[M].北京:科学出版社,2007.
[3]滕艳平.基于非对称密钥体制Ellipse曲线加密算法的应用研究[D].吉林大学,2007.
[4]宋金秀,杨秋翔.椭圆曲线密码体制的研究与探讨[J].山西农业大学学报,2008,28,(2).
[5]宋国琴.椭圆曲线密码体制ECC[J].电脑开发与应用,2008,21,(8).
[6]张楠,张建华,吴兵,陈建英,傅春常.基于椭圆曲线密码体制的数字签名[J].西安民族大学学报,2007,33,(1).