椭圆曲线数字签名

2024-05-28

椭圆曲线数字签名（精选9篇）

椭圆曲线数字签名第1篇

随着Internet技术的发展和普及, 全球信息化已经成为人类发展的大趋势。由于计算机网络具有连接形式多样性、终端分布不均匀性和网络的开放性、互联性等特征, 致使网络易受黑客、恶意软件和其他不轨人员的攻击, 计算机网络的安全问题日益突出, 网络安全越来越成为人们所关注的焦点。

数字签名技术能够有效地保证网络安全。所谓数字签名, 就是附加在数据单元上的一些数据, 或是对数据单元所做的密码变化。这种数据或变换允许数据单元的接受者, 用以确认数据单元的来源和数据单元的完整性并保护数据, 防止被伪造。数字签名技术即进行身份认证的技术。在数字化文档上的数字签名类似于纸张上的手写签名, 是不可伪造的。接收者能够验证文档确实来自签名者, 并且签名后文档没有被修改过, 从而保证信息的真实性和完整性。

主要介绍基于椭圆曲线密码体制 (Elliptic Curve Cryptosystem, ECC) 。

2 椭圆曲线算法

所谓椭圆曲线, 是指由维尔斯特拉斯 (weierstrass) 方程:

y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)

所确定的平面曲线。若F是一个域, ai∈F, i=1, 2…, 6。满足1式的数偶 (x, y) 称为F域上的椭圆曲线E的点。F域可以是有理数域, 也可以是复数域, 还可以是有限域。椭圆曲线通常用E表示。除了曲线E的所有点外, 还要加上一个叫做无穷远点的特殊点O。

对于椭圆曲线加密算法来说, 我们更关心的是一种受限形式的椭圆曲线。这种椭圆曲线定义在一个有限域上。密码编码学特别感兴趣的是被称为模P椭圆群的对象, 其中P是一个素数。这个群的定义如下:

选择两个满足下列条件的小于P的非负整数a和b:

4a3+27b2 (mod p) ≠0 (2)

那么Ep (a, b) 表示满足下列条件的模p椭圆群:该群中的元素 (x, y) 是满足下面方程的小于P的非负整数另外加上无穷点O:

y2=x3+ax+b (mod p) (3)

椭圆曲线离散对数问题ECDLP定义如下:给定素数p和椭圆曲线E, 对Q=kP, 在已知P, Q的情况下求出小于p的正整数k。可以证明, 已知k和P计算Q比较容易, 而由Q和P计算k则比较困难, 至今没有有效的方法来解决这个问题, 这就是椭圆曲线加密算法的原理。

3 基于椭圆曲线算法的数字签名

3.1 基于椭圆曲线算法数字签名的原理

3.1.1 生成密钥对

首先, 需要确定加密算法的公钥与私钥。选择一条椭圆曲线E (a, b, p值给定) , 在E上选取一个周期很大的点P= (Xp, Yp) , 它的周期为一个很大的素数n。在椭圆曲线密码体制中, 具体的曲线E及点P和它的周期n都是公开信息。给定参数 (p, E, P, n) 以后, 选择d∈R[1, n-1]。计算Q=dP, 返回 (Q, d) , 其中, Q为公钥, d为私钥。

3.1.2 加密算法

确定了椭圆曲线加密算法的公钥与私钥以后, 就可以进行加密了。加密算法如下:

首先, 确定参数组 (p, E, P, n) , 公钥Q, 明文m;然后, 将明文m表示为椭圆曲线E上的点M;选择k∈R[1, n-1], 计算C1=kP, C2=M+kQ。 (C1, C2) 就是加密后的密文。

3.1.3 解密算法

收到密文以后, 可以对密文进行解密, 解密算法如下:

首先, 确定参数组 (p, E, P, n) , 私钥d, 密文 (C1, C2) ;然后, 计算M=C2-dC1, 并从点M中取出明文m。

3.2 基于椭圆曲线算法数字签名过程

3.2.1 签名过程

假如现在A想给签署一份文件, 为确认这份文件确实是A签署的, 可以先对这份文件进行数字签名。用椭圆曲线算法的数字签名过程如下:

(1) 对明文使用HASH算法, 得到明文的数据摘要。 (大多时候, 明文的信息都比较长, 如果直接用椭圆曲线算法加密, 加密的速度会比较慢, 而且耗费系统资源。这时候, 可使用HASH函数, 使用MD5或者SHA算法生成数据摘要。这样做的优点是:输出较短, 一般是128位;抗逆向攻击;抗碰撞攻击) ;

(2) 对数据摘要进行加密, 使用A的私钥进行椭圆曲线算法加密, 得到数据摘要的密文;

(3) 将明文和加密后的摘要同时进行DES加密, 将密文送给B。

数字签名过程, 如图1所示。

3.2.2 验证过程

B收到A发来的密文后, 为了验证密文确实是A发送的, 可以对密文进行验证, 验证过程如下:

(1) 对密文进行DES解密, 得到明文和A用椭圆曲线算法机密后的摘要;

(2) 对明文使用HASH算法, 得到明文的数据摘要;

(3) 使用A的公钥对A加密的数据摘要进行解密, 得到数据摘要;

(4) 将 (2) 和 (3) 得到的数据摘要进行比较, 如相同, 则说明该密文确实是A发送的, 如不同, 则说明该密文不是A发送的。

验证过程, 如图2所示。

4 椭圆曲线算法的安全性分析

一个公钥密码系统的安全性一般通过该算法的抗攻击强度来反应。椭圆曲线的离散对数问题 (ECDLP) 的计算困难性在计算复杂度上目前是完全指数级, 而RSA是亚指数级的。ECC算法和其它几种公钥系统相比, 其抗攻击性具有绝对的优势。

以目前应用较为广泛的RSA算法为例, RSA算法的优点主要在于原理简单, 易于使用。但是, 随着整数因子分解方法的不断完善、计算机素的的提高以及计算机网络的发展, 作为RSA加解密安全保障的大整数要求越来越长。要保证RSA使用的安全性, 就要相应地增加其密钥的位数, 但是, 密钥的长度增加导致了其加解密速度大大降低, 硬件实现也变得越来越困难, 这对使用RSA算法带来了沉重的负担, 从而也使得RSA算法的应用范围越来越受到限制。相反, ECC算法能以相对较短的密钥长度提供更大的安全性。例如, 一个160比特的ECC密钥能够提供相当于一个1024比特的RSA或者DSA密钥所提供的安全性。

在签名和解密方面, 椭圆曲线密码体制要比RSA或DSA快很多, 缺点是椭圆曲线签名验证和加密速度太慢。另外, ECC系统的密钥生成速度比RSA快百倍以上。

ECC算法与其它公钥加密算法相比, 能提供更好的加密强度、更快的执行速度和更小的密钥长度, 因此ECC可用较小的开销和时延实现较高的安全性。

5 结语

介绍了基于椭圆曲线算法的数字签名技术, 分析了它的原理及特点。椭圆曲线密码体制是一种能适应未来通信技术的信息安全技术发展的新型密码体制, 在运算速度和存储空间方面占有很大的优势。随着网络的发展和硬件计算能力的提高, 椭圆曲线密码体制以其自身的优点, 一定会在网络安全领域有更广泛的应用。

摘要：椭圆曲线密码体制是一种高安全性、高效率的公钥密码体制, 它已逐渐取代RSA加密算法, 成为下一代公钥加密的标准。本文介绍了基于椭圆曲线算法的数字签名技术的基本原理及其安全性, 展望了公钥密码体制未来的发展方向。

关键词：椭圆曲线算法,数字签名,网络安全

参考文献

[1]宋金秀, 杨秋翔.椭圆曲线密码体制的研究与探讨[J].山西农业大学学报 (自然科学版) , 2008, 28 (2) :234-236.

[2]张霓.椭圆曲线密码机制的应用研究[J].重庆科技学院学报 (自然科学版) , 2007, 9 (3) :82-84.

椭圆与双曲线——奇妙的类比第2篇

注意到椭圆与双曲线在定义与标准方程的差别仅在“和”与“差”上，因此表现在性质的差异上可能就是矛盾的两个方面。抓住这一点，可以先研究椭圆的几何性质，然后再类比到双曲线上。为便于讨论，只以焦点在x轴上的圆锥曲线的标准方程进行讨论。

一、内外之分

1.设椭圆（a，b＞0）两焦点为F1，F2，点Q为椭圆上除顶点外的任一点，过椭圆的一个焦点作∠F1QF2的一个外角平分线的垂线，垂足为P，则P点轨迹是圆的一部分。

证明：如图1，QP为∠F1QF2的一个外角平分线，过F2作QP的垂线，垂足为P。延长F2P与F1Q的延长线交于点N，则QP为F2N的垂直平分线，|QF2|=|QN|，又|QF1|+|QF2|=2a，∴|F1N|=2a，又OP为△F1F2N的中位线,所以OP∥F1N且OP=a，所以P在以O为圆心，半径为a的圆上。

