一种通用GF(2m)模乘加速器的快速实现
2008-07-25
作者：杨先文1, 李 峥1，方 斌2
摘 要： 在椭圆曲线密码体制" title="椭圆曲线密码体制">椭圆曲线密码体制(ECC)中，有限域GF(2m)上模乘运算是最基本的运算，加速模乘运算是提高ECC算法性能的关键。针对不同不可约多项式广泛应用的现状，提出了一种通用GF(2m)模乘加速器设计方案。该加速器通过指令调度的方式，能快捷地完成有限域上模乘运算。实现结果表明，该设计完全适用于智能卡等应用要求。
关键词： 有限域; 椭圆曲线密码体制; 模乘运算; 快速实现
Neal Koblitz和V.S.Miller在公钥密码理论中引入椭圆曲线群，提出了椭圆曲线密码体制ECC（Elliptic Curve Cryptography）。随着传统公钥密码体制受到大数分解和并行处理技术的日益严峻的挑战，ECC便以最强的单比特安全性、曲线参数的更多可选性等优点得到了人们越来越多的重视，其中基于GF(2m)上的椭圆曲线密码体制的设计与实现是研究的热点之一。针对ECC应用现状，本文提出一种通用GF(2m)模乘加速器结构（密钥扩展范围：160≤m≤400）并对其快速实现。
1 算法及加速器结构设计
椭圆曲线密码系统运算层次如图1所示。由图1可知，模乘运算是ECC中最基本的运算之一，且模平方和模逆运算都可以转化为模乘运算操作。因此，快速实现模乘加速器具有很强的应用价值。对于有限域GF(2m)中的元素，一般有正规基表" title="基表">基表示和多项式基表示两种形式。采用不同基表示，虽然都可以表示成二进制数串的形式，但其对应的有限域中的运算却不一样。模乘加速器采用正规基表示基域元素时，很容易进行平方和指数运算，但是实现面积较大，也不具有通用性，这是因为正规基通常选取最优正规基(ONB)，而最优正规基的存在是有条件的。考虑到一般的有限域元素最直接、最常用的表达式是多项式的形式，且具有通用性。因此，本文提出的模乘加速器设计是基于一般不可约多项式的。
1.1 有限域GF(2m)上模乘运算
基域GF(2m)上多项式基表示下的模乘运算从处理方式上大体可以分为全串行、全并行、串并" title="串并">串并结合三种类型，且对应三种不同的快速设计方案。全串行模乘加速器是最简单的一种设计方案，完成一次GF(2m)上模乘运算至少需要m个时钟周期" title="时钟周期">时钟周期，运算效率相对较低。由于其实现面积小，因此通常应用于资源受限环境。全并行模乘加速器可以用一个时钟周期完成运算，但是其电路规模和m2成正比，所以当遇到较大m时，其面积和功耗将会急剧增大。串并结合模乘加速器是一种比较现实的设计方案，在设计该加速器之前需要选取一个合理的数字大小(digit-size)。若选取数字大小为g，则完成一次GF(2m)上模乘运算需[(m+1)/g]个时钟周期。在综合考虑效率、规模和功耗等各种因素情况下，本文模乘加速器将采用数字大小为8的串并结合加速器设计方案。若记
则其算法描述如下：
在上述算法步骤①中，V1的计算实际上只需将P(x)逻辑左移g bit，然后再模约不可约多项式F(x)即可。在快速实现时，该操作是在一个时钟周期内完成的。其原理如图2所示，其中L&R表示逻辑左移1bit后模约不可约多项式操作。
若记LeftShift(g)为逻辑左移1位，则对于任意k（0
因此，在上述算法步骤②中，V2的计算类似于V1的计算。只是在最后结果输出时要考虑乘数的作用，该部分对应在硬件结构上就是m×g个与门和m×(g-1)个异或门，其原理如图3所示，其中bit(j)表示m bit数据的第j bit(0≤j
在模乘加速器片选信号有效时，计算V1的逻辑电路和计算V2的逻辑电路在同一时钟周期内是并行工作的，并且时钟延迟相当，计算结果在下个时钟上升沿到来时得到。
1.2 通用GF(2m)模乘加速器结构设计
结合上述原理和方法，本文提出的通用GF(2m)模乘加速器架构如图4所示。
该加速器支持定义在GF(2m)和160≤m≤400上的模乘和模加运算。分为逻辑控制单元" title="控制单元">控制单元、运算逻辑单元和寄存器三个模块。逻辑控制单元主要对运算逻辑单元及各个寄存器读写进行控制。根据外部指令OC内容的不同，它控制加速器完成不同的操作。指令与操作之间的对应关系如表1所示。
运算逻辑单元主要包括乘运算逻辑和模约逻辑，在逻辑控制单元控制下每个时钟周期完成8bit模乘运算，并且在[(m+1)/8]个时钟周期后将运算结果送入结果寄存器。寄存器模块主要保存运算数据，在进行模乘运算时，在当前时钟周期内，被乘数寄存器和不可约多项式寄存器中的数据是一次性读入到运算逻辑，而乘数寄存器中的数据只有高8位被读入，同时乘数寄存器逻辑左移8位等待下一个时钟周期的到来。
对于基于椭圆曲线离散对数问题(ECDLP)的公钥加密体制，只有当私钥长度至少为160bit时，才能达到理想中的安全强度。因此，通用模乘加速器应用时要解决其接口问题。该加速器引脚定义如表2所示。
需要说明的是，为了使该加速器适合不可约多项式的任意选取，在设计乘运算逻辑和模约逻辑时应考虑到各种不可约多项式的情况。如果选取特殊的不可约多项式：三项式或五项式、全一式(AOP)，则加速器规模将有所减小，效率将有所提高，但是达不到通用的目的。这也是本文选取一般不可约多项式的原因。
2 实现和结果分析
采用VHDL语言作为设计工具，对上述加速器进行了设计实现。使用ModelSim软件对实现结果进行功能仿真，保证了功能设计的正确性。利用Quartus II软件平台，选择器件环境为CycloneII EP2C35F672C6完成通用加速器的逻辑综合和时序仿真，并经过FPGA开发环境验证，逻辑综合所得性能参数如表3所示。其中，标量乘速度是在频率为50.17MHz时钟驱动下，加速器配合微控制器（MCU）工作时的应用评估。
参考文献
[1] 吴永一，李庆，曾晓洋．具有防御功耗攻击性能的双域椭圆曲线密码处理器设计[J]．小型微型计算机系统，2006，27(12)：2321-2325．
[2] 蒋林，章倩苓，谢晓燕．基于GF(2n)的ECC协处理器芯片设计[J].微电子学与计算机，2003，(9)：50-54．
[3] DAILEY D V, PAAR C. Efficient arithmetic in finite field extensions with application in elliptic curve cryptography[J]. Journal of Cryptology, 2001,14(3):153-176．
[4] Standard specifications for public key cryptography[S]. IEEE P1363-2000, August 2000．
[5] KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987,48(177)：203-209．