基于FPGA 的ECC 算法高速实现∗武玉华，黄允，李艳俊，欧海文（北京电子科技学院，北京 100070）摘要：椭圆曲线密码体制(Elliptic Curve Cryptosystem ，ECC)是目前已知的所有公钥密码体制中能提供最高比特强度（strength-per-bit ）的一种公钥加密体制。
研究椭圆曲线密码算法的芯片设计有较大的研究价值和实用价值。
本文在深入研究椭圆曲线加解密理论基础上，使用Verilog 硬件描述语言实现了一种ECC 加密算法，具有高速低功耗的特点。
关键词：ECC ；FPGA ；高速中图分类号：TP309 文献标识码：AThe FPGA design of ECC encryption algorithmWU Yu-hua, HUANG Yun, LI Yan-jun, OU Hai-wen(Beijing Electronic Science and Technology Institute ，Beijing 100070 China)Abstract ：ECC is one of the known public crypto methods that provide the best strength-per-bit. Researching in the hardware design of ECC have much value. In this paper, we lucubrate the ECC’s theory, and implement a sort of ECC encryption algorithm, it has some advantages such as high-speed and low-exploit.Keywords ：ECC; FPGA; high-speed1 引言1985年，Neal Koblitz 和V ler 提出了基于椭圆曲线群上离散代数问题的公钥密码体制——椭圆曲线密码体制(简记为ECC)。
ECC 与RSA 相比具有密钥更短、安全性更高的特点，通常认为163位的ECC 密钥长度能够提供相当于1024位RSA 密钥长度的安全性，571位的ECC 密钥长度能够提供相当于15360位RSA 密钥长度的安全性。
ECC 是目前所有公钥密码系统中单位密钥安全性最高的密码系统。
因为ECC 的密钥较短，所以运算耗费的资源较少，目前ECC 广泛应用于无线连接设备中，譬如PDA, smart cards 等等。
目前，欧洲、俄罗斯、韩国和中国等都己经或打算将ECC 作为国家密码标准。
椭圆曲线密码系统的基域包括素域GF （P)和二进制域GF(n 2)，在硬件实现上GF(n2)椭圆曲线密码系统占用系统资源更少，效率更高。
因此最近几年有限域GF(n 2)上基本运算的硬件实现、有限域GF(n 2)上椭圆曲线密码系统的硬件实现都得到了业内重视。
相对于软件实现的椭圆曲线加密/解密体制，硬件实现可以提供更高的安全性和更快的速度。
本文在深入研究椭圆曲线加解密理论基础上，使用Verilog 硬件描述语言实现了一种ECC 加密算法，并通过QuartusII5.0工具进行了编译仿真，实验结果表明其功能正确，具有高速低功耗的特点。
2 椭圆曲线算法理论2．1 椭圆曲线数学基础2.1.1 椭圆曲线定义椭圆曲线E 是一个光滑的Weierstrass 方程在P(K)中的全部解(x ，y)的集合。
K 为域。
K 上的摄影平面P(K)是一些等价类的集合{(XY ：Z)}。
22322313246:E Y Z a XYZ a YZ X a X Z a XZ a Z ++=+++其中曲线上唯一的一个无穷远点是（0：1：0）。
这个点对应于点∞。
经过上述方程作如下转化可得：设x ＝X/Z,y ＝Y/Z ∗基金项目：国家自然科学基金资助项目（70431002）；北京电子科技学院信息安全与保密重点实验室基金项目（YZDJ0509）得：23213246y a xy a y x a x a x a ++=+++此时，椭圆曲线E 就是方程在射影平面2()P K 上的全部解，外加一个无穷远点O 组成的集合。
特征值为大于3的素数时，所化简得来的就是我们常见的椭圆曲线方程： 23:E y x ax b =++其中，a 、b ∈q F ，且324270a b +≠，则q F 上的椭圆曲线E 被定义为由参数a 和b 决定的点q=（x ，y ）的集合。
此外。
E 还包括一个无穷远点O.2.1.2 椭圆曲线运算规则椭圆曲线上的加法运算如下。
如果其上的三个点位于同一直线上，那么它们的和为0。
(1)0为加法单位元．即对椭圆曲线上任一点P ，有P+O=P(2)设P=(X ．Y)是椭圆曲线上的一点，它的加法逆元定义为Q=-p=(X ，—y)(3)设P 和Q 是椭圆曲线上X 坐标不同的点。
Q+P 的定义如下：画一条通过Q ，P 的直线与椭圆曲线交于R 。
由Q+P+R =0得Q+P= 一R ，即Q+P=R 。
如图1所示：图1 椭圆曲线几何原理图设P=(x1，Y1)．Q=(x2，Y2)．P ≠Q ，则P+Q=(x3，Y3)由以下规则确定：2312(mod )x x x p λ=−−3131()(mod )y x x y p λ=−−其中：λ =(Y2一Y )／(x2一x1) P ≠Q211(3)/(2)x a y λ=+ P=Q(4)点Q 的倍数定义如下：在Q 点作椭圆曲线的一条切线．设切线与椭圆曲线交于点S ．定义2Q=Q+Q= 一S 。
2.2 安全的椭圆曲线在使用椭圆曲线加密/解密协议时，必须保证使用的椭圆曲线是符合安全标准的，在国际上，如何生成一条安全的椭圆曲线一直范围原因是研究的热点和重点。
本文仅给出FISP186-2提供的，经过验证是安全的一条椭圆曲线。
232y xy x ax b +=++椭圆曲线的系数：a=1b=2 0a601907 b8c953ca 1481eb10 512f7874 4a3205fd基点的阶n=5846006549323611672814742442876390689256843201587基点G:X G =3 F0EBA162 86A2D57E A0991168 D4994637 E8343E36Y G =0 D51fbc6c 71a0094f a2cdd545 b11c5c0c 797324f1因子 h=22.3 椭圆曲线加解密Alice 和Bob 要进行通讯，首先需要得到一个椭圆曲线及椭圆曲线上面的一个点000(,,)P x y z E =∈和大素数n ：Bob （使用者）执行了下列计算：（1）在区间[1,n-1]中随机选取一个整数d 。
（2）计算点:()Q d P d P =×个相加（3）Bob 公开自己的公开密钥――q （E(F ),p,n,Q） （4）Bob 的私钥为整数d ！Alice 要发送消息m 给Bob ，Alice 执行：（1）查找Bob 的公钥q （E(F ),p,n,Q）， （2）将m 表示成一个域元素∈q m F ，（3）在区间[1,n-1]内选取一个随机数k,（4）使用Bob 的公钥计算点11(,):()x y k P k P =×个相加（5）计算点22(,):,x y k Q =×,如果20x =，则回到（3）（6）计算C g2：＝m x （7）传送加密数据11(,,)x y C 给BobBob 收到Alice 的密文11(,,)x y C 后执行（1）使用私钥d ，计算点2211(,):(,),x y d x y =再计算12x −q F 中＝？（2）通过计算m:=1C −g 2x ,恢复出明文数据m 。
不难看出，第三者无法从Q ，11(,)x y ，P 得到密钥，因为A,B 的私钥d,k 并没有被传播，从Q ，11(,)x y ，P 计算d 或是k ，是离散对数问题，是为人熟知的困难问题。
2．4 基于FPGA 的椭圆曲线加密算法的高速实现实现椭圆曲线加密系统可以分为以下几个层次：有限域底层运算――点加和倍加――点乘――加密。
目前关于椭圆曲线密码实现有很多种不同的算法，常用的一种思路是按照椭圆曲线加密的整个过程一次实现有限域运算、点加、倍加、点乘和最后的加密，这种方法的好处是思路自然顺畅，依次进行。
缺点是在进行点乘运算时，需要进行大量的求逆运算，耗费惊人的资源和时间，对程序设计提出了很高的要求。
还有一种方法是采用射影坐标来代替投影坐标进行点乘运算，这样做的好处是可以减少求逆运算的次数，并且在进行点乘的同时集成了点加和倍加运算。
由于在进行加密运算时需要在区间[1,n-1]内选取一个随机数k ，所以需要设计一个生成随即数的程序模块，利用的数学公式为：_(_)mod Rand Number Rand Seed X Y Z =×+,其中X 和Y 中必须有一个数为素数，Z 相当于确定的区间。
整个随机数的函数模块为：function [m-1:0]random;input [m-1:0]a;beginrandom =(a*x+c)%p; endendfunction由于生成的数为二进制形式，所以必须要对其度进行判断，即对生成的二进制数第一位进行判断，为0表示此数不符合要求。
函数模块如下：function [3:0] mydeg;input [m-1:0]a;begin:brkfdghinteger i;reg [m-1:0]tmp;reg [3:0]n;tmp =a;n =m_b-4'h1;for(i =(m-1);i>=0;i =i-1)beginif(tmp[(m-1)]!=1'b1)begintmp =tmp<<1;n =n-4'h1;endendmydeg =n;if(a ==9'b0_0000_0000)mydeg =4'h0;end endfunction 加密程序实现的步骤为：（1）查找公钥q （E(F ),p,n,Q）， （2）将m 表示成一个域元素∈q m F ， （3）在区间[1,n-1]内选取一个随机数k, （4）使用Bob 的公钥计算点11(,):()x y k P k P =×个相加（5）计算点22(,):,x y k Q =×,如果20x =，则回到（3）（6）计算C g 2：＝m x时钟信号CLK 为上升沿触发。
输入为msg ，输出为C,x1,y1。
仿真结果见图2。
图2 椭圆曲线加密仿真波形图4 实验结果和结论我们使用Verilog 语言实现了一种ECC 加密算法，在QuartusII5.0工具下进行了仿真、综合，实验结果证明，我们的设计正确。