椭圆曲线数字签名算法

椭圆曲线数字签名算法（ECDSA）

原文The Elliptic Curve Digital Signature Algorithm (ECDSA)

CERTICOM公司

李鹤帅译（部分内容有删节）

摘要

椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线对数字签名算法（DSA）的模拟。ECDSA于1999年成为ANSI标准，并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受，并且包含它的其他一些标准亦在ISO的考虑之中。与普通的离散对数问题（discrete logarithm problem DLP）和大数分解问题（integer factorization problem IFP）不同，椭圆曲线离散对数问题（elliptic curve discrete logarithm problem ECDLP）没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。本文将详细论述ANSI X9.62标准及其协议和实现方面的问题。

1、介绍

数字签名算法（DSA）在联邦信息处理标准FIPS中有详细论述。它的安全性基于素域上的离散对数问题。椭圆曲线密码（ECC）由Neal Koblitz和Victor Miller于1985年发明。它可以看作是椭圆曲线对先前基于离散对数问题（DLP）的密码系统的模拟，只是群元素由素域中的数换为有限域上的椭圆曲线上的点。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题（ECDLP）的难解性。

椭圆曲线离散对数问题远难于离散对数问题，椭圆曲线密码系统的单位比特强度要远高于传统的离散对数系统。因此在使用较短的密钥的情况下，ECC可以达到于DL系统相同的安全性。这带来的好处就是计算参数更小，密钥更短，运算速度更快，签名也更加短小。因此椭圆曲线密码尤其适用于处理器速度、带宽及功耗受限的场合。

ECDSA是椭圆曲线对DSA的模拟。ECDSA首先由Scott Vanstone在1992年为了响应NIST对数字签名标准（DSS）的要求而提出。ECDSA于1998年作为ISO标准被采纳，在1999年作为ANSI标准被采纳，并于2000年成为IEEE和FIPS标准。包含它的其他一些标准亦在ISO的考虑之中。本文中我们将介绍ANSI X9.62标准。也将介绍一些签名的基础知识以及协议及实现方面的问题。

本文其他部分的安排如下：第二节中我们将回顾数字签名方案和DSA。第三节和第四节将分别介绍有限域和椭圆曲线。第五节将讲述域参数的产生，第六节将讲述密钥对的产生。第七节的内容是ECDSA的签名和验证过程。第八章论证ECDSA的安全性。第九节和第十节讲述的是ECDSA协议和实现方面的问题。

2、数字签名方案

2.1背景知识

数字签名的目的是提供一个手写签名的数字化副本。签名是一个依赖于签名者私钥和一段消息的比特串。签名必须是可验证的，即如果对签名的真实性存在疑问，必须由一个中立的第三方作出公正的裁决，并且无需知道签名者的私钥。对签名的抵赖以及伪造签名应该能被发现。

本文论述的是非对称摘要数字签名。“非对称”即用户的密钥对各不相同。用户的私钥用于签名，其他用户用他的公钥来检验签名的真实性。摘要是指对一段消息先用哈希函数进行摘要计算，尔后再对消息摘要进行签名。

安全性。从理论上讲，在选择消息攻击下，数字签名应该是不可伪造的。这一概念由Goldwasser Micali 和Rivest提出。更一般的讲就是攻击者获得用户A的摘要和签名，但他无法用其他的摘要来伪造这样一个签名。

应用。数字签名方案用于以下一些用途：数据完整性（确保数据没有被未知或未授权的中间人改变），数据源认证（确保数据的来源是可信的），不可否认性（确保用户不能对自己的行为进行抵赖）。数字签名是密码学协议的基本组成部分，并且可以提供其他一些服务如：身份认证（FIPS 196，ISO/IEC 9798-3），密钥传递前的认证（ANSI X9.63，ISO/IEC 11770-3），经验证的密钥协商（ISO/IEC 11770-3）。

分类。数字签名方案可以根据所基于的数学难题进行分类：

1、基于大整数分解（IF）的方案，安全性基于大整数分解的难度。实例有RSA方案和Rabin方案。

2、基于离散对数（DL）的方案，安全性基于有限域上普通的离散对数问题。实例包括ElGamal，Schnorr，DSA和Nyberg-Rueppel方案。

3、基于椭圆曲线（EC）的方案，安全性基于椭圆曲线离散对数问题。

2.2数字签名算法

DSA于1991年由NIST提出，并在FIPS 186中得到确认。DSA可以看作是ElGamal签名方案的一个变形。其安全性建立在素域上的离散对数问题的困难性之上。

DSA参数的产生。每个用户的安全参数产生如下：

1、选择160比特的素数q和1024比特的素数p，满足q|p-1。

2、在有限域Zp*中寻找q阶循环子群的生成元g，具体方法是在Zp*选取元素h计算g=h(p-1)/q modp，当g≠1时即找到满足要求的g。

3、域参数就是p，q和g。

DSA密钥对的产生。每个拥有域参数p，q和g进行如下操作：

1、选择伪随机数x满足1

2、计算y=gx modp。

3、用户的私钥是x，公钥是y。

DSA签名过程：

1、选择伪随机数k满足1

2、计算X=gk modp，r=X modq，若r=0则返回第一步。

3、计算k-1modq。

4、计算e=SHA-1(m)。

5、计算s=k-1 (e+xr) modq，若s=0则返回第一步。

6、对消息m的签名就是(r,s)。

DSA签名的验证。为了验证(r,s)是对m的签名，需要使用签名者的域参数(p,q,g)和公钥y进行如下运算：

1、验证r，s在区间[1,q-1]中。

2、计算e=SHA-1(m)。

3、计算ω=s-1 modq。

4、计算u1=ωe modq和u2=rωmodq

5、计算X=gu1 yu2 modp及v=X modq。

6、如果v=r则认可此签名。

安全性分析。由于r和s均小于q，故DSA签名长度小于320比特。DSA的安全性依赖于两个方面，它们都基于离散对数问题的难解性，一个是Zp*上的离散对数问题，目前已有数域筛算法去加以解决，这是一种亚指数级的算法。其平均运算时间为：

O(exp((c+o(1))(lnp)1/3 (lnlnp)2/3))

其中c约为1.923，若p是1024比特的素数，则上式的计算量是无法接受的。因此目前1024比特的DSA 可以应付现有攻击。另一个是q阶子群上的离散对数问题，给定p，q，g和y，y=gx modp，要寻找x，目前最好的算法是Pollard’s Rho算法，大约要做sqrt(пq/2)步。若q是160比特的，则该算法在计算上不可行，因此DSA是很安全的。DSA的安全性主要取决于p和q的尺寸。增加其中一个的尺寸而不增加另一个的尺寸对安全性的提高并无益处。此外，对两种离散对数问题解决算法的提高都会削弱DSA。

安全参数的产生。DSA的早期版本受到了一些批评，因此FIPS 186推出了一种新模式以产生素数以及“可证明的随机性”。它可以防止用户故意构造一个利于破译的素数（例如可以由CA来产生域参数并发送给用户）。FIPS指定了两个模式，分别使用SHA-1和DES，产生伪随机私钥x。FIPS 186指定使用这两种模式以及其他经过FIPS认可的安全模式。

3、有限域

我们将简要介绍有限域的知识。更多详细内容请参看其他书籍。有限域由一个有限集合F和F上的两个二

元运算组成，这两个运算满足某种运算规则，分别称为加法和乘法。有限域的阶即域中元素的个数。当仅当q是素数时存在一个q阶有限域，这个有限域是唯一的，记作Fq。有很多方法可以描述Fq的元素，有些描述方式可以使域上的软件及硬件运算更加高效。若q=pm，其中p为素数，m为正整数，则p称为Fq 的特征，m称为Fq的度。至于椭圆曲线密码，一般基于素域或是多项式域。在3.1和3.2中我们将分别介绍这两种有限域上的元素和运算以及多项式域的两种表示方法：多项式表示方法和正规基表示方法。

3.1有限域Fp

P为素数，有限域Fp称为素域，由整数集{1,2,……,p-1}和其上的符合下列规则的运算组成：

1、加法。a,b∈p，a+b=r，r为a与b的和模p所得的值。

2、乘法。a,b∈p，a*b=s，s为a与b的积模p所得的值。

3、求逆运算。a是Fp中的非零元素，a的逆是唯一的，记作a-1，有a*a-1=1 modp

例1．F23，全部元素为{1,2,……,22}，其上三种运算：12+20=9，8*9=3，8-1=3。

3.2有限域F2m

F2m称之为特征为2的有限域，可以看做是F2上的m维向量空间。F2m中存在m个不同的元素?0, ?1……, ?m-1，任一个?∈F2m均可写为以下形式：

?=a0 ?0+ a1?1+……+am-1?m-1 ai∈{0,1}

集合{ ?0, ?1……, ?m-1}称为F2m在F2上的基。有这样一个基，域中所有元素就可以用一个比特串

(a0,a1,……am-1)来表示。这样，加法就可以用向量的逐比特异或运算来表示，乘法运算则依赖于基的选择。基的选择方式是多种多样的。一些基可以使运算变得高效。ANSI X9.62给出了两种基，分别是多项式基和正规基。

多项式基

f(x)=xm +fm-1xm-1+……f2x2+f1x+f0（fi∈{0,1}）是F2上的m次本原多项式。

域元素。有限域F2m由F2上的所有不多于m次的多项式组成。

F2m={am-1xm-1+……+a1x+a0|ai∈{0,1}}

域元素am-1xm-1+……+a1x+a0可以写为比特串(am-1,……a1,a0)形式。

因此F2m的元素可以写为长度为m的比特串。乘法单位元是(0,0,…,0,1)，加法零元是全零串(0,0,……,0)。域运算。

加法。a=( am-1,……a1,a0)，b=(bm-1,……,b1,b0)，a+b=c=(cm-1,……,c1,c0)，ci=ai XOR bi。

乘法。a=( am-1,……a1,a0)，b=( bm-1,……,b1,b0)，a*b=r=(rm-1,……,r1,r0)，多项式rm-1xm-1+……+r1x+r0由(am-1xm-1+……+a1x+a0)*( bm-1xm-1+……+b1x+b0)模f(x)而来。

求逆运算。a是F2m中的非零元素，a-1满足a-1*a=1

例2.有限域F24,模多项式为f(x)=x4+x+1，有限域中16个元素分别为：

0(0000) 1(0001) x(0010)

x+1(0011) x2(0100) x2+1(0101)

x2+x(0110) x2+x+1(0111) x3(1000)

x3+1(1001) x3+x(1010) x3+x+1(1011)

x3+x2(1100) x3+x2+1(1101) x3+x2+x(1110)

x3+x2+x+1(1111)

F2^4上的运算举例：

(1101)+(1001)=(0100)

(1101)*(1001)=(1111) (x3+x2+1)*( x3+1)=x6+x5+x2+1 (x6+x5+x2+1)mod(x4+x+1)= x3+x2+x+1 (1101)-1=(0100)

x=(0010)是F24的生成元

x1=(0010) x2=(0100) x3=(1000) x4=(0011)

x5=(0110) x6=(1100) x7=(1011) x8=(0101)

x9=(1010) x10=(0111) x11=(1110) x12=(1111)

x13=(1101) x14=(1001) x15=(0001)

模多项式的确定。ANSI X9.62的两条标准如下：

1.如果在F2上有m次三项本原多项式xm+xk+1，则模多项式应在这些多项式中选取k最小的那个。

2.若不存在那样的多项式，则f(x)应为m次5项本原多项式xm+xk3+xk2+xk1+1。这时有三条原则：(1)k3应尽量小。(2)k3确定时k2应尽量小。(3)k3,k2确定时，k1应尽量小。

正规基（略）

4、有限域上的椭圆曲线

本节我们将给出椭圆曲线的简要介绍，更详细的内容请参见其他书目。

4.1Fp上的椭圆曲线

P为大于3的奇素数，定义在Fp上的椭圆曲线有如下形式：y2=x3+ax+b，a,b∈Fp，4a3+27b2≠0 modp。集合E(Fp)包括所有满足方程的(x,y)，x∈Fp,y∈Fp，另外还包括一个无穷远点O。

例4.F23上的椭圆曲线y2=x3+x+4，4a3+27b2=22 mod23，下面是E(F23)上的除无穷远点之外的所有点：(0,2) (0,21) (1,11) (1,12) (4,7) (4,16) (7,3)

(7,20) (8,8) (8,15) (9,11) (9,12) (10,5) (10,18)

(11,9) (11,14) (13,11) (13,12) (14,5) (14,18) (15,6)

(15,17) (17,9) (17,14) (18,9) (18,14) (22,5) (22,19)

加法公式。

椭圆曲线上点的加法遵循的规则称之为“弦切规则”。椭圆曲线上的点及其运算规则即构成椭圆曲线密码系统的基本结构。加法规则最好用几何方法来描述。P=(x1,y1)，Q=(x2,y2)是曲线E上两个不同的点，P与Q的和R(x3,y3)用以下方法求得：作过P和Q的割线，这条线与曲线交于第三点，这个点的共轭即是R。

在进行倍点运算时，只需把割线改成切线即可。

由上面的几何描述，可以导出下面的点加和倍点公式。

