椭圆曲线密码的芯片集成

   椭圆曲线密码(ECC)是公钥密码算法的一种，1985年由Koblitz和Miller分别提出，它的理论基础是椭圆曲线的算术理论。ECC是一种非常复杂的数学算法，人们虽然可以通过对高速通用处理器编程很好地实现ECC，但是由于其算法的复杂性，专门用于实现较完整ECC的专用集成电路(ASIC)芯片还未见到，如何设计出能够完整实现ECC的ASIC芯片需要探索。

1 ECC概述
    ECC是利用定义在某个有限域上的某椭圆曲线有限群而构造的密码。常用的有限域有素数域GF(p )和特征2域GF(2m)。一条定义在有限域GF(p )上的椭圆曲线通常是指方程：
y2=x3+ax+b(mod p)          (1)
    在GF(p )上的解(x,y)连同一个特殊元素O 所构成的集合为：
E={(x,y)|y 2=x 3+ax+b(mod p),O } (2)
    其中，a和b是GF(p)上的两个数。当(x,y)是以上方程的解时，一般称P=(x,y)是该椭圆曲线的一个点。特殊元素O 通常被称为无穷远点。一条定义在有限域GF(2m)上的椭圆曲线通常是指方程y 2+xy =x 3+ax 2+b在GF(2m)上的解(x,y )连同一个特殊元素O 所构成的集合。
    假如P和Q是椭圆曲线E上的两个点，则P+Q始终会是E上的另外一个点。已知椭圆曲线E上的两个点P和Q，则当P和Q不相等时，由P和Q计算P+Q的过程称为椭圆曲线E上的点加运算；当P和Q相等时，由P和Q计算P+Q，或者由一个点P计算P +P的过程称为倍点运算。对于定义在以上两种有限域上的椭圆曲线，都有相应的固定的点加运算公式和倍点运算公式。假如P是椭圆曲线E上的一个点，k是一个正整数，将点P连续自加k次时，其结果通常用kP表示，即：
kP=P+P+…+P         (3)
    已知椭圆曲线E和E上的点P以及正整数k，由E、P及k计算kP的过程通常称为椭圆曲线E上的多倍点运算或标量乘法。而已知椭圆曲线E和E上的点P 以及kP，由E、P和kP求解k的问题又通常称为椭圆曲线E上的离散对数问题，常简记为ECDLP。正如大数分解问题和素数域上的离散对数问题一样，椭圆曲线离散对数问题是一个更加困难的问题。基于椭圆曲线离散对数问题的公钥密码就称为椭圆曲线密码或椭圆曲线密码系统。

2 ECC的实现
    ECC是一种多参数密码。要实现一个ECC算法，必须对所涉及的各个参数及有关的算法做出选择。ECC算法的实现呈现出一种多样性特征。这一特征与对称密码中的分组密码算法有着根本不同，与非对称密码算法中的RSA算法也有所不同。也正因如此，造成了ECC算法实现的复杂性，给ECC的芯片集成带来了极大困难。
    ECC算法实现时呈现出的多样性特征也决定了ECC算法芯片的多样性。根据不同的应用将需要不同芯片。一般地ECC算法主要应用于两种场合：一是服务器系统(高端)，二是用户端系统(低端)。所以研制ECC一定要区分清它的应用场合。针对不同的应用场合，需要研制不同的芯片。此外，针对不同的密码功能或安全协议(例如是做密钥交换用还是做签名用，或是二者都需要)也可能要研制不同的芯片。因此，ECC芯片将具有多样性和系列化特征。
3 ECC芯片现状

3.1 学术研究情况
    采用硬件方式实现ECC的报道最早见于文献[1]。文献[1]构造了一块专门用于执行有限域GF((231)5)=GF(2155)上乘法运算的VLSI芯片，然后再利用一个高效的可编程控制器实现了基于GF(2155)上的ECC。利用这一芯片，加密速度大致可以达到40 kb/s。换算为签名速度大致是130次。2000年文献[2]介绍了对定义在GF(2163)上的Koblitz曲线采用现场可编程门阵列(FPGA)方式实现和采用ASIC方式实现的仿真结果。在0.25 μm的CMOS工艺下，ASIC芯片的规模是16.5万门电路，主频可以达到66 MHz。利用这一芯片，两种曲线的签名速度分别可以达到每秒900和1 500次以上。这一速度对服务器应用是能够满足的。2000年文献[3]还介绍了对定义在GF(2167)上的曲线利用Xilinx XCV400E FPGA芯片的实现结果。这一实现中，芯片的最高工作频率可达76.7 MHz。这时，完成一次多倍点运算只需要0.21 ms。从而每秒可以完成4 762次多倍点运算。