上述性质类比到双曲线上，即可得到：

设双曲线（a，b＞0）两焦点为F1，F2，点Q为双曲线上除顶点外的任一点，过双曲线的一个焦点作∠F1QF2的平分线的垂线，垂足为P，则P点轨迹是圆的一部分。

本题结论本身也许并不重要，但解题依据却是最基本的定义，题目条件中的外角平分线与内角平分线的差别恰好就是椭圆与双曲线在定义上区别的体现。

二、正余有别

1.设椭圆a，b＞0）两焦点为F1，F2，点Q为双曲线上

除顶点外的任一点，∠F1QF2=θ，则三角形F1QF2的面积证明：如图2，由椭圆定义得：|QF1|+|QF2|=2a （1）△QF1F2中，由余弦定理可得：|QF1|2+|QF2|2-2|QF1|·|QF2|

cosθ=4c2 （2）

（1）式平方-（2）式得2|QF1|·|QF2|（1+cosθ）=4a2-4c2，

上述性质类比到双曲线上，即可得到：

设双曲线（a，b＞0）两焦点为F1，F2，点Q为双曲线上除顶点外的任一点，∠F1QF2=θ，则三角形F1QF2的面积

本题结论中，两个面积公式的不同之处仅在正切与余切的区别上，这种形式的类似既是曲线性质规律性的反映，也是运用类比方法的典型案例。

三、对立统一

1.直线y=kx+b与椭圆（a，b＞0）交于A，B两点（图3），设AB中点为M，O为坐标原点，则有

（其中e为离心率）。

证明：设A（x1，y1），B（x2，y2），中点M（x0，y0），则有：

整理得，，所以有上述性质类比到双曲线上，即可得到：直线y=kx+b与双曲线

交于A，B两点，设AB中点为M，O为坐标原点，则有（其中e为离心率）。

本题结论中，椭圆与双曲线性质的区别仅在于符号的正、负，但又都能表示为e2-1，可以说是既对立又统一。

椭圆曲线数字签名第3篇

计算机和网络技术的发展将人类带入信息化社会,随之而来的是倍受关注的信息安全问题。密码技术已经成为安全电子商务、安全通信、安全支付和保密的关键手段,而数字签名又是现代密码技术主要研究的内容之一。数字签名技术在身份识别和认证、数据完整性、抗抵赖等方面具有其它技术所无法替代的作用,它在军事、电子商务和电子政务等领域有着极广泛的应用。

公钥密码系统很好地解决了数字签名中的一些关键问题。而椭圆曲线密码系统与RSA,ElGamal等公钥密码系统相比,具有密钥短、运算量小等优点,并具有更高的安全性,这些优点使椭圆曲线密码系统成为近年来的研究热点。

椭圆曲线数字签名算法(ECDSA)的硬件实现已成为热点之一。本文以基本的数论理论、抽象代数和硬件设计理论为依据,结合信息论、密码学的一些知识以及一些具体的相关算法。确定了ECDSA的硬件实现方案。设计选用了Altera 公司的Stratix系列器件,利用Quartus II 5.0软件进行综合、布局、布线和时序仿真。

1 椭圆曲线数字签名方案概述

1.1 算法描述

1.1.1 ECDSA的域参数

ECDSA的域参数由一条特征为q的有限域Fq的椭圆曲线E和基点G,E(Fq)组成,域参数可被组中的所有成员共享,也可单独为某用户分配。为充分利用互用性和防止一些已知攻击,在域的大小q,用于Fq元素的描述上以及在椭圆曲线和基点阶数上做了一些限制,域参数由以下部分组成:

(1)域的大小q,这里q=p,p为奇素数;或q=2m。

(2)用一个描述指标FR(域描述)描述Fq元素。

(3)位串长度至少为160位。

(4)Fq上的椭圆曲线E的等式定义的Fq上的两个元素a和b。

(5)定义E(Fq)素数阶有限点G=(xG,yG)的Fq上的两个域元素xG和yG。

(6)点G的阶数n,n>2160且undefined。

(7)伴随因子h=#E(Fq)/n,(其中,#E(Fq)表示椭圆曲线上的点的个数)。

1.1.2 ECDSA密钥对

ECDSA的公钥是基点的随机倍数,私钥是用来生成这个倍数的整数,成员A必须在密钥生成前得到域参数有效的保证,为生成ECDSA的密钥对,每一个成员A都要做如下操作:

(1)在区间[1,n-1]中选择一个随机或伪随机整数d。

(2)计算Q=dG。

(3)A公钥是Q, 私钥是d。

1.1.3 生成ECDSA签名

为签署消息m,具有域参数D=(c,FR,a,b,G,n,h)及相关密钥对(d,Q)的成员A做如下操作:

(1)选择一个随机或伪随机整数k满足1

(2)计算KG=(x1,y1)且将x1转换成整数undefined1。

(3)计算undefined,如果r=0则回到第一步。

(4)计算k-1mod n。

(5)计算SHA(m)将该位串转换成整数e。

(6)计算s=k-1(e+dr) mod n 如果s=0则回到第1步。

(7)A对消息m的签名为(r,s)。

1.1.4 ECDSA签名验证

要验证A在消息上的签名为(r,s),B取得A域参数D=(q,FR,a,b,G,n,h)的可信副本和相关公钥Q,推荐B也验证D和Q的有效性,然后B做以下的操作:

(1)验证r和s是区间[1,n-1]内的数。

(2)计算SHA(m)并将该位串转换成整数e。

(3)计算w=s-1mod n。

(4)计算u1=ew mod n和u2=rw mod n。

(5)计算X=u1G+u2Q。

(6)如果X=∞则拒绝签名;否则转换X的x1坐标为整数undefined1并计算undefined。

(7) 当且仅当v=r时接受签名。

1.1.5 签名验证的依据

如果消息m上的签名(r,s)真正是由A生成的,则由s=k-1(e+dr) mod n得:

k=s-1(e+dr)mod n=we+wrd=

u1+u2d(mod n)

因而u1G+u2Q=(u1+u2+d) G=kG同时也需要v=r。

1.2 算法安全性

ECDSA的安全目标是对于选择明文攻击在现有的基础上是不可伪造的,对一个合法成员A发动此类攻击的目标是在获取A在攻击者所选择的消息集(不包括m)上的签名之后,能获取A在某一单条消息上的有效签名。在离散对数问题是困难的而且所使用的哈希函数是随机函数的前提下,Point cheval和Stern已经证明了对于选择明文攻击,ECDSA在现有的情况下是不可伪造的。Brown已经证明了在基本群为普通群而且所使用的哈希函数是在抗碰撞的前提下,ECDSA本身是安全的。

2 椭圆曲线数字签名方案的硬件优化设计

2.1 总体设计框图

图1是总体设计框图。这是一种高性能的处理器。除了程序和数据内存外,还有三个主要的组件:算术逻辑单元(AU)、算术单元控制器(AUC)和主控制器(MC)。算术逻辑单元执行加法、平方、乘法和求逆等基本运算,它由算术单元控制器控制。算术控制单元执行椭圆曲线的点加和倍加操作。主控制器与主机系统相互结合,协同执行点乘方法。当随机选择整数k时,由主机提供k和P的(仿射)坐标,主机要求处理器生成kP,其中整数k被载入MC转换为点加和倍点公式所需的投影坐标。MC会扫描k的比特位,并命令AUC执行适当的椭圆曲线操作,AUC将顺次指使AU执行适当的有限域操作。当k的所有bit位被处理后,MC将控制AUC把返回的结果转换为仿射坐标,主机则从AU的寄存器中读取kP值。拥有两个控制器有两方面的重要性,即并行处理的能力和流水线操作。MC也会使用数据存储的能力来实现更有效地利用预计算来计算kP值的算法。

2.2 二元域上的求逆设计

本文用a来表示二进制多项式a(z)。F2m的非零元素a的逆是域F2m的唯一元素g,在域F2m上满足ag=1,即满足ag≡1(modf)。这个逆元素用符号a-1modf表示,若约减多项式不会产生混淆,则可表示为a-1。用多项式Euclidean算法可快速求出逆元素[1]。

2.3 用Montgomery方法进行kP的优化设计

2.3.1 相关算法

LOPEZ和DANAB提出了一种基本思想基于Montgomery方法的点乘算法[1]。该算法的一个优点是不需要额外的存储器。另一个优点是在主循环的每一次迭代中都完成相同的操作,因此增强了抵抗时间分析攻击和能量分析攻击的能力。

2.3.2 具体实现及优化设计

可以通过以下几步来分析上述算法的实现过程:

第一步:进行坐标转换,即将仿射坐标转换为射影坐标。只涉及到平方运算,在时间上只需一个时钟周期。