1.任意P∈E(Fp)，P+O=O+P=P。

2.P=(x,y)∈E(Fp)，(x,y)+ (x,-y)=O。（点(x,-y)称为-P）

3. P=(x1,y1)∈E(Fp)，Q=(x2,y2)∈E(Fp)，P≠±Q，P+Q=R=(x3,y3)。

x3=((y2-y1)/(x2-x1))2 -x1-x2 y3=((y2-y1)/(x2-x1))(x1-x3)-y1

4. P=(x1,y1)∈E(Fp)，P≠-P，2P=(x3,y3)

x3=((3x12+a)/2y1)2-2x1 y3=((3x12+a)/2y1)(x1-x3)-y1

想要完成这些计算，就需要定义在Fp上的一系列运算，包括加法、减法、乘法和求逆运算。

例5.例4中椭圆曲线上的点加和倍点。P=(4,7)，Q=(13,11)

P+Q=(15,6) 2P=(10,18)

4.2F2m上的椭圆曲线

F2m上的椭圆曲线形式如下：y2+xy=x3+ax2+b，a,b∈F2m，b≠0。集合E(F2m)包括所有满足方程的(x,y)，x∈F2m,y∈F2m，另外还包括一个无穷远点O。

例6.有限域F24，模多项式f(x)=x4+x+1。曲线E: ：y2+xy=x3+?4x2+1。下面是曲线上的除无穷远点之外的所有点：

(0,1) (1, ?6) (1, ?13) (?3, ?8) (?3,?13) (?5,?3)

(?5,?11) (?6,?8) (?6,?14) (?9,?10) (?9,?13) (?10,?)

(?10,?8) (?12,0) (?12,?12)

加法公式。几何描述与Fp上的椭圆曲线一致。

点加和倍点公式如下：

1. 任意P∈E(F2m)，P+O=O+P=P。

2. P=(x,y)∈E(F2m)，(x,y)+(x,x+y)=O，(x,x+y)称为-P。

3. P=(x1,y1)∈E(F2m)，Q=(x2,y2)∈E(F2m)，P≠±Q，P+Q=R=(x3,y3)。

x3=((y2+y1)/(x2+x1))2 +(y2+y1)/(x2+x1)+x1+x2+a y3=((y2+y1)/(x2+x1))(x1+x3)+x3+y1

4. P=(x1,y1)∈E(F2m)，P≠-P，2P=(x3,y3)

x3=x12+b/ x12 y3=x12+( x1+y1/x1)x3+x3

例7.例6中椭圆曲线上的点加和倍点。P=(?6,?8)，Q=(?3,?13)

P+Q=(1, ?13) 2P=(?10,?8)

4.3基本性质

群的阶。E是Fq上的椭圆曲线。Hasse定理指出椭圆曲线上的点（包括无穷远点）个数为#E(Fq)=q+1-t，|t|≤2sqrt(q)，#E(Fq)就是E的阶，t称为E的迹。也就是说曲线的阶大致等于基域的尺寸q。

群结构。E(Fq)是一个秩为1或2的阿贝尔群。E(Fq)同构于Zn1×Zn2，n2整除n1。Zn是n阶循环群。另外n2整除q-1，若n2=1，则E(Fq)是循环群。此时E(Fq)同构于Zn1，存在P∈E(Fq)，使E(Fq)={kP|0≤k ≤n1-1}，这个点叫作E(Fq)的生成元。

例8.循环椭圆曲线。例4中的椭圆曲线E(F23)。# E(F23)=29，曲线的阶为素数，E(F23)是一个循环群并且除O外的其他点都是生成元。选取P=(0,2)。

1=(0,2) 2=(13,12) 3=(11,9) 4=(1,12)

5=(7,20) 6=(9,11) 7=(15,6) 8=(14,5)

9=(4,7) 10(22,5) 11(10,5) 12(17,9)

13(8,15) 14(18,9) 15(18,14) 16(8,8)

17(17,14) 18(10,18) 19(22,18) 20(4,16)

21(14,18) 22(15,17) 23(9,12) 24(7,3)

25(1,11) 26(11,14) 27(13,11) 28(0,21)

29O

5、ECDSA域参数

ECDSA的域参数包括一条合适的椭圆曲线和其上一个基点G。域参数可以全局公开，也可以只对单个用户公开。5.1部分讲述域参数应该满足的要求，5.2部分讲解如何产生随机曲线，5.3部分介绍了一种产生域参数的方法，5.4部分给出了验证域参数是否符合要求的方法。

5.1域参数

为了提高实现效率，基域尺寸和参数的选择都有限制：另外，为了抵抗已知的攻击方式，曲线的选择和基点的阶都有一定的限制。

对域的要求。基域的阶要么q等于p,要么等于2m。前者模一个大素数p，后者模一个多项式或正规基。对曲线的要求。为了抵抗Pollard’s rho和Pohlig Hellman攻击。E上的点的个数应能被一个大素数n整除。ANSI X9.62规定n应大于2160和4sqrt(q)。定义辅因子h=#E(Fq)/n。

选择曲线时应注意的一些其他事项。为了抵抗MOV和FR攻击，曲线应是非超奇异（即要求p不能整除q+1-#E(Fq)）的。更一般的，应当满足n不能整除qk-1，1≤k≤C，一般取C为20。最后，为了抵抗SSSA 对反常曲线的攻击，不得取反常曲线（即#E(Fq)不得等于q）。

为了抵御上面提到的和将来可能出现的对这些特殊曲线的攻击，应使用随机方式选取一条椭圆曲线满足#E(Fq)能被一个大素数整除，满足上述一系列条件的随机曲线不甚可能被这些攻击方式所攻破。可以使用随机数发生器（如SHA-1一类的单向函数）来产生曲线的系数。5.2中介绍了一种类似FIPS-186的模式以产生随机曲线。

概述。域参数的概述。

1.域尺寸q，q=p或2m。

2.域的表示方法FR和其中元素的表示方法。

3.至少160比特长度的随机比特串。

4.两个域参数a和b。

5.基点G(xG,yG)。

6.点G的阶n>160bit，n>4sqrt(q)。

7.辅因子h=#E(Fq)/n。

5.2用随机方法产生椭圆曲线

本节讲述如何用随机方法产生椭圆曲线。随机参数使用SHA-1来产生。使用这种方法产生的椭圆曲线具有良好的随机性，可以避免性质较差的曲线的产生。

q=p的情况

下面要使用到这些参数：t=┌㏒p┐，s=└(t-1)/160┘，v=t-160s

算法1.产生一条随机椭圆曲线。

输入：域尺寸p。

输出：至少160比特的比特串，参数a，b，它们确定了一条Fp上的椭圆曲线。

1．选择一个长度g大于160比特的随机比特串SeedE。

2.计算H=SHA-1(SeedE)，c0表示H的右起v长比特串。

3.W0是H的左起v长比特串。

4.z是比特串SeedE所表示的整数。

5.for i from 1 to s do

(1)si是(z+i) mod2g的比特串。

(2)计算Wi=SHA-1(si)。

6.W是比特串W0||W1||……||Ws。

7.r是比特串W所表示的整数。

8.若r=0或4r+27=0 modp则返回第一步。

9.选择随机整数a,b∈Fp，不能同时为0，要求rb2=a3 modp（可以让a,b同时为r）。

10.选定的曲线为y2=x3+ax+b。

11.输出SeedE，a，b。

Fp上的椭圆曲线同构类。两条定义在Fp上的椭圆曲线E1:y2=x3+a1x+b1和E2:y2=x3+a2x+b2在Fp上同构的充要条件是存在u∈Fp使得a1=u4a2，b1=u6b2（同构的椭圆曲线可以认为是相同的，若E1同构于E2，则E1(Fp)同构于E2(Fp)）。若E1同构于E2且b1不为0，则有a13/b12=a23/b22。奇异椭圆曲线：曲线E:y2=x3+ax+b，4a3+27b2=0 modp，要么是a,b同时为0，要么是a3/b2=-27/4。若r∈Fp，r≠0，r≠-27/4，则存在两个曲线同构群E: y2=x3+ax+b，a3/b2=r modp。算法1的第9步中(a,b)就只有两种选择。第8步中的限制条件确保曲线不是异常曲线。另外我们注意到算法1产生的曲线不会发生a,b有一个为0而另一个不为0的情况，这无关紧要因为这些曲线只是所有曲线中微不足道的一部分，任何算法都不可能完全随机地来产生曲线。

Fp上的扭曲线。两条非同构曲线：E1: y2=x3+ax+b，E2: y2=x3+ac2x+bc3，c∈Fp，是一个非模p二次剩余，则称E1,E2相互扭转。它们的r是相等的。它们的阶满足：#E1(Fp)+ #E2(Fp)=2p+2，若能计算出其中一条曲线的阶，另一条曲线的阶可轻易得出。

算法2.证明一条曲线是在Fp上随机产生的。

输入：域尺寸p，长度g≥160bit的比特串SeedE，域参数a,b。

1.计算H=SHA-1(SeedE)，c0是H的右起v长比特串。

2. W0是H的左起v长比特串。

3. z是比特串SeedE所表示的整数。

4. for i from 1 to s do

(1)si是(z+i) mod2g的比特串。

(2)计算Wi=SHA-1(si)。

5. W是比特串W0||W1||……||Ws。

6. r是比特串W所表示的整数。

7. 验证rb2=a3 modp是否成立，成立则接受，反之则拒绝。

q=2m的情况

下面要使用到这些参数：s=└(t-1)/160┘，v=m-160s

算法3：产生F2m上的一条随机椭圆曲线。

输入：域尺寸2m。

输出：至少160比特的比特串，参数a，b，它们确定了一条F2m上的椭圆曲线。

1. 选择一个长度g大于160比特的随机比特串SeedE。

2. 计算H=SHA-1(SeedE)，b0表示H的右起v长比特串。

3. z是比特串SeedE所表示的整数。

4. for i from 1 to s do

(1)si是(z+i) mod2g的比特串。

(2)计算bi=SHA-1(si)。

5. b是比特串b0||b1||……||bs。

6.若b=0则返回第一步。

7.a是F2m上的随机数。

8.F2m上的椭圆曲线E:y2+xy=x3+ax2+b。

9.输出SeedE，a，b。

F2m上的椭圆曲线同构类。F2m上的两条曲线E1: y2+xy=x3+a1x2+b1，E2: y2+xy=x3+a2x2+b2在F2m上

同构的充要条件是b1= b2且TR(a1)= TR(a2)，TR(?)= ? +?2+ ?4+……+ ?2^(m-1)。同构的椭圆曲线可以认

为是相同的，若E1同构于E2，则E1(F2m)同构于E2(F2m)。下面是F2m上的一个典型的椭圆曲线同构类{ y2+xy=x3+ax2+b|b∈F2m,b≠0,a∈{0, ? }}，其中?∈F2m，是一个满足TR(?)=1的固定元素（若m是奇数，则令?=1）。因此对于已经选定的b，算法3中的步骤7中a只有两种选择。

F2m上的扭曲线。两条不同构的曲线E1: y2+xy=x3+a1x2+b，E2: y2+xy=x3+a2x2+b，TR(a1)≠TR(a2)，则这两条曲线互称为扭曲线。它们的阶满足#E1(F2m)+ #E2(F2m)=2p+2，若能计算出其中一条曲线的阶，另

一条曲线的阶可轻易得出。F2m上的椭圆曲线的阶总是偶数，若TR(a1)=0，则#E1(F2m)=0 mod4，若TR(a1)=1，则#E1(F2m)=2 mod4。

算法4. 证明一条曲线是在F2m上随机产生的。

输入：域尺寸2m，长度g≥160bit的比特串SeedE，域参数a,b。

输出：判断算法3产生的曲线是否是随机的。

1. 计算H=SHA-1(SeedE)，b0表示H的右起v长比特串。

2. z是比特串SeedE所表示的整数。

3. for i from 1 to s do

(1)si是(z+i) mod2g的比特串。

(2)计算bi=SHA-1(si)。

4. b’是比特串b0||b1||……||bs。

5.若b=b’，则接受反之则拒绝。

5.3域参数的产生

下面是产生安全参数的方法：

1.利用算法1或算法3产生曲线E:y2=x3+ax+b或y2+xy=x3+ax2+b。

2.计算N=#E(Eq)。

3.验证N是否有一个长度大于160bit且大于4sqrt(q)的因子n，若没有，则返回第一步。

4.验证n是否能整除qk-1(1≤k≤20)，若能，则返回第一步。

5.验证n是否等于q，若等于，则返回第一步。

6.随机选择点G’∈E(Eq)，计算G=(N/n) G’，重复这一步，直至G≠O，G就是基点。

曲线阶的计算。1985年Schoof提出了一个多项式时间的算法以计算素域上椭圆曲线的阶，后来Koblitz使其也能用于F2m。在q较大时Schoof的算法效率较低。经过若干年的改进，形成了Schoof-Elkies-Atkin算法，即SEA算法（算法细节详见其他资料）。有了SEA算法，在工作站上用若干个小时就可以产生大约200bit左右尺寸的随机曲线。Satoh提出了针对F2m上曲线的新算法，在一台高速PC上若干秒就可以产生一条大约200bit尺寸的曲线。

