基于FPGA的椭圆曲线加密设计

椭圆曲线加密是一种目前已知的所有公钥密码体制中能够提供最高比特强度的一种公钥体制。在FPGA实现椭圆曲线加密系统时，基于GF(2)的多项式有限域中的乘法、求逆运算是其中的两大难点。本文提供了一种椭圆曲线加密的FPGA实现的结构，着重讨论了基于GF(2)的多项式有限域中的乘法、求逆运算的实现，并与软件实现的性能进行了比较。
　　

加密的安全性
　　

从数论的角度来说，任何公钥密码系统都建立在一个NP(无法处理的问题)的基础上，即对于特定的问题，没有办法找到一个多项式时间算法求解该问题。一般求解此类问题的算法都是指数时间或者亚指数时间，例如现在常用的RSA算法就是基于大整数因式分解问题的难解性。经过近三十多年的研究，RSA算法虽然并不存在多项式时间的算法，但是可以找到亚指数时间的算法，目前其密钥长度必须大于1024位才能保证信息传递的安全，而椭圆曲线加密系统 (EllipTIc Curve Cryptosystem—ECC) 是目前已知的所有公钥密码体制中能够提供最高比特强度 (Strength-Per-Bit) 的一种公钥体制，只需要160的密钥就可以达到1024位RSA算法提供的安全等级。其根据是有限域上的椭圆曲线上的点群中的离散对数问题(ECDLP)，许多密码专家认为它是指数级的难度。因此对于椭圆曲线加密系统来说，这一点从计算量、处理速度、存储空间和通信带宽等角度分析，椭圆曲线加密系统都有很大的优势。IEEE已经制定的公钥加密算法标准P1363就是基于ECC算法的。现在密码学界普遍认为它将替代RSA成为通用的公钥密码算法，目前已成为研究的热点，是很有前途的研究方向。　　

图1 点算法实现 

图2 密钥、数据交换
　　 

图3 椭圆曲线加密系统结构图 

图4 椭圆曲线加密系统FPGA电路模块框图
　　

椭圆曲线加密体制
　　

椭圆曲线
　　

引进Non-supersingular椭圆曲线Weierstrass方程E:Y2+XY=X3+aX2+c其中a,c∈GF(2k),c≠0。为简化以后的运算，引进z使X=x/z;Y=y/z，则椭圆曲线方程化为E:y2z+xyz=x3+ax2z+cz3，定义(x, y, z)=λ(x, y, z)。可以看出当z≠0，(X, Y)和(x, y, z)相对应，当z=0可以理解为沿y轴趋向无穷远，定义为无穷远点O。则椭圆曲线上所有的点外加无穷远点构成的集合构成一个Abel群，O是单位元(零元)。在椭圆曲线E上定义了两种点运算：点运算和点运算。 

1) 椭圆曲线上点运算定义为：设P=( x1, y1, 1)∈E，Q=( x2, y2, 1) ∈E，-P=( x1, y1+ x1, 1), 当Q≠-P时 PQ=(x3, y3, z3) 则
　　

当P≠Q时：
　　

其中A=(x2z1+x1),B=(y2z1+y1), C=A+B,D=A2(A+a2z1)z1BC
　　

当P=Q时：
　　

其中
　　

2) 椭圆曲线上的点运算定义为：设P=(x1, y1, 1)∈E，(ltlt-1...l0)2是整数l的二进制表示形式，lP=PPAP=Q且Q∈E。 

利用上面的点运算，得点算法实现如图1所示。定义l=logpQ，若P的周期很大，则利用l、P求Q是比较容易的，但利用P、Q求l是很难处理的，这就是ECDLP，椭圆曲线加密就是建立在这个难题之上。 

加密体制
　　

在Diffe-Hellman公钥系统体制中，具体的椭圆曲线、曲线上点P及P的周期大素数N都是公开信息。

A和B要进行通讯，首先得到椭圆曲线E、点P及素数N。然后用户A将[1,N-1]中随机选取的整数a作为私钥，A将KpubA=aP作为自己的公钥传送给用户B，与此同时B将 [1,N-1]中随机选取的整数b作为私钥，并将KpubB=bP作为自己的公钥传送给A。A、B各自将自己的私钥点乘于对方传过来的公钥得到KAB，这样就完成了密钥的交换过程。当用户A需要将待传数据m传送给用户B时，A利用m和KAB生成Em，当用户B得到Em后，利用密钥交换过程自己生成的KAB和从用户A处得到的加密数据Em生成数据m。