一种基于椭圆曲线的数字签名与盲签名方案

韩然，吴正朋，胡小莉

(中国传媒大学理学院，北京 100024)

一种基于椭圆曲线的数字签名与盲签名方案

韩然，吴正朋，胡小莉

(中国传媒大学理学院，北京 100024)

椭圆曲线数字签名算法实际上是数字签名算法的椭圆曲线模拟，本文在ANSI(1999)颁布的椭圆曲线数字签名(ECDSA)标准的基础上，提出了椭圆曲线数字签名的一个变形方案，并设计了一种新的基于椭圆曲线的盲数字签名方案，其安全性是建立在椭圆曲线离散对数问题的难解性基础上的，从理论上讲是安全的，具有一定的实用价值。

椭圆曲线离散对数;椭圆曲线数字签名;盲数字签名

1 引言

随着密码理论的研究深入，计算机技术的飞速发展，经典的RSA，Diffie-Hellman等公钥密码体制(密钥长度一般为512bit)已变得越来越不安全了。因此，为了确保信息安全，密码体制的密钥要达到足够的长度，这对于速度缓慢的RSA密码体制来说，更是不堪负重，同时一些较短密钥的应用产品(例如Smart卡等)也需要新的密钥体制来实现。自1985年N.Koblitz和V.Miller提出椭圆曲线公钥密码体制的新思想以来［1］，使得被数学家研究了一百多年的椭圆曲线在密码领域中得以发挥重要作用。人们利用椭圆曲线上有理点组成的Abel群及其上离散对数问题求解的困难性构成了一些公钥密码体制，它们具有每bit位最高安全强度，也就是说，使用较短的密钥，即可具有满足现实要求的安全强度。例如，椭圆曲线密码体制中160bit长的密钥所具有的安全强度相当于RSA密码体制中1024bit长的密钥所具有的安全强度。椭圆曲线密码体制不仅能够对信息进行加密，而且还能用来构造数字签名和盲数字签名方案，椭圆曲线数字签名算法(ECDSA)实际上是数字签名算法(DSA)的椭圆曲线模拟。

在本文中，基于椭圆曲线数字签名算法，我们给出了一个椭圆曲线数字签名的变形方案，并设计了一种新的基于椭圆曲线的盲数字签名方案。本文结构如下:第2节介绍相关的数学背景，有限域上的椭圆曲线;第3节描述了安全椭圆曲线的选择问题;第4节给出了一个ECDSA的变形方案，并设计了一种基于椭圆曲线的盲数字签名方案。

2 有限域上的椭圆曲线

设Fq是特征值大于3的有限域，其中q=pm，a，b∈Fq，满足4a3+27b2≠0，则在仿射坐标平面上，由参数a，b定义在有限域Fq上的椭圆曲线E(Fq)是方程y2=x3+ax+b 的所有解(x，y)，x∈Fq，y∈Fq连同一个附加的“无穷远点”(记为O)的元素组成的点的集合。E(Fq)的点数用#E(Fq)表示。点集合E(Fq)对应下面的加法规则构成一个Abel加法群:群运算的恒等元是O，设P，Q∈E(Fq)，

关于椭圆曲线更详细内容请参考［2］。

3 安全椭圆曲线的选择

对于给定的椭圆曲线E(Fq)，若给定一个点P∈E(Fq)，R∈E(Fq)，那么给定一个整数m，计算mP=R是容易的，但是若从点R及点P推导出整数m，则是非常困难的，即没有多项式时间求解算法，这就是椭圆曲线离散对数问题(ECDLP)。椭圆曲线密码体制是以椭圆曲线离散对数问题的难解性为基础的。从目前的研究结果看，椭圆曲线上的离散对数问题比有限域上的离散对数问题似乎更难处理，迄今还没有出现类似于解有限域上的离散对数问题的indexcalculus算法来求解一般椭圆曲线上的离散对数问题，这就意味着可以在椭圆曲线公钥密码中采用较小的数以达到与更大的有限域同样的安全性。