复乘模式（CM）。（略）

Koblitz曲线。这种曲线是多项式域上的一种反常曲线，首先由Koblitz提出。这种曲线定义在F2m上，而它的系数在F2中取值。因此有两种Koblitz曲线：y2+xy=x3+x+1和y2+xy=x3+1。Koblitz曲线上的标量乘法效率很高。Koblitz曲线在ECDSA中的应用前景广阔。

5.4域参数的验证

域参数的验证确保选定的域参数具有必须的算术性质。这一步骤的必要性包括两点：(1)防止攻击者利用较弱的参数进行攻击。(2)防止在传递参数时出现偶然的编码或传输错误。使用较弱的参数将达不到安全要求。验证域参数的方法。判断D={q,FR,a,b,G,n,h}是否合用可使用下面之一的算法：

1.使用算法5进行验证。

2.D是由一个可靠的系统产生的。

3.D由可靠的组织提供且经过算法5验证。

4. D由可靠的组织提供且由一个可靠的系统产生的。

算法5.椭圆曲线域参数的验证。

输入：D={q,FR,a,b,G,n,h}。

输出：判断参数是否合乎要求。

1.验证q=p或2m。

2.验证FR是合乎要求的。

3.验证G≠O。

4.验证a,b,xG,yG在p或模多项式所规定的范围内。

5.若随机曲线是用户自己用5.2的算法1或算法3产生的，验证a,b确由SeedE生成。

6.q=p时，验证4a3+27b2≠0 modp；q=2m时，验证b≠0。

7.将G代人曲线方程，证明其确在曲线上。

8.验证n是素数。

9.验证n>2160且n>4sqrt(q)。

10.验证nG=O。

11.计算h’=└(sqrt(q)+1)2/n┘，验证h=h’。

12.验证n不整除qk-1(1≤k≤20)。

13.验证n≠q。

14.通过上述验证的D才是合格的。

求椭圆曲线的阶。由Hasse定理可知(sqrt(q)-1)2≤#E(Fq)≤(sqrt(q)+1)2。由于n>4sqrt(q)，故n不可能整除#E(Fq)，因此E(Fq)只有一个n阶子群。另外由于(sqrt(q)+1)2-(sqrt(q)-1)2=4sqrt(q)存在唯一整数h使

(sqrt(q)-1)2≤nh≤(sqrt(q)-1)2，即h=└(sqrt(q)+1)2/n┘。算法5的9，10，11步就是验证nh=#E(Fq)。

正如5.2所指出的，计算椭圆曲线的阶是件异常费时的工作。实际应用中用户可以购买厂家的软件计算曲线的阶，不过这样的软件必须是经过认证的。

6、ECDSA密钥对

ECDSA密钥对的选择与域参数的选择有关。私钥是一个随机整数，公钥是私钥与基点的乘积。6.1介绍如何产生密钥对，6.2讲述怎样验证公钥是否满足要求，6.3将讨论CA的重要性。

6.1密钥对的产生

用户A的密钥对与参数D={q,FR,a,b,G,n,h}有关。在生成密钥对前用户必须确保域参数是安全可靠的（见5.4）。

ECDSA密钥对的产生：

1.在区间[1,n-1]中选定一个随机数d。

2.计算Q=dG。

3.私钥为d，公钥为Q。

6.2公钥的验证

公钥的验证最早由Johnson提出，其目的在于确保公钥具有良好的算术性质。公钥的验证并不关心用户私钥的情况，甚至不管私钥是否存在。进行公钥的验证出于以下两个理由：(1)防止攻击者利用性质较差的公钥进行攻击。(2)避免偶然的编码或传输错误。使用性质较差的公钥会使其他安全措施无效。这方面的攻击实例可参见Lim和Lee的文献。

公钥的验证方法。可使用以下方法之一进行验证：

1.用户A使用算法6进行验证。

2.Q由可靠的系统产生。

3.Q由可靠的组织提供且经过算法6验证。

4. Q由可靠的组织提供且由一个可靠的系统产生的。

算法6.ECDSA公钥的验证。

输入：公钥Q=(xQ,yQ)，参数D={q,FR,a,b,G,n,h}。

输出：是否接受公钥Q。

1.验证Q≠O。

2.验证xQ,yQ在p或模多项式所规定的范围内。

3.验证xQ,yQ在曲线上。

4.验证nQ=O。

5.若Q通过上述验证，则接受之。

6.3持有私钥的证明

若干用户C能够确认A的公钥确系其本人的，C就可以要求A签名。为了做到这一点，在CA确定每个

用户A对其私钥的所有权之前，CA需要每个A证明他们对其公钥的所有权。对所有权的认证有多种形式，如对一段由CA选定的消息的签名，也可以用一些所谓的“零知识”方法。私钥所有权的认证和公钥所有权认证所起的作用是不一样的。同时进行这两种验证提供了高水平的安全保障。

7、ECDSA签名的产生和认证

本节介绍ECDSA签名产生和认证的方法。

ECDSA签名的产生。有参数D={q,FR,a,b,G,n,h}和密钥对{d,Q}的用户A使用以下方法对消息m进行签名：

1.产生随机或伪随机数k，1≤k≤n-1。

2.计算kG=(x1,y1)。

3.计算r=x1 modn，若r=0则返回第一步。

4.计算k-1 modn。

5.计算e=SHA-1(m)。

6.计算s=k-1(e+dr) modn，若s=0则返回第一步。

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

ECDSA签名的验证。为了验证A对消息m的签名(r,s)，B需要A的公钥Q和A的公开参数D=(q,FR,a,b,G,n,h)。B最好对D和Q也进行确认（见5.4和6.2）。B进行如下操作：

1.验证r和s在区间[1,n-1]中。

2.计算e=SHA-1(m)。

3.计算ω=s-1 modn。

4.计算u1=ωe modn，u2=rωmodn。

5.计算X=u1G+u2Q。

6.若X=O，则签名非法，x1为X的x坐标，v=x1 modn。

7.若v=r则接受签名。

签名验证的根据。若对消息m的签名(r,s)确为A所为，则s=k-1(e+dr) modn。将其化简可得：

k=s-1(e+dr)=s-1e+s-1dr=ωe+ωdr=u1+u2d modn。因此u1G+u2Q=(u1+u2d)G=kG，因此v=r时认可签名。

数据类型的转换。ANSI X9.62规定了一个将域参数转换为整数的规则，它用在产生签名的第二步和验证签名的第六步，在计算x1 modn之前将x1转换为整数。ANSI X9.62也规定了一个将比特串转换为整数的规则，它用于将SHA-1产生的比特串转换为整数。

公钥证书。在验证A的签名之前B需要一份A的公开参数D和公钥Q的副本，ANSI X9.62对此未作详细说明。实践中可靠的公钥一般由证书来分配。A的公钥证书应包括能唯一标识他的信息（如姓名，住址等），公开参数D，公钥Q，以及CA对这些信息的签名。B可以利用CA对A的证书来可靠地获得A的公开参数D和公钥Q的副本。

在签名验证中对r和s进行验证的基本原理。在签名验证的第1步中验证r和s是否在区间[1,n-1]中，这一操作是高效且极有必要的，ElGamal签名方案不进行这一操作，有一些攻击方法可以利用这一点进行攻击。下面是一个在ECDSA不验证r≠0 modn时可以采用的攻击方式，A使用Fp上的椭圆曲线：y2=x3+ax+b，b是模p的二次剩余，并且假设A使用的基点是G(0,sqrt(b))（这是有可能的，用户可能会选择一个x坐标为0的点作为基点，这样可以使参数组D变得短小），攻击者可以对任意消息m伪造A的签名，签名是(r=0,s=e)。

DSA和ECDSA的比较。单从概念上讲，ECDSA和DSA的区别仅在于DSA的子群是Zp*上由g上生成的，而ECDSA的子群是椭圆曲线点群上由G生成的。在实现上，ECDSA和DSA的唯一重要区别是r的产生，DSA的r是通过计算X=g-1 modp再模q，而ECDSA的r是取kG的x坐标而来。

8、安全方面的考虑

ECDSA在安全性方面的目标是能抵抗选择明文（密文）攻击。而攻击A的攻击者的目标是在截获A的签名后，可以生成对任何消息的合法签名。

尽管ECDSA的理论模型很坚固，但是人们仍研究很多措施以提高ECDSA的安全性。在ECDLP不可破解及哈希函数足够强的前提下，DSA和ECDSA的一些变形已被证明可以抵抗现有的任何选择明文（密文）攻击。在椭圆曲线所在群是一般群并且哈希函数能够抗碰撞攻击的前提下，ECDSA本身的安全性已经得到证明。

ECDSA可能面临的攻击：

1.对ECDLP的攻击。

2.对哈希函数的攻击。

3.其他攻击。

本阶将介绍目前对ECDSA的攻击方式及防御它们的方法。

8.1椭圆曲线离散对数问题

若攻击者能由A的公钥和公开参数计算出A的私钥，则攻击者就可以随心所欲地伪造A的签名。

问题的定义。椭圆曲线离散对数问题（ECDLP）：一条定义在有限域Fq上的椭圆曲线E，E(Fq)上的一个n 阶点P，Q=lP，1≤l≤n-1，求l。

已知的攻击

这一部分将介绍一些已知的对ECDLP的攻击方式，并将论证它们在实际中是不可行的。

1.穷尽搜索法。依次计算P,2P,3P,4P……直到与Q匹配为止，最差情况下要作n次。

2.Pohlig-Hellman算法。该算法由Pohlig和Hellman发明，利用P的阶n的因子分解。该算法将模n条件下求l的问题转化为求模每个n的因子条件下求l的问题。利用中国剩余定理即可求得l。

为了抵抗这种攻击，椭圆曲线的阶应被一大素数n整除，或者曲线的阶就是素数或近乎是一个素数（即由一个大素数和一个小整数相乘而来）。在本节的剩余部分我们假定曲线的阶是素数。

3.小步-大步算法。该算法是一种需要很大存储空间的穷尽搜索算法，在最差情况下，需要存储sqrt(q)个点，运算sqrt(q)步。

4.Pollard’s Rho算法。该算法由Pollard发明，这是小步-大步算法的一种随机化版本。它大约需要sqrt(пn/2)步，但其所需要的存储空间几乎可以忽略不计。

Gallant, Lambert ,Vanstone和Wiener,Zuccherato的文章向我们介绍了Pollard’s Rho算法的改进。改进后的算法效率提高了sqrt(2)倍，即算法只需sqrt(пn)/2步。

5.并行Pollard’s Rho算法。Van Oorschot和Wiener的文章告诉我们在使用r个处理器并行运算时，Pollard’s Rho算法的时间复杂度为sqrt(пn)/2r，即使用r个处理器时，运算效率提高了r倍。

6.Pollard’s Lambda算法。这也是小步-大步算法的一种随机化版本，在并行化时速度也有线性提高。并行Pollard’s Lambda比并行Pollard’s Rho要略慢一些。不过，如果已知离散对数在[0,b]，b<0.39n时Pollard’s Lambda算法要快一些。

7.多重对数算法。R.Silverman和Stapleton注意到若一个ECDLP被（并行）Pollard’s Rho算法解决，那么已进行的工作对解决另一个ECDLP（曲线和基点不变）大有好处。更精确地说，若解决第一个ECDLP 耗时t=sqrt(пn)/2r，则第二个耗时(sqrt(2)-1)t≈0.41t，第三个耗时需(sqrt(3)-sqrt(2)) ≈0.32t，第四个耗时(sqrt(4)-sqrt(3)) ≈0.27t……以此类推。这样对于一条特定的曲线和一个特定的点，ECDLP会越来越易于解决。从另一方面看，解决k个ECDLP（曲线和基点不变）只需sqrt(k)倍解决单个ECDLP所需代价。这里的分析没有考虑存储方面的问题。

为了避免这种情况的出现，最好的办法就是使得密码系统足够强使得首次破解不可能。

8.超奇异椭圆曲线。Menezes, Okamoto,Vanstone,Frey 和Ruck的研究表明，在某些适当的条件下，定义在有限域Fq上的椭圆曲线E上的ECDLP可以化为某个扩域Fqk（k≥1）上的普通乘法群上的DLP，从而可以使用数域筛法加以解决。这样的转化算法只有在k较小时才有实用价值，因此对绝大多数椭圆曲线都不适用。为了抵抗这种攻击方式，在选择安全曲线时必须检验基点P的阶n不整除qk-1，1≤k≤20。这样可以使上述攻击方式在计算上不可行。

若E的迹t能够被Fq的特征p所整除，则称E是超奇异椭圆曲线。对于这类曲线，它们的k≤6，使用上面的方法就可以产生解决ECDLP的亚指数算法。因此ECDSA严禁使用超奇异椭圆曲线。

更一般地讲，在选择安全曲线时检验基点P的阶n不整除qk-1可以剔除那些可以将ECDLP转化为Fq上的DLP的曲线，不仅包括超奇异椭圆曲线，也包括迹为2的椭圆曲线。

9.素域反常椭圆曲线。定义在Fp上，且#E(Fp)=p的曲线称为素域反常曲线。其上ECDLP存在高效攻击方式SSSA。这种攻击方式不能用于其他曲线，因此只要确保#E(Fp)≠p即可使这种攻击无效。

