引言
人们根据密钥的特点，将密码系统分为私钥和公钥两大密码系统。在私钥密码系统中，解密密钥和加密密钥相同或者很容易从加密密钥导出，这一特点致使加密系统变得不安全。1976年Diffie和Hellman发表了著名的“密码学的新方向”一文［1］，提出公开密钥密码的思想，从此开始公钥密码的发展。在公钥密码体制中，解密密钥和加密密钥不同，从一个难于推出另一个，加密和解密是可分离的，通信双方事先无须交换密钥就可建立起保密通信。1978年由Rivest、Shamir和Adleman提出的RSA［2］方案及1984年提出的ELGamal［3］方案均属于公钥密码体制。RSA的安全性依赖于大整数分解因子问题的困难性，ELGamal的安全性则是建立在有限域上离散对数问题困难性基础上的。
随着计算机网络的迅速发展，相互之间进行通信的用户数量的增多，RSA与ELGamal公钥密码体制的公钥位数较大（一般为512比特以上）的弱点逐渐暴露出来。1985年Koblitz［4］和Miller［5］分别独立地提出利用椭圆曲线上离散对数代替有限域上离散对数，可以构作公钥位数较小的ELGamal类公钥密码。
1 椭圆曲线
定义1：设K=GF(q)（其中q=pd）为一有限域，K上椭圆曲线方程E为：
y2=x3+ax+b (p≥5，a,b∈K，4a3+27b2≠0)
y2+xy=x3+ax+b (p=2,a,b∈K)
满足椭圆曲线方程E的所有点及一个称为无穷远点O［6］的点所构成的集合
E(K)={(x,y)|(x,y)∈E,且x,y∈K}∪O
为该曲线的K-有理点集合，它是一个有限集，元素个数称为该椭圆曲线E的阶，记#E(K).我们在该有限集上定义一个加法运算［6］,使得这些点对于该加法运算形成一个Abel群，群的单位元为无穷远点O.
定理1(Hasse不等式)：设K=GF(q), E/K为有限域上的椭圆曲线，有不等式
|#E(K)-pd-1|≤2(pd)1/2成立。
定义5：设E/K为椭圆曲线，点P为其上的点，最小的满足条件rP=O，正整数r称为点P的阶。根据有限域的知识，我们知道这样的r总是存在且整除椭圆曲线阶#E(K).整数k,l，满足条件kP=lP，当且仅当k=lmod(r).
2 椭圆曲线上的密码体制
椭圆曲线上离散对数问题ECDLP定义如下：给定素数p和椭圆曲线E，对Q＝kP，在已知P，Q 的情况下求出小于p的正整数k.可以证明由k和P计算Q比较容易，而由Q和P计算k则比较困难。ECDLP是比整数因子分解问题IFP和离散对数问题DLP难得多的数学难题。基于该难题，Neal Koblitz和Victor Miller［4］［5］在1985年分别提出了椭圆曲线密码系统（ECC）.ECC既可以用于数据加密，也可以用于数字签名。
将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，将椭圆曲线中的乘法运算与离散对数中的模幂运算相对应，我们就可以建立基于椭圆曲线的对应的密码体制。
例如，对应Diffie-Hellman公钥系统，我们可以通过如下方式在椭圆曲线上予以实现：在E上选取生成元P，要求由P产生的群元素足够多，通信双方A和B分别选取a和b,a和b 予以保密，但将aP和bP公开，A和B间通信用的密钥为abP,这是第三者无法得知的。
对应ELGamal密码系统可以采用如下的方式在椭圆曲线上予以实现：
将明文m嵌入到E上Pm点，选一点B∈E，每一用户都选一整数a,0＜a＜N，N为阶数已知，a 保密，aB公开。欲向A送m,可送去下面一对数偶：［kB,Pm+k(aAB)］,k是随机产生的整数。A可以从kB求得k(aAB).通过：Pm+k(aAB)- k(aAB)=Pm恢复Pm.同样对应DSA我们可以在椭圆曲线上构造ECDSA.
3 椭圆曲线密码与智能卡
智能卡通常用在安全性要求比较高的场合，并与密码学的应用相结合。这首先是由于智能卡能够保护并安全的处理敏感数据；而智能卡能保护密钥也是相当重要的，因为“一切秘密寓于密钥之中”，为了能达到密码所提供的安全服务，密钥绝对不能被泄密，但为安全原因所增加的成本却不能太多。
智能卡自身硬件的资源极为有限。用其实现安全系统面临着存储器容量和计算能力方面受到的限制。目前市场上的大多数智能卡有128到1024字节的RAM，1 k到16 k字节的EEPROM，6 k到16 k字节的ROM，CPU通常为8比特的，典型的时钟频率为3.57 MHz.任何存储或者是处理能力的增强都意味着智能卡成本的大幅度提高。
另外智能卡的数据传送是相对慢的，为提高应用的效率，基本的数据单元必须要小，这样可以减少智能卡与卡终端之间的数据流量，其传送时间的减少则意味着实用性的增强。
将椭圆曲线密码体制应用于智能卡的优点是：生成私钥公钥方便；节省内存空间；节省带宽，提高实用性；节省处理时间，而不需要增加硬件的处理等方面。ECC密钥短所带来的各优点恰好弥补了智能卡硬件的各种局限，不仅能有效地降低智能卡的生产成本，也能提高智能卡的实用性。
4 参数的选取
椭圆曲线上的公钥密码体制的安全性是建立在椭圆曲线离散对数的基础上，但并不是所有椭圆曲线都可以应用到公钥密码体制中，为了保证其安全性，我们必须选取安全椭圆曲线，即阶为大素数或含大素数因子的椭圆曲线为安全椭圆曲线。一般来说有四种寻找安全椭圆曲线的方法：
1）有限域GF(q)上随机生成一椭圆曲线，直接计算其阶，判断阶是否为大素数或含大素数因子，若是即确定，否则继续选取曲线，直至符合条件。
2）取具有一定特殊性椭圆曲线的系数，计算该椭圆曲线的阶，对该阶进行判断，直至找到所需要的安全曲线。
3）如果q=2m，其中m能被一个比较小的整数d整除，我们首先在有限域GF(q1)(q1=2d)上选择一椭圆曲线E‘并计算其阶，根据此值，利用Weil定理［6］计算该曲线在其扩域GF(q)上的阶，若此阶符合安全标准，我们再找曲线E‘在域GF(q)上的嵌入E，则E即为所需的安全椭圆曲线。
4）首先给出具有安全条件的曲线阶，然后构造一具有此阶的椭圆曲线。
目前国内外比较流行的计算椭圆曲线阶的算法有complex multiplication算法、SEA算法、Satoh算法［7］,［8］均属于上述几种方法之一种。应用广泛的椭圆曲线公钥密码体制中大多是基于特征2的有限域上，因此寻找特征2的有限域上的安全椭圆曲线必须先予以解决，Satoh算法正是为此提出的。
5 有关Satoh算法的实现问题
作者使用Mathematica语言实现了特征2时Satoh算法。在算法实现的验证部分用到了上述方法，为了在有限域F2160上寻求安全椭圆曲线，首先在有限基域F216上随机生成一条椭圆曲线E，利用Satoh算法计算其Frobenius同态迹C，根据椭圆曲线阶的计算方法可知该曲线的阶为216+1-C.设方程x2-Cx+216=0的两个根为α，β，根据Weil共轭［6］可知该条椭圆曲线在扩域上的阶为：(216)10+1-(α10+β10)，如果这个阶为大素数或含大素数因子，我们将E嵌入到F2160上就找到了一条符合密码体制要求的安全曲线。
Satoh算法的C语言实现所涉及的运算领域有：有限域Fq，2-adic环Zq和2-adic整数环Z2，各个领域的元素之间的运算是大整数的基本运算，这里q=2160.2-adic整数环Z2中元素α的形式如同α=a1+a22+a322+a423+...an2n-1+...幂级形式，ai的值或为0或为1.由于算法只需要精度precision为83=［160+62］，2-adic整数环Z2中元素级数不能超出83.2-adic整数环中元素的数据结构定义为：
Typedef unsigned long BIGword；
Typedef struct{
int length
BIGword value［3］
}Z2word；
两个元素的相加减运算为模283意义下的大整数的加减运算，相乘为模283意义下的乘法运算。求元素a的逆元运算采用牛顿迭代算法，迭代的初始值为1（该元素为奇数，否则无逆元），迭代公式为x←x-x(ax-1)，迭代一次精度翻倍，达到所需83的精度要迭代7次。
有限域Fq上的元素α=a1+a2t+a3t2+a4t3+...a160t159，其形式为一次数不高于159次的多项式，多项式的系数或为0或为1，两个多项式相加为对应次数的系数模2加，减法与加法是一个运算。相乘为模一多项式f(t)=t160+t5+t3+t2+1意义下的乘法，在实际的运算过程中采用边乘边模的方法，也即次数出现160，就用低次多项式t5+t3+t2+1代替。求逆运算采用扩展欧几里德算法。Fq元素的数据结构定义如下：
typedef struct {
int length
BIGword coef［5］
}Fqword
环Zq为2-adic整环Z2上的多项式Z2［t］，模去多项式f(t)生成的理想［f(t)］所形成的商环，即Zq：=Z2［t］/［f(t)］，f(t)同上。从环Zq的构造可知，Zq中元素的形式为一次数不高于159的多项式，系数为2-adic整环Z2上的元素，这样，我们可以定义Zq的元素数据结构。
typedef struct {
int length
Z2word coef［159］
}Zqword
元素的加、减法运算同一般多项式运算类似，只是对应次数的系数进行加、减运算是2-adic环Z2上元素的加、减。乘法运算的处理方式如同有限域中元素乘法的运算处理。求元素a的逆运算采用牛顿迭代方法。迭代初始值求法为：首先将元素a系数模2，得到有限域上的一元素a‘，利用有限域上元素求逆方法计算出a‘的逆，a‘的逆即为迭代初始值。迭代多项式与2-adic整数环中元素的求逆迭代多项式相同。
在上述基本运算得到解决后，我们着手于椭圆曲线阶的计算。随机选取椭圆曲线y2+xy=x3+α（α为有限域中元素），利用Satoh算法可求出该曲线的阶。每给出一个α值（实际上给出了一条曲线E），就会算出该曲线的阶。
|
a的选取 |
对应曲线的点的个数 |
|
0x40582590ac00873494fc02b180ba640130acb252 |
0x1000000000000000000014c3ec7372a968d0b1138 |
|
0xd80c00e8008e2021384a0243012d600554e10200 |
0xfffffffffffffffffffed059c32e5457a83e0314 |
|
0x8992b8ca2b70624440f6003100411646002d102c |
0xffffffffffffffffffff203b8ad8bf63e2891eac |
作者在攻读硕士学位期间实现了素域上安全椭圆曲线构造的SEA算法，在后期学习和工作中，分别用Mathematica和C两种语言实现Satoh算法。这两个算法的实现解决了有限域上安全曲线的构造问题，对今后的研究——椭圆曲线密码体制在移动通信领域中的应用做了充分的准备工作。
6 结束语
1.分析了将安全椭圆曲线引进公钥密码体制的优点是，与目前应用较普遍的ＲＳＡ算法相比，在同等安全的情况下，其所需的密钥长度远比ＲＳＡ低，因而ＥＣＣ的特性更适合当今电子商务需要快速反应的发展潮流，在快速加密、密钥交换、身份认证、数字签名、移动通信、智能卡的安全保密等领域，具有广阔的市场前景。
2.椭圆曲线公钥密码体制实现的关键是安全曲线的构造问题，对此本文给出了实现Satoh算法验证部分的技巧：首先计算小基域上一椭圆曲线阶，通过Weil定理可知该曲线在其有限扩域上的阶，若该阶符合椭圆曲线公钥密码体制的要求，则将曲线嵌入到其扩域上即可求得一条安全曲线。
参考文献：
［1］ W Diffie,M E Hellman.NEW Directions in Cryptography［J］.IEEE Trans Informat Theory,1976,IT-22:644-654.
［2］ Rivest R L,Shamir A,Adleman L.A Method for obtaining Digital Signatures and Public-key Cryptosystem［J］.Comm ACM，1978,21(2):120-126.
［3］ L ElGamal.A Public Key Cryptosystem and Signature Scheme Base on Discrete Logarithm［J］.IEEE Transactions of information Theory,1985,31:469-472.
［4］ V Miller.Use of Elliptic Curves in Cryptography［A］.A M Odlyzko.Advances in Cryptology-Proceedings of CRYPTO 1986,volume 263 of Lecture Notes in Computer Science［C］.New york:Springer,1986.417-426.
［5］ N Koblitz.Elliptic Curve Cryptosystems［J］.Mathematics of Compution,1987,48:203-309.
［6］ Joseph H Silberman.The Arithmetic of Elliptic Curves［M］.New York:Springer-Verlag,1986.46-61,130-136.
［7］ T Satoh.The canonical lift of an ordinary elliptic curve over a finite field and its point counting［J］.Ramanujan Mathematical Society,2000,15:247-270.
［8］ M Fouquet,P Gaudry,R Harley.An extention Satoh‘ algorithm and its implementation［J］.Ramanujan Mathematical Society,2000,15:281-318.
本文作者：华南农业大学理学院计算机系 郭艾侠