基于椭圆曲线数字签名系统的设计与实现

李海平　凌广明　裴宸平

摘 要： 通过网络传输获取信息，这在人们日常生活中日益普及。信息在网络传输过程中面临着被截获、被修改等安全性威胁。数字签名技术能够在数据传输过程中提供一系列的安全保障服务。基于C/C++和椭圆曲线数字签名算法，设计并实现了一个数字签名系统。测试表明，该系统具有良好性能并满足签名算法的安全性要求。

关键词： 网络传输； 数字签名； 椭圆曲线； 电子商务

中图分类号：TP309 文献标志码：A 文章编号：1006-8228（2015）05-44-03

Abstract： Access to information through the network is becoming more and more popular in people's daily life. At the same time， the information during the network transmission is faced with the security threats such as being intercepted or modified and so on， while digital signature technology can provide a range of security services in the data transmission. This paper designs and implements a digital signature system with C/C++ and the elliptic curve digital signature algorithm. The test shows that the system has a good performance and meets the safety requirements of the signature algorithm.

Key words： network transmission； digital signature； elliptic curve； e-commerce

0 引言

随着信息和电子技术的迅速发展以及网络技术的广泛应用，世界已经步入了信息社会。在政治、军事、商业和日常生活中，人们经常需要在纸质材料上手写签名。手写签名具有确认、核准、生效、负责等多种作用。近些年随着计算机网络技术的飞速发展，陆陆续续出现了电子商务、电子政务和电子金融系统。在这些系统应用中，人们需要通过网络信息传输对电子的文件、合同、信件及账单等进行数字签名以代替手写签名。计算机作为国家的关键基础设施和战略命脉，其安全状况直接影响到国家的安全和发展。信息加密是保证信息安全的关键技术，其理论是信息安全的核心内容之一。目前的数据加密、数字签名、消息认证等信息安全技术都是以密码技术作为基础进行设计的。

在电子商务活动日益盛行的今天，数字签名技术已经受到人们的广泛关注与认可，其使用已经越来越普遍。各国对数字签名的使用已颁布了相应法案，我国也于2004年8月通过了《电子签名法》。目前已有的签名算法主要有RSA签名方案、ELGamal签名方案、椭圆曲线数字签名算法、盲数字签名方案等等。因此，设计出简单、安全、高效的数字签名系统对于电子商务、电子政务的推广和应用具有十分重要的意义。

1 椭圆曲线公钥密码系统简介

1985年，Victor Miller和Neal Koblitz首次提出将椭圆曲线用于公钥密码学的思想。其理论基础是定义在有限域上的某一椭圆曲线上的有理点可构成有限交换群[1]。

1.1 椭圆曲线密码体制

如果能通过某种方法将明文通过适当的编码方式嵌入到椭圆曲线E上的点，则可以定义基于椭圆曲线E的ElGamal公钥密码系统[2]。

密钥生成算法：设（E，+）是有限域Fp上的椭圆曲线，G是E的循环子群，生成元为P，其阶n足够大，使得循环子群G上的离散对数问题是难解的。随机挑选一个整数a，使得1?a?n-1，计算Q=a·P；公开公钥（Q，P，G），保存私钥a。

加密算法：假设Bob想把明文m加密发送给Alice，Bob首先获取Alice的公钥（Q，P，G），将明文m编码为群G中的元素Pm，再选取随机数r，1?r?n-1，然后计算c1=r·P=（x1，y1），c2=Pm+r·Q=（x2，y2），则密文为（c1，c2）。

解密算法：Alice收到密文（c1，c2）后，利用私钥a计算出Pm=c2-a·c1，再对Pm解编码得到明文m[3]。

1.2 椭圆曲线数字签名算法

椭圆曲线数字签名算法ECDSA的安全性是基于有限域上椭圆曲线有理点群上离散对数问题的困难性。ECDSA已于1999年接受为ANSI X9.62标准，于2000年接受为IEEE 1363及FIPS 186-2标准[4]。

1.2.1 参数建立