第二步:在射影坐标下计算椭圆曲线点乘。这一部分是整个实现的关键,椭圆曲线点乘实现的效率也由它来决定。计算出deg k之后进行主循环。通过加运算和倍加运算完成。

当进行加运算时,有四次模乘,它们分别为:

(1)X1×Z2

(2)X2×Z1

(3)(X1×Z2)×(X2×Z1)

(4)x×(X1×Z2+X2×Z1)2

观察这四次模乘,(3)、(4)必须在(1)、(2)结束后才能进行,即(3)、(4)与(1)、(2)之间必须串行。还有一次平方运算,只需要一个时钟周期,在这里不予讨论。

进行倍加运算时,有两次模乘运算和四次平方运算,这六次模乘的实现可以有三种方案。

方案一:全部串行。由此产生的多路选择器所耗费的资源也是很大的。最重要的是,全部串行方案总的运算时间为degk×m×6,会使总的椭圆曲线点乘运算的速度降低。

方案二:(1)、(2)之间并行,(3)-(6)之间并行,它们两者之间串行。该方案总耗费时间为degk×m×2。但是在(3)-(6)的并行电路势必会耗费庞大的逻辑资源,而且在实现(1)、(2)时,有一部分电路没有充分利用。

方案三:(1)、(2)之间并行,(3)、(4)之间并行,(5)、(6)之间并行,它们三者之间串行。这种方案的总的运算时间为degk×m×3,并且逻辑资源在每次运算都充分利用。

在设计中,本文选择了时间和速度折衷的方案三。该方案需要两个模乘模块,一个平方模块,以及寄存器单元和多路选择器,而模乘模块也由运算器和多路选择器组成。为节省资源,在这里,采用归一化的设计思想,即只通过一个多路选择器,再在时钟和运算器的配合下,使模乘、平方模块的输入信号都来自于运算器的输出,通过这种改进的结构,在椭圆曲线点乘的实现中,节省了三分之一的资源,改进的椭圆曲线点乘的结构框图如图2所示。

改进的椭圆曲线设计方法,用每一个循环增加几十个时钟周期的代价,不但可以换取节省三分之一以上的器件资源,而且总的电路延迟也会相应降低。总的来说,对于算法的速度不但没有降低,反而有所提高。

2.3.3 kP的部分代码

以下是kP的部分代码(该代码为9位示意,并不是实用的高位方案)。

3 验证结果和结论

在QuartusII5.0工具下,采用Verilog HDL语言实现了椭圆曲线数字签名方案,并对其进行了仿真、综合,实验结果证明,本文的设计正确有效,实现了签名功能。其中关键的kP仿真波形如图3所示。

本文主要进行了椭圆曲线数字签名方案的硬件设计和优化工作,其中采用了归一化的设计思想,使点乘的实现节省了三分之一的资源。椭圆曲线密码是近年来密码体制中的研究热点之一,使用FPGA,VLSI等进行其硬件设计已成为信息安全领域的引人关注的工作,值得进一步的研究和探讨。

参考文献

[1]Darrel Hankerson,Alfred Menezes,Scott Vanstone.Guide to Elliptic Curve Cryptography[M].2003.

[2]曾晓洋,周晓方,沈泊,等.参数可选的高速椭圆曲线密码专用芯片的VLSI实现[J].通信学报,2003,24(9):35-41.

[3]高献伟,靳济方,方勇,等.GF(2m)域乘法器的快速设计及FPGA实现[J].计算机工程与应用,2004(25):111-123.

[4]Sunar B,Koc C K.An Efficient Optimal Normal Basis Type II Multiplier[J].IEEE Trans.Computers,2001,50:83-87.

[5]候整风,李岚.椭圆曲线密码系统(ECC)整体算法设计及优化研究[J].电子学报,2004,32(11):1904-1906.

椭圆曲线数字签名第4篇

[关键词]椭圆双曲线焦点三角形面积离心率

【中国分类法】：G633.6

正文：椭圆（或双曲线）上一点与它的两个焦点的连线构成的三角形称之为焦点三角形。

椭圆（或双曲线）中焦点三角形问题是一类常见的圆锥曲线题型，教学中有两个极富魅力的性质，这些性质有趣地揭示了解析几何的性质特征。

性质1：①证明：设，由椭圆的定义：

例1：设椭圆的两个焦点为，椭圆上点满足，则

△F1PF2的面积是

解析：本题属于焦点三角形问题，

例2：已知、是椭圆（＞＞0）的两个焦点，为椭圆上一点，且 .若的面积为9，则 =__________

解析：本题属于焦点三角形问题，

例3．已知点是中心在原点,长轴在x轴上的椭圆的一个顶点,离心率为 ,椭圆的左右焦点分别为F1和F2 .试探究椭圆上是否存在一点P,使 ,若存在,请求出点P的坐标;若不存在,请说明理由.

解析：本题属于焦点三角形问题，依题意，可求得椭圆方程是：，设上顶点为，，当与重合时，达到最大，此时在△F1BF2由中由余弦定理可知：，故椭圆上存在四个点使得，设使得，由等面积法得：

代入得

故，，，

性质1：②证明：设，由双曲线定义：

例4．已知为双曲线的两个焦点，P在双曲线上，且 =32。

则（）（A）（B）（C）（D）

解析：本题属于焦点三角形问题，由面积公式：

另外故所以易知选（B）

例5.已知双曲线的焦点为F1、F2，点M在双曲线上且则点M到x轴的距离为（）

（A）（B）（C）（D）

解析：本题属于焦点三角形问题，由面积公式：

而故所以易知选（C）

例6【2012高考辽宁文15】已知双曲线x2 y2 =1,点F1,F2为其两个焦点，点P为双曲线上一点，若P F1⊥P F2,则∣P F1∣+∣P F2∣的值为___________________.

【解析】焦点三角形面积公式求解：

性质2：③证明：设，

由椭圆的定义：

性质2：④证明：设，由双曲线的定义：

例7．（2013年高考湖南（文））设F1,F2是双曲线C,(a>0,b>0)的两个焦点.若在C上存在一点P.使PF1⊥PF2,且∠PF1F2=30°,则C的离心率为___________.

解析：本题考查的是双曲线中焦点三角形的离心率。

对应的

例8．椭圆的左、右焦点分别为，焦距为．若直线

经过点且与椭圆有一个交点，满足，则该椭圆的离心率等于

【解析】本题考查的是椭圆中焦点三角形的离心率．由题意可知，中，

结束语：我们对焦点三角形问题的研究，不仅可以深入了解圆锥曲线的有关性质特征，还可以有利于解决与焦点三角形有关的问题。能够熟练运用这两组性质，既方面解题又可增强我们在教学活动中对问题的研究。

参与文献：

[1] 2004年05期《数学通报》, 熊光汉，“椭圆焦点三角形的若干性质”；

[2] 《考试》，朱益民，“独具魅力的焦点三角形”；

[3] 《数学通讯》2000年12期, 魏华， “关于焦点三角形面积的求法”。

椭圆曲线数字签名第5篇

数字签名方案具有抗假冒、不可否认和不可伪造性, 即接受者能够验证签名者对报文的签名, 签名者无法否认自己的签名, 接受者无法伪造或篡改签名的报文。在现实生活中, 不仅需要单个人对某个消息进行签名, 有时还需要多人合作对某个消息进行签名。

多重数字签名[1,2]是多个成员合作对同一消息进行的签名, 签名的长度与签名的人数无关。在多重数字签名中, 每个成员利用自己的私钥对消息签名;签名的验证者只需利用群体唯一的公钥就可以验证签名的有效性。根据签名过程的不同, 多重数字签名可分为有序多重数字签名[3]和广播多重数字签名。有序多重签名是一种串行的签名, 它要求签名者按照一定的次序对消息进行签名, 每一个签名者收到上一签名后首先验证签名的有效性;如果签名有效, 则继续签名, 然后发送到下一个签名者;如果签名无效, 则拒绝对消息签名并终止整个签名。广播多重签名是并行的, 所有签名者可以同时对消息进行签名并发送给签名收集者, 然后由签名收集者将所有签名整理成一个多重签名。而结构化的多重数字签名[4,5,6]是指签名团体具有事先约定的签名结构, 这种结构可以是有序的或者广播的, 也可以两者结合。其结构比较灵活, 适用于现实应用, 因在实际过程中不同的签名者往往具有不同的权限, 因此每个签名者在签名结构中的不同位置也会影响签名的有效性。

基于椭圆曲线离散对数问题的密码体制具有密钥短小、运算速度快等优点, 并且椭圆曲线系统的参数规模要小得多, GF (2160) 上的椭圆曲线系统相当于1024bit的RSA系统。因此, 本文基于椭圆曲线的离散对数问题, 寻找一种合适的签名函数[7], 提出了一种基于椭圆曲线的结构化多重数字签名方案 (简称ECSMS) , 此方案具有较好的安全性和实用性。

1 结构化椭圆曲线多重数字签名

