论文导读：本文所设计的签名方案的模型是基于椭圆曲线密码体制的。该算法无需进行模逆运算。即要引入一个身份识别协议。模逆运算，一种改进的数字签名算法及其身份识别协议。
关键词：椭圆曲线密码体制，模逆运算，改进算法，身份识别
1 引言
1985年，N．Koblitz和V.Miller提出了建立在椭圆曲线上的公钥密码体制方案（ECC）[1-2]，其优越性主要体现在：密钥短、占用带宽、存储空间小、单位密钥安全性高，这些优点非常适合现今计算机资源的终端设备，越来越受到人们的关注，逐渐成为研究的热点。
王龙葛（1983_），女，汉族，河南省南阳人，硕士，主要研究方向：信息安全
张校慧（1981-），女，汉族，河南省平顶山人，硕士，主要研究方向：数据挖掘，信息安全
本文在已提出的基于椭圆曲线数字签名模型的基础上[3]，就如何提高网络数据的传输效率及安全性、提高签名效率进行了研究，提出了一种改进的基于椭圆曲线的数字签名算法，
该算法无需进行模逆运算，不仅增强了网络数据通信的安全性，还大大提高了签名效率，对模逆运算的研究可能成为未来椭圆曲线密码体制提高效率的一个研究热点[4]。论文参考，模逆运算。
2 改进后的数字签名算法
文献[3]给出了传统的基于椭圆曲线的数字签名方案，下面给出改进后的签名算法：
2.1 改进后的签名算法
(1)参数的选定
P为一个大素数或2的幂次方(p≥160bit)
椭圆曲线E: y2=x3+ax+b,a,b ∈Fp 且4a3+27b2≠0
A∈Fp 是一个公开基点，且ord(A)=q, ,在 ＜A＞上离散对数是难解的。
设P={0,1}*，A= *q *q，定义K={(p, q,E, A, m, B): B=mA}，其中1≦m≦q－1，p, q, E，A和B是公开的，m为私钥，B为公钥，x为待签名的消息。
(2)改进后的签名算法
Step1: 秘密选择一随机数k，k∈[1,k-1]；
Step2: 计算kA=(u,v),r=u mod q，若r=0，则返回step1；
Step3:计算SHA-1(x)的消息摘要值，并将该消息摘要值转化为整数e；
Step4:计算s=k-em,并将签名(s,r,x)发送给验证方Bob。
2.2 改进后的验证算法
当Bob接收到签名方Alice发送的签名(s,r,x)后，将采用以下的验证算法来验证：
Step1: 验证x∈{0,1}*和r,s∈*q;Step2: 计算SHA-1(x,r),并将该位串转换成整数e；
Step3: 计算r’=sG+eB；
Step4: 当且仅当r’=r是Bob才接受签名。
2.3 不需要模逆操作证明
整个计算过程不需要进行模逆操作，签名与验证过程如下：
签名过程：S=k-em；
验证过程: R=sA+eB；
验证证明：sG+eB=(k-em)A+eB=KA=r，故r’=r。
新方案将需要验证的消息x与r一起进行Hash摘要，这样使得签名与验证过程分别少了一步乘法运算，提高了签名的运算效率。论文参考，模逆运算。
2.4 性能分析评估
参照文献[5],G是椭圆曲线E(Fq)上的一个基点，E是定义在域Fq上的椭圆曲线，且要求q
≈2160。给定mG,m是一个随机的160位整数，时间复杂度换算关系可按如下关系式运算：
TEC-MUL≈29Tmul(1)
TEC-ADD≈0.12Tmul(2)
TINV≈0.4TEC-MUL≈11.6Tmul (3)
为了便于比较计算时间效率，不妨设Tmul为模意义下2个整数相乘的时间，Tinv为在模意义下逆运算所需时间，TEC-Mul为椭圆曲线模意义下数乘的时间，TEC-ADD为椭圆曲线意义下模加的时间，在椭圆曲线的加密或者签名过程中，求逆运算是一种比较耗时的运算，改进后的签名算法没有模逆运算，提高了运算效率。具体数据计算如表1：
 时间复度 签名方案 |
签名时间复杂度 |
签名时间复杂 度粗略估计 |
验证时间复杂度 |
验证时间复杂 度粗略估计 |
| ECDSA方案 |
2Tmul+TEC-Mul+TINC +TEC-ADD |
42.72 |
2Tmul+TEC-Mul+TINC +TEC-ADD |
42.72 |
| 新ECDSA方案 |
TEC-Mul+2Tmul+TEC-ADD |
31.12 |
Tmul+TEC-Mul+TEC-ADD |
30.12 |
3身份识别协议
由于网络的开放性和共享性，在信道上传输的信息可能会遭到潜在敌手的恶意攻击（如截取，篡改等）并被敌手假冒，为了提高整个系统的安全性，我们需要在服务器端对用户身份进行识别，即要引入一个身份识别协议。
在上述签名方案中引入了网络服务机构—TA，其中TA中包括了所有参与者不愿公开的个人信息，以及他们的公钥、ID号和签名方的签名，按照上述的签名方案可以生成签名(r,s,x)，下面详细讲述服务器端身份识别的过程。
3.1 系统参数选定
P为一个大素数或2的幂次方(p≥160bit) ,椭圆曲线E: y2=x3+ax+b,a,b ∈Fp且4a3+27b2≠0, A∈Fp是一个公开基点，且ord(A)=q, ,在 ＜A＞上离散对数是难解的。论文参考，模逆运算。
定义○为椭圆曲线E上的无穷远点，因此○满足如下性质：
对于所有的 ，满足： 其中， 是公开的。
Alice随机秘密选取t个随机数： (普通整数序列，且不具有超递增属性)，其中 ， 。论文参考，模逆运算。并计算：
Alice将 作为公钥公开，作为私钥保密。
3.2身份识别协议
Step1: Alice秘密选择一个随机数r，且 ，计算 并将x传送给TA；
Step2: TA随机选择t个二进制比特序列 ，并将其传送给Alice；
Step3: Alice计算 ，并将y传送给TA；
Step4: TA计算如下式子
 
Step5: TA验证,  是否成立，如果成立，则说明Alice不是假冒的，反之，
说明Alice是假冒的。论文参考，模逆运算。
3.3安全性证明
上述协议是基于零知识证明的身份识别协议，由于离散对数问题难解性，敌手假冒Alice成功的概率都基于 的随机行，每个比特（0或1）选取的概率为1/2，则敌手假冒成功的概率为 ，如果重复执行该协议k次，则成功的概率为 。论文参考，模逆运算。在实际应用中，如果t、k的值选择适当，则该系统的安全性相当高。
4 安全性分析
本文所设计的签名方案的模型是基于椭圆曲线密码体制的，目前还没有有效求解椭圆曲线离散对数问题的算法，所以该方案具有很高的安全性。同时，从表1的实验数据中可以看
到，该模型的核心算法消除了模逆操作，大大提高了运算效率，另外该系统还引入了零知识证明的身份识别协议，保证了只有合法的用户才能对文档进行签名和验证，从而保证了文档数据的完整性，防止了签名的伪造。因此，该模型在办公自动化系统中有一定的实用价值。
参考文献
[1]Koblitz N. Elliptic curvecryptosystems[J]. Mathematics of Computation，1987，48（177）：203—209.
[2]Miller V S.Use of ellipticcurve in cryptography [A ]. Advances in Cryptology
CRYPTO 85 (santa Barbara, Calif. ,1985) [C].Lecture Notes in Comput. Sci. ,Spring Verlag, 1986. 218, 417—426.
|