⑴ 设q（>2160）是一个素数幂，E是有限域Fq上的一条椭圆曲线（q为素数或2m。当q为素数时，曲线E选为y2=x3+ax+b。当q=2m时，曲线E选为y2+xy=x3+ax2+b）。

⑵ 设G是E上有理点群E（Fq）上的具有大素数阶n（>2160）的元，称此元为基点。

⑶ h是单向Hash函数h，可选择SHA-1或SHA-256等。

⑷ 随机选取整数d：1⑸ （q，E，G，h）是公开参数，d与P分别是签名者的私钥和公钥。

1.2.2 签名生成过程

⑴ 对消息，Alice随机选取一个整数k，1?k

⑶ 记r=x1modn。如果r为0，返回第一步。

⑷ 计算s=k-1（h（m）+dr）modn。如果s为0，则返回第一步。

⑸ （r，s）是Alice对消息m的签名。将（r，s）发送给Bob。

1.2.3 签名验证过程

Bob收到（r，s）后执行以下操作。

⑴ 检验r与s是否满足：1?r，s?n-1，如不满足，则拒绝此签名。

⑵ 获取公开参数（q，E，G，h）及Alice的公钥P。

⑶ 计算w=s-1modn。

⑷ 计算u1=h（m）wmodn及u2=rwmodn。

⑸ 计算标量乘R=u1G+u2P。

⑹ 如果R=O，则拒绝签名，否则将R的x坐标转换成整数，并计算。

⑺ 检验v=r是否成立，若成立，则Bob接受签名，否则拒绝该签名。

2 签名系统分析及设计

本节主要讨论椭圆曲线数字签名系统的总体分析和设计。

2.1 域参数的选取

椭圆曲线密码体制的安全性是基于有限域上椭圆曲线离散对数问题的难解性。为了使签名系统更加安全，应该选取更加安全的椭圆曲线，基于某条椭圆曲线的离散对数问题求解难度很大。

设定义于有限域上的椭圆曲线E，其中q=pn，p是一个素数。椭圆曲线E的有理子群E（）的阶用表示。椭圆曲线好坏的标准在于的大小。Hasse定理给出的是域上椭圆曲线的阶，其中q=pn。

对于超奇异椭圆曲线：

⑴ n是偶数，。

⑵ n是偶数，。

⑶ n是奇数或偶数，p≠1mod4，t=0。

对于非超奇异椭圆曲线，t满足性质。

2.2 签名系统流程

该签名系统包括签名和验证两个主要过程，分别如图1和图2所示。

2.3 系统总体设计

签名系统总体流程图如图3所示。