结构化的多重数字签名是指签名团体具有事先约定的签名结构, 这种结构可以是有序的或者广播的, 也可以两者结合, 比较灵活, 能够较好地适用于现实应用。结构化椭圆曲线多重数字签名结构如图1所示。

在图1中, U1, U2, …, Ut是有序的结构, 而Ui, 1, Ui, 2, …, Ui, l是广播的结构, 在此结构中, 所有签名者可以同时对消息进行签名并发送给集合节点Ui, 然后Ui将所有签名整理成自己的签名。

2 结构化椭圆曲线多重数字签名算法

2.1 ECSMS系统初始化

系统参数:GF (q) , E, G, n, h。其中GF (q) 是有限域, E是GF (q) 上的椭圆曲线, G是E上的一个有理点, 即基点, G的阶为n (n为素数) , h为一个Hash函数。每一个签名者Ui的私钥为di∈{1, 2, …, n-1}, 公钥ei=diGmodn。

对于签名中的有序部分, 消息发送者U预先设计一种签名顺序 (U1, U2, …, Ut) , 并将这种签名顺序发送给每一位签名者Ui和签名验证者Uv。

2.2 ECSMS有序签名结构

2.2.1 有序签名产生过程

U将消息m发送给第一个签名者U1, 设s0=0, 有序签名者按照消息发送者U事先预定的签名顺序 (U1, U2, …, Ut) 依次签名。那么当Ui收到 (m, (si-1, Ri-1) ) 和Rj (j=1, 2, …, i-1) 之后, 首先要对前i-1个签名者进行验证。

(1) Ui:有序签名结构的前面几个签名人为Uj (j=1, 2, …, i-1) , 令vj=ejmodn。

(2) Ui:计算 $\bar{R} = \sum_{j = 1}^{i - 1} R_{j} m o d n = (x, y)$ , 取R=xmodn;计算 $Η_{i} = s_{i - 1} G + \sum_{j = 1}^{i - 1} (h (m) - r_{j}) v_{j} m o d n = (X_{i}, Y_{i})$ , 如果Hi=0拒绝;否则判断R?=Ximodn, 如果等式成立, Ui认为前i-1个签名有效, Ui继续产生多重签名;否则签名无效, 终止签名。

(3) Ui:随机选择ui∈{1, 2, …, n-1}, 计算Ri=uiGmodn= (xi, yi) , ri=ximodn。

(4) Ui:计算si=si-1+ui- (h (m) -ri) dimodn。

(5) Ui:将 (m, (si, Ri) ) 发送给下一个签名者, 将Ri分别发送到以后的签名者及签名验证者。

定理1 签名人U1, U2, …, Ui-1以及Ui都遵守协议, 则Ui总将接受前i-1个签名人的多重签名, 并将继续对消息进行签名。

证明:

由于R=Xmodn, 所以R=Ximodn成立, 前i-1个签名人的多重签名被签名者Ui接受。

2.2.2 有序签名验证过程

Ui要对前i-1个签名者的多重签名进行验证, Uv要对最终的签名进行验证, 那么验证者进行如下的操作:

(1) 若签名人为Ui (i=1, 2, …, t) , 则令vi=eimodn。

(2) Uv: $\bar{R} = \sum_{i = 1}^{t} R_{i} m o d n = (x, y)$ , 取R=xmodn。

计算 $Η = s_{i} G + \sum_{i = 1}^{t} (h (m) - r_{i}) v_{i} m o d n = (X, Y)$ , 如果H=0, 则拒绝这个签名, 否则, 判断R?=Xmodn, 如果成立则接受这个签名。

定理2 U1, U2, …, Ut和签名验证者Uv都遵守协议, 则签名验证者Uv总是会接受多重签名。

证明:

$\begin{array}{l} Η = (X, Y) = s_{i} G + \sum_{i = 1}^{t} (h (m) - r_{i}) v_{i} m o d n \\ = \sum_{i = 1}^{t} (u_{i} G - (h (m) - r_{i}) v_{i}) m o d n \\ + \sum_{i = 1}^{t} (h (m) - r_{i}) v_{i} m o d n_{i} \\ = \sum_{i = 1}^{t} u_{i} G = \sum_{i = 1}^{t} R_{i} = \bar{R} = (x, y) \end{array}$

由于R=xmodn, 因此R=Xmodn成立, 则多重签名将被验证者Uv接受。

2.3 ECSMS广播签名结构

2.3.1 广播签名生成过程

消息发送者U将消息m发送给每个签名者Ui, j (j=1, 2, …, l) , 消息签名者Ui, j进行如下操作:

(1) Ui, j:随机选择ui, j∈{1, 2, …, n-1} 计算:

Ri, j=ui, jGmodn= (xi, j, yi, j)

ri, j=xi, jmodn

(2) Ui, j:将Ri, j发送给集合者。

(3) Ui: 计算 $\bar{R} = \sum_{i = 1}^{l} R_{i, j} m o d n = (x, y), R = x m o d n$ 。

(4) Ui:集合者Ui将R和h (R) 发送给用户。

(5) Ui, j:

签名方程为:

si, j=ui, j- (h (m) -R) (di, j+h (R) ) modn

验证方程为:

Hi, j=si, jG+ (h (m) -R) vi, jmodn

其中vi, j= (ei, j+h (R) G) modn。

(6) Ui, j:将 (m, si, j) 签名结果发送给集合者Ui。

2.3.2 单用户签名验证过程

Ui收到 (m, si, j) 后进行以下操作:

(1) Ui:令Ri, j= (xi, j, yi, j) , 取ri, j=xi, jmodn。

(2) Ui:验证消息签名 (m, si, j) 的有效性。

Hi, j=si, jG+ (h (m) -R) vi, jmodn。如果Hi, j=0拒绝, 否则判断ri, j?=Xi, jmodn, 如果等式成立, 签名有效, 继续产生多重签名, 否则签名无效, 终止签名。

2.3.3 多重签名产生过程

当结构化的多重签名退化到单纯的广播结构时, 集合节点作为收集者要求出最终的多重签名结果, Ui计算 $S = s_{i, 1} + s_{i . 2} + \dots + s_{i, l} = \sum_{j = 1}^{l} s_{i, j} m o d n$ , (m, S) 即为消息的多重签名;否则它只是作为广播多重签名的验证者对单用户的签名进行验证, 此时它在有序结构中的一些参数不是由它自己产生, 而是由广播中的节点产生, 即集合节点Ui的私钥为di=di, 1+di, 2+…+di, j-1+di, l;公钥为ei=diGmodn , 集合节点Ui的随机数ui= (ui, 1+ui, 2+…+ui, j-1+ui, l) modn, Ri=uiGmodn= (xi, yi) , ri=ximodn。

2.3.4 多重签名验证过程

Ui:计算:

$V = \sum_{j = 1}^{l} e_{i, j} m o d n Η = S \times G + (h (m) - R) V = (X, Y)$

如果H=0, 则拒绝这个签名, 否则, 判断R?=Xmodn, 如果成立则接受这个签名。

3 算法的安全性分析

目前存在的针对多重数字签名的攻击主要有以下几种:伪造数字签名、否认自己的签名、合谋攻击、重法攻击、前向性攻击。下面就针对以上的几种攻击, 对算法的安全性进行分析:

(1) 签名的不可抵赖性可有效防止签名实体内部有人提供不正确的签名, 因为签名收集者会验证每个签名的有效性, 即通过等式Hi=siG+ (h (m) -R) vimodn= (Xi, Yi) 进行验证。

(2) 抗合谋伪造签名针对该安全性分析如下:

si, j=ui, j- (h (m) -R) (di, j+h (R) ) modn

即 $\sum_{j = 1}^{l} s_{i, j} \neq \sum_{j = m + 1}^{l} s_{i, j}$

如果攻击团体Ui, 1, Ui, 2, …, Ui, m选取私钥满足 $\sum_{j = 1}^{m} d_{i, j} = 0$ 且随机数ui, j∈{1, 2, …, n-1}满足 $\sum_{j = 1}^{m} u_{i, j} = 0$ , 并计算Ri, j=ui, jGmodn= (xi, j, yi, j) , 把Ri发送给集合者后试图构造u′i, j=ui, j+ (h (m) -R) h (R) 并产生签名si, j=u′i, j- (h (m) -R) (di, j+h (R) ) modn, 则:

然而, 此签名无法通过签名验证方程:

Hi, j=si, jG+ (h (m) -R) vi, jmodn= (Xi, j, Yi, j)

如果攻击团体中的m-1个成员Ui, j (j=1, 2, …, m-1) 选取 $\sum_{j = 1}^{m - 1} u_{i, j} = 0$ , 并根据另外一个成员Ui, m选择的ui, j计算 $\bar{R} = \sum_{j = 1}^{l} R_{i, j} m o d n = \sum_{j = m}^{l} R_{i, j} m o d n = (x, y)$ , 然后构造u′i, j=ui, j+ (h (m) -R) h (R) , 最后生成签名, 既满足S=0又能通过验证方程, 但是因为只有先公布Ri才能生成 $\bar{R}$ , 并且攻击团体无法在公布Ri之前虚假构造u′i, j=ui, j+ (h (m) -R) h (R) 。

