admin 椭圆曲线加密算法的实现有软件和硬件两种方式。从安全性角度上考虑，硬件方式实现更具有优越性。但是绝大多数都是针对某一个固定有限域设计的，具体到应用场合，有时需要系统参数可选择。那么我今天就给大家介绍一种参数可选的椭圆曲线加密算法。
一、基于ONB的有限域运算法则
在有限域GF（2n）上进行乘法运算时，多项式基比正规基表示法简单，但在该域上进行乘方运算时，多项式基比正规基表示法困难。优化正规基（OptimalNormalBase，ONB）是一种特殊的正规基。基于ONB表示法的域元素在执行平方运算时非常高效，仅需对表示元素的矢量进行循环移位。在幂运算方面ONB表示法也比多项式表示法有效得多。在ANSIX.9162和ANSIX.9.63中强调：有限域中元素以正规基表示
时，优先选取存在Ⅱ型优化正规基，并且在选取的域GF（2n）中，当n为合数与n为素数时相比，椭圆曲线加密算法的安全性会降低，所以本文设计中采用Koblitz曲线，选取n为素数，存在Ⅱ型优化正规基的有限域GF（2191）和GF（2233），域元素用优化正规基表示。
1）乘法。当Fn2域元素用ONB表示时，其乘法法则是由一个n×n的矩阵M（乘法矩阵）来表征的。
设有限域GF（2n）中进行乘法的两个域元素用正规基表示为a=（an-1，…，a1，a0），b=（bn-1，…，b1，b0），乘法运算的结果为c=（cn-1，…，c1，c0），用ak、bk分别表示a、b循环左移k比特后的序列，则ck=akMbtrk。
（2）求逆。费尔马定理：若a∈F2n（a≠0），则a的逆元a-1=a2n-2=a2+22+…+2n-1
正规基表示下的元素求逆通常使用费尔马定理，但是直接应用需要的乘法次数太多。完成一次求逆运算所需乘法次数最少为I（m）=[log2（n-1）]+ω（n-1）-1次。其中ω（n-1）表示域GF（2n）中n-1的二进制数表示中1的个数。在此基础上，Sandhooh和ChangHanKim提出优化求逆算法（OptimalInverseAlgorithm，OIA）。该算法求逆主要用到乘法和平方运算，乘法次数和Itoh的算法相同。
二、椭圆曲线加密算法实现的硬件结构
从图1分析，椭圆曲线加密算法可分为三个层次，即输入/输出控制、有限域运算模块控制、ECC加/解密运算控制。
有关椭圆曲线加密算法曲线的参数，基点P的坐标、密钥通过外部存储器接口由32位总线输入到存储器中，在I/O状态机的控制下，由串并转换模块将有关数据输入到内部寄存器组中。寄存器组由233位的存储单元组成，主要存放运算过程中所需的中间变量和运算所需的系统参数。
有限域运算模块主要负责有限域的各种算术运算，通过状态机控制，完成域GF（2n）中的有限域加法、乘法、平方和求逆运算。运算控制级中的点乘状态机通过对有限域运算模块的合理调用，完成椭圆曲线上P=Q和P≠Q的加法运算，快速得到KP的结果，KP的计算也是整个ECC设计的核心。加/解密控制则是利用KP的值进行数据加/解密运算。
本文设计的支持多域宽的ECC加密系统模块如图2所示。域宽控制单元是选择域宽的，此处只选择了两个域宽。
椭圆曲线加密算法加/解密控制单元完成两个域宽下的椭圆曲线加密算法加/解密运算。
设计中采用了两个寄存组，分别存储GF（2191）和GF（2233）的外部输入参数。当数据总线输入191bits下的参数时，选择域宽191bits下的椭圆曲线加密算法加密；数据总线输入233bits下的参数时，选择域宽191bits下的ECC加密。本设计可以进行扩展，只要增加寄存器组，对域宽控制单元作简单修改，便可以完成更多域宽下的椭圆曲线加密算法运算。
1、点乘单元设计
椭圆曲线加密算法的核心是求点乘KP的运算。点乘运算层是通过对点加和点倍进行调度来实现。求点乘的算法主要有二进制算法、m进制方法、符号数字表示法、滑动窗口法等。本文实现椭圆曲线加密算法时采用的点乘法算法为冗余编码的二进制方法，其理由如下：
（1）该方法简单，易于硬件实现；
（2）M进制方法和滑动窗口方法都需要预计算，需要较大的存储空间，需要资源较大，并且编程复杂，不利于硬件实现。
其加密算法描述如下：
k的冗余编码：k=（kn-1，kn-2，…，k0）
（1）初始化：temp=G
（2）依次对（kn-1，kn-2，…，k0）进行下列运算：
①倍点:temp=temp+temp；
②如果ki为1，点加计算：temp=temp+P；
③如果ki为-1，点减计算：temp=temp-P
P=（x，y），由-P=（x，x+y），有temp-P=temp+（-P），故点减运算转换为点加来进行。冗余编码后计算点乘平均需要t/4次点加，t次点倍;最坏需要t/2次点加，t次点倍。冗余编码后，平均情况下减少了t/4个点加运算、点乘运算速度。
图3为KP运算结构图。在它的组成部分中，有限域运算模块包括乘法运算器、求逆运算器、加法及平方运算器，负责完成有限域上的各种算术运算功能。移位寄存器为线性反馈寄存器，其中保存经过冗余编码后的私钥值K。点加和点倍运算为两个独立的单元，分别通过状态机对有限域运算模块进行调度，完成点加与点倍运算。点乘状态控制器根据移位寄存器中存储的数值，选择进行点加或是点倍运算，完成点乘KP的计算。
2、有限域运算单元设计
图4是支持多域宽的乘法器结构。
其主要单元功能如下：
（1）域宽转换单元根据外部输入参数的不同，协同乘法器控制单元完成不同域宽下的乘法运算。
（2）与或阵列1与2分别对应GF（2191）和GF（2233）的与或阵列表。运算时，根据SEL值选择不同的与或阵列完成不同域宽的乘法运算。
（3）输出控制单元对两个与或阵列分别计算出的ck值进行拼接，得到最后的乘法结果。设计中寄存器的宽度为233位，当输入191位乘数时233位的寄存器的前191位保存运算结果。这样做的好处是不需要另外用寄存器来存储191位乘法时的运算值，可以节约面积。
基于有限域乘法模块，本文设计了一个逆控制器:具有求逆和乘法的双重功能。
基于串并结合结构的乘法模块，本文设计了一个逆控制器：具有求逆和乘法的双重功能。其单元模块如图5所示，它的主要组成部分是有限域逆控制器、模式选择器、求逆状态机和有限域乘法模块。
（1）模式选择信号CompType是由选择信号发生器产生的，主要控制运算的类型:乘法还是求逆。进行乘法运算时，模式选择信号低有效，对输入A和输入B执行乘法过程，输出A×B;进行求逆运算时，逆使能信号（Invstr）高有效，模式选择信号保持为高，对输入A执行求逆运算，输出A的逆运算。在这种情况下，输入B没有作用。运算结果存储在有限域乘法模块的寄存器中。
（2）控制器的主要功能是接收输入信号，按照求逆算法产生控制序列，控制乘法器执行操作。当运算完成时，由乘法模块中的寄存器输出结果，并置Finish为高电平。
（3）有限域乘法模块为串并结合结构的乘法器，完成乘法功能。
（4）求逆状态机根据OIA算法协同控制器对求逆运算进行控制。
加法器:正规基下的加法器十分简单，有限域任意两元素相加，结果是各自矢量表达位的逐位异或（XOR）。做加法运算时，输入/输出寄存器均选择并行工作模式，整个运算只需要一个时钟周期。
平方器:正规基下的元素平方是元素矢量表达式循环移位，完成整个运算也只需要一个时钟周期，这是选择正规基的突出优点。
本文通过对椭圆曲线加密算法进行研究，从点乘与群运算层的设计出发，给出了一种参数可选的椭圆曲线加密算法的FPGA实现方案。在调试阶段，本设计选择了存在Ⅱ型优化正规基的191bits和233bits有限域为例，采用VHDL语言进行描述，Altera公司的QuartusⅡ开发软件作为编译及综合工具。设计原形在AlteraCyclone的EP1C12Q240C8器件上实现并进行了验证，共占用17733个逻辑单元，最高时钟频率可达73.82MHz。在50MHz的时钟频率下，F2191上，平均一次椭圆曲线点乘运算时间为141365ms;F2233上，平均一次椭圆曲线点乘运算时间为191565ms，本文的设计突破了单一结构、参数固定的椭圆曲线加密算法专用芯片形式，使之能满足不同用户的需要。
小知识之费尔马定理
费尔马定理，又被称为“费马最后的定理”，由法国数学家费马提出。它断言当整数n >2时，关于x， y， z的方程 x^n + y^n = z^n 没有正整数解。被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·怀尔斯证明。
