椭圆曲线数字签名（精选9篇）
椭圆曲线数字签名 篇1
摘要：信息安全是WebGIS、电子政务等领域的主要技术问题之一。基于椭圆曲线加密(ECC)的门限密码数字签名体制是近年信息安全领域中的研究热点．本文对基于椭圆曲线的门限数字签名机制进行深入研究，并对它们的有效性及安全性进行系统分析，研究表明椭圆曲线的特点决定椭圆曲线门限签名具有门限签名的正确、安全、可检验、防欺骗等特点．
关键词：门限签名,认证,可信中心
0前言
随着网络的迅速发展和普遍使用,网络信息安全已成为国家安全的战略性问题。WebGIS是以网络为基础的GIS技术,因此如何保证WebGIS的信息安全是WebGIS应用的一个重要技术问题。
基于椭圆曲线(ECC)的门限密码数字签名体制是近年信息安全领域中的研究热点之一。它主要是利用椭圆曲线上有理点组成的代数系统中离散对数问题的难解性来实现对非法入侵的防卫,从而达到信息安全。它的安全性不仅依赖于ECC的选取和它的体制,而且也依赖于ECC上的有理点组成的代数系统中离散对数问题的难解性,这与有限域上的离散对数或整数分解问题的情形不同。目前对ECC已知最好的离散对数算法需要指数时间,这就意味着ECC实现密码算法可以用较小的数来达到使用更大的有限域所获得的安全性。另一方面,ECC密码体制比RSA等有限域的公钥体制要快得多,这无疑提高ECC密码体制的吸引力[1]。随着大整数分解和并行处理技术的发展,当前采用的公钥体制必须进一步加长密钥,这将使其速度更慢、实现更复杂,而ECC则可用较小的开销(所需的计算量、存储量、带宽等)实现较高的安全性。预期能够在WebGIS,电子商务、电子政务等重要信息的加密存储及加密传输,以及决策者的数字签名与验证中提供很好的应用。
本文首先对秘密共享与群体密码学及相关知识进行概述,在此基础上对几种典型的基于椭圆曲线的门限数字签名机制进行深入研究,并对它们的有效性及安全性进行系统分析。
1 秘密共享与群体密码学概述
秘密共享[2,3]是由A.Shamir和G.R.Blakley于1979年各自独立提出的一个重要的密码学概念,在密钥管理、多方安全计算、密钥托管等方面有重要作用。所谓秘密共享,是指将一个秘密S以某种方式划分成若干个子秘密S1,S2,…,Sn,这n个子等密称作秘密S的部分份额(Share),分别由n个参与者P1,P2…,Pn掌管,参与者集合P={P1,P2,…,Pn}的某些指定子集可以通过出示其掌握的子秘密重构秘密S;而P的其他任何子集都不能得到秘密S的任何有用信息。对于一个秘密共享方案,参与者集合P的可重构秘密的所有子集的集合称作该方案的“访问结构(access structure)”,P的其他子集(即这些子集不可重构秘密,也不能得到有关秘密的任何有用信息)的集合称作该方案的“禁止结构(forbidden structure)”[4]。对一个具有n个参与者的秘密共享方案,如果其访问结构为其参与者集合P的所有元素大于等于t(1≤t≤n)的子集的全体,即任何大于或等于t个子秘密拥有者可重构秘密S,而任何小于或等于t-1个子秘密拥有者不能得到秘密S的任何信息,则称秘密共享方案为(t,n)门限方案,它是门限密码学中最简单、常用的秘密共享方案。
群体密码学[5]由Desmedt于1987年提出,是面向社团或群体的密码体制。在群体密码中,群体外的人可以使用群体的唯一群公钥,向群体发送加密信息,而只有群体中的某些子集成员合作才能解密这些信息。同样,群体密码学中也有群体签名问题,群体外的用户只需知道群体的唯一公开密钥就可以验证该签名。门限数字签名是群体密码学的一个重要分支,特别适用电子政务的某些安全要求。其方法是将一个群体的签名密钥颁发给群体中的每个成员,使得任何成员个数大于或等于门限值的子集可以产生签名;而任何成员个数小于门限值的子集都无法产生签名。
2 基于ECC的EIGamal数字签名方案
2.1 ECC的基本知识
给定任一有限域Fq,q为大素数,定义了Fq上的ECC,在密码学中使用的是曲线上的整数离散点,所有这些整数点都包含在某一个区域内部,区域越大,曲线的安全性越高;区域越小,计算速度越快,但安全性降低。
以有限域F(p)上的ECC:y2=x3+ax+b为例,p和q是两个大素数,P是ECC上的基点,其阶数为q。p、q、ECC和P都是公开的,Zq为有限域。
2.2 基于ECC的ElGamal数字签名方案
ElGamal签名体制由T.ElGamal在1985年提出[6],其修正形式已被美国NIST作为数字签名标准(DSS)。设待签名的消息为m,用户A、B分别为签名者和验证者,其数字签名方案如下:
(1)密钥产生。
用户A产生密钥对,①随机选取密钥d,d∈Zq。②计算点Q=d×P。③A的公钥是(ECC,P,q,Q),私钥为d。
(2)签名产生。
用户A对消息m进行签名,①随机选取整数k,k∈[1,q-1]。②计算k×P=(x,y),令r=x(mod q),若r=0,则转步骤①。③计算s=dr+kh(m)(modq),若s=0,则转步骤①。④(r,s)为用户A对消息m的数字签名。
(3)签名验证。
用户B验证用户A的数字签名(r,s),①获得A的公钥(ECC、P、q、Q),验证r和s都是区间[1,q-1]上的整数。②计算(x',y,)=s×h(m)-1P-rh(m)-1 Q。③若x'=r(mod q),则接受签名;否则拒绝。
3 基于ECC的门限数字签名方案
建立在ECC上门限数字签名方案[7],密钥需要n个参与者一起秘密生成。设D表示秘密处理者,G={P1,...,Pn}表示签名者群体,此门限签名由密钥产生协议和签名发布协议组成。密钥产生协议由D执行。在签名发布协议里,若签名者子集T是G的子集,并且T中包含t或t个以上诚实的签名者,则能够发布签名(r,s)。而任何小于等于(t-1)个不诚实的签名者不能伪造有效签名。
3.1 密钥产生协议
D产生随机整数d(1≤d≤q-1)作为签名者群体G共享的密钥,公钥为Q=dG。D按密钥共享方案将密钥d分割成多种组合,d的每种组合都与包含t个不同的签名者子集相对应。
3.2 签名发布协议
(1)从G中选择t个签名者P1,P2,…,Pt,设这t个签名者根据对应的组合各自决定使用的影子分别为d1,…,dt,有。
(2)每个签名者Pi(1≤i≤t)计算并广播Qi=tiP。
(3)每个签名者Pi(1≤i≤t)产生一随机数ki(1≤ki≤q-1),计算并广播Ri=kiP。
(4)每个签名者Pi(l≤i≤t)计算(每个Pi计算出来的(x,y)值都相同)。
(5)每个签名者Pi(1≤i≤t)计算r=x(mod q),si=dir+kih(m)(mod q),并广播si。
(6)对于1≤j(≠i)≤t,每个签名者Pi(1≤i≤t)验证Rj=sj h(m)-1P-r(m)-1Qj是否成立。如果不成立,则拒绝Pj并停止。
(7)每个签名者Pi(i∈S)计算,然后输出(r,s)作为签名者群体的数字签名。
3.3 签名协议的有效性分析
设,对上述协议的数字签名(r,s)分析如下:
(1)由第(5)步可得r=x(mod q);由第(4)步、第(5)步可得。所以x是点kP的x坐标。
(2)由于h(m))(由第(5)步)=dr+kh(m)(由第(1)步)。所以,s=dr+kh(m)(mod q)。
可见,上述签名协议产生的签名(r,s)同基于ECC的ElGamal数字签名方案生成的签名形式完全相同,签名(r,s)的验证也同基于ECC的ElGamal签名验证的方法相同,因此本方案是有效的。
4 基于ECC的可验证门限签名方案
基于ECC的可验证(t,n)门限签名方案包含两个过程[1],秘密共享过程和门限签名过程。秘密共享过程利用可信中心的可验证秘密共享方案,门限签名以ElGamal签名为基础,并设有一名非签名的群服务员A,负责收集和验证签名成员的签名,把消息m和最终的签名(r,s)发送给接收方。令P1,P2,…,Pn为n个秘密共享者。
4.1 基于ECC的可验证门限签名机制
可验证签名过程如下:
第(1)步由签名者Pi1,Pi2,…,Pit对消息m进行门限签名,B={i1 i2,…,it}。同时对每位签名者Pi(i∈B)计算ei,B=ai,B ti,Qi=ei,BP,其中,并向群服务员A公开Qi其中
第(2)步每位签名者Pi(i∈B)任选一随机数ki≤ki≤q-1),计算Ri=kiP并向B中的成员公开Ri。并计算。
第(3)步,每位签名者Pi(i∈B)计算r=x-h(m)(modq),si=ei,Br+ki(modq),并把(r,si)发送给服务员A。
第(4)步,群服务员A对所有的j∈B验证Rj=sjP-rQj。若成立,计算,然后把消息m连同群签名(r,s)发送给接收方。若不成立,拒绝Pi,并停止。
4.2 可验证签名协议的有效性分析
由上述门限签名过程的第(2)步知,又由第(3)步知r=x-h(m)(nod q)显然成立。
另一方面,
(由拉格朗日公式知)。即上述签名(r,s)满足r=x-h(m)(mod g)和s=dr+k(mod q)。其中x满足(x,y)=kP,d是系统密钥(公钥Q=dP),。
可见,上述签名协议产生的签名(r,s)同基于ECC的ElGamal数字签名方案生成的签名形式完全相同,签名(r,s)的验证也同基于ECC的ElGamal签名验证的方法相同,因此本方案是有效的。
4.3 安全性分析
我们对上述可验证签名方案的安全性进行了以下几方面的分析:
(1)成员身份和子密钥分发的验证
为了保证签名成员身份的正确性,防止伪造签名。在签名过程中,群服务员A负责收集和验证签名成员的签名,由签名的第(4)步可知,如果有伪造签名者Pj(j∈B),验证Rj=sjP-rQj不成立,则计算签名也不成立,拒绝Pj的签名,这样保证了成员身份的正确性。子密钥是每个签名成员Pj(j∈B)的密钥,如果在可信中心分发了错误的子密钥,则可在第(1)步被共享者检验出子密钥是否有误。
(2)签名的有效性
每位签名成员Pj(j∈B)进行签名时,都任选自己的随机数ki(1≤ki≤q-1),由第(2)步计算得到Ri并向B中的成员公开,同时得到(x,y),第(3)步计算r=x-h(m)(mod q),si=ei,B r+ki(mod q),并把(r,si)发送给服务员A。如果有假冒签名,第(4)步就可以由群服务员A检验出来。
(3)可靠性与防欺骗性
群服务员A在签名过程中,只负责收集和验证签名成员的签名保证了此方案的可靠性;若参与签名的签名者在第(3)步有欺骗行为,则可由第(4)步检验出来。
(4)防止明文攻击
对(t,n)门限签名方案,选择明文攻击是不可伪造性,攻击者要想得到签名,必须得到t个参与的签名,这通常比较困难。如果某些参与者丢失了签名子秘钥,攻击者利用这些子秘钥仿造签名,由第(3)步和第(4)步可知,群服务员A能验证是否是伪造签名。
结果表明,建立在可信中心的ECC可验证门限签名方案是切实可行和安全的。
5 结论
(1)建立在ECC上门限数字签名方案产生的签名(r,s)及基于ECC的可验证(t,n)门限签名方案同基于ECC的ElGamal数字签名方案生成的签名形式完全相同,签名(r,s)的验证同基于ECC的ElGamal签名验证的方法也相同,上述两种方法有效。
(2)由椭圆曲线的特点决定椭圆曲线门限签名具有门限签名的正确、安全、可检验、防欺骗等特点,建立在可信中心的ECC可验证门限签名方案是切实可行和安全的。
(3)有关方法在WebGIS、电子政务等领域中的应用还需进一步研究。基于椭圆曲线的数字签名机制的相关算法也可进一步优化,从而提高门限数字签名的效率。
参考文献
[1]韩锦荣，吕继强．王新梅．基于椭圆曲线的可验证门限签名方案[J]．西安电子科技大学学报(自然科学版)，2003．30(1)：26～28．
[2]Blakley G R.Safeguarding Cryptographic Keys[Z].In:Proc.Nat.Cpmputer Conf,AFIPS Conf;Proc.Vol.48,1979,pages:313～317.
[3]Shamir A.How to Share a Secret[A].Comm_unications of the ACM[C],1979,22(11):612～613.
[4]张鹏．门限数字签名相关特性研究[D]．济南：山东大学，2004．
[5]Desmedt Y,Frandkel Y.Shared generation of authenticators and signatures[A].In: Advances in Cryptology-CRYPTO'91[C]. 1991:457～469.
[6] Kazuo Takaragi,Kunihiko Miyazaki,Masashi Takahashi,et al.A threshold digital signature issuing scheme without secret communication [EB/OL].http://grouper.Ieee.org/groups/1363/Study -Group/contributions/th-sche.pdf.
[7]张险峰，刘锦德．一种基于门限ECC的入侵容忍CA方案[J]．计算机应用，2004，24(2)：5～8．
[8]张先红．数字签名原理及技术[M]．北京：机械工业出版社，2004．
椭圆与双曲线的那些“似” 篇2
“似”点1 设[AB]是椭圆[x2a2+y2b2=1][(a>b>0)]的任意一条弦，[Q]为[AB]的中点，则[kAB⋅kOQ=-b2a2].
证明 设[A(x1,y1),B(x2,y2)]，
则[Q(x1+x22,y1+y22)]，
[x21a2+y21b2=1] ①，
[x22a2+y22b2=1] ②，
[①-②]得[x21-x22a2+y21-y22b2=0],
当[x21≠x22]时，则[y1-y2x1-x2⋅y1+y2x1+x2=-b2a2] ，
即[kAB⋅kOQ=-b2a2].
同理可得：设[AB]是双曲线[x2a2-y2b2=1][(a,b>0)]的任意一条弦，[Q]为[AB]的中点，则[kAB⋅kOQ=b2a2].
“似”点2 设[P(x0,y0)]是椭圆[x2a2+y2b2=1][(a>b>0)]内一点，则以[P]为中点的弦所在直线的方程是[x0xa2+y0yb2=x20a2+y20b2].
证明 易知直线[OP]的斜率[kOP=y0x0]，设此弦所在直线为[l]，由“似”点1可知，[kl⋅kOP=-b2a2] ，从而[kl=-b2x0a2y0]，则直线为[l]的方程为[y-y0=-b2x0a2y0(x-x0)]，即[x0xa2+y0yb2=x20a2+y20b2].
同理可得：设[P(x0,y0)]是平面内一点，则以[P]为中点的双曲线[x2a2-y2b2=1][(a>b>0)]的弦所在直线的方程是[x0xa2-y0yb2=x20a2-y20b2].
“似”点3 设[AB]是椭圆[x2a2+y2b2=1][(a>b>0)]的任意一条过中心的弦，[M]为椭圆[C]上任意一点，则[kMA⋅kMB=-b2a2].
证明 设[A(x0,y0),M(x,y)]，则[B(-x0,-y0)]，[x2a2+y2b2=1]，[x02a2+y02b2=1]，
则[y2=-b2a2(x2-a2)]，[y02=-b2a2(x02-a2)]，
从而[kMA⋅kMB=y-y0x-x0⋅y+y0x+x0=y2-y20x2-x20=-b2a2].
同理可得：设[AB]是双曲线[x2a2-y2b2=1][(a,b>0)]的任意一条过中心的弦，[M]为双曲线上任一点，则[kMA⋅kMB=b2a2].
“似”点4 设椭圆[x2a2+y2b2=1][(a>b>0)]的左右焦点分别为[F1、F2]，点[P]为椭圆上任意一点[∠F1PF2=α]，则椭圆的焦点三角形的面积为[SΔF1PF2=b2tanα2].
证明 由椭圆定义知[|PF1|+|PF2|=2a①]
在[ΔPF1F2]中，由余弦定理知
[|PF1|2+|PF2|2-2|PF1|⋅|PF2|cosα=4(a2-b2)②]
由[①2-②]得[|PF1|⋅|PF2|=2b21+cosα,]
则[SΔF1PF2=12|PF1|⋅|PF2|sinα]
[=b2sinα1+cosα=b2tanα2].
同理可得：设双曲线[x2a2-y2b2=1][(a,b>0)]的左右焦点分别为[F1,F2]，点[P]为双曲线上任意一点[∠F1PF2=α]，则双曲线的焦点角形的面积为[SΔF1PF2=b2tanα2].
“似”点5 过椭圆[x2a2+y2b2=1][(a>b>0)]上任一点[P(x0,y0)]任意作两条倾斜角互补的直线交椭圆于[B、C]两点，则直线[BC]有定向且[kBC=b2x0a2y0].
证明 设[B(x1,y1),C(x2,y2)]，
直线[PB:y-y0=k(x-x0)]，
则直线[PC:y-y0=-k(x-x0).]
由[y-y0=k(x-x0),x2a2+y2b2=1,]得
[(a2k2+b2)x2+2a2k(y0-kx0)x+a2(y0-kx0)2-a2b2=0.]
由[x0⋅x1=a2(y0-kx0)2-a2b2a2k2+b2]，
则[x1=a2(y0-kx0)2-a2b2(a2k2+b2)x0.]
同理可得[x2=a2(y0+kx0)2-a2b2(a2k2+b2)x0.]
则[kBC=y2-y1x2-x1=][-k(x1+x2-2x0)x2-x1][=b2x0a2y0].
同理可得：过双曲线[x2a2-y2b2=1][(a,b>0)]上任一点[P(x0,y0)]，任意作两条倾斜角互补的直线交双曲线于[B、C]两点，则直线[BC]有定向且.
椭圆曲线数字签名 篇3
自公开密钥加密算法问世以来，专家们提出了许多种公钥加密方法，它们的安全性都是基于复杂的数学难题。一般来讲，对某种数学难题，如果利用算法计算出秘钥的时间越长，那么基于这一难题的公钥加密系统就被认为越安全。基于所应用的数学难题来分类，有以下三类系统目前被国际公认为是安全和有效的。一、整数因子分解系统 (代表算法如R SA) ，二、离散对数系统 (代表算法如D SA) ，三、椭圆曲线加密系统（Elliptic Curve Cryptosystem s）。有时也把椭圆曲线类归为离散对数类。
椭圆曲线密码体制 (Elliptic Curve Cryptosystem s) 来源于对椭圆曲线的研究，所谓椭圆曲线指的是由维尔斯特拉方程：
所确定的平面曲线。其中系数ai (i=1, 2, …, 6) 属于某个域K，可以是有理数域、实数域、复数域，有限域等，椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个A bel群。根据椭圆曲线的加法原理，可以计算，令Q=m P，在等式中，已知m和P求Q很容易；反之，已知点P和点Q求m相对困难，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。
2. 基于有限域的椭圆曲线密码算法
在椭圆曲线加密系统中，我们使用的是某种特殊形式的椭圆曲线，即定义在有限域上的椭圆曲线。其方程如下：
这里p是一个大素数，a和b为属于某一有限域两个元素，并满足：4a3+27b2 (m od p) =0，满足方程（1）的椭圆曲线如图1。
用E (a, b) 表示模p椭圆群，其元素是满足上面方程的小于p的非负整数对 (x, y)
以及无穷远点O。在E上定义加法运算，P+Q=R, R是过P、Q点的直线与曲线的交点关于X轴的对称点（如图1），当P=Q时R是过P点的切线与曲线的交点的对称点（如图2）。将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，将椭圆曲线中的乘法运算与离散对数中的模幂运算相对应，就可以建立基于椭圆曲线的对应的密码体制。
3. 基于椭圆曲线的数字签名方案
设系统参数为，为有限域，E为上的一条强安全椭圆曲线为基点，其阶为大素数n，即nG=O, O为无穷远点，H为安全哈希函数SH A 1。签名方（发送者）取随机数（小于n）为原始私钥，令为公钥。这里J表示时间函数，若，则为空串；若，则。
签名方案签名过程：
签名方计算，H (M）为所要签名的消息M经过安全哈希函数SH A 1得出。
签名方案验证过程：
接收签名方计算；
计算；
计算
如果，表示签名有效；否则表示签名无效。
签名方案安全性分析：
1、可验证性
若签名方A、接收者B按照上述方案执行，则该方案是可验证的。
2、不可伪造性
签名方案的不可伪造性是指攻击者或是接收者试图伪造文件或签名，任何人能够通过验证签名得知文件是否伪造。攻击者（包括接收者）只有获得签名方的私钥才能伪造其签名，想要获得私钥两种途径：一是通过公钥来推导出私钥，而这就需要求解椭圆曲线的离散对数问题，做不到；二是通过签密文推导出，由于中含有两个未知数k和，也做不到。
3、机密性
机密性指只有指定的接收者才可以从签密文中恢复原始消息。攻击者想由恢复消息M有两种途径：一是通过安全哈希函数SH A 1推导出M，由于hash函数的性质，这不可能；二是通过推导出M，由于攻击者根本无法得到签名方的私钥，也不可能。
摘要：本文介绍了椭圆曲线数字签名的来源和定义, 同时描述了有限域上的椭圆曲线算法, 提出了一种新的基于椭圆曲线的数字签名方案, 并对其进行详细的安全性分析, 从而证明椭圆曲线算法具有很强的安全性。
关键词：椭圆曲线,安全,数字签名
参考文献
[1]张传林, 林立东.伪随机序列发生器及其应用[J], 数值计算及计算机应用, 2002, 3:188-208
[2]Anderson R.Low Cost At t acks on Tamper Resist ant Devices[C].Fourt h Annual Conference on Comput er and Communicat ion Securit y, ACM, 1997
椭圆曲线数字签名 篇4
1 找出已知椭圆的对称轴、顶点和焦点
步骤如下：
图1
1.利用文[1]的方法找到椭圆的中心O;
2.如图1，在椭圆上任找一点A（不是椭圆的
顶点），以O为圆心，OA为半径作圆，该圆与椭圆
的其余三个交点分别为B、C、D;
3.连接AB、AD，过点O分别作AB、AD的
平行线，得到直线l1、l2，则直线l1、l2就是椭圆的
两条对称轴;
4.直线l1与椭圆交于E、F两点，直线l2与椭圆交于G、H两点，则E、F、G、H是椭圆的四个顶点;
5.比较OE与OG的大小，若OE>OG，则EF是长轴，GH是短轴;若OE<OG，则EF是短轴，GH是长轴（图1中OE<OG，所以EF是短轴，GH是长轴）;
6.以E为圆心，OG为半径作圆，与直线l2交于F1、F2两点，则F1、F2就是椭圆的两个焦点.
备注 若点A恰好是椭圆的顶点，则该圆与椭圆只有两个交点（其中一个是点A），此时，可对点A进行调整，使得点A不是椭圆的顶点.
下面给出该作法的证明.
证明 如图1，不妨设椭圆的方程为x2a2+y2b2=1（a>b>0），点A的坐标为x0，y0，其中x0≠±a且x0≠0，于是圆的方程为x2+y2=x20+y20.由于椭圆和圆都关于x轴、y轴、原点对称，所以点B、C的坐标分别为x0，-y0、-x0，-y0，于是直线AB、AD的方程分别为x=x0、y=y0，所以直线l1、l2的方程分别为x=0、y=0，所以直线l1、l2就是椭圆的两条对称轴.
因为OE=b，EF1=a，所以OF1=EF12-OE2=a2-b2=c，同理，OF2=c，于是F1、F2是椭圆的两个焦点.
2 找出已知双曲线的对称轴、顶点和焦点
步骤如下：
图2
1.利用文[2]的方法找到双曲线的中心O;
2.如图2，在双曲线上任找一点A（不是双曲线的
顶点），以O为圆心，OA为半径作圆，该圆与双曲线
的其余三个交点分别为B、C、D;
3.连接AB、AD，过点O分别作AB、AD的平
行线，得到直线l1、l2，则直线l1、l2就是双曲线的两条对称轴;
4.直线l2与双曲线交于E、F两点，则E、F是双曲线的两个顶点;
5.以O为圆心，OE为半径作圆C1;
6.过点D，利用文[3]的方法作双曲线的切线l3，与C1交于点G;
7.过点G作l3的垂线，交l2于点F2，作点F2关于直线l1的对称点F1，则点F1、F2就是双曲线的两个焦点.
备注 若点A恰好是双曲线的顶点，则以O为圆心，OA为半径的圆与双曲线只有两个交点（其中一个是点A），此时，可对点A进行调整，使得点A不是双曲线的顶点.
关于双曲线的顶点、对称轴的证明方法与椭圆的证明类似，此处不再赘述.下面证明F1、F2是双曲线的两个焦点.
证明 如图2，不妨设双曲线的方程为x2a2-y2b2=1（a>0，b>0），点D的坐标为x0，y0，其中x0≠±a，点G的坐标为m，n.
因为点D在双曲线上，所以x20a2-y20b2=1，即
x20=a2+a2y20b2………①.
点G在圆C1上，所以m2+n2=a2………②.
切线l3的方程为x0xa2-y0yb2=1，而点G在l3上，所以mx0a2-ny0b2=1，即b2mx0-a2ny0=a2b2，两边平方，化简可得
2mnx0y0a2b2=b4m2x20+a4n2y20-a4b4………③.
因为GF2⊥l3，所以直线GF2的斜率为-a2y0b2x0，所以直线GF2的方程为y-n=-a2y0b2x0x-m，令y=0，可得点F2的横坐标为xF2=b2nx0+a2my0a2y0，平方可得x2F2=b4n2x20+a4m2y20+2mnx0y0a2b2a4y20，将③式代入该式子，可得
x2F2=b4n2x20+a4m2y20+b4m2x20+a4n2y20-a4b4a4y20=b4m2+n2x20+a4m2+n2y20-a4b4a4y20.
将②式代入，可得
x2F2=a2b4x20+a6y20-a4b4a4y20.
将①式代入，可得
x2F2=a2b4a2+a2y20b2+a6y20-a4b4a4y20
=a4b4+a4b2y20+a6y20-a4b4a4y20
=a4b2y20+a6y20a4y20
=
a2+b2=c2，所以xF2=c，于是点F2是双曲线的右焦点，从而点F1是双曲线的左焦点.
3 找出已知抛物线的焦点
步骤如下：
1.利用文[2]的方法找到抛物线的顶点O和对称轴l;
2.如图3，在抛物线上任找一点A（不是抛物线的顶
点），过A作AB⊥l于点B，作点B关于顶点O的对称点
C，连接AC;
3.过点A作AD⊥AC，交对称轴l于点D;
4.取CD中点为F，则点F就是抛物线的焦点.
下面给出该作法的证明.
图3
证明 不妨设抛物线的方程为y2=2px（p>0），点A的坐标为x0，y0，其中x0≠0，则点B的坐标为x0，0，点C的坐标为-x0，0.于是直线AC的斜率为y0-0x0--x0=y02x0，直线AD的方程为y-y0=-2x0y0x-x0.令y=0，可得x=x0+p，所以点D的坐标为x0+p，0，所以CD中点F的坐标为p2，0，所以点F就是抛物线的焦点.
参考文献
[1] 张伟.使用几何画板如何找出已知椭圆的中心[J].中学数学杂志，2014（7）：23.
[2] 黄伟亮.使用几何画板找出双曲线的中心和抛物线的焦点[J] .中学数学杂志，2015（3）：65.
[3] 黄伟亮.双曲线、抛物线切线的尺规作法[J].数学通报.2004（12）：26
椭圆曲线数字签名 篇5
网络全球化已经加快了人们的电子信息交流,电子商务、电子政务、电子银行等都是网络全球化的重要应用领域。如何保证网络通信的安全已成为人们密切关注的问题之一,其中建立在RSA和ELGamal上的许多数字签名机制,其安全性依赖于因数分解和离散对数问题。然而,RSA的加解密钥要求比较大,ELGamal的签名认证花的时间太长,使得它们不适合某些系统的应用。现在,椭圆曲线密码体制的研究已经成为密码学的热点之一,由于在相同的条件下,椭圆曲线(EC)比其它公钥密码体制具有更强的安全性和效率,使得它在信息安全和密码系统的应用越来越引起了人们的重视。在某些应用领域ECC可以代替RSA、DSS和其它密码系统的使用[1,2]。一般来说,160位的ECC与1024位的RSA的安全性相当,这意味着ECC只需要更窄的带宽和更小的存储空间,这是网络应用的关键。
本文利用ECC短密钥和(t,n)门限方法建立一种多人同时签名的机制[3],这个方案的显著特点是群签名的成员个数t不能小于门限n的值,消息的接收者都能够验证签名。
1 有效群签名方案
群体密码学[4]由Desmedt于1987年提出,是面向社团或群体的密码体制。在群体密码中,群体外的人可以使用群体的唯一群公钥,向群体发送加密信息,而只有群体中的某些子集成员合作才能解密这些信息。同样,群体密码学中也有群体签名问题,群体外的用户只需知道群体的唯一公开密钥就可以验证该签名。门限数字签名是群体密码学的一个重要分支,特别适用电子政务的某些安全要求。其方法是将一个群体的签名密钥颁发给群体中的每个成员,使得任何成员个数大于或等于门限值的子集可以产生签名,而任何成员个数小于门限值的子集都无法产生签名。
群数字签名方案的安全性是建立在椭圆曲线离散对数的难解性上。当有n个成员的群想公开发布一个消息时,t(1≤t≤n)或者t个以上的成员能够代表群的签名,t个以下的成员不能代表群的签名。签名过程分为三个阶段:密钥产生、门限数字签名、门限数字签名的验证。验证中心CA(Center Authority)负责生成系统参数,验证每个成员的签名并公开群签名。
1.1 密钥产生[5]
CA产生和公开系统参数、群公钥,每个成员公钥和门限函数的其它部分。系统参数生成如下:
(1)CA产生和公开的参数
ECC:y2=x3+ax+b mod p,a、b∈Zp,4a3+27b2≠0 mod p,p是大素数,GF(p)={0,1,…,p-1},椭圆曲线的阶N也是一个大素数,且p+1-2≤#E(GF(p))≤p+1+2,单向哈希函数h(·),椭圆曲线的基点G,其阶为n,群成员Ui的公开身份Xi。
(2)CA产生和保留的参数
(t,n)门限函数f(x)=at-1xt-1+…+a1x+a0mod n,其中{i=0,…,t-1},ai∈[1,n-1],群密钥f(0)=a0,群成员Ui的密钥为f(xi)。
(3)CA计算并公开群公钥N
(4)CA计算并公开每个成员公钥Ni
1.2 门限数字签名产生[6]
假设群需要对消息m进行签名,群成员U1,U2,…,Ut能代表群签名。这一阶段需要产生每个人的数字签名、验证每个人的数字签名以及产生(t,n)门限签名。步骤如下:
(1)每个成员Ui使用密钥f(xi)和随机整数ki(ki∈[1,n-1]),计算对消息m的签名(ri,si)。Ri=kiG,公开Ri,
其中h(m)为消息m的单向哈希函数,有利于提高系统的安全性,成员Ui把自己的数字签名(ri,si)发送给CA中心。
(2)CA中心收到每个成员Ui的数字签名(ri,si)后,CA利用以下方程验证签名:检查di=ri是否满足,如果满足,则(ri,si)是成员Ui对m的有效签名;否则,成员Ui的签名无效。
(3)收到所有成员的签名(ri,si)后,CA计算并公开对消息m的群签名(r,s)。CA首先获得所有成员的公钥Ri=(XRi,YRi),然后计算R。
1.3 群数字签名的验证
任意一个接收到(r,s)的接收者能够验证对消息m的群签名:
(1)接收者首先计算判断S=s是否成立,如果成立则执行(2),否则群签名无效。
(2)计算Q=(xQ,yQ)=s G+h(m)N,q=xQmod n,如果q=r,则(r,s)是群对消息m的签名,否则签名无效。
证明2:由方程
2 安全性和可行性分析
我们从不同的角度来分析方案的安全性和可行性。从可能潜在的攻击来分析它的安全性,这也是通过对这个系统的缺陷研究来证明系统的安全性。通过目前的签名机制和提出的方案来比较分析系统的可行性,包括密钥长度、签名长度、签名时间等方面来证明方案的优越性。
2.1 安全性分析
使用(t,n)门限签名方案,要有t或t个以上的成员才能建立有效的群签名并获得群密钥,使攻击不可行。如果攻击者企图从群公钥N=-f(0)G获得群密钥f(0),攻击者首先必须解决椭圆曲线离散对数问题(ECDLP),这比离散对数问题还困难,因此攻击不可行。
如果攻击者想通过改变成员签名进行攻击,由方程要从Di获得Di'伪造有效的签名si',他仍然要解决ECDLP问题。
如果攻击者获得了Q、s、G、h(m)、N,想通过(t,n)门限群签名验证方程伪造有效签名:Q=(xQ,yQ)mod n=s G+h(m)N,则攻击者还是必须解决ECDLP问题,并且对消息m使用了单向哈希函数,这样不仅提高了消息m的安全性,而且也避免了消息m受到的攻击。
2.2 可行性分析
在签名和验证过程中,所进行的计算用加法代替了乘法和指数运算,运算速度比传统的ELGamal签名方案和DSA系统要快。在个人签名和群签名使用相同的协议,减少了系统设计代价。
在方案中,群成员可以同时进行签名,另外(t,n)门限方案在任何时候验证签名人的身份提供了灵活性。然而许多目前建立在RSA、ELGamal上的签名机制的安全性不如建立在椭圆曲线离散对数问题的(t,n)门限签名方案。这个方案只使用160bits与RSA使用1024bits的安全性相同,相同的安全级别只需更短的密钥,可以减少内存空间;另外也加快了消息的传输。参数n只要160bits可以与RSA的1024bits的安全性相同,因此消息只要320bits。
可见,上述签名协议产生的签名(r,s)同基于ECC的ElGamal数字签名方案生成的签名形式完全相同,签名(r,s)的验证也同基于ECC的El Gamal签名验证的方法相同,因此本方案是有效的。
3 结束语
建立在椭圆曲线上的公钥系统不仅使用的钥匙短,而且它的安全性更高。优越的可行性和较窄的带宽是未来公钥系统的主流。不管在内网还是在外网的商业事务中都能利用这种有效的门限群签名系统发送签名的消息。而且,系统还能够在没有改变和伪造的情况下进行群成员签名的验证。
在未来的应用中,建立在椭圆曲线上的(t,n)门限数字签名能够有效地改善签名机制,这样不仅缩短了签名密钥,也缩短了产生和验证消息的时间。在安全的网络环境下,对电子政务和电子商务的未来发展也有很重要的意义。
摘要：本文结合椭圆曲线密钥短和(t,n)门限方案的特点,研究了一种基于椭圆曲线的多人同时签名并可验证的门限群数字签名算法,并分析了这个算法的安全性、可行性。
关键词：门限,群数字签名,椭圆曲线密码系统
参考文献
[1]M.Robshaw,Y.Yin,Elliptic curve cryptosystems,An RSA Laboratories Technical Note,1997,Revised June27.
[2]G.J.Lay,H.G.Zimmer,Constructing elliptic curves with given group order over large finite fields,in:Algorithmic Number Theory Proceedings LCNS877,Springer-Verlag,Berlin,1994:.250-263.
[3]C.Blundo,A.De Santis,D.Stinson,Graph decompositions and secret sharing schemes,in:Proceeding of EUROCRYPT_92,Springer-Verlag,Berlin,1992:1-20.
[4]Desmedt Y,Frandkel Y.Shared generation of authentica-tors and signatures[A].In:Advances in Cryptology-CRYPTO'91[C].1991:457-469.
[5]Tzer-Shyong Chen,Jen-Yan Huang,Tzer-long Chen.An efficient undeniable group-oriented signature scheme.Applied Mathematics and Computation165,2005:95-102.
椭圆曲线数字签名 篇6
关键词：椭圆曲线,数字签名,伪造签名,模乘,模逆,仿真
0 引言
椭圆曲线密码体制于1985年由Koblitz和Miller提出, 它是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码体制。经典的椭圆曲线签名算法 (ECDSA) [1]于2001年被提出, 其签名方程为s=k-1 (e+rd) modn, 验证方程为es-1G-rs-1Q=k G, 签名方案中有2次模逆、3次模乘运算。ECDSA提出后, 研究人员对模逆、模乘运算进行了各种改进[2,3,4,5,6,7,8]。2009年, 侯爱琴等对模逆运算进行了分析, 提出了无求逆的签名方案[2], 其签名方程为s= (k+ (ω+r) d) modn, 验证方程为s G- (ω+r) Q=k G, 方案中模逆运算为0次, 模乘为3次。2008年, 张庆胜等对模乘运算进行了改进, 提出了一种改进的ECDSA方案[3], 其模乘运算为2次, 模逆运算为2次。但该算法可被伪造签名攻击。本文给出了两种伪造签名攻击方法, 分析了可被伪造签名的原因, 提出了一个模乘和模逆均达到最低值2次和0次的最快速改进签名方案。仿真说明, 该改进签名方案的效率高于已有的签名方案。
1 张庆胜等算法描述[3]
已知数字签名方程通用形式[4]为z=xk+yd, 有6种基本形式e=sk+rd, e=rk+sd, s=ek+rd, s=rk+ed, r=sk+ed, r=ek+sd。该算法从s=ek+rd出发进行推导, 分别用e-1和r-1代替e和r, 方程变为s=e-1k+r-1d= (er) -1 (kr+ed) , 由于e和r对信息签名的发方和收方都是已知的, 并且方程中已有 (er) -1项, 就可以用k和d分别取代kr和ed, 此时签名方程变为s= (er) -1 (k+d) , 其详细算法如下:
设ECC域参数为D= (q, FR, a, b, G, n, h) , GF (q) 为有限域, A用户私钥为d, 公钥Q=d G。A用户要对消息m签名, 步骤如下:
(1) 随机数k∈[1, n-1];
(2) 计算k G= (x1, y1) 和r=x1modn;
(3) 计算e=SHA-1 (m) ;
(4) 计算s= (er) -1 (k+d) modn;
(5) A对消息m的签名即为 (r, s) 。
B接收到A的签名, 验证的步骤为:
(1) 验证r∈[1, n-1];
(2) 计算e=SHA-1 (m) ;
(3) 计算w= (er) smodn= (k+d) modn;
(4) 计算w G-Q= (x1, y1) ;
(5) 计算v=x1modn。
若v=r, 接受该签名;否则不接受。
2 伪造签名攻击
2.1 替换消息伪造签名攻击
接收者B接收到签名 (r, s) 后, 可用另一消息m'替换原有消息m进行伪造签名。伪造签名过程如下:
(1) 由于s, e, r已知, 由s= (er) -1 (k+d) modn可计算出 (k+d) modn;
(2) 设另有一消息m', 计算e'=SHA-1 (m') ;
(3) 计算s'= (e'r) -1 (k+d) modn;
则 (r, s') 为m'的签名。
定理1上述 (r, s') 为m'的有效签名。
证明:B'接收到签名 (r, s') 后按照算法进行如下验证:
(1) 验证r∈[1, n-1];
(2) 计算e'=SHA-1 (m') ;
(3) 计算w'= (e'r) s'modn= (k+d) modn;
(4) 计算w'G-Q= (x', y') , v=x'modn;
显然有v=r, 所以签名有效。
上述伪造之所以成功, 主要是由于能够计算出 (k+d) modn, 而r值又已知, 这样就能够用m'取代m并计算出相应的s', 产生有效的伪造签名。
相似的, 伍红梅硕士论文“椭圆曲线数字签名方案的研究”给出了一种改进方案[5]s= (ωr) (α-t-1d) modn, 可利用此方法进行相同的伪造签名攻击, 只需设一新的消息m', 计算e'=SHA-1 (m') , 并求e'的Hamming重量ω', 计算s'= (ω'r) (α-t-1d) modn, 则 (r, s') 即为伪造的有效签名。
2.2 替换随机数k伪造签名攻击
B接收到A发送的签名消息后, 可替换随机数k进行伪造签名, 方法如下[5]:
(1) 由于s、e、r已知, 由s= (er) -1 (k+d) modn可计算出 (k+d) modn;
(2) 随机的选取一个整数t, 给出表达式k'=k+t (k', k都未知, 且k是A签名选取的随机数k) ;
(3) 设tG= (x2, y2) , k'G= (k+t) G=kG+tG= (x1, y1) + (x2, y2) = (x', y') 。因为r=x1modn, x1=r+an, 在 (0, q-1) 内x1只有有限种情况, 可穷举求出x1。进一步将x1代入椭圆曲线方程y21=x31+ax1+b (bmodp) , 可计算出y1值, 则可求出 (x1, y1) , 又因为tG= (x2, y2) 已知, 所以 (x', y') 可求出;
(4) 计算r'=x'modn;
(5) 计算e=SHA-1 (m) ;
(6) 计算s'= (er') -1 (k'+d) modn= (er') -1 (k+t+d) modn, 由于e, r', t, (k+d) modn都是已知的, 所以s'也可求出;
则接收者B对消息m的签名为 (r', s') 。
定理2上述 (r', s') 为m的有效签名。
证明:B'接收到签名 (r', s') 后按照算法作出如下验证:
(1) 验证r'∈[1, n-1];
(2) 计算e=SHA-1 (m) ;
(3) 计算w'= (er') s'modn= (k'+d) modn;
(4) 计算w'G-Q= (k'G+dG) -dG=k'G= (x', y') ;
(5) 计算v'=x'modn;
显然v'=r', 所以签名有效。
上述伪造之所以成功, 主要是由于能够计算出 (k+d) modn, 这样就能够用k'=k+t取代k并计算出相应的r'和s', 产生出有效的伪造签名。
相似的, 陈亮、游林的论文“椭圆曲线数字签名算法优化与设计”[6]采用的签名算法为s= (k-er-d) modn, 此签名算法亦可采取相同的k'=k+t取代k进行伪造签名攻击。另外, 如果签名算法中k和d的出现形式只为kd (签名方程为s= (kd+f (e, r) ) modn形式) , 则可以用k'=kt进行相似的伪造签名攻击。
3 新的ECDSA改进方案
如果要从通用签名形式z=xk+yd进行推导并要求两种运算同时达到理论最优的情况 (模乘运算2次, 模逆运算0次) , 则要求s为单独一项 (可保证计算签名s时不必求逆) , k为单独一项 (可保证验证签名时计算k G不必求逆) 。如果再要求模乘运算只有2次, 则需要d为单独一项。最终的签名方程只能为s=k+d+f (e, r) 形式, 则可被上述两种伪造签名攻击, 因此从通用签名方程z=xk+yd进行推广不能达到此种要求, 需结合其它运算才能达到此种要求, 下面给出一个新的签名方案。
为进一步提高运算速度, 签名方案中可采用Hash值的Hamming重量代替Hash值参与签名。以当前普遍使用的Hash函数MD5为例, Hash值为128位二进制数, 而Hamming重量不大于128 (7位二进制数) 。研究发现该Hash值的Hamming重量对消息的变化很敏感, 若消息变化, Hamming重量发生变化的概率为92%以上[8]。
3.1 算法描述
设ECC域参数为D= (q, FR, a, b, G, n, h) , GF (q) 为有限域, A用户私钥为d, 公钥Q=d G。A用户对消息m的签名过程如下:
(1) 随机选择整数k∈R[1, n-1];
(2) 计算k G= (x, y) 和r=xmodn, 如果r=0, 则返回第 (1) 步;
(3) 随机选取α, β∈R[1, n-1], 计算u= (k-αr-βm) modn (即k= (αr+βm+u) modn) ;
(4) 计算e=SHA-1 (m) , 并求e的Hamming重ω;
(5) 计算s= (ω+αr+d) modn;
(6) A对消息m的签名为 (r, s, β, u) 。
B接收到A的签名, 验证的步骤为:
(1) 验证r∈[1, n-1];
(2) 计算e=SHA-1 (m) , 并求e的Hamming重ω;
(3) 计算γ= (s-ω+βm+u) modn;
(4) 计算γG-Q= (x1, y1) ;
(5) 计算v=x1modn;
若v=r, 接受该签名;否则不接受。
定理3上述 (r, s, β, u) 为m的有效签名。
证明:γ= (s-ω+β) modn= (αr+βm+u+d) modn
= (k+d) modn, 因此γG-Q= (αr+d+β) G-d G=k G= (x1, y1) , 可推出v=x1=x=rmodn。
3.2 安全性分析
(1) 如果攻击者C想从公钥Q和基点G推导出d是不可能的, 因为这是椭圆曲线离散对数问题, 要想求解至少需要完全指数时间。
(2) 接收者B接收到签名组 (r, s, β, u) , B即知r, s, β, r, w, m, u, k= (αr+βm+u) modn中有两个变量α, k, 无法求出α, k的值。由签名方程s= (ω+αr+d) modn可求出 (αr+d) modn, 有两个未知数α, d, 因此无法破译出私钥d。
3.3 抗替换消息伪造签名攻击分析
B接收到A发送的签名消息后, 按照前述伪造签名方法:
(1) 用另一消息m'替换原有消息m, 计算e'=SHA-1 (m') , 并求e'的Hamming重ω';
(2) 由s= (ω+αr+d) modn, 可计算出 (αr+d) modn;
(3) 伪造签名s= (ω'+αr+d) modn;
将伪造签名 (r, s', β, u) 发给接收者B';
B'接收后验证过程如下:
计算γ'= (s'-ω'+βm'+u) modn= (αr+d+βm'+u) modn≠ (k+d) modn, 可得γG-Q≠k G, v≠r, 因而签名失效。
3.4 抗替换随机数k伪造签名攻击分析
B接收到A发送的签名消息后, 按照前述伪造签名方法:
(1) 随机选取一个整数t, 给出表达式k'=k+t (k', k都未知, 且k是A签名选取的随机数k) ;
(2) 计算k'G= (k+t) G=k G+t G= (x1, y1) + (x2, y2) = (x', y') , 由2.2节中相似方法可计算出 (x', y') ;
(3) 计算r'=x'modn;
(4) 因为不知k'值, 所以只能假设有表达式k'= (α'r'+β'm+u') modn, 式中k', α', β', u'均未知;
(5) 计算e=SHA-1 (m) , 并求e的Hamming重ω;
(6) 若要伪造签名, 需计算出s'。
式中ω, t, k+d, m已知, 但β', u'不知。而在式k'=k+t= (α'r'+β'm+u') modn中, 因为t, r', m已知, k, α', β', u'未知, 无法求出β', u', 所以伪造签名不成功。
4 签名算法运算量分析与Matlab仿真
从算法运算量角度分析, 设模乘运算的数据规模为n, 1次点积运算复杂度为O (n2) , 1次模逆运算相当于9次点积运算量, 运算复杂度为O (9n2) , 1次模乘运算复杂度为O (n2log2n) [7]。将ECDSA算法[1]和侯爱琴等改进算法[2]与本文改进算法进行运算量复杂度比较。结果如表1所示。
其中N1=O[ (3log2n+22) n2], N2=O[ (3log2n+2) n2], N3=O[ (2log2n+3) n2]。三种复杂度图形表示如图1所示。
对上述签名算法采用Matlab编程进行仿真, 检验签名方案效率。硬件环境:CPU 2.13G, 内存2G。软件环境:Matlab 7.0, 相关参数 (p, a, b, G, n, h, k) = (211, 1, 1, [53, 223], 223, 1, 50) , 使用三种方案对一个word文件进行签名及验证, 结果如表2所示。
单位:s
由上分析, 本文改进算法签名时间比ECDSA快44%, 验证时间快63.9%, 总运算量快54.3%;与侯爱琴等签名算法比较签名时间近似相同, 验证时间快50.6%, 总运算量快29.5%。上面的对比是在特殊的情况下做出的比较, 具体的数值还和椭圆曲线的选取及密钥长度有关。
5 结语
本文分析了一个椭圆曲线数字签名的改进方案, 找出了其中的不足之处, 对其进行了两种伪造签名攻击, 进而提出一种改进方案, 能够抵抗两种伪造签名的攻击, 同时模乘运算达到最低2次、模逆运算达到最低0次, 点积运算只有3次, 该改进算法是最快速签名算法, 解决了椭圆曲线数字签名算法效率改进的问题。最后利用仿真与现存的两种签名算法进行了验证比较, 效率有明显的提高。
参考文献
[1]Johson D, Menezes A, Vanstone S.the Elliptic Curve Digital Signature Algorithm (ECDSA) [J].International Journal of Information Security, 2001, 1:36-63.
[2]侯爱琴, 高宝建, 张万绪, 等.基于椭圆曲线的一种高效率数字签名[J].计算机应用与软件, 2009, 26 (2) :58-60.
[3]张庆胜, 郭宝安, 程登峰.快速椭圆曲线验证算法[J].计算机工程与设计, 2008, 17 (29) :4425-4427.
[4]赵泽茂, 刘凤玉, 徐慧.基于椭圆曲线密码体制的签名方程的构造方法[J].计算机工程, 2004, 30 (19) :96-97.
[5]伍红梅.椭圆曲线数字签名方案的研究[D].西南交通大学, 2010.
[6]陈亮, 游林.椭圆曲线数字签名算法优化与设计[J].电子器件, 2011, 34 (1) :89-92.
[7]韩益亮, 杨晓元, 户军茹, 等.改进的ECDSA签名算法[J].计算机科学, 2003, 30 (10) (增刊) :377-378.
椭圆曲线数字签名 篇7
数字签名属于公钥密码学范畴，但又不同于数据加密，是信息安全的一项关键技术，是实现电子交易安全的核心技术之一。通过数字签名，可以实现身份认证、数据完整性、不可抵赖性等功能。虽然数字签名在三十多年前就已开始研究了，但并没有被广泛应用。21世纪随着我国各种通信网络的迅速普及，数字签名的应用也被提上日程，尤其在密钥分配、电子银行、电子证券、电子商务和电子政务等许多领域有重要应用价值。
椭圆曲线密码体制于1985年由Koblitz[1]和Mille[2]提出，它是利用有限域上的椭圆曲线有限群代替基于离散对数问题(DLP)的密码体制中的有限群所得到的一类密码体制。椭圆曲线密码体制安全性的数学基础是椭圆曲线离散对数问题(ECDLP)的计算复杂性。由于ECDLP比DLP更加困难，椭圆曲线系统中每个密钥位的强度在本质上要比传统的离散对数系统大得多[3]。因而除了具有相同等级的安全性外，椭圆曲线密码系统(ECC)所用的参数比离散对数(DL)系统所用的参数少。ECC的优点是参数少、速度快以及密钥和证书较小，这些优点在处理能力、存储空间、带宽和能源受限的环境中尤其重要。因此研究椭圆曲线签名与认证以及软件模拟，对我国信息安全、社会经济的发展显得尤其重要。
1 椭圆曲线数字签名的生成和验证
1.1 数字签名
简单地说，数字签名是附加在数据单元上的一些数据，或者是对数据单元所作的密码变换。这些数据或变换允许数据单元的接收者用来确认数据单元的来源和完整性并保护数据，防止他人(例如接收者)进行伪造。它是对电子形式的消息进行签名的一种方法，签名消息能够在通信网络中传输。签名必须可以验证，是指签名者利用私钥对消息实施运算，产生新的信息，包含消息的完整内容和签名人的身份等，同时应具有防止第三方假签名和原始内容篡改等功能;相反，验证签名就是利用签名者的公钥作用于签名，再将结果与签名所对应的消息进行比较，验证完整真实。如果出现诸如某个成员是否签署某个文档出现争执时，公正的第三方不需要访问签名者的私钥能够公平解决此问题。数字签名的实现基础是加密技术，它使用公钥加密算法与散列函数，其安全性是建立在有限子群Z*p上离散对数问题(DLP)的难解性。
数字签名是实现认证的重要工具，如在网络中的密钥分配、电子安全交易等方面都有重要的应用。它提供了基本的消息源可信、消息完整性、不可否认等功能。
1.2 ECDSA参数
ANSIX9.62 ECDSA当运用适当的控制时，该标准提供消息源、消息内容的完整性、消息初始可信性和抗抵赖性[3]。ECDSA算法参数分为全局参数和公钥私钥参数，其中全局参数的数字签名算法(DSA)复杂许多，其简单表示为(q,FR,a,b,G,n,h);公钥参数是椭圆曲线上的一个点，私钥参数是一个整数。
1.2.1 全局参数
ECDSA全局参数为(q,FR,a,b,G,n,h)，其参数表述如下：
(1)有限域的大小q，如果椭圆曲线基于Fp，则q=p;如果是基于F2m的椭圆曲线，则q=2m。本系统使用基于Fp的椭圆曲线。
(2)FR为Fq中的一个元素。
(3)一个长至少为160bit的比特串种子seedE，用来检查椭圆曲线方程是否随机生成，为可选项。
(4)a,b为Fq中的元素，用来定义椭圆曲线方程。
(5)椭圆曲线的基点G(xG,yG),xG,yG∈Fq，是椭圆曲线的一个生成数。
(6)且G的阶为素数
(7)h=#E(Fq)/n。
1.2.2 公钥和私钥的产生
公钥是椭圆曲线上对应的一点，是椭圆曲线基点G的若干倍，其倍数就是对应的私钥参数。每对公钥私钥都对应一个全局参数组(q,FR,a,b,G,n)，ECDSA的公钥私钥对产生算法如下：
(1)选择一个随机数d,且1
(2)计算Q=dG。
(3)得到密钥对(d,Q)，其中公钥为Q，私钥为d。
当然，除了上面的算法外，还可以在可信的第三方(如CA)处得到所需要的密码参数，并对生成的密钥参数进行合法性检查，避免使用那些容易被攻击的密钥参数，或检查无意的疏忽、错误造成的损失等。
算法输入:(q,FR,a,b,G,n),Q。
算法输出:是/否。
算法步骤如下：
(1)检查Q点是否等于无穷远点O。
(2)检查Q点的x和y，当q=2m时，x、y的长度为m的比特串，当q=p时，x,y∈[0,p-1]。
(3)检查Q点是否满足椭圆曲线方程。(4)检查nQ是否为无穷远点O。
(5)如果以上条件都成立，则表示参数合法，输出“是”，否则输出“否”。
1.3 ECDSA签名与验证算法
1.3.1 签名过程
对待签署的消息m签名，全局参数D=(q,FR,a,b,G,n,h)，签名者的公钥私钥对(Q,d)。签名算法如下：
(1)选取一随机数k,k∈[1,n-1]。
(2)计算kG=(x1,y1)。
(3)计算r=x1mod(n)，如果r=0，返回步骤(1)。
(4)计算k-1mod(n)。
(5)计算e=SHA1(m)。
(6)计算s=k-1(e+dr)mod(n)，如果s=0，返回步骤(1)。
(7)对消息的签名为(r,s)。
(8)签名者将消息m和签名(r,s)发送给接收者。
1.3.2 验证过程
当接收者收到消息m和签名(r,s)之后，验证对消息签名的有效性，需要取得全局参数D=(q,FR,a,b,G,n,h)，发送者的公钥Q，并对参数D和Q进行合法性检验。验证算法如下：
(1)检查r,s，要求r,s∈[1,n-1]。
(2)计算e=SHA1(m)。
(3)计算w=s-1mod(n)。
(4)u1=ew mod(n),u2=rw mod(n)。
(5)计算X=u1G+u2Q。
(6)如果X=O，表示签名无效;否则X=(x1,y1)，计算v=x1mod(n)。
(7)如果v=r，表示签名有效;否则表示签名无效。
2 ECDSA的Java实现
通过深入研究椭圆曲线算法及其基于椭圆曲线数字签名方案，本文设计了一套应用于网络环境的椭圆曲线数字签名和认证系统，并用Java模拟实现。
2.1 系统功能结构、数据库流程和客户端验证界面
本系统主要由后台管理模块、前台应用模块、签名模块和验证模块组成，其系统功能结构图、数据库流程和运行的客户端验证界面如图一至图三所示。
2.2 性能分析
ECDSA的安全目标是在现有软硬件条件下使用选择明文攻击签名不可伪造，对一个合法成员A发动此类攻击的目标是攻击者在获取A所选择的消息集(不包括m)上签名之后，能获取A在某一单条消息上的有效签名。本系统在实现的过程中，不仅做到了健壮性、即时性，而且还具有以下的特点：
(1)通用性：按系统要求可以运行在不同操作平台以及不同的机器类型上。
(2)稳定性：为了能稳定运行，采用最先进技术，进行数据分析处理，不管在任何地方都可以进行快速操作。
(3)实用性：本系统实现的功能与手工操作实现功能一样，并有清晰的用户界面，方便用户操作。
(4)容错性:具有较强的容错能力。
(5)保密性:数据处理以及数据传送过程中，每个环节都具有高度的可靠性、保密性以及安全性。
3 结束语
ECDSA是ANSI、IEEE、FIPS、NIST和ISO标准，通过对其软件实现、运行测试及分析表明，它具有抗攻击性强、计算量小、处理速度快、密钥尺寸和系统参数小、带宽要求低等优点。所以研究开发具有自主知识产权的椭圆曲线网络签名与认证系统对于提高信息安全和社会经济的发展有重要的战略意义。
参考文献
[1]N Koblitz.Elliptic curve cryptosystems[J].Mathematics of Computation,1987,(48):203-209.
[2]V Miller.Uses of elliptic curves in cryptography[A].Advances in Cryptology-Crypto’85,Lecture Notes in Computer Science[C],1986,218:387-398.
[3]Don B Johnson,Alfred J Menezes.Elliptic Curve Digital Signature Algorithm(ECDSA)[Z/OL].http://www.certicom.com/resources/download/ecdsa.ps.
[4]张先红.数字签名原理及技术[M].北京:机械工业出版社,2004.
[5]卢开澄.计算机密码学(第3版)[M].北京:清华大学出版社,2003.
数控车削椭圆曲线探析 篇8
关键词：数控车削,椭圆,宏程序
椭圆是数控车床加工中经常遇见的零件轮廓曲线, 这种非圆曲线轮廓是用数控车床的普通G代码指令难以加工的, 以图1所示工件 (毛坯为d26棒料) 为例, 针对FANUC 0i系统推荐2种具有实际意义的数控车削椭圆曲线轮廓方案。
1 四弧逼近法
1.1 四弧逼近法作图方法
根据椭圆放样法原理, 可确定4段特定的圆弧, 传统方法为用手工绘图来确定4段特定的圆弧, 并用解析法求出圆弧半径和圆弧连接处点的坐标, 然后进行编程。这里用AutoCAD软件进行操作, 可做到方便快捷。方法如下:以直角坐标系xoy的原点为圆心, 分别以椭圆的长半轴a和短半轴b为半径作2个同心圆, 他们与坐标轴的交点为点A (a, 0) 和点B (0, b) ;连接AB, 在AB上取点C, 使BC=a-b;作AC的垂直平分线, 与x, y轴分别交于点O1 (x0, 0) 和 (0, -y0) ;以O1为圆心, O1A为半径作圆, 以O2为圆心, O2B为半径作圆, O1圆在N1点内切于O2圆, 则圆弧N1A和圆弧N1B光滑连接, 构成近似椭圆。利用图1中数据a=20, b=12进行作图, 再利用AutoCAD的查询功能, 便可得知A (20, 0) , N1 (15.6619, 7.6619) , B (0, 12) , 圆弧AN1 半径为8.9352, 圆弧N1B半径为30.4413, 根据这些数据就可以利用FANUC 0i系统的G71和G70功能编制该工件的粗加工和精加工的数控车削程序了。
1.2 四弧逼近法误差分析
通过固定长轴、改变短轴的方法, 用AutoCAD绘出多组四弧逼近法构建的近似椭圆, 并与椭圆绘制功能绘制的相同长、短轴的标准椭圆进行比较, 得出如图2所示的结论:
1) 近似椭圆与标准椭圆相比较, 误差的最大值均出现在圆弧AN1段;
2) 随着椭圆短半轴与长半轴比值的减小 (即椭圆变扁) , 误差最大值增大;
3) 椭圆短半轴与长半轴比较接近, 其比值约大于等于0.7时, 误差较小[1]。
2 宏程序编程方法
2.1 精车椭圆宏程序编程
椭圆的参数方程为:
undefined
undefined
根据图1, 车床加工的椭圆长轴a在z轴方向, 短轴b在x轴方向, 单纯用外圆车刀精加工椭圆时车刀将沿x和z轴方向做直线插补运动, 数学坐标系转化为实际车床坐标系, 式 (1) 和式 (2) 应修改为:
undefined
undefined
根据式 (3) 和式 (4) 编制精车椭圆的宏程序如下:
O0001;
︙
#100=20;椭圆长半轴
#101=12;椭圆短半轴
#102=0;椭圆切削起点
#103=90;椭圆切削终点
#104=0.5;角度增量
WHILE[#102 LE #103] D01;
#105=2*[#101]*SIN[#102];
#106=#100*COS[#102];
G01 X[#105] Z[#106] F0.1;
#102=#102+#104;
END1;
︙
M30。
角度增量是用线段逼近椭圆的最小等分角度, 等分角度越小椭圆越逼真。
2.2 椭圆曲线轮廓粗车宏程序编程
在FANUC 0i系统上不可以用粗车循环指令G71调用椭圆精加工的宏程序进行粗加工[2], 因此, 一般采用调整磨耗、计算机绘图确定粗车路线等方法进行椭圆曲线的粗加工, 相对比较麻烦, 下面介绍2种用宏程序编程的椭圆曲线粗车方法。
a) 利用参数方程编制粗车宏程序
根据式 (3) 和式 (4) , 以角度α为变量, 编制粗车的宏程序如下:
O0002;
︙
#110=20;椭圆长半轴
#111=12;椭圆短半轴
#112=90;增角初值
#115=0.5;精加工余量
WHILE [#112 GT 0] DO2;
#113=#111*SIN[#112];
#114=#110*COS[#112];
G00 X[2*#113+#115];
G01 Z[#114+#115] F0.1;
U0.2;
W[60-#114];
#112=#112-5;
END 2;
︙
M30。
用这种方法粗车椭圆曲线的刀具走到路线示意图如图3所示, 车刀首先根据增角α递减计算出直径进给量, 沿x向进给, 计算出z方向进给量, 沿z向进给, 再利用增量编程的方法使刀具退回z向进给起始位置, 然后, 增角α递减, 重复上述循环, 直至α递减为0, 粗车完毕。
这种方法因以α均匀递减来计算x方向的进给量, 因而使车刀在x方向的进给量由小到大变化, 这比较适合椭圆短半轴与长半轴比较接近的情况。
b) 利用标准方程编制粗车宏程序
椭圆标准方程为:
undefined (5)
根据图1, 车床加工的椭圆长轴a在z轴方向, 短轴b在x轴方向, 单纯用外圆车刀精加工椭圆时车刀将沿x和z轴方向做直线插补运动, 数学坐标系转化为实际车床坐标系, 式 (1) 和式 (2) 应修改为:
undefined (6)
以x为变量, 则由式 (6) 计算得:
undefined (7)
根据式 (7) , 以x方向进给为变量, 编制粗车宏程序如下:
O0003;
︙
#110=20;椭圆长半轴
#111=12;椭圆短半轴
#112=24;X方向直径值初值
#114=0.5;精加工余量
WHILE [#112 GE 0] DO2;
#113=[#110/#111]*SQRT[#111*#111-0.25*#112*#112];
G00 X[#112+#114];
Z[#113+#114] F0.1;
U0.2;
W[60-#113];
#112=#112-4;
END 2;
︙
M30。
用这种方法粗车椭圆曲线的刀具走到路线示意图如图4所示, 车刀首先给出直径进给量, 沿x向进给, 根据标准方程计算出z方向进给量, 沿z向进给, 再利用增量编程的方法使刀具退回z向进给起始位置, 然后, 均匀改变直径进给量, 重复上述循环, 直至粗车完毕。
这种方法因车刀在x方向的进给量均匀变化, 即每刀的切深相同, 因而更加符合加工的工艺要求。
3 结语
四弧逼近法和宏程序编程方法是在实践中总结出来的数控车削椭圆曲线的较为经济实用的方法, 用宏程序编程方法编制的椭圆曲线粗加工程序, 解决了椭圆曲线粗加工的问题, 该程序可做为子程序进行调用, 使椭圆曲线的粗加工变得简单易行, 具有推广意义。
参考文献
[1]刘佳慧, 崔怀德.在FANUC系统上建立椭圆曲线插补宏程序[J].制造技术与机床, 2005 (1) :27-28.
数控车床加工椭圆曲线的方法探讨 篇9
关键词：数控加工,椭圆,宏程序,编程
椭圆加工, 普通机床很难完成, 而数控机床确能够轻松的加工出来, 主要是因为椭圆加工的时候X、Z两坐标是同时变化的, 数控机床是通过程序控制的方式来驱动两轴, 实现两轴的共同运动。但数控车床只具有直线插补和圆弧插补两种基本插补功能, 不具备椭圆插补功能, 所以加工椭圆时可以采用直线逼近法的方式进行加工, 即把曲线用许多小段的直线来代替, 无限接近椭圆轮廓的加工方法。下面选用FANUC--Oi数控车削系统, 结合工作实践谈谈如何巧用宏程序解决椭圆编程问题。
1 宏程序组成
1.1 变量的类型
变量号#0, 空变量;变量号#1～#3 3, 局部变量;变量号#10 0～#10 9、#5 0 0～#9 99, 公共变量;变量号#1 00 0以上, 系统变量。
1.2 变量的运算
定义#1=#2;加法#1=#2+#3、减法#1=#2-#3、乘法#1=#2*#3、除法#1=#2/#3;正弦#1=S I N[#2]、余弦#1=COS[#2]、正切#1=TAN[#2];平方根#1=SQRT[#2]、绝对值#1=ABS[#2]。
1.3 运算符
EQ (=) 、GE (≥) 、NE (≠) 、LT (<) 、GT (>) 、LE (≤) 。按照优先的先后顺序依次是函数→乘和除运算→加和减运算。
1.4 条件转移 (IF) 功能语句
IF[表达式]GOTO n。指定的条件不满足时, 转移到标有顺序号n的程序段。
2 椭圆宏程序的编制步骤
2.1 标准方程
椭圆的标准方程为:
其中:a为椭圆的长轴, b为椭圆的短轴。
2.2 对标准方程进行转化成车床椭圆方程
根据笛卡儿坐标系的规定, 数控车床的坐标系只有X轴和Z轴, 将椭圆标准方程转化成车床椭圆方程:
2.3求值公式推导
为编程方便, 一般用Z作为变量。假设Z变量是已知的, 将机床坐标系的标准化方程转化为用含有自变量Z来表示X:
有些零件的椭圆中心不在Z轴轴线处, 就要根据实际椭圆写出正确的方程。
3 利用标准椭圆方程编写宏程序
3.1 工艺分析
毛坯直径为Ф40, 总长为40, 用变量进行编程, 经计算椭圆起点的X轴坐标值为10.141。
由于椭圆中心不在Z轴轴线处, 根据公式3得出实际的椭圆方程为:
3.2 加工程序
编写程序时, 设定#2代表自变量Z, 由于椭圆圆心距工件的左端面的距离为14, 因此#2=#1+14, 其中, #1为自变量, #1的初始值为0。
#3代表因变量X, 由公式4可得出#3的表达式为:
程序编写如下:
4 结语
实践证明, 在数控车床上用宏程序加工椭圆曲线的方法是实用可行的。在实际操作时, 应注意下述问题:在用宏程序编制椭圆程序时, 首先能够选对变量和写出正确的方程, 通过方程计算出另一变量, 其次能正确确定工件原点与椭圆中心之间的关系, 再编出正确的椭圆宏程序。实践工作中遇到具体的加工实例要具体分析, 不能硬套固定模式, 要多方面综合考虑, 合理运用宏指令进行编程。
参考文献
[1]陈海舟.数控铣削加工宏程序及应用实例[M].北京:机械工业出版社, 2007.12.
[2]冯志刚.数控宏程序编程方法技巧与实例[M].北京:机械工业出版社, 2008.6.