因此, 本文提出的方案可以抵抗合谋攻击。

(3) 防止重放攻击可以在消息中加入时间戳防止重放攻击。

(4) 抗前向攻击我们可以使用先前的密钥生成新的密钥, 可以如Ui在j时段的私钥为dij, 则在j+1时段的私钥为dij+1=dijGmodn。

4 结束语

本文是基于椭圆曲线的结构化多重数字签名, 相对于其它多重签名方案更具灵活性。本方案适用于各种复杂的签名结构, 且安全性高, 满足数字签名所要求的不可伪造性、不可抵赖性、抗合谋攻击、防止重发攻击、前向安全性等安全特性。同时本方案基于椭圆曲线离散对数问题的密码体制, 具有密钥短小、运算速度快等优点, 从而使该签名算法具有更高的抗攻击性和更具实用性。

摘要：基于椭圆曲线数字签名函数, 提出了一种广播和有序相结合的结构化多重数字签名方案, 并对算法进行安全性分析。该方案结构灵活, 适合于各种复杂多重数字签名且能满足数字签名所要求的不可伪造性、不可抵赖性、抗合谋攻击、防止重发攻击、前向安全性等安全特性。

关键词：椭圆曲线,多重签名,结构化

参考文献

[1]Harn L, Kiesler T.New digital signature based on discrete logarithm[J].Electronics Letters, 1994, 30 (5) :396-398.

[2]李子臣, 杨义先.ElGamal多重数字签名方案[J].北京邮电大学学报:自然科学版, 1999, 22 (2) :30-34.

[3]赵择茂, 刘凤玉, 徐慧.基于椭圆曲线密码体制的签名方程的构造方法[J].计算机工程, 2004, 30 (19) :96-97.

[4]Harn L, Lin C Y, Wu TC.Structured multi-signature algorithms IEEP-roc-Comput.Digit.Tech.2004, 151 (3) :231-234.

[5]朱南希, 李志斌.一种改进的结构化多重数字签名[J].计算机安全, 2006 (9) :13-15.

[6]卢鹏菲, 詹雄泉, 洪景新.基于椭圆曲线的有序多重数字签名方案[J].厦门大学学报:自然科学版, 2005, 44 (5) :341-343.

椭圆曲线数字签名第6篇

1985 年Montgomery在文献[1]中提出了一种基于Montgomery型椭圆曲线计算标量乘kP的算法,这是一种与Weierstrass曲线上标量乘完全不同的计算方法。该方法无需预计算,只需利于并行运算,且能有效抵抗时间攻击和能量分析攻击,因此具有一定优势。

1999 年,J. Lopez和R. Dahab在文献[2]中基于Montgomery思想［3］提出了一种定义在二进制域GF( 2m) 上的椭圆曲线快速标量乘算法,称作Algo- rithm2A算法。该算法在计算标量乘的过程中只需对x坐标进行计算,在最后通过公式将y计算出来,从而降低了计算量,提高了计算效率。

2003 年,白国强等人在文献[4]中,为提高椭圆曲线数字签名方案中验证过程的速度,提出了一种一次性并行计算kP + lQ的方法。该方法较分别计算kP和lQ减少了约25% 的计算量,提高了签名验证的效率, 但该方法存在一定的局限性。

文中首先对白国强的方法进行了改进,克服了不足,然后基于该方法思想,提出一种快速标量乘算法, 并对该算法进行了分析。最后将快速标量乘算法和改进的方法分别应用到ECDSA的签名生成及验证中,提高了ECDSA的效率。

1 基于Montgomery思想的标量乘算法

1. 1 Montgomery型曲线

Montgomery型曲线［1，3］是Montgomery引入的,其定义为: 对于A,B∈GF( q) ,B( A2- 4) ≠0,由式( 1) 定义的曲线称为一个Montgomery形式的椭圆曲线

相比传统的Weierstrass型椭圆曲线,基于Montgomery曲线计算标量乘算法具有以下优势: ( 1) 无需预计算, 适合在存储空间有限的条件下实现。( 2) 可并行计算,这使得在计算多标量乘时更具优势。( 3) 据研究分析,Montgomery算法能有效抵抗时间攻击和能量攻击。因此,Montgomery型椭圆曲线在ECC密码体制中地位重要,而基于Montgomery的快速标量算法的研究也有着重要意义。

1. 2 基于Montgomery思想的标量乘算法

基于Montgomery思想的标量乘算法较多,最初是1985 年Montgomery在文献[1]中提出的算法1。

算法1计算标量乘的Montgomery方法。

输入:正整数k,椭圆曲线上一点P。

输出: Q = kP。

(1)计算k的2进制序列k=(kt-1kt-2…k1k0)2。

(2)令P1=P,P2=2P。

( 3) Q←O。/ /其中O为无穷远点。

( 4) 对于i从t - 2 到0,重复执行: 若ki= 1,则P1= P1+ P2,P2= 2P2。否则P2= P2+ P1,P1= 2P2。

( 5) 返回( Q = P1) 。

该算法无需预计算,因此不需要额外的存储器,更适合存储能力有限的场合,且主循环中的每一次迭代均完成相同的操作,因此对时间分析攻击和能量分析攻击具有良好的抵抗能力。

1999 年J. Lopez和R. Dahab在文献[2]基于Montgomery的思想提出了一种新的计算标量乘的方法［2］,该方法基于定义在GF( 2m) 的椭圆曲线。在迭代点乘计算中,该方法只需计算x坐标,在最后一步根据GF( 2m) 的椭圆曲线引理1［2］和引理2［2］求得标量乘的y坐标。

引理1设P=(x,y),P1=(x1,y1)和P2=(x2,y2)为椭圆曲线E上的点,假如P2=P1+P,则P2+P1的x坐标x3可由点P,P1和P2的x坐标的计算如下

引理2设P=(x,y),P1=(x1,y1)和P2=(x2,y2)为椭圆曲线E上的点,假设P2=P1+P,x≠0。则P1的y坐标可由点P的x,y坐标及点P1和P2的x坐标按照如下公式计算

由于在迭代运算中无需求y坐标,因此该方法相对于算法1,其运算量有所减少。

2003 年,白国强等［4］提出了一种基于Montgomery思想的双标量乘签名验证的快速算法,算法提出一种一次性计算kP + lQ的方法,如算法2 所示。该方法避免了分别计算kP和lQ,因此减少了计算量。

算法2 基于Montgomery思想计算kP + lQ。

输入: 正整数k,正整数l,椭圆曲线上点P、Q∈ E( Fq) 。

输出: kP + lQ。

(1)计算k的2进制序列k=(kn-1kn-2…k1k0)2。计算l的2进制序列l=(ln-1ln-2…l1l0)2。

( 2) 令R1= P + Q,R2= 2( P + Q) ,s = 0。

( 3) 对于i从n -2 到0,重复执行: 若ki= 1,li= 1, s = 0 则R1= R1+ R2,R2= 2R2。若ki= 1,li= 0,s = 0 则R1= R1+ R2,R2= 2( R2- Q) ,s = 1。若ki= 0,li= 0,s = 0 则R2= R1+ R2,R1= 2R1。若ki= 0,li= 1,s = 0 则R2= R1+ R2,R1= 2( R1+ Q) ,s = 1。若ki= 1,li= 1,s = 1 则R1= R1+ R2,R2= 2( R2+ Q) ,s = 0。若ki= 1,li= 0,s = 1 则R1= R1+ R2,R2= 2R2。若ki= 0,li= 1,s = 1 则R2= R1+ R2,R1= 2R1。若ki= 0,li= 0,s = 1 则R2=R1+R2,R1=2(R1-Q),s=0。

(4)若s=1,则R1=R1-Q。

(5)返回R1=kP+lQ。

可以说,算法2 就是在算法1 的基础上,提出的一种一次性计算kP + lQ的方法。与分别计算kP、lQ相比,该算法约减少了25%的计算量,故提高了效率。

1. 3 算法2 的局限性分析及改进

但算法2 仍存在一定的局限性［6］: 在利用算法2 计算多点乘kP + lQ时,默认标量k和l的二进制长度是相等的,若不等,则此算法不适用。对于标量k和l二进制长度不相等的情况,实际就是在运算过程中,算法默认将高位补0 后的l最高位置1,在这里首先假设k的长度较长,且长度为n,所以相当于最后结果多计算了2n － 1Q。易知,可采取预计算2n － 1Q,在计算最后减去2n － 1Q仍可得到正确的结果。但这种方式最终都会在算法2 的基础上,增加额外的计算量。

