近年来，信息安全问题变得日益重要，其核心技术——密码技术发展十分迅速， 尤其是公钥密码[1]得到了越来越广泛地应用。椭圆曲线密码（elliptic curve cryptography，ECC）[2-3]作为目前已公开的单位长度密钥加密强度最高的公钥算法，近年来大有取代应用最为广泛的公钥算法（RSA）的趋势。由于椭圆曲线算法复杂、计算量大，软件实现已不能满足应用需求，硬件实现也就成为一种必然选择。1993年，文献[4]是采用硬件方式实现ECC 的最早公开文献。目前，单个运算核做长度为192b 操作数的多倍点运算已经达到了几百次甚至近千次的水平，但仍然不能满足服务器、协处理器等高端领域上千次甚至几千次的需求。在双核条件下，工艺条件、工作频率等都不需要改变，只需要增加运算核的个数就可以成倍地提高运算速度。
本文给出了基于ECC 算法的双核处理器架构，明显地加快了运算速度。
1 双运算核
椭圆曲线数字签名算法（elliptic curve digital signature algorithm， ECDSA）是一种被很多国际和国内标准采用的算法，主要包括签名的产生和验证两部分。观察ECDSA 的签名产生和验证容易发现：1) 因为其他运算的运算量相对较小，所以多倍点在ECDSA 的签名或者验证中均占用绝大部分的运算时间；2) 签名算法只有一个多倍点运算，而验证算法则需要做两个多倍点运算。每一次多倍点运算的时间相差不多，这就出现了ECDSA 验证比签名慢得多的现象。在实际应用，特别是在网络协处理器中，有很多时候要求一组数据输入后尽可能快地给出运算结果。在单个运算核不能进一步加快运算速度的情况下，就要考虑多个运算核的协同运算或者并行运算。仔细观察ECDSA 验证算法，不难发现ECDSA 验证时2 个多倍点运算是不相关的，因此可以使用2 个运算核并行做多倍点运算，并把一个运算核的运算结果提供给另外一个运算核使用。2 个核协同工作使验证速度提高近一倍，详细步骤见表1，其中U1 和U2 分别表示2 个运算核。
表1 双核协同 ECDSA 验证
U1 U2
1)h mod n→A；
2)(A/s)mod n→k；
3)k·G→(Qx， Qy)；
4)if(Qx， Qy)=O，返回第(1)步else if u2·PA没结束，等待else从SRAM中读取u2·PA→(Px，Py )；
5)(Qx， Qy)+(Px，Py )→(Qx， Qy)；
6)Qx mod n-r→A；
7)if A=0通过验证，else没通过验证。 1)(r/s) mod n→u2；
2)u2·PA→(Qx， Qy)；
3)(Qx， Qy)→SRAM。

注: O 为椭圆曲线上的加法单位元。
2 个运算核协同工作把验证时间缩短了近一半，但是ECDSA 签名产生只有一个多倍点运算，无法通过两个运算核的协同工作显著地加快签名速度。在实际应用中还经常会遇到多组数据同时需要签名或验证的情况，并且每组数据之间除了配置信息其余数据相互独立。所以可以采用2 个运算核并行工作， 同时并行处理2 组相互独立的数据。 此时，2个运算核都能充分工作，签名或验证速度提高了近一倍。所以，采用双核实现ECDSA 时，既要支持2 个核协同验证，又要支持每个核独立地签名或验证，增加了应用的灵活性，提高了硬件效率。
其他椭圆曲线算法的基本运算与ECDSA 一样，都是有限域上的加法、乘法和除法，所以只需要在ECDSA 电路上增加部分控制电路就可以实现。本结构还具有可扩展性，支持外部接口直接验证椭圆曲线上的点是否有效、直接做点加或者多倍点运算。
2 硬件实现
本文实现的基于ECC 算法双核处理器结构如图1 所示。整个系统可以划分为输入输出、中断、裁决、 控制器、 存储器和运算核U1、U2。
输入输出部分接收外部的指令、配置信息、待签名或验证的数据以及内部反馈的控制器状态、存储器待输出的数据，给出可供外部查询的标志运算是否结束或异常的状态，输出最终结果。中断部分接收控制器的描述符运算完毕信号，向外部发送中断请求并且响应外部的中断应答， 再把应答完毕信号传输给控制器并且把对应的描述符传给输入输出部分。裁决部分接收来自控制器的各运算核对运行描述符的申请，裁决后再把申请到的描述符号传给控制器。
存储器使用了一片128×64b 的单口 SRAM、一个地址为0 的64b 模式寄存器（见表2）和一个地址为1 的64 b 状态寄存器（见表3）。
表2 模式寄存器
类 别 位 说 明
域 0 1表示素数域，0表示二元域
域宽 9-1 底层有限域元宽度
阶宽 18-10 基点阶二进制表示宽度
字数 21-19 有限域元或整数所占的64b的字数
描述符号 28-22 运算描述符的序号
禁用内核 32 1表示内核禁用，0表可用