10.小域上的椭圆曲线。E是一条定义在F2e上的椭圆曲线。Gallant,Lambert,Vanstone, Wiener和Zuccherato 的研究表明Pollard’s Rho算法在E(F2ed)上的效率可以提高sqrt(d)倍。即运算步骤变为sqrt(пn/d)/2步。如果E是Koblitz曲线，Pollard’s Rho算法在F2m上的效率提高了sqrt(m)倍。为避免这种情况的发生，在进行曲线安全性分析时应避免曲线方程的系数在一小子域中。

11.定义在F2m（m为合数）的椭圆曲线。Galbraith和Smart论述了当曲线定义在F2m（m为合数）（这样的域称为合域）时，Weil变换可以用于解决ECDLP。后来，Gaudry,Hess和Smart证明了当m有一个小因子l，如l=4时，存在比Pollard’s Rho算法更高效的算法。Menezes和Qu也做了类似的分析。根据这样的结论，椭圆曲线密码不应使用合域上的曲线。

现有的各种标准均禁止使用这种曲线。

12. 不适用于ECDLP的Index-Calculus方法。ECDLP是否存在普适性的亚指数算法是一个重要但却又尚不明确的问题，而ECDSA的安全性又与此密切相关。现在还没有人能够证明ECDLP不存在亚指数算法。

然而，对DLP的分析进行了24年，对ECDLP的分析进行了16年，至今未发现解决ECDLP的普适性亚指数算法。Miller,J. Silverman和Suzuki已经证明了用于解决DLP的Index-Calculus方法不适用于ECDLP。

13. Xedni-Calculus攻击。一种很有趣的攻击方式，由J. Silverman提出，它不仅可以解决ECDLP，还可以解决DLP和IFP。但后来它被证明在实际应用中并不可行。

14.超椭圆曲线。超椭圆曲线是一类任意亏格的代数曲线，椭圆曲线就是其中亏格为1的一种。对于大亏格的超椭圆曲线上的ECDLP，Adleman,DeMarrais和Huang提出了一种亚指数算法，不过对于椭圆曲线，这种方法比穷举法还要差。

15.与ECDLP等价的DLP。Stein和Zuccherato证明了亏格为1的二次同余函数域上的DLP等价于ECDLP。对于这类问题亦无亚指数算法，这从另一个方面证明了ECDLP的困难性。

试验结果

目前解决ECDLP最好的普适性算法是并行Pollard’s Rho算法，大约需要sqrt(пn)/2r步，n是基点P的阶，r是处理器个数。

Certicom的ECC挑战。Certicom公司于1997年启动了一项ECC挑战项目，旨在鼓励与促进对ECC的研究。他们的挑战由下面的一系列椭圆曲线的ECDLP组成，ECCp-k表示Fp上的椭圆曲线，ECC2-k表示F2m上的椭圆曲线，ECC2k-k表示F2m上的Koblitz曲线，k表示n的尺寸。这些曲线的基域的阶等于或略大于n（或者说这些曲线的阶是素数或近似是素数）。

1.Fp上的椭圆曲线，ECCp-79，ECCp-89，ECCp-97，ECCp-109，ECCp-131，ECCp-163，ECCp-191，ECCp-239，ECCp-359。

2.F2m（m为素数）上的椭圆曲线，ECC2-79，ECC2-89，ECC2-97，ECC2-109，ECC2-131，ECC2-163，ECC2-191，ECC2-238，ECC2-353。

3.F2m（m为素数）上的Koblitz曲线，ECC2k-95，ECC2k-108，ECC2k-130，ECC2k-163，ECC2k-238，ECC2k-358。

挑战的结果。1998年Escott介绍了一种经过Teske改进的并行Pollard’s Rho算法，他们所解决的最困难的ECDLP是ECCp-97，使用了至少16个国家的1200台机器，耗时53天。执行椭圆曲线点加运算的次数约为2*1014次，与理论值很接近（理论值为sqrt(пn)/2≈3.5*1014，n≈297）。他们估计要解决ECCp-109大约需要50000台200MHz的奔腾机运行3个月。

硬件攻击

Van Oorschot和Wiener研究了利用专用硬件实现并行Pollard’s Rho算法的可能性。他们估计花1000万美元制造一个有330000个处理器的机器可以在32天内解决n≈2120的ECDLP。由于ANSI X9.62规定n应大于2160，故在现有条件下，这样的硬件攻击不可行。

8.2对哈希函数的攻击

定义。哈希函数H是一种将任意长度比特串映射为定长t比特串的函数，满足下列条件：

1.H的计算足够高效。

2.（不可逆）对于所有的y∈{0,1}t，寻找比特串x使H(x)=y在计算上不可行。

3.（抗碰撞）寻找比特串x1和x2使得H(x1)=H(x2)在计算上不可行。

SHA-1的安全需要。下面显示了若SHA-1不能满足不可逆及抗碰撞条件时，攻击者可以这些问题成功攻破ECDSA。

1.若SHA-1是可求逆的，则攻击者E可以这样伪造A的签名：E可以选取一个随机整数l，尔后计算r等于Q+lG的横坐标模n的值。E令s=r，计算e=rl modn。若E能找到e=SHA-1(m)的逆m，则可构造m的合法签名(r,s)。

2.若SHA-1不能抗碰撞，则用户A可以这样否认自己的签名：A构造两个消息m和m’满足

SHA-1(m)=SHA-1(m’)，这样的一对消息称为SHA-1的碰撞。A可以对m签名却声称自己对m’签名。理想的安全性。一个t比特长度哈希函数满足下面两个条件时则有理想的安全性：1.寻找原象大约需要2t 步操作。2.寻找哈希碰撞大约需要2t/2步操作。SHA-1是160比特哈希函数，具有良好的安全性。攻击SHA-1

最高效的方法是寻找哈希碰撞，大约需要280步，因此通过哈希函数攻击ECDSA在计算上是不可行的。这里只是单纯讨论哈希函数的输出长度，而未讨论与之紧密相关的椭圆曲线基点阶尺寸。现在得到广泛使用的哈希函数并不多，只有SHA-1和RIPEMD-160（另一种160比特哈希函数）两种。

哈希函数的可变输出长度。在不久的将来，SHA-1将被一个可变长度哈希函数族Hl所代替，Hl是一个l 可变比特长度的具有理想安全性的哈希函数。若椭圆曲线基点的阶为n，则l应等于└logn┘。这样的话，通过攻击ECDLP和攻击哈希函数来攻破ECDSA所需代价基本一样。新的哈希函数开始使用256，384，512比特的输出长度。

8.3其他攻击方式

随机数k的保密要求。在ECDSA中随机数k与私钥d有同样的保密要求。因为攻击者E若获知了用户A 的随机数k，则他可以计算出A的私钥d=r-1(ks-e) modn。因此必须确保随机数k安全地产生，存储，销毁。随机数k的重复使用问题。用于对多个消息签名的随机数必须是互不依赖的。每次签名时k都必须不同，否则d可被恢复出来。实际中一般使用伪随机数发生器来产生，这样基本不可能产生相同的k。下面展示的是两次使用相同的k分别对m1和m2进行签名导致私钥d被计算出来的过程：两次签名分别为(r,s1)与(r,s2)；s1=k-1(e1+dr) modn，s2=k-1(e2+dr) modn；ks1=e1+dr modn，ks2=e2+dr modn；k(s1-s2)=(e1-e2) modn，由于s1与s2几乎不可能相当，因此可以计算出k=(e1-e2) (s1-s2)-1 modn，从而可以进一步求得d。Vaudenay攻击。Vaudenay发现了DSA中的一个漏洞：SHA-1的值要模q，q和SHA-1的输出都是160比特长度的，有时候SHA-1的输出大于q，因此有时SHA-1(m)≠SHA-1(m) modn。这个缺点使得攻击者可能伪造签名。在ECDSA中这个问题是不存在的，因为ECDSA标准要求n大于2160。

签名副本密钥选取攻击。对于一个签名方案S，如果给出A的公钥PA和对消息M的签名sA，攻击者E 可以找到一个合法的密钥对(PE,SE)使之对M签名仍得到sA，则称这个签名方案具有签名副本密钥选取（DSKS）的性质。使用这种攻击方式的前提是E必须要知道SE，Blake-Wilson和Menezes在他们的文献中详述了如何用这种方式去攻击一个签名体制。他们还论述了如果用户可以自行选择域参数，则ECDSA 会面临DSKS的问题。例子如下：假如用户A的域参数DA=(q,FR,a,b,G,n,h)，A的密钥对为(QA,dA)，(r,s)是A对M的签名。攻击者E选择随机整数c，1≤c≤n-1，令t=((s-1e+s-1rc)modn)≠0，计算X=s-1eG+s-1rQ （e=SHA-1(M)）以及G’=(t-1 modn)X，尔后E就有了自己的域参数DE=(q,FR,a,b,G’,n,h)，QE=cG’。易于验证DE和QE是合法的，并且(r,s)亦是E对M的签名。

具有DSKS性质的签名方案是不可靠的，设计签名方案的目标之一是能抵抗住这种选择消息攻击。对抗DSKS很简单，确保域参数选取的随机性即可。同时，我们也看到了域参数和公钥的选取是多么的重要。实现方面的攻击。ANXI 9.62没有提到ECDSA实现方面的攻击，比如计时攻击，差分攻击，能量攻击以及针对伪随机数的弱随机性的攻击。

9、实现方面的考虑

在实现ECDSA之前，必须进行一些基本的选择：

1.基域的选择，Fp或F2m。

2.若选取F2m上的曲线，要决定使用正规基表示方法还是多项式表示方法。

3.曲线的类型，一般曲线还是Koblitz曲线。

4.曲线点的表示，仿射坐标还是投射坐标。

在进行选择时由很多影响因素，总的来说就是针对不同的应用进行不同的选择已取得最好的结果，这些影响因素包括：

1.安全性方面的考虑。

2.有限域运算高效性方面的考虑（包括加法，平方，乘法，求逆运算）。

3.椭圆曲线算术高效性方面的考虑（点加和倍点）。

4.应用环境（软件，硬件，嵌入式系统）。

5.计算环境的考虑（速度，存储空间，处理器位数，门运算，能耗）。

6.通信环境的考虑（带宽，时延）。

参考文献。目前最详细并且得到广泛应用的椭圆曲线标准是IEEE 1363-2000。

10、通用性方面的考虑

一个加密标准要达到的目标包括两方面：

1.密码系统的健壮性。

2.在不同系统间的通用性。

影响通用性的因素。通用性可以通过规范密码系统的步骤和格式来实现数据的共享，如共享域参数，密钥，交换消息等；也可以通过对实现密码体制的设备的种类来实现。对于椭圆曲线密码学，特别是ECDSA来说，影响通用性的因素包括：

1.可使用的有限域的个数和类型。

2.有限域中元素的表示方式。

3.有限域上椭圆曲线的条数。

4.域元素，曲线上的点，曲线参数，公钥，签名的表示方式。

10.1 ECDSA标准

ECDSA的标准和标准草案有很多，其中已经过颁发部门批准的有：ANSI X9.62 ,FIPS 186-2,IEEE

1363-2000,ISO 14888-3。ECDSA也被密码标准化组织（SECG，这是一个从事密码标准通用性潜力研究的组织）加以标准化。

首先我们将简要介绍这些标准，然后对它们进行比较，最后还会提到一些其他ECDSA标准。

主要的ECDSA标准。

1.ANSI X9.62。该项目始于1995年，并于1999年正式作为ANSI标准颁布。ANSI X9.62具有高安全性和通用性。它的基域可以是Fp，也可以是F2m。F2m中的元素可以以多项式形式或正规基形式来表示。若用多项式形式，ANSI X9.62要求模多项式为不可约三项式，标准中提供了一些不可约三项式，另外还给出了一个不可约五项式。为了提高通用性，针对每一个域提供了一个模多项式。若使用正规基表示方法，ANSI X9.62规定使用高斯正规基。椭圆曲线最主要的安全因素是n，即基点阶，ANSI X9.62的n大于2160。椭圆曲线是使用随机方法选取的。ANSI X9.62规定使用以字节为单位的字符串形式来表示曲线上的点，ASN.1语法可以清楚地描述域参数，公钥和签名。

2.FIPS 186-2。1997年，NIST开始制定包括椭圆曲线和RSA签名算法的FIPS 186标准。1998年，NIST 推出了FIPS186，它包括RSA与DSA数字签名方案，这个方案也称为FIPS 186-1。1999年NIST又面向美国G0vment推出了15种椭圆曲线。这些曲线都遵循ANSI X9.62和IEEE 1363-2000的形式。2000年，包含ANSI X9.62中说明的ECDSA，使用上述曲线的FIPS 186-2问世。