通过观察可知计算2n － 1Q相当于对Q做了n - 1 此倍点运算,而刚好计算过程中,循环次数为n -1 次, 因此可考虑在第一步赋初值时将R1、R2均减Q,则经过n -1 次循环后刚好减少了2n － 1Q。经验证,这一想法是可行的。由于篇幅原因,具体分析过程不在此做以赘述。

综上可知,对算法2 的改进主要是针对标量k和l二进制长度不相同的情况。改进思路如下:

( 1) 在循环开始前,首先判断标量k和l的二进制最高位是否为0。

( 2) 若存在最高位为0,则给R1、R2赋初值时减去相应的基点。

体现在算法中,可第二步表示如下,其他不变。

令R1=P+Q,R2=2(P+Q),s=0;

若kn-1=0,则R1=R1-P,R2=R2-P;

若ln-1=0,则R1=R1-Q,R2=R2-Q。

改进的算法2 弥补了原算法的不足,使算法更具普遍性和通用性,并适合任意标量k、l的组合。

2 分段快速标量乘算法设计

算法2 及其改进算法提供了一种椭圆曲线数字签名中快速验证kP+lQ的方法,同时还提供了另一种计算快速标量乘hP的思路,在此称为基于Montgomery的分段快速标量乘算法。

2. 1 算法思路与设计

分段思想是该算法的核心,是指将标量乘hP中的标量h的二进制序列分成等长的两段,从而转化为两个标量乘进行计算。基于分段思想,研究的基于Montgomery的分段快速标量乘算法就是将标量h的二进制序列分成等长的k和l两段,然后转化为kP和lQ两个标量乘,再利用改进的算法2 的Montgomery方法,一次性并行计算kP + lQ得到标量乘hP。该算法仅需预算少量的点,就能使算法效率显著提高。

设标量h的二进制序列为h = ( hn － 1hn － 2…h1h0)2, 根据分段思想将其分成k和l两段:

若n为偶数,即n =2m,则k和l各m位。

若n为奇数,即n =2m -1,则将前m位分给l,然后在后一段将其高位补0 ~ n位。

于是有

因此,hP = kP + lQ,显然Q =2mP,则有

再将标量乘hP的计算转化为kP + lQ后,就可用算法2 的思想,一次性并行计算kP + lQ。

由此可见,基于Montgomery的分段快速标量乘算法,是对改进的算法2 的一个扩展应用,提供了一种良好的计算标量乘的方法。为使算法易于扩展各编程的实现,在改进算法2 的基础上再进行以下改进:

( 1) 由上文可知,变量s为一个步调参数,与ki、li, 有关,则可设。

( 2) 对算法2 第二步的改进中,增加了对k和l最高有效位是否为0 的判断,但在分段快速标量乘算法中,由于分段方法的限定,最高有效位为0 的情况只会出现在标量k中。因此,只需对k进行判断,且判断可简化为“”。

( 3) 循环中会出现Rx= 2( Rx+ eQ) 的计算式,x∈ { 1,2} ,其中e∈{ 0,1,-1} 的值与ki、li和s的值有关。当ki⊕li⊕s = 0 时,e = 0,则Rx= 2Rx; 当ki⊕li⊕s = 1 时,e =1 或-1,此时e的值与li值相关。当li= 0 时, 有Rx= 2( Rx- Q) ; li= 1 时,有Rx= 2( Rx+ Q) 。所以, 可设。

因此,分段快速标量乘算法如下:

算法3分段快速标量乘算法。

输入: 正整数h的2 进制序列h = ( hn － 1hn － 2… h1h0)2,椭圆曲线上点P∈E( Fq) 。

输出: hP。

( 1) 若n为偶数,则令n =2m,且等分h的二进制序列为k和l。若n为偶数,则令n =2m -1,且依次将前m位和后m -1 位分给l和k,并在k高位补0 ~m位。即

预计算Q =2mP,P + Q,P - Q。

( 3) 对于i从n -2 到0,重复执行:,若ki= 1,则R1= R1+ R2,R2= 2( R2+ eQ) ; 若ki= 0,则R2= R1+ R2,R1= 2( R1+ eQ) ;。

(4)若s=1,则R1=R1-Q。

(5)返回R1=hP=kP+lQ。

2. 2 算法效率分析

分段快速标量乘算法虽然将单标量hP乘变成了双标量乘kP + lQ,看似使计算更为复杂。但若直接计算hP,将需循环n - 1 次。而将hP分段转化为kP + lQ后, 需要的循环次数减少为原来的1/2,约为( n -1) /2 次。

此外,算法3 是对算法2 改进后的一个扩展应用, 与改进的算法2 相比,只相应地多了对标量h的分段过程。而分段过程相对于域Fq的乘法、平方和求逆运算则可忽略不计。因此,分段快速标量乘算法的平均计算量与算法2 的计算量相同。由文献[3]可知,在仿射坐标下,算法2 平均总计算量为3m( I + M + S) + mM + I + 4M + 2S。

若基于Montgomery思想直接计算hP,由文献[2 ~3] 可知,平均总计算量为2n( I + M + S) + I + 4M + 2S。其中n =2m,且m和n足够大。则与直接计算标量乘hP相比分段标量乘快速算法计算量减少的概率是

因此,基于Montgomery的分段快速标量乘算法的效率约提高了25%。

为更清楚地体现分段快速标量乘算法在效率上的提高,本文通过编程实现,对Montgomery标量乘算法与分段快速标量乘算法做了对比分析。实验环境为: 主频1. 88 GHz,内存1. 0 GB的计算机。实验参数选取为: 二进制域,参数n∈( 100,512) ,并任意选取100 ~ 512 之间的标量若干参与对比分析。取x坐标为参加对比标量的二进制位数,y坐标为计算相应标量乘所需的时间。则比较结果如表1 所示。

3 基于快速标量乘算法数字签名方案

综合改进的算法2 和分段快速标量乘算法优势, 本文设计了一种基于椭圆曲线的快速数字签名［7］方案。方案中,将分段快速标量乘算法运用到签名生成过程中,用其计算签名生成过程中的标量乘kG。将改进的算法2 运用于签名验证过程中,用其计算验证过程中的u1G + u2Q,具体应用如图1 所示。

本方案是基于传统椭圆曲线数字签名的一个改进的快速数字签名方案,该方案在签名过程和验证过程中均有所改进,具体如下: ( 1) 签名的生成阶段,在选择伪随机数k后,需计算标量乘kG = ( x1,x2) 。此时, 方案采用了本文设计的基于Montgomery的分段快速标量乘算法,提高了计算效率。( 2) 签名的验证阶段, 计算量最多的是u1G + u2Q,方案采取改进的算法2,一次性并行计算u1G + u2Q,提高了签名验证的速度。

4 结束语

本文分析了基于Montgomery思想的标量乘算法, 针对算法2 的局限性进行了改进,并基于改进的算法2, 提出了一种分段快速标量乘算法。经分析验证,该算法减少了计算量,且提高了运算速度。最终将改进的算法2 和分段快速标量乘算法运用到ECDSA中,设计了快速ECDSA方案,提高了签名与验证的效率。

摘要：计算标量乘kP是ECC快速实现的关键,也是ECC研究的热点问题。文中介绍了基于Montgomery思想的快速标量乘算法,重点介绍了白国强等人的运算多标量乘kP+lQ的算法,并分析了其局限性,同时对其进行了改进。在此基础上,设计了一种分段快速标量乘算法,将改进的算法与分段标量乘算法运用到ECDSA中。经分析验证,分段快速标量乘算法,提高了效率,对ECDSA的快速实现具有一定意义。

椭圆曲线数字签名第7篇

离散对数问题(DLP)是公钥密码体制的一个基本问题，它的困难性决定了很多密码算法或方案的安全性。DLP公钥密码体系基于有限乘法群上的离散对数问题的求解困难性，其中最著名的有ElGamal公钥密码体系和DSA(Digital Signature Algorithm)数字签名算法。

椭圆曲线离散对数问题(ECDLP)这种密码体制的诱人之处在于在安全性相当的前提下，可使用较短的密钥，密钥长度为160比特，其安全性相当于RSA使用1024比特模数。密钥短意味着小的带宽和存储要求，这在群签名的应用中可能是决定性的因素。椭圆曲线密码体制的诱人之处还在于它建立在一个不同于大整数分解及素域乘法群离散对数问题的数学难题之上，椭圆曲线资源丰富，同一个有限域上存在着大量不同的椭圆曲线，这为安全性增加了额外的保证,这也为软、硬件实现带来方便[2]。

由于椭圆曲线密码体制在安全性和效率上的优势，它已经成为公钥密码学下一步发展的方向，本节设计了一个基于椭圆曲线数字签名的群签名方案。

1 基于椭圆曲线的群签名方案设计

1.1 初始化

