李明株，刘瑞芹

(华北科技学院 理学院，北京 东燕郊 065201)

0 引言

上世纪九十年代，通用的是 RSA 公钥密码体制，密钥长度一般为512bit。1999年RSA-512被破解，之后只能用加长密钥保证信息的安全性，导致运行速度更加缓慢。1985年，Koblitz[1]和Miller[2]提出将椭圆曲线用于公钥密码学的思想，标志着椭圆曲线密码体制(ECC，Elliptic Curve Cryptography)的诞生。ECC是建立在基于椭圆曲线上的点构成的Abelian加法群的离散对数问题上的密码体制。研究表明：基于有限域上椭圆曲线的离散对数问题运算位数远小于传统离散对数的运算位数，它可以使用较短的密钥达到较高的安全性，且计算速度快、存储量小、带宽要求低[3]。

数字签名在网络环境中可以代替传统手写签名或印章，是实体签名的信息化实现。使用数字签名技术能够使得发送者事后不能否认发送的签名信息、接收者能够核实但不能伪造或篡改发送者的签名信息。数字签名是提供身份认证、确保信息完整性、不可伪造性、不可否认性的重要信息技术。Jonhson和Menezes于1999年提出了基于椭圆曲线的数字签名算法(ECDSA)。椭圆曲线数字签名算法也成为目前研究的热门问题[4-6]。

1 椭圆曲线密码体制

1.1 有限域上的椭圆曲线

椭圆曲线密码体制[7，8]的有效实现主要用到两种类型的有限域，它们是素数域GF(p)和二元域GF(2)上的扩域GF(2m)。

素数域GF(p)：设p是一个大素数，GF(p)={0，1，2…，p-1}。

二进制扩域GF(2m)：由二元域GF(2)上所有次数小于m的多项式组成，即：

GF(2m)={am-1xm-1+am-2xm-2+…a1x+a0}，ai={0,1}。

域元素(am-1xm-1+am-2xm-2+…+a1x+a0)通常用长度为m的二进制串(am-1，am-2，…，a1，a0)表示，则GF(2m)={(am-1，am-2，…，a1，a0)},ai={0,1}。扩域GF(2m)中包含2m个元素。

(1) 有限域GF(p)上的椭圆曲线是对于给定a,b(4a3+27b2)modp≠0，满足方程：