表3 状态寄存器
类 别 位 说 明
空闲 0 1表示内核空闲，0表示内核忙
阻塞 2 因来不及处理内核在等待
申请描述符 10-4 当前等待写入的运算描述符序号
完成描述符 18-12 完成的运算描述符序号

SRAM 按照地址由低到高分段存储运算描述符、运算核的配置信息、待签名验证或其他运算的数据、双核协同运算时两核间需要传递的数据以及最终的运算结果。控制器和外部接口以64b 字宽读写SRAM。SRAM 接收外部或者控制器的请求读写信号，写入外部或运算核所提供的数据，读出暂存的运算结果。输入输出部分读写2 个64b 寄存器数据，并且对读得的模式寄存器数据进行译码，然后传递给控制器配置各个模块单元。
控制器接收裁决部分输入的描述符号，从存储器中读取运算描述符（见表4）和数据，接收来自输入输出部分对模式寄存器的译码，使运算核U1 和U2单独或协同对读得的存储器数据进行操作，完成各种预定的运算。
表4 运算描述符
助记符 位 说 明
READY 0 1表示准备好运算描述符
DONE 1 1表示完成当前运算描述符
TYPE 6-2 当前运算的任务类型
RETVAL.0 10-7 核1的返回信号
RETVAL.1 14-11 核2的返回信号
PARAM 21-15 系统参数基地址
WORKSPACE 31-25 工作空间基地址

由于本处理器主要应用于高速网络协处理器，所以要支持多种协议，因此加大了控制器的设计复杂度和规模。 为了易于组织和控制，把控制器人为地分为2 个大小相近的大状态机。每个大状态机再进一步划分为4 个或5 个子状态机。每个子状态机仅仅实现某一种具体协议，而各子状态机相互独立。模块化设计使得整个控制器比较简洁和规整。
3 运算核
运算核U1 和U2 是2 个由脉动阵列构成的高效双域（素数域和特征2 扩域） ECC 运算处理器，结构完全相同， 示于图2。该运算核的基础是一种从求最大公因子的加-减（plus-minus）算法扩展得到新硬件算法，面积复杂度和时间复杂度与操作数位长是线性关系。由于脉动阵列采用了非交织架构，显著地减小了关键路径延时，与Kaihara 和Takagi提出的冗余数架构相比，该运算核在面积增加20%的基础上吞吐率提高了一倍。所以，本文提出的运算核架构实现ECC 运算效率非常高[5-6]。
图2 中， rst 异步复位，clk 时钟上升沿有效，cmd 为16b 输入指令，di为64b 的输入数据，do 输出64 b 的数据， st 输出3b 的状态。译码器接收运算核外部输入的cmd 信号并对它译码，把译得的工作域、启动信号、标志位等传输给控制器；同时把域、写信号、乘法、除法次数传输给脉动阵列。控制器根据译码器传进来的信号和前一次脉动阵列反馈的运算结果生成新的运算指令，传递给脉动阵列。同时控制器还把生成的任务完成信号和运算异常信号反馈给译码器。脉动阵列接收cmd 信号中的地址信息，根据控制器传进来的指令对输入的数据进行处理，实现以64b 为间隔双域上的加法、乘法、除法、点加以及多倍点，然后把运算状态送给控制器，同时输出最终运算结果。运算核内部寄存器和数据通路宽度都是388b，但是外部只可以访问寄存器低384b。如果数据实际宽度小于384b 则高位补0。多倍点运算性能见表5， 详细信息见文献[5-6]。
表5 单核多倍点运算性能
有限域元宽度/b GF(p)/ms GF(2m)/ms
160 0.90 0.71
192 1.29 1.01
256 2.25 1.79
384 4.99 3.99