3.2 产品开发情况
    2001年，德国的Infineon公司推出了一款安全芯片，产品型号为SLE 66C42P。它使用了一个16位的安全控制器，具有数据加密标准(DES)和三重DES算法(3DES)的对称加/解密功能和实现椭圆曲线数字签名算法(ECDSA)的功能。对椭圆曲线数字签名算法，它只对定义在GF(2m )，m =192上的椭圆曲线有效。在5 MHz的工作频率下，完成一次签名的产生所能需要的时间是285 ms，完成一次签名验证所需要时间是540 ms。在10 MHz的工作频率下，完成一次签名的产生所需要的时间是142 ms，完成一次签名验证所需要时间是270 ms。
    2001年，Motorola公司推出了一款多功能安全处理器，型号为MPC180。这是一款功能上几乎做到了包罗万象的芯片，主要是为了实现网络协议安全(IPsec)协议而为客户端用户所设计。该芯片具有实现DES、3DES、RC4、DM4、MD5、SHA-1、RSA、ECC和随机数产生等算法功能。
    关于ECC算法功能，MPC180芯片可以同时兼容素数域曲线和特征2域曲线。对素数域情况，只要求定义曲线的素数域GF(p )中的素数p是一个规模在64比特到512比特之间的素数即可。对特征2域情况，也只要求定义曲线的有限域GF(2m)中的m是一个64到512之间的数即可。对两种情况下的椭圆曲线，芯片没有提供任何完整的密码算法或密码协议的实现，只提供了标量乘法的计算功能和计算椭圆曲线上点加P+Q和计算倍点2P的功能。

4 基于K-233曲线的ASIC芯片
    最近我们选择了ANSI X9.62中定义在GF(2233)上的一条Koblitz曲线(即K-233曲线)作为目标曲线，采用IEEE Std 1363-2000标准[4]中的算法，对ECC的ASIC实现技术进行了探讨。下面对基于K-233曲线的ASIC芯片进行介绍。

4.1 芯片功能
    芯片定义了两种功能，4种不同的工作状态。

4.1.1  ECDSA数字签名功能
    (1)签名的产生(工作状态Ⅰ)
输入：长度不超过231位的消息m，私钥kA；输出：对m的签名r、s；其中r 和s 的长度不超过231位。
    (2)签名的验证(工作状态Ⅱ)
输入：公钥PA，消息m，签名r、s；输出：真、伪。

4.1.2  计算ECC中标量乘法的功能
    (1)有输入的情况(工作状态Ⅲ)
输入：长度不超过231位的随机数k，固定基点P；输出：kP。
    (2)无输入的情况(工作状态Ⅳ)
芯片自身产生长度不超过231位的随机数，输出：k、kP。
ECDSA采用了IEEE Std 1363-2000中规定的算法。

4.2 THECC/233-100芯片
    我们将基于K-233曲线的ASIC芯片命名为THECC/233-100。THECC/233-100芯片主要由随机数产生模块、大整数模运算模块和椭圆曲线运算模块组成。随机数产生模块主要为算法在运算过程中提供所需要的随机数；大整数模运算模块主要完成整数的模加、模减、模乘和模逆运算；椭圆曲线运算模块是芯片的最主要模块，完成椭圆曲线多倍点运算功能。
    椭圆曲线多倍点运算分两个层次来完成。一个是底层运算，主要执行有限域GF(2233)中的各种运算；另一个是上层运算，主要利用底层运算来完成椭圆曲线上的各种运算，包括点加运算、倍点运算和多倍点运算等。底层运算中主要包括一个平方运算器、一个乘法运算器和一个加法运算器。GF(2233)中的求逆运算先利用Fermat小定理方法，将其转化为一系列平方和乘法运算，再利用平方器和乘法器完成运算。上层运算中的多倍点运算采用了Montgermy方法[5]。
    根据设计，完成一次GF(2233)上的加法和平方运算只需1个时钟，完成一次GF(2233)上的乘法运算平均需要30个时钟。芯片的关键路径包含4个门延时。芯片完成一次椭圆曲线多倍点运算共需要GF(2233)上的平方运算1 163次、乘法运算1 170次和求逆