3. IEEE 1363-2000。该标准于2000年作为IEEE标准问世。IEEE 1363的覆盖面很广，包括公钥加密，密钥协商，基于IFP、DLP、ECDLP的数字签名。它与ANSI X9.62和FIPS 186完全不同，它没有最低安全性限制（比如不再对基点阶进行限制），用户可以有充分的自由。因此IEEE 1363-2000并不是一个安全标准，也不具有良好的通用性，它的意义在于给各种应用提供参照。它的基域可以是Fp，也可以是F2m。F2m中的元素可以以多项式形式或正规基形式来表示。Fp中元素表示形式是整数，F2m中元素表示形式是字符串。这与ANSI X9.62和FIPS 186是一致的。

4.ISO/IEC 14888-3。这个标准包含若干签名算法，其中ECDSA部分与ANSI X9.62一致。

5.SEC 1和SEC 2。SEC 1描述了ECDSA，椭圆曲线加密算法，椭圆曲线密钥交换协议。而SEC 2给出了具体的椭圆曲线。SEC 1的ECDSA遵从ANSI X9.62，但对域的尺寸未作限制。

比较。这些标准的关系如下图：

其他的ECDSA标准。ECDSA还有其他很多标准，它们包括：

1.ISO/IEC 15946。该标准草案包括多种椭圆曲线密码技术，包括公钥加密，数字签名，密钥产生等。与ANSI X9.62，FIPS 186-2，IEEE 1363-2000中曲线基域必须是素域或多项式域不同，ISO/IEC 15946对基域类型未作限制。其在ECDSA描述方面与ANSI X9.62一致。

2.IETF PKIX。供X.509证书使用的一个标准，其格式与ANSI X9.62一致。

3.LETF TLS。这是IETF为SSL制定的标准，将会包含ANSI X9.62的ECDSA。

4.WAP WTLS。为移动通信工具提供传输层安全保障，使之能够安全地浏览网页，其认证使用ANSI X9.62的ECDSA。

10.2 NIST推荐的曲线

这部分内容给出了NIST向美国G0vment推荐（而非强制规定）的15条曲线。

推荐的有限域，共十个：

1.素域Fp，p=2192-264-1，p=2224-296+1，p=2256-2224+2192+296-1，p=2384-2128-296+232-1，p=2521-1。

2.多项式域F2163，F2233，F2283，F2409，F2571。

选择这些域的原因在于：

1.点的阶长度至少应该二倍于分组密码的密钥长度，这是因为一般认为使用穷尽法破译密钥长度为k的分组密码的代价大致相当于使用Pollard’s Rho方法破译阶为2k的椭圆曲线密码。它们的对比如下：

2.对于素域Fp，模数p应该是伪梅森素数或类梅森素数，这样可以使模乘运算效率更高。

3.对于多项式域F2m，选择m的原则是使得F2m上存在有大素因子的阶的Koblitz曲线。由于当l整除m 时，#E(F2l)也整除#E(F2m)，因此需要m是素数。

推荐的椭圆曲线，它们分为三种类型：

1.Fp上的随机曲线。

2.F2m上的Koblitz曲线。

3.F2m上的随机曲线。

下面就是推荐曲线的参数，用十进制和十六进制表示。

Fp上的随机曲线

各种参数的含义如下：

P：基域Fp的阶。

Seed：使用算法1来随机产生曲线参数过程中要用到的系数。

R：算法1中SHA-1的输出。

a，b：曲线方程的参数，其中a取-3，这样可以提高运算效率。

xG，yG：基点G的坐标。

n：G的阶。

h：辅因子h=#E(Fq)/n。

Curve P-192

p =6277101735386680763835789423207666416083908700390324961279

n=6277101735386680763835789423176059013767194773182842284081

seed=3045ae6f c8422f64ed579528d38120eae12196d5

r =3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65

a=-3

b =64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1

G x =188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012

G y =07192b95ffc8da78631011ed6b24cdd573f977a11e794811

h=1

Curve P-224

p =26959946667150639794667015087019630673557916260026308143510066298881

n =26959946667150639794667015087019625940457807714424391721682722368061

seed=bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5

r=5b056c7e11dd68f40469ee7f3c7a7d74f7d121116506d031218291fb

a=-3

b =b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4

G x =b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21

G y =bd376388 b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34

h=1

Curve P-256

P=115792089210356248762697446949407573530086143415290314195533631308867097853951

n=115792089210356248762697446949407573529996955224135760342422259061068512044369

seed =c49d360886e704936a6678e1139d26b7819f7e90

r =7efba1662985be9403cb055c75d4f7e0ce8d84a9c5114abcaf3177680104fa0d

a=-3

b =5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

G x =6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296

G y =4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

h=1

Curve P-384

p

=394020061963944792122790401001436138050797392704654466679482934042457217714968703290472660 88258938001861606973112319

n=39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956 308152294913554433653942643

seed=a335926aa319a27a1d00896a6773a4827acdac73

r=79d1e655f868f02fff48dcdee14151ddb80643c1406d0ca10dfe6fc52009540a495e8042ea5f744f

6e184667cc722483

a=-3

b

=b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2a ef

G x =aa87ca22 be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c

3a545e3872760ab7

G y

=3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e 5f

h=1

Curve P-521

p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640 661454554977296311391480858037121987999716643812574028291115057151

n=68647976601306097149819007990813932172694353001433054093944634591855431833976553942450577 46333217197532963996371363321113864768612440380340372808892707005449

seed=d09e8800291cb85396cc6717393284aaa0da64ba

r=0b4 8bfa5f420a34949539d2bdfc264eeeeb077688e44fbf0ad8f6d0edb37bd6b533281000518e19f1b9ffbe0fe9 ed8a3c2200b8f875e523868c70c1e5bf55bad637

a=-3

b =051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951

ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00

G x =c6

858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de 3348b3c1856a429bf97e7e31c2e5bd66

G y =11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee7299

5ef42640c550b9013fad0761353c7086a272c24088be94769fd16650

h=1

F2m上的Koblitz曲线与F2m上的随机曲线

尺寸为163的多项式域。

T = 4

p(t) = t 163 + t 7 + t 6 + t 3 + 1

Curve K-163

a = 1

n = 5846006549323611672814741753598448348329118574063

多项式表示法：

G x =2 fe13c0537bbc11acaa07d793de4e6d5e5c94eee8

G y =2 89070fb05d38ff58321f2e800536d538ccdaa3d9

正规基表示法：

G x =05679b353caa46825fea2d3713ba450da0c2a4541

G y =235b7c6710050689906bac3d9dec76a835591edb2

Curve B-163

n = 5846006549323611672814742442876390689256843201587

多项式表示法：

b = 20a601907b8c953ca1481eb10512f78744a3205fd

G x =3f0eba16286a2d57ea0991168d4994637e8343e36

G y =0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1

正规基表示法：

s =85e25bfe 5c86226cdb12016f7553f9d0e693a268

b =6645f3cacf1638e139c6cd13ef61734fbc9e3d9fb

G x =0311103c17167564ace77ccb09c681f886ba54ee8

G y =333ac13c6447f2e67613bf7009daf98c87bb50c7f

尺寸为233的多项式域

T = 2

p(t) = t 233 + t 74 + 1

Curve K-233

a = 0

n =3450873173395281893717377931138512760570940988862252126328087024741343

多项式表示法：

G x =172 32ba853a 7e731af129f22ff4 149563a4 19c26bf5 0a4c9d6e efad6126

G y =1db 537dece8 19b7f70f555a67c4 27a8cd9b f18aeb9b 56e0c110 56fae6a3

正规基表示法：

G x =0fde76d9dcd 26e643ac26f1aa901aa129784b71fc0722b2d05614d650b3

G y =0643e317633155c9e0447ba8020a3c43177450ee036d633501434cac978

Curve B-233

n = 6901746346790563787434755862277025555839812737345013555379383634485463

多项式表示法：

b =066647ede6

c 332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad

G x =0fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b

G y =1006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052

正规基表示法：

s =74d59ff0 7f6b413d 0ea14b34 4b20a2db 049b50c3

b =1a003e0962d4f9a8e407c904a9538163adb825212600c7752ad52233279

G x =18b863524b3cdfefb94f2784e0b116faac54404bc9162a363bab84a14c5

G y =04925df77bd8b8ff1a5ff519417822bfedf2bbd752644292c98c7af6e02

尺寸为283的多项式域

T = 6

p(t) = t 283 + t 12 + t 7 + t 5 + 1

Curve K-283

a = 0

n = 3885337784451458141838923813647037813284811733793061324295874997529815829704422603873

多项式表示法：

G x =503213f78ca44883f1a3b8162f188e553cd265f23c1567a16876913b0c2ac2458492836

G y =1ccda380f1c9e318d90f95d07e5426fe87e45c0e8184698e45962364e34116177dd2259

正规基表示法：

G x =3ab9593f8db09fc188f1d7c4ac9fcc3e57fcd3bdb15024b212c70229de5fcd92eb0ea60

G y =2118c4755e7345cd8f603ef93b98b106fe8854ffeb9a3b304634cc83a0e759f0c2686b1

Curve B-283

n = 7770675568902916283677847627294075626569625924376904889109196526770044277787378692871

多项式表示法：

b =27b680ac8b8596da5a4af8a19a0303fca97fd7645309fa2a581485af6263e313b79a2f5

G x =5f939258db7dd90e1934f8c70b0dfec2eed25b8557eac9c80e2e198f8cdbecd86b12053

G y =3676854fe24141cb98fe6d4b20d02b4516ff702350eddb0826779c813f0df45be8112f4

正规基表示法：

s =77e2b07370eb0f832a6dd5b62dfc88cd06bb84be

b =157261b894739fb5a13503f55f0b3f10c5601166633102201138cc180c0206bdafbc951

G x =749468e464ee468634b21f7f61cb700701817e6bc36a2364cb8906e940948eaa463c35d

G y =62968bd3b489ac5c9b859da68475c315bafcdc4ccd0dc905b70f62446f49c052f49c08c

尺寸为409的多项式域

T = 4

p(t) = t 409 + t 87 + 1

Curve K-409

a = 0

n = 3305279843951242994759576540163855199142023414821406096423243950228807112892491910506732584 57777458014096366590617731358671

多项式表示法：

G x

=060f05f658f49c1ad3ab1890f7184210efd0987e307c84c27accfb8f9f67cc2c460189eb5aaaa62ee222eb1b35540cfe 9023746

G y

=1e369050b7c4e42acba1dacbf04299c3460782f918ea427e6325165e9ea10e3da5f6c42e9c55215aa9ca27a5863ec4 8d8e0286b

正规基表示法：

G x

=1b559c7cba2422e3affe13343e808b55e012d726ca0b7e6a63aeafbc1e3a98e10ca0fcf98350c3b7f89a9754a8e1dc0 713cec4a

G y

=16d8c42052f07e7713e7490eff318ba1abd6fef8a5433c894b24f5c817aeb79852496fbee803a47bc8a203878ebf1c4 99afd7d6

Curve B-409

n = 6610559687902485989519153080327710398284046829642812192846487983041577748273748052081437237 62179110965979867288366567526771

多项式表示法：

b

=021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae31 7b13545f

G x

=15d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e 54bb7996a7

G y

=061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba 0273c706

正规基表示法：

s =4099b5a457f9d69f79213d094c4bcd4d4262210b

b

=124d0651c3d3772f7f5a1fe6e715559e2129bdfa04d52f7b6ac7c532cf0ed06f610072d88ad2fdcc50c6fde72843670 f8b3742a

G x

=0ceacbc9f475767d8e69f3b5dfab39813685262bcacf22b84c7b6dd981899e7318c96f0761f77c602c016ced7c548d e830d708f

G y

=199d64ba8f089c6db0e0b61e80bb95934afd0caf2e8be76d1c5e9affc7476df49142691ad30390288aa09bcc59c157 3aa3c009a

尺寸为571的多项式域

T = 10

p(t) = t 571 + t 10 + t 5 + t 2 + 1

Curve K-571

a = 0

n

=193226876150862917234767594546599367214946366485321749932861762572575957114478021226813397 8522706711834706712800825351461273674974066617311929682421617092503555733685276673

多项式表示法：

G x

=26eb7a859923fbc82189631f8103fe4ac9ca2970012d5d46024804801841ca44370958493b205e647da304db4ceb0 8cbbd1ba39494776fb988b47174dca88c7e2945283a01c8972

G y

=349dc807f4fbf374f4aeade3bca95314dd58cec9f307a54ffc61efc006d8a2c9d4979c0ac44aea74fbebbb9f772aedcb 620b01a7ba7af1b320430c8591984f601cd4c143ef1c7a3

正规基表示法：

G x

=04bb2dba418d0db107adae003427e5d7cc139acb465e5934f0bea2ab2f3622bc29b3d5b9aa7a1fdfd5d8be66057c10 08e71e484bcd98f22bf8476423767367429ef2ec5bc3ebcf7

G y

=44cbb57de20788d2c952d7b56cf39bd3e89b18984bd124e751ceff4369dd8dac6a59e6e745df44d8220ce22aa2c852 cfcbbef49ebaa98bd2483e33180e04286feaa253050caff60

Curve B-571

n = 3864537523017258344695351890931987344298927329706434998657235251451519142289560424536143999 389415773083133881121926944486246872462816813070234528288303332411393191105285703

多项式表示法：

b

=2f40e7e2221f295de297117b7f3d62f5c6a97ffcb8ceff1cd6ba8ce4a9a18ad84ffabbd8efa59332be7ad6756a66e294a fd185a78ff12aa520e4de739baca0c7ffeff7f2955727a