首先,构造一条安全的椭圆曲线y=x2+ax+b,a,b∈RZp且满足4a3+27b2≠0。#E(Zp)为椭圆曲线的点数，有#E(Zp)|n(n≥160)，G是一个素基点，|#G|=n。群管理者T随机选择一数xT为私钥xT∈RZp，并计算公钥：yT=xT·G，并公开参数{a,b,p,n,G,yT}。

1.2 成员加入

如果一个用户Ui想加入该群，首先随机选取私钥xi∈RZn*，并计算公钥：PKUi=xi·G，然后使用群管理者公钥yT加密后发送给群管理者Ey T(PKUi)，群管理者使用自己的私钥解密后，随机选择ri∈RZn*,然后进行下列计算：

并把(Ri,Si)用Ui的公钥加密EPKUi(Ri,Si)后发送给用户，群管理记录并保存(Ri,Si,ri)，为以后验证作好准备。用户Ui收到发送的消息后，先使用私钥解密，再检验等式ri-xi·xT(mod n)=-ri·G+ri·PKUi(mod n)是否成立，如果成立，则把(Ri,Si)作为群签名的证明书。

1.3 签名

因为群签名具有匿名性，所以签名用户Ui先要对自己的签名证书进行盲化，然后才能对消息进行签名。群签名者Ui要对消息M签名，按以下步骤进行：

1)Ui随机选择两个随机数R1,R2∈RZn*;

2)计算：

3)群签名

签名者Ui再随机选择β∈RZn*，计算

则对消息M的群签名为：(r,s,A,B,C,D,M)。

1.4 验证

消息接收者收到群签名信息后，首先计算：

再计算：

如果上式成立，则群签名有效。

1.5 打开

如果发生争执，那么群管理者就要打开群签名信息(r,s,A,B,C,D,M)，因为群管理者先前保存了签名者的成员证书(Ri,Si,ri)，只要找出满足Si·xT·D=xi·E的(Ri,Si,ri)就能识别出签名者的身份。

2 安全性分析

由于椭圆曲线密码体制本身的特性，我们可知这种群签名方案是很安全的，具体分析如下：

2.1 不可伪造性

如果有成员想伪造Ui签名者对消息M进行群签名，首先必须获取Ui的用户证明书(Ri,Si)，但是这个证明书是群管理者使用用户Ui的公钥加密后发送给用户Ui的，所以一般别人很难得到。假设伪造分子得到了用户Ui的证明书，但签名必须满足：Si·G·xi·yT+yT+Ri=xi(Si·G+xi·yT)，那么由于Ri=-ri·G+ri·PKUi=(xi,yi)，这里的ri是真正群签名用户Ui随机选取的，所给伪造者无法知道。任何人想要从上面的式子计算出参数，需要求解基于椭圆曲线上的离散对数问题，而这在计算上是不可能的[3]。

2.2 不可链接性

由于群签名者在每次签名时都重新随机选取两个数R1,R2∈RZn*，因此，同一个签名者进行多次签名是不具有链接性的。如果想通过求解方程组A,B,C,D,E来得到R1,R2也不可能，这是因为还要知道(Ri,Si)及觖椭圆曲线离散对数问题才可能[4]。

2.3 匿名性

因为每次群签名时，签名者都是随机选择R1,R2，而A,B,C,D,E都经过这两个随机数盲化产生的，而对于外界来说，(Ri,Si)是不会被知道的[5]，所以签名具有匿名性。

2.4 可跟踪性

如果发生争执，需要打开群签名提示签名者的身份，那么由于群管理者在生成群成证明书时，已经保存了签名者的身份信息(Ri Si,ri)，即具有跟踪功能[6]。

群签名另一个重要的领域是它的应用问题，如何基于椭圆曲线密码体制的特性，设计群签名设计其他应用协议，如电子现金协议[7]、电子投票协议、电子投票协议以及电子拍卖协议，是一个重要而艰巨的任务。

摘要：群签名在设计上比较复杂,目前的方案基本都是基于离散对数或者知识签名的,签名长度都比较长,因此只有提高群签名的效率,才能使它真正的得到广泛应用。椭圆曲线密码体制在于在安全性相当的前提下,可使用较短的密钥和较小的空间,论文设计了一个基于椭圆曲线数字签名的群签名方案。

关键词：椭圆曲线,群签名,离散对数,安全性

参考文献

[1]Harn.Digital signature with(t,n)shared verification based on discrete algorithms[J].Electronic Letter,1993,29(24):2094-2095.

[2]Chen and Pedersen.New group signature[J].In Advance in Cryptology.EUROCRYPT'94,Lecture Notes in Computer Science,1994:171181.

[3]Camenisch.Efficient and generalized group signature[J].Advances in Cryptology,EUROCRYPT'97,Lecture Notes in Computer Science,1997:465-479.

[4]Camenisch,Stadler.Efficient group signature scheme for large groups[J].In Advance in Cryptology,CRYPTO'97,Lecture Notes in Computer Science,1997:410-424.

[5]Chaum,Heyst.Group signatures[J].Advances in Cryptology-EUROCRYPT'91,Lecture Notes in Computer Sciense,1991:257-265.

[6]张建红.一种高效的群签名[J].电子学报,2005,33(6):113-115.

椭圆曲线数字签名第8篇

代理签名、多重签名、盲签名、多级签名都得到了广泛的研究和应用。然而,现实生活它们还不能满足人们的需要。例如,一个跨国公司的总公司授权某个子公司签署一份合同,而授权过程中不能越级,需从高往低依次进行。总公司的所有董事一起授权给下级公司,下一级公司再往下授权直至权利到达该子公司,签署合同时又不能让子公司知道合同的内容,这样就需要一种新的签名方案来解决这个问题。针对这一点,我们提出了一种新型的签名方案:多级代理盲多重签名方案,并分析了该方案的安全性和效率。

1 方案描述

1)可信中心在有限域GF(p)(p为一大素数)上选择一条椭圆曲线E:y2=x3+c1x+c0及一个具有高阶的基点G0∈E(GF(p)),并定义其阶为q。

其中,P:一个大素数;G0:椭圆曲线上的一个基点;q:基点G0的阶,即qG0=O;ci:i=0,1确定椭圆曲线的系数;H():一个单向的哈希函数。

2)Ai(i=1,2,3...m)表示m个原始签名人,他们想把权力委托给一个代理签名人,让该代理签名人代表他们行使签名权力,GA为该组的管理员。原始签名人Ai的私钥为ki∈Zq*,对应的公钥为PAi=kiG0。

3)Bj(j=1,2,3...n)表示各级代理签名人,他们的私钥为dj∈Zq*,对应的公钥为PBj=djG0。

4)原始签名组和1级代理人之间有授权证书mw1,它不仅包含原始签名组与1级代理人的身份、签名的范围、有效时间等信息,更重要的是它包含对1级代理签名人再授权范围等事项的说明。1级代理签名人对2级代理签名人的授权是否合理要根据mw1进行判断。同样,i-1级代理签名人与i级代理签名人之间有授权证书mwi,包含的内容同上。

5)以上所有的公钥都被CA认证并公开。

2 基于椭圆曲线的多级代理盲多重签名方案

本方案共由三个阶段组成:授权阶段、签名阶段和验证阶段。在授权阶段中为了描述更加清楚,分为第一级授权和第i级授权两个部分。

2.1 授权阶段

2.1.1 第一级授权

m个原始签名人共同将自己的权力委托给代理签名人B1,让他代表他们行使签名权,具体步骤如下:

1)各原始签名人Ai随机选取一整数ri∈Zq*,计算Ri=riG0=(xRi,yRi),xi=xRiG0,Ui=kiH(mw1)+xRi,将Ui发送给GA,并公开xi。

2)GA收到m个Ui后,验证等式是否成立,若m个等式都成立,计算U=,则U为该原始签名组的群私钥,相应的群公钥为V=UG0,并公开V。

3)GA计算S0=UH(mw1),将S0送给B1。

4)B1收到S0后验证等式是否成立,若等式成立则计算:g1=S0+d1H(mw1),那么g1为B1的代理私钥,代理公钥为Pg1=g1G0,公开Pg1。

2.1.2 第i级授权

第i-1级代理签名人Bi-1将权力授给第i个代理签名人Bi,让Bi代表他去行使签名权,具体步骤如下:

1)Bi-1计算Si-1=Si-2+di-1H(mwi),并把Si-1送给Bi。

2)Bi收到Si-1后验证等式是否成立。

3)若上面的等式成立,Bi计算gi=Si-1+diH(mwi),则gi为Bi的代理私钥,代理公钥为Pgi=giG0。

2.2 签名阶段

签名用户要求Bi对消息m进行签名,具体步骤如下:

1)Bi随机选取ti∈Zq*,计算Zi=tiH(mwi),将Zi发送给用户。

2)用户随机选择α,βZq*作为盲因子对消息进行加盲变换,计算Z'i=αZi+αβH(mwi),h=α-1H(m||Z'i)+β,将h发送给Bi。