运算1次。这样，THECC/233-100芯片完成一次多倍点运算约需要23 000个时钟，完成一次签名的产生大约需要25 000个时钟。从而在1 MHz的工作频率下，芯片每秒完成签名产生约40次。
    THECC/233-100采用上海中芯国际集成电路有限公司0.18 μm CMOS标准工艺。芯片的管芯面积2.35×2.35 mm，电路规模约12万等效门。芯片最高工作频率125 MHz，最高运算速度每秒完成5 000次签名产生。芯片采用16位输入和16位输出数据线接口，有效管脚56个，工作电压3.3 V。经测试，芯片的最高工作频率可达140 MHz。在100 MHz的工作频率下芯片工作稳定，每秒可以连续完成数字签名4 000次。表1给出了THECC/233-100芯片及公开文献中所介绍同类芯片的性能指标。

5 结论
    ECC的芯片集成是一个很复杂的问题。ECC多参数特性能够为ECC的使用者提供丰富多彩的ECC算法，这是ECC的最大特点之一。但ECC的这一特点与ECC的芯片集成存在着矛盾。对ECC芯片来说，芯片基本功能和由基本功能所实现的ECC算法总是十分有限的。这样，在设计ECC芯片时，就需要在丰富多彩的ECC算法和功能相对稳定的ECC芯片之间做出合理规划，以便将来所设计的ECC芯片能够最大限度地发挥其功能。ECC算法的多样性与ECC芯片集成之间所存在的这种矛盾，与RSA算法的芯片集成有着很大的不同(在考虑RSA算法的芯片集成时，事实上只有一个参数，即模长。芯片需要完成的运算也非常单一，只有模乘和模幂)。这也是为什么RSA算法的芯片集成相对容易，市场上能见到的RSA芯片比较多，而ECC算法的芯片集成复杂以及目前市场上ECC芯片非常少见的原因之一。

6 参考文献
[1] Agnew G B, Mullin R C, Vanstone S A. An Implementation of Elliptic Curve Cryptosystems over GF(2155) [J]. IEEE J on Selected Areas in Communications,1993,11(5):804—813.
[2] Okada S, Torii N, Kouichi I. Implementation of Elliptic Curve Cryptographic Coprocessor over GF(2m) on an FPGA [C]. Workshop on Cryptographic Hardware and Embedded Systems — CHES’2000. Spring-verlag, LNCS 1965, 2000:
25—40.
[3] Orlando G, Paar C. A High-performance Reconfigurable Elliptic Curve Processor for GF(2m) [C]. Workshop on Cryptographic Hardware and Embedded Systems — CHES’2000. Spring-verlag, LNCS 1965, 2000:41—56.
[4] IEEE std 1363-2000. Standard Specifications for Public-key Cryptography [S]. 2000.
[5] Lopez J, Dahab R. Fast Multiplication on Elliptic Curves over GF(2m) Without Precomputation [C]. Cryptographic Hardware and Embedded Systems — CHES’99, LNCS 1717, 1999:316—327.

收稿日期：2004-06-07

[摘要] 椭圆曲线密码(ECC)是一种非常复杂的数学算法，设计出能够完整实现ECC算法的专用集成电路芯片(ASIC)非常困难。当前，对ECC的研究主要集中在ECC的实现方面，其中，尤其是ECC的芯片集成引人关注。为此文章在总结已有ECC芯片实现情况的基础上，介绍了清华大学微电子学研究所在ECC芯片实现方面所做的工作。

[关键词] 椭圆曲线密码；算法；有限域；集成电路

[Abstract] Elliptic Curve Cryptography (ECC) is a rather complicated algorithm. It is difficult to design an application specific integrated circuit (ASIC) to fully implement ECC. Presently, studies for ECC are mainly concentrated on implementations of various ECC algorithms, especially by the integrated circuits technology. After some existing hardware implementations of ECC being reviewed, this paper presents the research achievements that the Institute of Microelectronics of Tsinghua University has made in ECC chip development.

[Keywords] elliptic curve cryptography; algorithm; finite field; integrated circuits