G x

=303001d34b856296c16c0d40d3cd7750a93d1d2955fa80aa5f40fc8db7b2abdbde53950f4c0d293cdd711a35b67fb 1499ae60038614f1394abfa3b4c850d927e1e7769c8eec2d19

G y

=37bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a 8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b

正规基表示法：

s =2aa058f73a0e33ab486b0f610410c53a7f132310

b

=3762d0d47116006179da35688eeaccf591a5cdea75000118d9608c59132d43426101a1dfb3774115f586623f75f00 001ce611983c1275fa31f5bc9f4be1a0f467f01ca885c74777

G x

=0735e035def5925cc33173eb2a8ce7767522b466d278b650a2916127dfea9d2d361089f0a7a0247a184e1c70d4178 66e0fe0feb0ff8f2f3f9176418f97d117e624e2015df1662a8

G y

=04a36420572616cdf7e606fccadaecfc3b76dab0eb1248dd03fbdfc9cd3242c4726be579855e812de7ec5c500b4576 a24628048b6a72d880062eed0dd34b1096d3acbb6b01a4a97

11、总结（略）

RSA数字签名算法的模拟实现

RSA数字签名算法的模拟实现 摘要 本程序为简易版RSA算法加密解密过程的模拟实现。 程序分为加密和验证两部分。根据课上所学的MD5加密过程，以及RSA算法，本程序采用MD5算法，先对文件内容进行加密，得到文字摘要；再利用RSA算法的私钥，对文字摘要进行加密，得到数字签名。在验证部分，用RSA公钥对数字证书签名解密，得到文字摘要S1，再将需要验证的文档用公用的MD5算法处理，得到文字摘要S2，检验文字摘要S1与S2的一致性，从而断定原文是否被篡改。程序采用树形图对文件进行直观的显示管理。采用文本文档存储数字签名。 关键词：RSA MD5 文字摘要数字签名

Abstract This program is simple version of the RSA algorithm encryption and decryption process simulation. The procedures are divided into two parts, encryption and authentication. Lessons learned based on the MD5 encryption process, as well as RSA algorithm, the procedures used MD5 algorithm, first pairs contents of the file carry on encrypt, to obtain text abstract; re-use RSA algorithm's private key, encryption for text abstract, obtain the digital signature. In the verification part, with the RSA algorithm's public key pairs of digital certificate signature decryption, get text abstract S1, and then using a public MD5 algorithm encryption the document which need to be verify, to obtain text abstract S2, text the consistency of S1 and S2, thereby conclude that original text whether the been tampered with. Program uses the file tree intuitively display management the files. Adopt text document storage digital signatures. Key words：RSA MD5 Text abstract Digital signature

基于椭圆曲线的一种高效率数字签名

第26卷第2期 计算机应用与软件 Vol 126No .2 2009年2月 Computer App licati ons and Soft w are Feb .2009 基于椭圆曲线的一种高效率数字签名 侯爱琴　高宝建　张万绪　强　媛 (西北大学信息科学与技术学院　陕西西安710069) 收稿日期:2007-07-09。陕西省自然科学基金项目(2004A11)。侯爱琴,讲师,主研领域:信息安全,电子信息技术。 摘　要 为给出一种基于椭圆曲线密码的高效率的数字签名方案。不仅在算法设计时完全避免了费时的求逆运算,而且利用消 息HASH 值的汉明重量作为消息摘要进行签名与验证。结果在同等安全性下,该方案比通用的ECDS A 等方案运行时间更短。新方案可适用于网络等对签名实时性要求较高的场合。 关键词 椭圆曲线密码　哈希函数　汉明重量　椭圆曲线数字签名 A H I GH EFF IC I ENCY D IG ITAL S IGNATURE BASED O N ELL I PT IC CURVE Hou A iqin Gao Baojian Zhang W anxu Q iang Yuan (School of Infor m ation Science and Technology,N orthw est U niversity,X i ’an 710069,Shaanxi,China ) Abstract T o offer a high efficiency digital signature based on elli p tic curve cryp t ography .The design of the algorith m not only avoids ti m e 2costing inverse operati on comp letely but als o uses the hamm ing weight of HASH code of a message instead of HASH code itself as the message digest t o partici pate in the signature and verifying calculati on .The ne w scheme cost less ti m e than the popular EC DS A.The ne w sche me is a 2dap ted t o higher real 2ti m e needs f or signature such as internet . Keywords Elli p tic curve cryp t ography (ECC )　Hash Ha mm ing weight Elli p tic curve digital signature (EC DS A ) 0　引　言 数字签名是电子商务和网络安全认证的核心技术。基于公钥密码的数字签名体制一般有三类:基于大整数分解问题(I FP )的,如RS A;基于离散对数问题(DLP )的,如著名的E I Ga 2mal,DS A 等;基于椭圆曲线离散对数问题(EC DLP )的,如I EEE P1363标准中的EC DS A 等椭圆曲线数字签名。其中ECDLP 最难解,除几类特殊椭圆曲线外迄今没有找到有效的求解算法。椭圆曲线密码(ECC )是迄今为止每比特具有最高安全强度的密码系统,160位ECC 密钥的安全性能与1024位RS A 或ElGa mals 的密钥相当。 本文研究了以椭圆曲线密码理论为基础的一种高效率数字签名系统。 1　基于ECC 的数字签名方案分析 现有的椭圆曲线数字签名方案,典型的如ECDS A 是美国国家标准技术研究所(N I ST )出台的ANSI X9.62标准,其详细描述可参见文献[1-3];EC 2KC DS A 方案是韩国基于证书数字签名算法(KC DS A )的椭圆曲线版本,具体方案可参见文献[1]描述。还有E I Ga mal 方案等都是将有限域F p 上离散对数签名方案移植到椭圆曲线群上。 据文献[4]把一个传统的离散对数体制转变为椭圆曲线体制需要进行以下转换:①把模乘运算转变为椭圆曲线上的点加运算;②把模幂运算转换为椭圆曲线上的点乘运算。 而有限域F p 上离散对数签名方案一般是基于签名方程u =dv +kw (mod p -1),详见文献[5,6]。它由五个元素(d,k,u, v,w )组成,其中d 是签名者的密钥,k 是每次签名时生成的随机 整数(即消息密钥),u,v,w 可以分别取e,r ,s,其中,e =h (m )为被签名消息的Hash 值,r 是一个与k 有关的量,s 是消息m 的签名。 可以用不同的(e,r ,s )组合代替(u,v,w ),并且e,r,s 可分别换成其加法或乘法逆元,由此可以衍生出不同的签名方程,即可得到不同的数字签名方案。但不是所有的数学组合都能产生安全的数字签名方案,Harn 和Xu 给出了安全的离散对数签名方案的设计规则,并列出所有符合这种设计规则的数字签名方案[7]。 基于ECC 的E I Ga mal 方案和EC DS A 是其中的第(4)种方案,取u =e,v =r ,w =s,即为通用方程u =vd +kw (mod p )的变体:e =dr +ks,等价于s =k -1(e +dr ),该方程为EC DS A 签名方程;相应的验证方程s -1(eG +r Q )=kG 。 ECDS A 方案中的公钥产生算法是Q =dG,在签名的生成和验证时分别计算k -1mod n 和s -1mod n ,需要模逆运算。EC 2 KC DS A 方案最大的特点是公钥产生算法是Q =d -1 P ,采用了逆的预运算,这使得签名的生成和验证过程不需要进行模逆运算;EC 2KC DS A 方案的另一个特点是在计算消息的Hash 值前,将签名者的证书数据加入消息(计算e =H (hcert,m )),能够抵抗基于参数组数据的攻击。 在现有的椭圆曲线加密或者签名过程中,求逆是最费时的操作,一次求逆的时间大约相当于80次点乘运算,因而求逆是

椭圆曲线上的部分盲签名方案

第２７卷第４期纺织高校基础科学学报Ｖｏｌ．２７，Ｎｏ．４　２０１４年１２月ＢＡＳＩＣＳＣＩＥＮＣＥＳＪＯＵＲＮＡＬＯＦＴＥＸＴＩＬＥＵＮＩＶＥＲＳＩＴＩＥＳＤｅｃ．，２０１４　 文章编号：１００６‐８３４１（２０１４）０４‐０５０８‐０４ 椭圆曲线上的部分盲签名方案 张建中，陈　楠，苑　飞 （陕西师范大学数学与信息科学学院，陕西西安７１００６２） 摘要：针对椭圆曲线密码体制具有签名密钥短、运行速度快等优点，结合动态秘密共享和部分盲签名技术，提出了一个新的动态部分盲签名方案．该方案不但具备门限签名和盲签名的特性而且还可以随时更新签名密钥，密钥的分发和更新过程采用公开验证的方法，可以有效地抵抗相互欺诈行为的发生．分析表明，该方案操作简单，安全性高，应用范围广． 关键词：椭圆曲线；动态秘密共享；部分盲签名；门限签名 中图分类号：ＴＰ３９３ 文献标识码：Ａ ０　引　言 在现实生活中，人们从安全和保险的角度考虑，对一些具有重要价值的信息的访问权限不能只交给一个人掌握，如果只有一人拥有打开某信息的密钥，一旦密钥丢失或持有者无法提供正确的密钥，就会带来严重的损失．因此，１９７９年Ｓｈａｍｉｒ［１］提出了将秘钥分解成多个碎片发送给多个人掌管，其中达到一定数量的成员的集合便可以恢复密钥的（ｔ，ｎ）秘密分享的思想．秘密分享是门限密码学的基础，人们在这种思想的基础上提出了可验证的秘密分享体制［２］，公开可验证秘密分享体制［３］．为了避免密钥受到长期的、逐步的攻击，有时需要随时更新签名者的密钥，人们又提出了动态秘密分享体制［４］，其后又提出许多新的秘密共享体制［５‐６］．将这些思想与一些密码体制相结合形成了一些更安全、高效的新方案，比如基于ＲＳＡ的门限签名方案，基于ＥＬＧａｍａｌ的门限签名方案，还有基于椭圆曲线的门限签名方案等．与同等条件下的一些密码体制相比，椭圆曲线密码体制因具有签名密钥短、运行速度快、安全性高等优点而成为密码学界研究的热点．１９９２年ＳｃｏｔｔＶａｎｓｔｏｎｅ提出了椭圆曲线数字签名的算法［７］（ＥＣＤＳＡ），由于这种算法需要求解椭圆曲线上的逆元，运算复杂，经不断被改进，新的高效的椭圆曲线数字签名方案［８‐９］被提出，算法中尽量避免求解逆元，从而提高了椭圆曲线数字签名方案的运行效率． 盲签名的概念［１０］是１９８２年Ｃｈａｕｍ在美国密码学会上首次提出的，盲签名要求用户和签名者之间达成一个协议，如果协议被正确执行，则用户获得签名者的签名，但是对签名人来说却不知道所签消息的具体内容［１１］．部分盲签名［１２］是在盲签名的基础上由Ａｂｅ和Ｆｕｊｉｓａｋｉ在１９９６年提出的，在部分盲签名方案中［１３］，签名人可以在签名中嵌入一个和用户事先约定好的公共信息，用来防止普通盲签名中被签名的消 收稿日期：２０１４‐０１‐１０ 基金项目：国家自然科学基金资助项目（６１１７３１９０，６１２７３３１１）；陕西省自然科学基础研究计划资助项目（２０１０ＪＱ８０２７）； 陕西省教育厅科研计划项目（２０１０ＪＫ３９８，１２ＪＫ１００３）；中央高校基本科研业务费专项资金资助项目 （ＧＫ２０１００２０４１） 通讯作者：张建中（１９６０‐），男，陕西省周至县人，陕西师范大学教授，博士．研究方向为信息安全与密码学及认证理论．Ｅ‐ｍａｉｌ：ｊｚｚｈａｎｇ＠ｓｎｎｕ．ｅｄｕ．ｃｎ

密码学实验-实验6 DSA数字签名算法

实验报告 一、实验目的 理解DSA算法原理 二、实验内容与设计思想 数字签名是一种以电子形式给消息签名的方法，是只有信息发送方才能进行的签名、信息发送方进行签名后将产生一段任何人都无法伪造的字符串，这段特殊的字符串同时也是对签名真实性的一种证明。电子信息在传输过程中，通过数字签名达到与传统手写签名相同的效果。 数字签名的实现原理简单地说，就是发送方利用hash算法对要传送的信息计算得到一个固定长度的消息摘要值，用发送方的私钥加密此消息的hash值所生成的密文即数字签名；然后将数字签名和消息一同发送给接收方。接收方收到消息和数字签名后，用同样的hash算法对消息进行计算，得到新的hash值，再用发送方的公钥对数字签名解密，将解密后的结果与新的hash值比较，如果相等则说明消息确实来自发送方。 DSA（Digital Signature Algorithm）源于ElGamal和Schnorr签名算法，1991年被美国NIST采纳为数字签名标准DSS（Digital Signature Standard），具体实现过程参见图1。 DSS安全性基于有限域求离散对数的困难性，算法描述如下： 1.密钥生成算法 1)选取160比特长的素数q和L比特长的素数p，满足q|(p?1)，其中L≡0(mod 64)且 512≤L≤1024； 2)随机选取正整数h，11；q，p和g作为系统公开参数； 3)每个用户，随机选取正整数x，1≤x≤q?1，计算y=g x mod p；用户的公钥为y，私 钥为x。 2.签名算法 对于消息M，首先随机选取整数k，1≤k≤p?2，计算 r=(g k mod p) mod q s=(H(M)+xr)k?1mod q 则M的签名为(r,s)，其中H为Hash函数SHA。 3.验证算法 接收方收到消息M′和签名(r′,s′)后，计算 e1=H(M′)s′?1mod q e2=r′s′?1mod q 验证等式 (g e1y e2mod p) mod q 如果v=r′成立，则说明消息确实来自发送方。