对于椭圆曲线离散对数问题的攻击，如果椭圆曲线是超奇异的(#E(Fq)=q+1)，可以用一个MOV归约法能有效的将这些曲线上的离散对数问题约简到有限域上的离散对数问题，从而可应用index-calculus算法来求解，这类曲线已被椭圆曲线公钥密码标准禁止使用。同样还有一类弱的椭圆曲线是“反常曲线”，这是定义在Fq上的椭圆曲线E(Fq)，#E(Fq)恰好等于q，对这类曲线的攻击是由Semave，Smart以及Satoh和Araki分别独立发现的［3］。这类曲线也在椭圆曲线公钥密码标准中禁止使用。目前已知的求解椭圆曲线离散对数问题的最好算法是Pollard-ρ算法和Pohlig-Hellman算法，其时间都是指数级的，但当椭圆曲线的阶含有较大素因子时这两种方法也是无效的［4］。

因此，用来构建密码体制的椭圆曲线最好是非超奇异的，且满足条件:

1.#E(Fq)=c·l，其中l是一个大于2160的素数，正整数c通常叫做余因子，考虑到运算效率的问题，通常取 c≤4，详见［5］。

2.#E(Fq)≠q，这是为了避免“反常曲线”带来的攻击;

3.对 v=1，2，…，10，qv-1 不能被大素数 l整除，这个条件保证MOV归约法不能实现。

4 基于椭圆曲线的盲签名方案

数字签名是电子信息特殊的产物，是保证电子数据真实性的有效手段，数字签名可以用秘密密钥密码体制实现，也可以用公开密钥密码体制实现。椭圆曲线数字签名算法(ECDSA)实际上是数字签名算法(DSA)的椭圆曲线模拟，它在1999年作为一个ANSI(美国国家标准学会)标准认可，命名为ANSI X9.62［5］。本节先给出了一个ECDSA的变形方案，接着设计了一个基于椭圆曲线的盲数字签名方案，在签名前，为了提高效率，一般需要对文本(设为m)进行一定的预处理——应用Hash函数提取文件摘要，然后对文件摘要进行签名。

4.1 ECDSA的一个变形方案

(1)系统初始化:构造有限域Fq上的椭圆曲线，E(Fq)该曲线是非奇异的，且满足安全条件，选择一个公开的基点G∈E(Fq)，其阶为n，系统有一个安全Hash函数h:{0，1}*→Z，输入任意长度的消息，它将返回一特定长度的消息摘要(160比特是一种流行的选择)。

(2)密钥生成:用户A随机选取一个整数d作为密钥，公开点GA=dG作为公钥。

(3)签名生成:

4.2 基于椭圆曲线的盲签名方案

一般的数字签名中，签名者总是首先要知道签名文件的内容，然后才对文件签名，但是有时候，要求认证者只能通过签名来认证签名者的身份是否合法而不能得知具体的明文消息，称这种签名为盲签名。

(1)签名生成:系统初始化与密钥生成与上述ECDSA一样，

①用户A随机选一个整数k∈{1，…，n-1}，计算R=kG，并将R'传送给用户B;

③用户A计算s=k-rd mod n，将s传送给用户B;

④用户B计算y=r1s mod n，输出签名(y，e)即为m的盲签名。

(2)签名验证:只需验证Rx(yG+eGA)mod n=t是否成立即可，若成立，则签名正确，否则不正确。这是因为:y≡r1s≡r1k-r1rd≡r1k-r1(r2+r-11e)d≡r1k-r1r2d所以yG+eGA=r1kG-r1r2GA。

(3)性能分析:①由盲数字签名的特性，明文消息m对用户A来说应该是盲的;②攻击者若截取R'，试图通过R'来求解k，这是求解椭圆曲线离散对数问题;③攻击者若截取s，试图伪造s，但是不知道用户A的密钥，也是徒劳的。因此，本方案满足盲数字签名的要求。

5 结束语

本文设计了一个基于椭圆曲线密码体制的盲数字签名方案，其安全性是基于椭圆曲线离散对数问题的难解性基础上的，由于目前还没有对离散对数问题的有效解法，所以本方案是安全的。由于椭圆曲线密码体制有着自己独特的优越性如较短的密钥、运算速度快、便于计算机实现等方面，可被广泛应用于电子商务、较短密钥的应用产品中去。

［1］Neal Koblitz.Elliptic curve cryptosystems［J］.Math Comp，1987，(48):203-209.

［2］Silverman J H.The arithmetic of elliptic curves［M］.GTM106，Springer Verlag，New York，1986.

［3］N P Smart.The Discrete Logarithm Problem on Elliptic Curves of Trace One［J］.Journal of Cryptology，1999，12(3):193-196.

［4］Johannes Buchmann and Harald Baier.Efficient construction of cryptographically strong elliptic curves［C］.Progress in Cryptology-INDOCRYPT 2000，Springer，2000.

［5］ANSI X9.62 Public Key Cryptography for the Financial Services Idustry:The Elliptic Curve Digital Signature Algorithm(ECDSA)［R］.1999.

［6］张方国，王常杰，王育民.基于椭圆曲线的数字签名与盲签名［J］.通信学报，2001，22(8)，22-28.

［7］杨君辉，戴宗择，杨栋毅，刘宏伟.一种椭圆曲线签名方案与基于身份的签名协议［J］.软件学报，2000，11(10):1303-1306.

A Scheme Based on the Elliptic Curve Digital Signature and Blind Signature

HAN Ran，WU Zheng-peng，HU xiao-li
(College of Science，Communication University of China，Beijing 100024)

Elliptic curve digital signature algorithm is the elliptic curve analogue of the digital signature algorithm.This paper proposes a varied form of elliptic curve digital signature scheme by ANSI(1999)standard and a new blind digital signature scheme based on the elliptic curve cryptosystem.The safety of this scheme is based on the difficulty of solving the elliptic curve discrete logarithm problem.The scheme is secure in theory and is suitable for some practical application.

elliptic curve discrete logarithm;elliptic curve digital signature;blind digital signature

TP 309

A

1673-4793(2012)02-0075-03

2011-03-29

韩然(1976—)，男，山东潍坊人。中国传媒大学硕士研究生。Email:hanran@cuc.edu.cn。

(责任编辑

:龙学锋)