[开始][系统登录][合法

图4中，密钥生成模块主要负责生成签名所需密钥；摘要处理模块主要针对需要签名的文档生成HASH摘要；签名生成模块主要对数字摘要进行签名并将签名附加到源文档末尾；验证模块即对签名进行验证并返回验证结果，用数字1表示验证通过、数字0代表未通过。

3 椭圆曲线数字签名算法的实现

该系统利用C/C++基于.NET平台设计并实现[5]。系统中常用的运算法则为加减乘除和取余运算（取余运算被包含在除法运算中）。因为ECDSA算法均是大整数的运算，所以此系统所有运算方法均采用有符号的二进制运算方法且结果同样为有符号二进制数。由于加法和减法运算较为简单，下面主要列出乘法和取余数算法的具体过程。

乘法运算算法描述：

step 1 被乘数与乘数按低位对齐；

step 2 取乘数为运算的低位与被乘数相乘；

step 3 使用加法算法将此次step 2的结果与step 3的结果相加；

step 4 重复step 2直至加数位数取完。

取余数运算算法描述：

step 1 被除数与除数按低位对齐；

step 2 依次取被除数未被运算高位直至取出的数大于等于除数。当此数值小于除数是商，上0，否则上1；

step 3 将step 2的得数按减法算法减去除数；

step 4 重复step 2直至被减数取完，step 3的结果即为余数。

因为ECDSA算法的效率很大程度上取决于倍点算法的效率，所以在此详述此系统中的倍点算法[6]。在系统运行中无论是签名过程还是验证过程均需要计算k*G（x，y）即k倍的点G。k的取值是从1到n（n为基点G的阶）n为一个大素数，所以k的取值可能很大。这就意味着逐步点加的方法将消耗大量的时间。因此，在此系统中设计了一种较为快速的倍点算法，需要输入椭圆曲线上的点G及整数K，输出椭圆曲线上的点P=k*G（x，y），具体过程描述如下：

step 1 令num=1，i=1，P=G；建立数组point以储存每一步的点值，Point[0]=G；

step 2 如果num<=k，则计算num=2*num； P=2*P； 将P值存入point[i]中，对i值加1；重复这个过程至num<=k不再成立；

step 3 计算num=num/2，n=num，i=i-2；P=point[i]；执行下列循环：

for j from i to 1

如果 num=k 则输出P；否则 n=n/2，num=num+n；

P=P+point[j-1]；

系统实现时初始化过程主要确定签名系统中各个参数，签名过程使用的是ECDSA中的签名生成算法，可以对本地文件进行签名。打开系统后，点击签名可以对选定的文档（TXT文件或者DOC文件）进行电子签名。

签名成功后，签名结果会追加在文档末尾，如图5所示。

文档验证人收到文档后，选择验证按钮来对已签名文档进行验证。若文档从未被篡改过，则会显示验证成功，如图6所示；若在传输过程中或者是在验证该文当前，有人对签名后的文档进行修改，则验证结果提示文件不可信（即有人篡改文档内容）。演示文档中以删除“war”为例进行验证，结果如图7所示。

4 安全性分析

该签名系统是基于有限域Fq上的椭圆曲线数字签名系统，其安全性基于椭圆曲线密码体制的安全性即椭圆曲线上离散对数问题的难解性。具体实现时还有几点需要考虑[7]。第一，系统参数组中使用安全的随机数。签名算法中使用了随机数，每一次的随机数需要安全生成、保存和使用并销毁，并且每次都使用不同的随机数，这在一定程度上可以提高系统的安全性。第二，确定合适的系统参数。选择恰当的系统参数可以保证ECDLP问题的难解性，可以使用NIST推荐的系统参数。第三，使用安全的Hash函数。算法中需要使用Hash函数对文档内容进行处理，好的Hash函数应具有如下特点：函数的正向计算容易；函数尽可能随机且不可逆。可以选取SHA-1等安全的Hash函数。

5 结束语

近年来，在电子商务、电子政务等快速发展的推动下，数字签名技术也得到了快速发展和应用，并且日益成为内容丰富、应用广泛的信息安全技术领域的核心技术之一。其中，椭圆曲线数字签名算法是众多签名算法中广受关注的一种算法。本文基于椭圆曲线数字签名算法，采用C/C++编程实现了一个椭圆曲线数字签名系统。通过测试表明，所设计和实现的签名系统完全满足信息防篡改等安全性要求，在电子商务、电子政务以及电子金融等领域具有一定的实用前景。

参考文献：

[1] 张龙军，沈钧毅，赵霖.椭圆曲线密码体制安全性研究[J].西安交通大学学报，2001.35（10）.

[2] 何大可，彭代渊，唐小虎等.现代密码学[M].人民邮电出版社，2009.

[3] 赵泽茂.数字签名理论及应用研究[D].南京理工大学博士学位论文，2005.

[4] 徐茂智，游林.信息安全与密码学[M].清华大学出版社，2007.

[5] 郑阿奇，丁有和.Visual C++教程（第2版）[M].机械工业出版社，2008.

[6] 赖忠喜，陶东娅，张占军.GF（2～n）域椭圆曲线密码体制中快速标量乘算法的研究[J].计算机应用与软件，2014.8.

[7] 秦晓东，辛运帷，卢桂章.基于椭圆曲线的数字签名系统的设计与实现[J].计算机工程与应用，2003.28：151-155