数字签名算法原理

实验1-5 数字签名算法 DSS 一．实验目的 通过对数字签名算法DSS的实际操作，理解DSS的基本工作原理。 二．实验原理 以往的文件或书信可以通过亲笔签名来证明其真实性，而通过计算机网络传输的信息则通过数字签名技术实现其真实性的验证。 数字签名目前采用较多的是非对称加密技术，其实现原理简单的说，就是由发送方利用哈希算法对要传送的信息计算得到一个固定位数的消息摘要值，用发送者的私有密钥加密此消息的哈希值所产生的密文即数字签名。然后数字签名和消息一同发给接收方。接收方收到消息和数字签名后，用同样的哈希算法对消息进行计算得出新的哈希值，然后用发送者的公开密钥对数字签名解密，将解密后的结果与新的哈希值相比较，如相等则说明报文确实来自发送方。 下面我们以DSA(Digital Signature Algorithm)为例，介绍数字签名算法。DSA源于ElGamal和Schnorr签名算法，被美国NIST采纳作为DSS(Digital Signature Standard)数字签名标准。DSS数字签名算法的具体实现过程课参见图1-5。 比较 a 签名过程 b 验证过程 图1-5 DSS算法的实现过程 首先介绍DSS算法的主要参数： 1. 全局公开密钥分量 　1)素数p, 2511

基于椭圆曲线和RSA的数字签名的性能分析,数字签名,椭圆曲线

基于椭圆曲线和RSA的数字签名的性能分析，数字签名，椭圆曲线密码体制，RSA，C++ 1引言数字签名是实现认证的重要工具，他在身份认证、数据完整性、抗抵赖性以及匿名性等方面有重要的应用，是电子商务应用、电子政务推广中的核心技术，数字签名能保证文件中每页内容均不会被改动或替换。数字签名是特指以公钥密码实现的签名，或者可以定义为记录的一次变换，通过一个非对称密码系统和一个杂凑函数，使得有初始记录和签名者公钥的任何人都可以准确地判断该变换是否由相对应的私钥产生、初始记录在变换之后是否被修 1 引言 数字签名是实现认证的重要工具，他在身份认证、数据完整性、抗抵赖性以及匿名性等方面有重要的应用，是电子商务应用、电子政务推广中的核心技术，数字签名能保证文件中每页内容均不会被改动或替换。数字签名是特指以公钥密码实现的签名，或者可以定义为记录的一次变换，通过一个非对称密码系统和一个杂凑函数，使得有初始记录和签名者公钥的任何人都可以准确地判断该变换是否由相对应的私钥产生、初始记录在变换之后是否被修改。 常用的数字签名体制：RSA，EIGamal，ECC。其中基于RSA的数字签名算法现在应用十分广泛，而基于ECC的数字签名算法ECDSA则是未来签名算法的热点方向，本文就两种算法的性能进行了分析和比较，同时讨论了各自的应用范围。 2 RSA的数字签名算法 RSA算法是公钥密码体制中最著名的算法，他是以其发明人Rivest，Shamir和Adleman三人的首字母来命名的。RSA是建立在大整数分解的困难上的，是一种分组密码体制。RSA即可用于数据加密，也可用于数字签名。 2．1 RSA数字签名算法密钥对产生的过程 (1)选择2个大的素数p，q。 (2)计算n：n=pq。 (3)随机选取e，满足1<e<φ(n)，gcd(e．φ(n))=1，那么公钥就是(e，n)。 (4)计算d：满足ed=1modφ(n)，那么私钥就是(d，n)。 2．2 RSA数字签名算法的签名过程

一种椭圆曲线快速生成算法

一种椭圆曲线参数生成的快速算法 谷勇浩 刘勇 （北京邮电大学通信网络综合技术研究所） 摘要：椭圆曲线密码体制是公钥密码中的研究热点。该文介绍了椭圆曲线密码体制的基本概念及相关知识，讨论了目前基于离散对数问题的椭圆曲线密码的研究动态。本文的创新点是针对目前椭圆曲线研究重点之一——椭圆曲线参数生成算法，给出了一种生成参数a 、b 的快速算法。这种算法利用了Jacobi 符号和二次剩余的理论，并且用matlab 计算出利用这种算法生成一个椭圆曲线的平均时间，最后我们分析了今后椭圆曲线密码系统的研究方向和重点。 关键词：椭圆曲线；离散对数问题；Jacobi 符号；二次剩余；阶 1976年Diffie 和Hellman 提出公钥密码思想以来，国际上提出了许多种公钥密码体制的实现方案。一些已经被攻破，一些被证明是不可行的。目前，只有3类公钥密码体制被认为是安全有效的，按照其所依据的数学难题划分为：基于大整数分解问题（IFP ），如RSA 体制和Rabin 体制；基于有限域离散对数问题（DLP ），如Diffie-Hellman 体制和ElGamal 体制；基于椭圆曲线离散对数问题（ECDLP ），如椭圆密码体制。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller 在1985年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强度最高的一种体制。它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注。而SET(Secure Electronic Transaction)协议的制定者已把它作为下一代SET 协议中缺省的公钥密码算法。深入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。 1建立椭圆曲线公钥密码体制 1.1椭圆曲线域的参数 在基于椭圆曲线的加解密和数字签名的实现方案中，首先要给出椭圆曲线域的参数来确定一条椭圆曲线。在 IEEE P1363标准中，定义其参数为一个七元组：T=(q,FR,a,b,G,n,h)，其中q 代表有限域GF(q)，q 为素数或 2 m ;FR 为域表示法，如f(x)为 2 m F 域元素的不可约 多项式的表示法；曲线的方程，当q 为素数时，方程为2 3 ax b y x =++，当q 为2m 时， 方程为 2 32 xy a b y x x +=++，a,b 是方程中的系数；G 为基点；n 为大素数并且等于点G 的阶，h 是小整数称为余因子且#()/q h E n F =。主要的安全性参数是n ，因此ECC 密钥 的长度就定义为n 的长度。 1.2椭圆曲线密码的密钥 选取了基域 q F 和椭圆曲线后，得到了在有限域 q F 上的曲线E 确定的具体形式，即 上述的椭圆曲线域参数的一个七元组。每个用户选取一个整数d(1≤d ≤n-1) 作为其私钥，而以点Q=dG(G 为基点)作其公钥，这样形成一个椭圆曲线公钥密码系统。在这个密码体制中，具体的曲线，基域 q F ，基点G 及其阶n ，以及每个用户的公钥都是该系统的公开参

RSA算法和RSA数字签名算法的实现

RSA算法和RSA数字签名算法的实现

RSA算法和RSA数字签名算法的实现 摘要 RSA算法是一种公钥密码算法.实现RSA算法包括生成RSA密钥， 用RSA加密规则和解密规则处理数据。RSA数字签名算法利用RSA算法实现数字签名。本文详述了RSA算法的基本原理, RSA加密算法的实现以及如何利用RSA实现数字签名. 关键字 RSA算法, 数字签名, 公开密钥, 私人密钥, 加密, 解密 中图分类号 TP301 一、引言 随着网络技术的飞速发展，信息安全性已成为亟待解决的问题。公钥密码体制中，解密和加密密钥不同，解密和加密可分离，通信双方无须事先交换密钥就可建立起保密通信，较好地解决了传统密码体制在网络通信中出现的问题。另外，随着电子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗也成为非常重要的问题。数字签名可以起到身份认证、核准数据完整性的作用。目前关于数字签名的研究主要集中基于公钥密码体制的数字签名。 公钥密码体制的特点是：为每个用户产生一对密钥（PK和ＳＫ）；ＰＫ公开，ＳＫ保密；从ＰＫ推出ＳＫ是很困难的；Ａ、Ｂ双方通信时，Ａ通过任何途径取得Ｂ的公钥，用Ｂ的公钥加密信息。加密后的信息可通过任何不安全信道发送。Ｂ收到密文信息后，用自己私钥解密恢复出明文。 公钥密码体制已成为确保信息的安全性的关键技术。RSA公钥密码体制到目前为止还是一种认可为安全的体制。本文详述了RSA算法和用RSA算法实现数字签名的理论，以及它们在实际应用中的实现。 二、RSA算法和RSA数字签名算法的理论描述 1 RSA算法 RSA算法的理论基础是一种特殊的可逆模幂运算。 设n是两个不同奇素数p和q的积，即：n=pq, ?(n)=(p-1)(q-1)。 定义密钥空间 k={(n,p,q,d,e)|n=pq,p和q是素数，de≡1 mod ?(n),e 为随机整数}, 对每一个k=(n,p,q,d,e), 定义加密变换为E k(x)=x b mod n，x∈Z n; 解密变换为D k(x)=y a mod n,y∈Z n，Z n为整数集合。 公开n和b，保密p,q和a. 为证明加密变换E k和解密变换 D k满足D k(E k(x))=x,这里不加证明的引用下面两个定理： 定理1（Euler）对任意的a∈Z n *,有a?(n)≡1 mod n,其中 Z n *={x∈Z n |gcd(x,n)=1},?(·)表示Euler函数。 定理2 设p和q是两个不同的素数，n=pq, ?(n)=(p-1)(q-1)，对任意的x∈Z n 及任意的非负整数k,有 x k?(n)+1≡x mod n. 现在来证明RSA算法的加密变换和解密变换的正确性。 证明：对于加密变换E k和解密变换D k。因为ab≡1 mod ?(n)，所以可设

椭圆曲线加密算法

椭圆曲线加密算法 椭圆曲线密码学（英语：Elliptic curve cryptography，缩写为 ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。 ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA 加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长 1.椭圆曲线 在数学上，椭圆曲线（英语：Elliptic curve，缩写为EC）为一代数曲线，被下列式子所定义 y2=x3+ax+b 其是无奇点的；亦即，其图形没有尖点或自相交。 满足此条件的a b满足：4a3+27b2≠0 图1 在基础上需要定义一个无穷远的点，将此点作为零点：此时椭圆曲线定义为：{(x,y)∈?2|y2=x3+ax+b,4a3+27b2≠0}∪{0} 在椭圆曲线中的群的运算律： 1. 所有的点都在椭圆曲线上 2. 0点作为群上的单元点即 P+0=P 3. P点关于X轴的对称点为P点的逆即 P+(?P)=0

4.对于位于同一条直线上的三个点P,Q,R.则有 P+Q+R=0 图2 P+Q+R=0（无限远点 P Q R三个点的位置是任意的，他们满足加法的结合律，因为这个群是一个阿贝尔群。 2.椭圆曲线加法 当P和Q不相等时(x P≠x Q) 由于是在阿贝尔群上可以将P+Q+R=0改写为P+Q=?R所以在椭圆曲线上的加法定义为P Q 两点加法为P,Q两点连线与曲线的交点R的关于X轴对称点?R 图2-3 P+Q=-R P Q两点的直线的斜率为： m=y P?y Q x P?x Q 这条线与曲线的交点为：R=(x R,y R) x R=m2?x P?x Q y R=y P+m(x R?x P) 因此(x P,y P)+(x Q,y Q)=(x R,?y R)如果在图上表示即为上述的P+Q=?R

信息安全之电子签名技术的实现

滨江学院 课程论文 题目数字签名的发展 院系计算机系 专业软件工程（动画方向）学生姓名陈婷 学号20092358009 指导教师朱节中 职称副教授 二Ｏ一二年五月二十日

数字签名的发展 陈婷 南京信息工程大学滨江学院软件工程（动画方向），南京210044 摘要： 数字签名是电子商务安全的一个非常重要的分支。随着电子商务的发展，电子签名的使用越来越多。实现电子签名的技术手段有很多种，但比较成熟的、世界先进国家目前普遍使用的电子签名技术还是基于PKI的数字签名技术。 关键词： 数字签名信息安全电子商务 1引言 1.1 研究背景 在当今信息社会,计算机网络技术得到了突飞猛进的发展。计算机网络日益成为工业、农业和国防等领域的重要信息交换手段,并逐渐渗透到社会的各个领域。在现实生活中,人们常常需要进行身份鉴别、数据完整性认证和抗否认。身份鉴别允许我们确认一个人的身份;数据完整性认证则帮助我们识别消息的真伪、是否完整;抗否认则防止人们否认自己曾经做过的行为。随着无纸化办公的发展,计算机网络的安全越来越受到重视,防止信息被未经授权的泄漏、篡改和破坏等都是亟待解决的问题。在Internet上,数字签名作为一项重要的安全技术,在保证数据的保密性、完整性、可用性、真实性和可控性方面起着极为重要的作用。同时由于信息技术的发展及其在商业、金融、法律等部门的普及, 数字签名技术又面临着新的挑战。 1.2 开发意义 数字签名是实现电子交易安全的核心技术之一，它在实现身份认证、数字完整性、不可抵赖性等功 能方面都有重要应用。尤其是在密钥分配、电子银行、电子证券、电子商务和电子政务等许多领域有重要 的应用价值。 2相关技术介绍 2.1PKI/CA 技术的介绍 PKI 就是公开密钥基础设施。它是利用公开密钥技术所构建的，解决网络安全问题的，普遍适用的一种基础设施。公开密钥技术也就是利用非对称算法的技术。说PKI 是基础设施，就意味着它对信息网络的重要。PKI 通过延伸到用户本地的接口，为各种应用提供安全的服务，如认证、身份识别、数字签名、