4 性能评估
使用Verilog HDL 语言描述整个硬件模块，并且用Modelsim SE 进行仿真。采用SMIC 0.18 LmCMOS 工艺库进行综合。 综合后规模是37. 2 万等效门，面积为3.72mm2， 关键路径为3.77ns。在频率为250MHz时，处理器运算性能见表6。表6 中：
1) ECDSA 签名栏和独立ECDSA 验证栏仅仅对应处理器中的一个核的性能，处理器整体性能是其2 倍；
2) [B]表示二元扩域运算，其余为素数域运算。
从表6 可见：1) 多倍点运算无论是在签名过程中还是在验证过程中，均占绝大部分的时钟周期；2) 双核协同工作使得验证速度较单核而言提高了近1 倍。作为速度提高1 倍的代价，双核实现较单核实现面积增加了77%。
考虑到工艺、频率、功能等方面的差异，仅仅将多倍点运算的时钟周期数与其他文献进行比较，如表7 所示。其中，文献[7]在标准RISC 架构中增加由5条指令构成的指令集加快有限域GF(p)和GF(2m)上的运算。文献[8]提出了一种支持双域非对称加密的硬件解决方案，主要实现交错模约的加法和乘法。从表7 中可以看到本文多倍点使用更少的时钟周期，表现更优的性能。
表7 多倍点运算比较
位数/b 类别 运算周期数
192 本文
[8]
[7] 320966
720000
1178000
256 本文
[8] 555450
1150000

为了进一步评估本处理器的性能，将它与文献[9]进行比较（见表8），所有数据均对应素数域。文献[9]通过改进模乘和倍点，提出了一种利用DSP 快速实现公钥加密的方法。
表8 ECDSA 运算比较
类别 文献 频率
MHz 位数
b 时间
ms 次数次·s-1
ECDSA
签名 [9] 200 192
239 1.67
2.85 598.8
350.9
产生 本文 250 192
256 1.30/2
2.26/2 769×2
442×2
ECDSA
签名
验证 [9] 200
 192
239 6.28
11.20 159.2
89.3
 本文 250 192
256 1.29
2.26 775.2
442.5

由表8 很容易看出，本处理器无论ECDSA 签名还是ECDSA 验证在不同数据长度下都表现了较优的性能。
5 结论
本文提出了一种支持多种ECC 协议的双核双域处理器结构，支持ECDSA 等多种数字签名的产生和验证，并且支持椭圆曲线点验证、点加、多倍点运算。这为我国自主的ECC 标准的芯片实现打下了基础。它有两种工作模式可供选择：1) 两个核中的每个核独立实现点验证、 点加、 多倍点、数字签名和验证；2) 两个核协同实现数字签名的验证。通过充分利用算法的并行性，验证的速度提高了近一倍。由于算法模块所有的参数均可变，适合用作网络协处理器等高端应用中的协处理器。目前，使用该双核双域ECC 处理器的一种高性能网络安全处理器正在设计之中。
参考文献 (References)
[1]  Diffie W， Hellman ME. New directions in cryp tography[J]. IEEE Transactions on Information Theory， 1976， 22(5): 644-654.
[2] Koblitz N. Elliptic curve cryptosystems [J]. Mathematics of Computations， 1987， 48: 203-209.
[3] Miller VS. Use of elliptic curves in cryptography [C]//CRYPTO'85， LNCS. New York: Springer-Verlag， 1986， 218: 417-426.
[4] A gnew GB， Mullin RC， Vanstone SA. Animplementation of elliptic curve cryp to systems over [J]. IEEE Jon Selected A reas in Communications， 1993 11(5): 804-813.
[5] CHEN Gang， BAIG guoqiang， CHEN Hongyi. A new systolicarch itecture for modular division [J]. IEEE Transactions on Computers， 2007， 56(2): 282-286.
[6] CHEN Gang， BAI Gguoqiang， CHEN Hongyi. A high-performance elliptic curve cryp tographic processor for general curves over based on a systolic arithmetic unit [J]. IEEE Transactions on Circu its and Systems II-express Briefs， 2007， 54(5): 412-416.
[7] Groβsch dlJ， SavaζE. Instruction set extensions for fastarithmetic in finite fields GF(p) and GF(2m) [C]//CHES 2004， LNCS. Springer-Verlag， 2004， 3156: 133-147.
[8] Wolkerstorfer J. Dual-field arithmetic unit for GF(p) and GF(2m) [C]//CHES 2002， LNCS. Springer-Verlag， 2003， 2523: 500-514.
[9] Itoh K， TakenakaM， ToriiN， etal. Fast Implementation of Public-Key Cryptography on a DSP TMS320C6201 [C]//CHES'99， LNCS. Springer-Verlag， 1999， 1717: 61-72
转载自清华大学学报(自然科学版)2008年第48卷第10期