3)Bi计算L'i=gi(Zi+h H(mwi)),并将L'i发送给用户。

4)用户收到Li后验证等式是否成立,若成立则对消息进行脱盲变换Li=αL'i,得到最终签名(Li,m,Z'i)。

2.3 验证阶段

接收者收到关于的代理盲签名后,验证等式是否成立,若成立则为合法签名,否则为非法签名。

下面对以上过程中的等式进行证明:

3 多级代理盲多重签名方案的分析

3.1 方案的安全性

对基于椭圆曲线的多级代理盲多重签名方案的安全性分析应该从以下几个方面进行考虑:

1)该方案在验证签名时,使用了原始签名人和代理签名人的公钥,实现了原始签名权和代理签名权的有效分离。

2)该方案的代理签名验证等式中包含了各级代理者的授权信息mwi,可判断各级的授权是否在许可的范围内,因此多级代理是安全的。

3)该方案中用户加盲变换中的α,β是随机选取的,因此h也是随机的,签名方想通过h来获得消息m是基于哈希难题的,所以每位参与签名者都没有办法获知消息的内容,这就保证了消息的盲签名性。

4)该方案可以抵抗不同级别的代理人之间的合谋攻击。由于椭圆曲线签名体制的安全性,任何人都不能求出各级代理签名者的私钥,就算各级代理人之间合谋也不会得到任何其他信息。

从这些角度看出,该方案在满足盲签名和多级代理多重签名的要求下,对消息的签名是安全的。

3.2 方案的效率

本方案因为采用了椭圆曲线的密码体制,密钥长度和签名长度与基于离散对数的密码体制相比,都大大降低。为保证相同的安全性,采用椭圆曲线密码体制密钥长度160bit时,采用基于离散对数的密码体制密钥长度需要1024bit的位长。因此与采用基于离散对数的密码体制实现这种多级代理盲多重签名相比,我们采用的椭圆曲线方案计算的效率更高,更有实际应用价值。

4 结束语

本文利用椭圆曲线构造了一个新型的多级代理盲多重签名方案,利用椭圆曲线密码体制密钥量小,安全性高和灵活性强的特点,将多级签名、门限签名、多重签名和盲签名结合起来,有效的保护消息发送方的隐私权,实现了消息的多级代理。该方案具有安全性强和效率高的优点。

摘要：该文设计了一种新的基于椭圆曲线密码体制的多级代理盲多重签名方案,该方案允许m个原始签名人共同将自己的权力委托给1级代理人,1级代理人在许可范围内继续逐级授权。而且该方案通过盲签名实现了签名的匿名性和不可追踪性。在此数字签名的基础上,采用了椭圆曲线的签名和验证方式,极大的提高了方案的安全性和实现速度。

关键词：椭圆曲线,多级代理签名,多重签名,代理盲签名,多级代理盲多重签名

参考文献

[1]MAMBO M,et al.Proxy Signatures:Delegation of the power to sign Message[J].IEICE Transactions on Fundamentals of Electronic Com-munication and Computer Science,1996,E79-A(9):1338-1354.

[2]MAMBO M,USUDA K Okamoto.Proxy Signature for Delegating Signing Operation[C].Proceedings of the 3rd ACM Conference on Com-puter and Communications,Security,ACM,New York,1996.48-57.

[3]伊丽江,白国强,肖国镇.代理多重签名方案:一类新的代理签名方案[J].电子学报,2001,29(4):569-570.

[4]曹天杰,林东岱,薛锐.基于椭圆曲线的代理多签名方案的安全性分析[J].小型微型计算机系统,2006,5:798-801.

[5]杨政宇,施荣华.一种基于离散对数的群代理多重签名方案[J].铁道学报,2004,8:70-72.

[6]金永明,徐秋亮,陈泽雄.椭圆曲线上的多级代理签名方案[J].计算机工程与应用,2006,20:98-102.

[7]谭作文,刘卓军,唐春明.基于离散对数的代理盲签名[J].软件学报,2003,14(11):1931-1935.

[8]KRAWCZYK H.Simple forward-secure signatures from any signature scheme.In:Proc.Of the 7th ACM Conference on Computer andCommunications Security(CCS2000),108-115.

[9]MIYAJI A.Another countermeasure to forgeries over message recovery signature[J].IEICE Trans Fundamentals,November 1997,E80-A(11):2191-2200.

关于一类椭圆曲线的整点问题第9篇

设Z, Q分别是全体整数和有理数的集合，D是无平方因子正整数，方程

是一类基本而又重要的指数Diophantine方程.1981年，柯召和孙琦[1,2]证明了:当D>2且不被6k+1形的素数整除时，方程 (1) 仅有整数解 (x, y) = (1, 0) .但当D被6k+1形的素数整除时，方程的求解较为困难.

本文考虑D=2p，其中p是奇素数的情形.此时方程 (1) 可写成

对于方程 (2) ，已有下面的结果:

罗明和黄勇庆[3]证明了p=13时，方程 (2) 仅有整数解 (x, y) = (1, 0) ， (3，±1) ， (313，±1086) .段辉明[4]证明了p=19时，方程 (2) 仅有整数解 (x, y) = (1, 0) .但文献[4]的证明有误，因为还有解 (x, y) = (7, 3) .

本文运用初等方法证明了以下结果:

定理设p是奇素数，则当p=199时，方程 (2) 仅有整数解 (x, y) = (1, 0) .

2. 若干引理

引理1不定方程x2-12y4=1仅有整数解 (x, y) = (±1, 0) .

证明可参见文献[5]第275页.

引理2设p是奇素数，则不定方程x4-py2=1仅有整数解 (p, x, y) = (p，±1, 0) ， (5，±3，±4) ， (29，±99，±1820) . (“±”号任取，下同)

证明可参见文献[5]第25-26页.

引理3设p是奇素数，则不定方程4x4-py2=1仅有整数解 (p, x, y) = (3，±1，±1) ， (7，±2，±3) .

证明可参见文献[5]第20页.

引理4不定方程x2-3y4=1仅有整数解 (x, y) = (±1, 0) ， (±2，±1) ， (±7，±2) .

证明可参见文献[5]第69页.

引理5设p是奇素数，则不定方程组

仅有整数解 (p, x, a, b) = (p, 1, 0，±1) ， (13, 313，±2,

证明x=1时，显然 (3) 有整数解 (p, x, a, b) = (p, 1, 0，±1) .下设x≠1，且不妨考虑 (3) 的正整数解.

由 (3) 得，3 (4pa2+1) 2+1= (2b) 2，即 (2b+1) (2b-1) =3 (4pa2+1) 2，所以必存在正整数u, v，使得

若 (4) 式成立，则

这里c>0, d>0, n=cd， (c, d) =1.

由 (8) 解得u=2pc2-d2, v=2pc2+3d2，代入 (6) 式整理得 (2pc2-3d2) 2-12d4=1.

根据引理1，此方程无整数解.

由 (9) 解得u=2c2-pd2, v=2c2+3pd2，代入 (6) 式整理得 (2c) 4-3 (2c2+pd2) 2=1.

根据引理2，此方程无整数解.

由 (10) 解得u=c2-2pd2, v=c2+6pd2，代入 (6) 式整理得4c4-3 (c2+2pd2) 2=1.

根据引理3, c2=1, c2+2pd2=1，即c2=1, d=0.此时n=0, a=0，这与a为正整数的约定矛盾.

由 (11) 解得u=pc2-2d2, v=pc2+6d2，代入 (6) 式整理得 (pc2-6d2) 2-3 (2d) 4=1.

根据引理4，有|pc2-6d2|=7, 2d=2，即d=1, p=13, c=1，故n=1, a=2, x=313, b=181.这给出 (3) 的一组正整数解 (p, x, a, b) = (13, 313, 2, 181) ，从而给出 (3) 的四组整数解 (p, x, a, b) = (13, 313, ±2, ±181) .

若 (5) 式成立，则u2-3v2=2，即u2≡2 (mod3) ，但Legendre符号不可能.因此引理5成立.

3. 定理证明

设 (x, y) 是方程 (2) 的一组整数解.由 (2) 式得

因为 (x-1, x2+x+1) =1或3，故方程 (12) 给出下列四种可能的分解:

情形Ⅰx-1=2a2, x2+x+1=199b2, y=ab;

情形Ⅱx-1=398a2, x2+x+1=b2, y=ab;

情形Ⅲx-1=6a2, x2+x+1=597b2, y=3ab;

情形Ⅳx-1=1194a2, x2+x+1=3b2, y=3ab.

这里a>0, b>0， (a, b) =1.

以下分别讨论这四种情形所给出的 (2) 的整数解.

情形Ⅰ由第一式知x≡1或3 (mod 8) ，代入第二式得

然而由于当p=199时，p≡7 (mod 8) .又b是奇数，故b2≡1 (mod 8) .这时有199b2≡7 (mod 8) ，与 (13) 式矛盾.故不可能.