【CN109981284A】一种椭圆曲线数字签名的实现方法及装置【专利】

(19)中华人民共和国国家知识产权局 (12)发明专利申请 (10)申请公布号 (43)申请公布日 (21)申请号 201910181267.8 (22)申请日 2019.03.11 (71)申请人 北京三未信安科技发展有限公司 地址 100102 北京市朝阳区广顺北大街16 号院2号楼14层1406室 (72)发明人 杨国强　 (74)专利代理机构 北京轻创知识产权代理有限 公司 11212 代理人 杨立 (51)Int.Cl. H04L 9/32(2006.01) H04L 9/08(2006.01) (54)发明名称 一种椭圆曲线数字签名的实现方法及装置 (57)摘要 本发明涉及一种椭圆曲线数字签名的实现 方法及装置，包括处理器将生成的签名消息数据 包发送至密码卡，签名消息数据包包括临时签名 公私钥对和待签名消息；密码卡接收签名消息数 据包，获取签名消息数据包中的临时签名公私钥 对和待签名消息，根据临时签名公私钥对、预先 存储的用户签名私钥和辅助公私钥对，得到待签 名消息的数字签名。本发明提高用户签名的安全 性， 同时提高数据处理的效率。权利要求书2页 说明书6页 附图1页CN 109981284 A 2019.07.05 C N 109981284 A

权　利　要　求　书1/2页CN 109981284 A 1.一种椭圆曲线数字签名的实现方法，其特征在于，包括： 处理器将生成的签名消息数据包发送至密码卡，所述签名消息数据包包括临时签名公私钥对和待签名消息； 密码卡接收所述签名消息数据包，获取所述签名消息数据包中的所述临时签名公私钥对和所述待签名消息，根据所述临时签名公私钥对、预先存储的用户签名私钥和辅助公私钥对，得到待签名消息的数字签名。 2.根据权利要求1所述的实现方法，其特征在于， 所述辅助公私钥对中的私钥由所述密码卡随机生成，所述辅助公私钥对中的公钥通过所述辅助公私钥对中的公钥和椭圆曲线的基点生成。 3.根据权利要求1所述的实现方法，其特征在于， 所述临时签名公私钥对中的私钥由所述处理器随机生成，所述临时签名公私钥中的公钥通过所述临时签名公私钥对中的私钥和椭圆曲线的基点生成。 4.根据权利要求2所述的实现方法，其特征在于， 所述辅助公私钥对定时更新。 5.根据权利要求1-4中任一项所述的实现方法，其特征在于，所述根据所述临时签名公私钥对、预先存储的用户签名私钥和辅助公私钥对，得到待签名消息的数字签名的具体步骤包括： 将所述临时签名公私钥对中的公钥和所述辅助公私钥对中的公钥执行点加运算，得到第一运算结果； 将所述临时签名公私钥对中的私钥和所述辅助公私钥对中的私钥执行模加运算，得到第二运算结果； 根据所述用户签名私钥、所述第一运算结果和所述第二运算结果，得到所述待签名消息的数字签名。 6.一种椭圆曲线数字签名的实现装置，其特征在于，包括处理器和密码卡； 所述处理器，用于将生成的签名消息数据包发送至所述密码卡，所述签名消息数据包包括临时签名公私钥对和待签名消息； 所述密码卡，用于接收所述签名消息数据包，获取所述签名消息数据包中的所述临时签名公私钥对和所述待签名消息，根据所述临时签名公私钥对、预先存储的用户签名私钥和辅助公私钥对，得到所述待签名消息的数字签名。 7.根据权利要求6所述的实现装置，其特征在于， 所述密码卡随机生成所述辅助公私钥对中的私钥，通过所述辅助公私钥对中的私钥和椭圆曲线的基点生成所述辅助公私钥对中的公钥。 8.根据权利要求6所述的实现装置，其特征在于， 所述处理器随机生成所述临时签名公私钥对中的私钥，通过所述临时签名公私钥对中的私钥和椭圆曲线的基点生成所述临时签名公私钥中的公钥。 9.根据权利要求6-8任一项所述的实现装置，其特征在于， 所述密码卡，用于将所述临时签名公私钥对中的公钥和所述辅助公私钥对中的公钥执行点加运算，得到第一运算结果； 将所述临时签名公私钥对中的私钥和所述辅助公私钥对中的私钥执行模加运算，得到 2

数字签名的制作方法整理-10页word资料

1。用keytool来创建一个密匙（同时指定时效，多久会过期，默认只给6个月） 2。用JARSigner用此密匙为JAR签名。 可以用同一个密匙来为多个JAR签名。 注意：大小写，签名一致，数字签名过期 为什么JAR要被签名？当用户启动一个Java Network Launching Protocol (JNLP，Java网络加载协议)文件或使用一个applet时，这个JNLP或applet可能请求系统提供一些非一般的访问。比如“文件打开”等进行这样的请求，就需要签名的JAR。 如果它是匿名的，系统会询问用户是否打算信任JAR的签署者。 1.首先生成签名文件，执行完成后，会在本目录内生成一个.keystore的密钥文件，2kByte大小。 yourProj是别名keypass后面是密文密码，keystore密码是存储密码（要改变此文时需要输入确认此密码） 在dos命令提示状态下输入 C:\Documents and Settings\Administrator>keytool -genkey -alias yourProj -keypass yourCompany:Kouling [回车],屏幕提示: 输入keystore密码：yourCompany:yourPassword 您的名字与姓氏是什么？ [Unknown]：ChinayourCompany 您的组织单位名称是什么？ [Unknown]：ChinayourCompany 您的组织名称是什么？ [Unknown]：Company 您所在的城市或区域名称是什么？ [Unknown]：City 您所在的州或省份名称是什么？ [Unknown]：Province 该单位的两字母国家代码是什么 [Unknown]：CN CN=ChinayourCompany, OU=ChinayourCompany, O=Company, L=City, ST=Province, C=CN 正确吗？ [否]：Y 2.为此密钥加有效期限：7200天，将近20年. [嘿嘿，足够用了吧？再也别想6个月] 输入命令： C:\Documents and Settings\Administrator>keytool -genkey -alias yourProj -keypass yourCompany:Kouling -selfcert -validity 7200 屏幕提示： 输入keystore密码：yourCompany:yourPassword 注意：-validity 7200 这个就是加时效的参数，7200单位是“天”。 检查密钥文件，输入命令： C:\Documents and Settings\Administrator>keytool -list 屏幕提示： 输入keystore密码：yourCompany:yourPassword Keystore 类型：jks

椭圆曲线数字签名中阈下信道通信研究

椭圆曲线数字签名中阈下信道通信研究 摘要:针对阈下信道技术在椭圆曲线数字签名中的应用可能以及存在的安全隐患问题,通过对其中存在的窄带阈下信道进行实时性测试,在平衡传输信息容量与签名时间的条件下,确定了合理的阈下信息传输位数。实验结果表明,窄带阈下信道在椭圆曲线数字签名中可以被有效利用。 关键词:椭圆曲线密码体制;数字签名;窄带阈下信道;信息隐藏;Miracl大数库 中图分类号: TP309 文献标志码:A Covert communication based on subliminal channel in?? elliptic curve digital signature algorithm ZHANG Qiuyu, SUN Zhanhui College of Computer and Communication, Lanzhou University of Technology, Lanzhou Gansu 730050, China ) Abstract: There are narrowband and broadband subliminal

channels in the Elliptic Curve Digital Signature Algorithm (ECDSA),but broadband subliminal channel cannot be safely used. Therefore, the realtime test of narrowband subliminal channel was done. The reasonable bit rate of the sent message was confirmed when the capacity and realtime requests of narrowband subliminal channel were satisfied. The result shows narrowband subliminal channel can be effectively used in ECDSA. Key words: Elliptic Curve Cryptography (ECC); digital signature; narrowband subliminal channel; information hiding; Miracl large number library 0 引言 自Simmons[1]于1978年提出阈下信道概念以来,阈下信道已经发展成为一种典型的信息隐藏手段。研究表明,绝大多数数字签名方案中都可包含阈下信道的通信,其最大的特点是阈下信息包含于数字签名之中,但对数字签名和验证过程无任何影响。目前,关于阈下信道的研究主要分为两个方面:一是研究如何建立阈下信道;二是研究如何封闭阈下信道。虽然已经提出许多构造阈下信道[2-4]和封闭阈下信道[5-8] 的方案,但多存在于理论研究阶段,真正得到的应用很少。

实验三DSA数字签名算法

实验三DSA数字签名算法 姓名： 学号: 学院：信息工程学院 指导老师：郑明辉

1.DSA算法原理 数字签名是数据在公开行信道中传输的安全保障，能够实现数据的公开、公正、不可抵赖等特点的方法，只能公开的密钥、密码签名算法。国际供认的公开密钥签字算法主要有RSA算法、ElGAMAL算法或者其变形的签名算法。 DSA(Digite Signature Arithmotic )是Schnore和ElGamal算法的变型。 美国国家标准技术研究所(NIST)1994年5月19日公布了数字签名标准的(DSS),标准采用的算法便是DSA，密钥长度为512~1024位。密钥长度愈长，签名速度愈慢，制约运算速度的只要因素是大数的模指数运算。 2.DSA签名中的参数 参数描述：Digital Signature Algorithm (DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(DigitalSignature Standard)。算法中应用了下述参数： p：L bits长的素数。L是64的倍数，范围是512到1024； q：p - 1的160bits的素因子； g：g = h^((p-1)/q) mod p，h满足h < p - 1, h^((p-1)/q) mod p > 1； x：x < q，x为私钥； y：y = g^x mod p ，( p, q, g, y )为公钥； H( x )：One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm )。 p, q, g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。签名及验证协议如下： 1. P产生随机数k，k < q； 2. P计算r = ( g^k mod p ) mod q s = ( k^(-1) (H(m) + xr)) mod q 签名结果是( m, r, s )。 3. 验证时计算w = s^(-1)mod q u1 = ( H( m ) * w ) mod q u2 = ( r * w ) mod q v = (( g^u1 * y^u2 ) mod p ) mod q 若v = r，则认为签名有效。 DSA是基于整数有限域离散对数难题的，其安全性与RSA相比差不多。 DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，你也能确认它们是否是随机产生的，还是作了手脚。RSA算法却做不到。 3.源码描述

DSA数字签名算法

DSA数字签名算法 1 引言 为了确保数据传输的安全性，不得不采取一系列的安全技术，如加密技术、数字签名、身份认证、密钥管理、防火墙、安全协议等。其中数字签名就是实现网上交易安全的核心技术之一，它可以保证信息传输的保密性、数据交换的完整性、发送信息的不可否认性、交易者身份的确定性等。DSA（Digital Signature Algorithm，数字签名算法，用作数字签名标准的一部分），它是另一种公开密钥算法，它不能用作加密，只用作数字签名。DSA使用公开密钥，为接受者验证数据的完整性和数据发送者的身份。它也可用于由第三方去确定签名和所签数据的真实性。DSA算法的安全性基于解离散对数的困难性，这类签字标准具有较大的兼容性和适用性，成为网络安全体系的基本构件之一。 2. 数字签名 2.1 数字签名的概念 数字签名在ISO7498—2标准中定义为：“附加在数据单元上的一些数据，或是对数据单元所作的密码变换，这种数据和变换允许数据单元的接收者用以确认数据单元来源和数据单元的完整性，并保护数据，防止被人（例如接收者）进行伪造”。 数字签名是通过一个单向函数对要传送的信息进行处理得到的用以认证信息来源并核实信息在传送过程中是否发生变化的一个字母数字串。数字签名提供了对信息来源的确定并能检测信息是否被篡改。 数字签名要实现的功能是我们平常的手写签名要实现功能的扩展。平常在书面文件上签名的主要作用有两点，一是因为对自己的签名本人难以否认，从而确定了文件已被自己签署这一事实；二是因为自己的签名不易被别人模仿，从而确定了文件是真的这一事实。采用数字签名，也能完成这些功能： （1）确认信息是由签名者发送的； （2）确认信息自签名后到收到为止，未被修改过； 签名者无法否认信息是由自己发送的。 数字签名和手签的区别是：手签是模拟的，易伪造，而数字签名是基于数学原理的，更难伪造。