椭圆曲线密码芯片安全与效率的博弈

邬可可，张平安，延霞

（深圳信息职业技术学院 计算机学院，广东 深圳 518172）

椭圆曲线密码芯片安全与效率的博弈

邬可可，张平安，延霞

（深圳信息职业技术学院 计算机学院，广东 深圳 518172）

椭圆曲线密码被广泛应用于便携式密码设备中，比如金融IC卡和网银USB Key等。虽然椭圆曲线密码具有很高的安全级别，但在密码设备的实现上则很容易受到侧信道攻击。国内外对ECC的侧信道分析技术的研究主要集中在发现新的攻击方法和新的防御方法上。本文综述了这些防御措施的安全性与计算效率，并基于椭圆曲线本身具有的丰富的代数特性，提出对未来研究方向的展望。

椭圆曲线密码；侧信道攻击；密码芯片

在密码学界，安全与效率往往是背道而驰，现有的国内外研究成果往往是靠牺牲一部分效率来达到安全的目的。针对计算资源相对丰富的大型计算机系统或互联网的安全性，通常不在意因安全性需求而牺牲一部分效率。然而，对于计算资源非常有限的椭圆曲线密码设备，研究防御侧信道攻击（Side Channel Attacks,SCA）的方法同时，又要保持椭圆曲线密码（Elliptic Curve Cryptosystems,ECC）原本的高效性，是必要且迫切的。本文归类总结了近年来国内外对ECC的侧信道分析技术，主要围绕“攻击”和“防御”这两条线索展开，分析了各类防御技术的计算效率。发现这些防御方法都是以牺牲计算效率来达到安全的目的，从而影响了ECC在计算资源非常有限的密码芯片上的实现。鉴于此，本文最后探讨了一条新的防御方法思路，而不增加其计算开销。

1 椭圆曲线密码

椭圆曲线密码（Elliptic Curve Cryptosystems,ECC）是迄今被实践证明安全有效的三类公钥密码体制之一，以高效著称，由Neal Koblitz[1]和Victor Miller[2]于1985年分别独立地提出,并在近年开始得到重视。ECC可以提供与RSA密码体制类似的功能。RSA密码的安全性是建立在整数因子分解的困难性之上，而ECC的安全性建立在更加复杂的椭圆曲线离散对数问题（ECDLP）的困难性之上。求解整数因子分解问题有亚指数时间算法，与此不同,ECDLP最好的算法具有全指数时间复杂度。这意味着为达到期望的安全程度，ECC可以使用较RSA密码更短的密钥，160位的ECC可以提供相当于1024位RSA密码的安全程度。由于密钥短而获得的优点包括加解密速度快、节省能源、节省带宽和节省存储空间等。因此，ECC尤其适用于计算资源受限的密码设备，特别是带有安全芯片的金融IC卡、网银USB Key设备等。所以，ECC在安全性和计算效率方面相对于其它公钥密码系统的优势，已经得到越来越广泛的应用，并被许多国家和国际标准组织采纳为公钥密码算法标准，其安全性问题自然得到人们的广泛关注和研究，尤其是基于计算资源受限的加密芯片中ECC密码算法引擎的计算效率和安全性的研究。

2 侧信道攻击技术

传统的密码分析理论认为，对密码设备的分析仅依赖于输入明文和输出密文的值。而在实际应用中，分析人员可以获得密码设备的算法操作过程中的功耗或电磁辐射信号。对于输入不同的明文而产生不同的功耗或电磁辐射信号，可以获取密钥的信息，这种密码分析方式称为侧信道攻击（Side Channel Attacks,SCA）。SCA是一种新的密码分析技术，最早由美国学者Paul Korcher于1996年提出[3]，它利用密码设备工作时所泄露的侧信道（Side Channel）信息（如时间、功耗或电磁信号等[4，5]）来破解密钥，从而给密码设备的安全性提出了新的考验。SCA方法大致可以分为两大类：简单侧信道分析（Simple Side Channel Analysis,SSCA）和差分侧信道分析（Differential Side Channel Analysis,DSCA）。SSCA主要是通过肉眼观察一条或若干条采集到的侧信道曲线来破解密钥，需要了解密码算法流程。如图1所示，只需采集一条经典的点乘方法，即可破解ECC密钥。DSCA需要集采数千条或更多的侧信道信号曲线，利用概率统计的方法将需要的某种侧信道信息差异放大，将无关信息过滤掉，从而找到侧信道信息与密钥数据的相关性。密码算法通常都是通过增加密钥的长度来增加其安全性，而SCA不因密钥长度越长而越难破解。SCA只与密码算法本身和集成电路的实现有关。如果密码算法及其软硬件实现未采取保护措施，则可能只需要很小的代价就可以实现破解密钥。例如功耗与电磁分析通常只需要数千美元的成本。

图1 SSCA攻击ECC点乘方法Fig.1 fig.1.SSCA attacks ECC point multiplication method

3 SCA攻击ECC的方法

由于ECC被大量地应用于智能卡等密码设备中，且ECC密钥的每个比特位都对应着ECC侧信道较长的轨迹部分，产生了密钥与侧信道信息的高度相关性，从而使SCA成为ECC最具威胁的攻击手段，受到了学术界和工业界的高度关注。国内外的解决方案通常是以牺牲ECC的计算效率来达到防御侧信道攻击的目的，从而影响了ECC在金融IC卡等计算资源非常有限的密码设备上的实现。1999年，Coron首次提出采用SSCA破解经典的ECC点乘Double-and-add方法[6]，并给出对应的防御方法（Double-and-add-always）。而另一种更强的DSCA则采用统计的方法来执行程序多次来破解密钥。Messerges等人最先将该方法应用于公钥密码系统，指出大数指数运算的传统算法是不能抵抗DSCA的[7]。1999年，Coron首次将DSCA应用在ECC上[6]，其思想和Messerges等人相类似，但针对ECC采用了其他的一些统计测试。Goubin于2003年提出了针对椭圆曲线的精细功耗攻击（Refined Power Attack,RPA）[8]，RPA利用一个零值取到一个特殊的椭圆曲线点来破解密钥，RPA能攻破Coron的防御措施。RPA后来进一步被扩展到更强的零值点攻击（Zero-value Point Attack,ZPA）[9]。Dupuy和Kunz-Jacques于2005年提出选择密文的侧信道攻击NIST椭圆曲线的点乘，包括选择密文的简单侧信道攻击和差分侧信道攻击[10]。Gebotys等人也于2005年首次提出电磁攻击（EMA）基于JAVA实现的ECC密码设备，分别采用了简单电磁攻击（SEMA）和差分电磁攻击（DEMA）[11]。Fan等人于2011年提出了合成攻击（combined attacks），把简单侧信道攻击（SSCA）和引入错误攻击（Fault attack）结合起来攻击做了简单和差分防御的ECC点乘[12]。

4 防御方法及计算效率

国内外对防御SCA攻击的ECC安全方法研究，通常做法是对ECC点乘dP运算的侧信道曲线的不平衡性，采用添加“砝码”（冗余）的方法来平衡ECC的核心操作点乘的3个级别操作（点乘算法级别、群运算级别和域运算级别），由此带来了额外的计算开销。通常的防御措施有两个过程：第一步是使得SSCA攻击不可行，第二步是使得DSCA攻击不可行。

4.1 防御SSCA攻击

对于Weierstrass形式的椭圆曲线，两种最基础的群运算（点加、点倍）是完全不同的，而且二者的计算复杂度相差也较大，通常在1.3～2.5倍之间。这给SSCA以用武之地，通常密码分析者只需采集1条侧信道信号曲线，即可破解ECC密钥。于是，十余年来，密码研究人员对防御SSCA的ECC安全方法进行了大量研究。这些方法通常归为如下3类：

点乘操作的统一化：Coron提出的ECC点乘dP运算的规则化，基于阿贝尔群运算，Joye提出了一种高规则的点乘运算的循环迭代，即冗余算法double-and-add-always方法[6,13]。在点乘运算中的每一步都进行点加和点倍运算，而无论是否需要。即通过插入额外的点加操作使得无论在比特“1”还是比特“0”的情况下，点乘dP都是由“点加-点倍”重复循环迭代完成。适用性广是该算法的突出优点，而缺点在于它引入了过多的不必要的计算，增加了大约33%计算开销。Wu等人提出的标量折半模型[14]是先通过折半密钥d来减少四分之一的点加操作次数，再通过增加点加操作来统一化点乘dP运算来防御SSCA攻击，但最终也增加了12.5%的计算开销。除了能防御SSCA，该标量折半模型最大的优点是容易并行化。因此，Wu等人对该标量折半模型做了并行化处理[15]，以适应多核的安全芯片。

点加点倍公式的同一化：Brier和Joye提出的Weierstrass形式曲线上点加和点倍的同一化公式[16]。清华大学的刘铎和戴一奇等人研究了该公式在各种坐标系统下的表现形式，并给出了Montgomery形式曲线上的同一化点运算公式[17]。Smart和Joye等人提出了使用非Weierstrass形式曲线的Hessian形式椭圆曲线来使用同一个过程（并不是同一个公式）来计算点加和点倍[18,19]，且Ghosh等人于2013年给出了这种算法的实现[20]。Liardet等人提出将一条椭圆曲线表现成两个二次型的交，其上的点加和点倍可以通过同一个公式进行计算[21]。同一化公式或同一个过程来计算点加和点倍，都需要增加额外的冗余椭圆曲线域操作，都增加了大约20～30%的计算开销。

侧信道原子块：通过插入额外的域操作来划分程序为循环执行的语句原子块，使得程序呈现相同的侧信道曲线循环模式[22,23]。同样，因增加冗余的椭圆曲线域操作，也增加了大约20～30%的计算开销。

图2清楚地阐明了上述各类防御SSCA的ECC点乘方法比经典的ECC点乘方法（二进制方法）要高出大约15～30%的计算开销。

图2 SSCA安全方法与二进制方法的计算开销比较fig.2 The computational cost comparation between SSCA secure methods and binary method

4.2 防御DSCA攻击

即使一个ECC点乘dP法能防御SSCA，它也可能不再防御更强的DSCA的攻击。目前防御DSCA的方法主要包括2种随机化技术，这些方法也都增加了大约15～30%的计算开销。

密钥的随机化：当d作为固定的密钥时，如果每次都用同样的过程计算，则攻击者可以不断选取不同的点，甚至是一些特殊的点或是“伪点”P，通过对计算点乘dP的时间和能耗进行的大量的统计，可以恢复d的一些比特甚至于全部比特。1999年，Coron提出了基于密钥的随机化技术[6]，选取一个随机数r与椭圆曲线上点E的阶#E相乘，来隐藏标量d，达到防御DSCA攻击ECC目的；另外还有一些作品[24,25,26]，是以随机参数来划分密钥比特串来防御DSCA；这些方法都是采用增加冗余的点乘运算。

点的随机化：如果在计算过程中出现了可以被窃听者得到的特殊信息（比如除法分子为0产生的意外）将使系统的安全性大幅降低甚至于丧失，因而要让计算过程中的每个对象尽可能随机。有一类做法是对于椭圆曲线点进行随机化处理。1999年，Coron[6]提出了采用增加一个秘密随机点来隐藏点乘运算，或者利用一个随机非零值来随机化处理输入点的投影坐标表达式，来达到防御DSCA目的。类似地，Okeya和Takagi提出了使用Jacobi坐标的点随机化方法[27]。Okeya和Sakura提出基于Montgomery曲线和算法的ECC实现方案[28]，在该方案中首先对Montgomery曲线上的点进行了随机化处理。Joye和Tymen于2001年提出了曲线同构和域同构的随机化技术来防御DSCA[29]，但为了求同构的逆运算而增加了近1倍的点乘运算。Taverne等人于2011年提出了基于NIST曲线ECC的随机化处理来防御DSCA[30]。Lee等人于2012年提出了通过随机化Montgomery操作来防御相关性功耗分析攻击双域ECC的处理器[31]。Mulder等人又于2013年提出了虽然这些方法在目前的DSCA攻击技术条件下，从理论上有很好的防御效果，但这些方法的安全性都来自对点乘dP计算效率的牺牲。

5 总结展望

综上所述，现有的防御简单侧信道攻击（SSCA）和差分侧信道攻击（DSCA）的安全方法都是在ECC点乘的基础上增加额外操作来达到侧信道安全的目的。这大大增加了计算开销，从而影响ECC在资源有限的密码设备上的计算效率。尽管在十余年的时间内，对ECC密码设备的侧信道攻击与防御技术这一崭新课题的研究已有了一定的研究成果，但在研究安全方法的同时保持ECC高效率的研究，却仍然不够。

相对于RSA简单的数学结构，椭圆曲线是亏格（genus）为1的代数曲线，从理论上讲有无穷多种椭圆曲线的具体表示，具有丰富的代数特性，因此可以基于椭圆曲线群和域上的代数结构理论（如同种、有理映射），建立ECC等价变换模型，来防御SSCA和DSCA而不增加ECC的计算开销，将会是未来的新热点方向。

（References）

[1]N.Koblitz,Elliptic curve cryptosystems,Mathematics of Computation,1987,48(177),pp.203-209.

[2]V.S.Miller.Use of elliptic curves in cryptography,Advances in Cryptology-CRYPTO 1985,LNCS 218,Springer-Verlag,pp.417-426.

[3]P.C.Kocher,Timing attacks on implementations of Diffie-Hellman,RSA,DSS,and other systems,International Cryptology Conference on Advances in Cryptology,1996,Santa Barbara,USA.

[4]P.C.Kocher,J.Jaffe,B.Jun,Differential power analysis,Advances in Cryptology-CRYPTO'99,LNCS 1666,Springer-Verlag,1999,pp.388-397.

[5]J.J.Quisquater,D.Samyde,Simple Electromagnetic analysis for Smart Cards:New Results,Rump session talk at Cyrpto 2000.

[6]J.S.Coron,Resistance against differential power analysis for elliptic curve cryptosystems,Cryptographic hardware and embedded systems-CHES 1999,LNCS 1717,pp.292-302.

[7]T.S.Messerges,E.A.Dabbish,and R.H.Sloan,Power analysis attacks of modular exponentiation in smartcards,Cryptographic Hardware and Embedded Systems-CHES 1999,LNCS1717,pp.144-157.

[8]L.Goubin,A refined power analysis on elliptic curve cryptosystems,Public Key Cryptography-PKC 2003,LNCS 2567,pp.199-211.

[9]T.Akishita,T.Takagi, Zero-value Point Attacks on Elliptic Curve Cryptosystem,ICS2003,Lecture Notes in Computer Science,Springer-Verlag,2003,pp.218-233.

[10]W.Dupuy,S.Kunz-Jacques,Resistance of Randomized Projective Coordinates Against Power Analysis,Cryptographic Hardware and Embedded Systems-CHES 2005,LNCS 3659,pp.1-14.

[11]C.H.Gebotys,S.Ho,and C.C.Tiu,EM Analysis of Rijndael and ECC on a Wireless Java-Based PDA,Cryptographic Hardware and Embedded Systems-CHES 2005,LNCS 3659,pp.250-264.

[12]J.Fan,B.Gierlichs,and F.Vercauteren,To Infinity and Beyond:Combined Attack on ECC Using Points of Low Order,Cryptographic Hardware and Embedded Systems -CHES 2011,LNCS 6917,pp.143-159.

[13]Marc Joye,Highly Regular Right-to-Left Algorithms for Scalar Multiplication,Cryptographic Hardware and Embedded Systems-CHES 2007,LNCS 4727,pp.135-147.

[14]K.Wu,H.Li,D.Zhu,F.Yu,“Efficient solution to secure ECC against side-channel attacks”,Chinese Journal of Electronics,Volume 20,Issue 3,2011,pp.471-475.

[15]K.Wu,H.Li,D.Zhu,“Fast and scalable parallel processing of scalar multiplication in elliptic curve cryptosystems”,Security and Communication Networks,Volume.5,Issue 6,June 2012,pp.648-657.

[16]E.Brier,M.Joye.Weierstrass elliptic curves and sidechannel attacks,Public Key Cryptography 2002,Heidelberg,Germany:Springer Berlin,2002,pp.335-345.

[17]刘铎,戴一奇,Brier-Joye点加公式的几点讨论,2003中国计算机大会论文集,北京,清华大学出版社,2003,pp.221-226.D.Liu，Y.Dai,Remarks on Brier-Joye addition formula,Proceedings of Chinese National Conference of Computer 2003,Beijing,Tsinghua University Press,2003,pp.22l～226.(in Chinese)

[18]N.P.Smart,The Hessian for of an elliptic curve,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.118-125.

[19]M.Joye,J.J.Quisquater,Hessian elliptic curves and sidechannel attacks,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.402-410.

[20]Santosh Ghosh,Amit Kumar,Amitabh Das,and Ingrid Verbauwhede,On the Implementation of Unified Arithmetic on Binary Huff Curves,Cryptographic Hardware and Embedded Systems-CHES 2013,LNCS 8086,pp.349-364.

[21]P.Y.Liardet,N.P.Smart,Preventing SPA/DPA in ECC systems using the Jacobi form,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.391-401.

[22]B.Chevallier-Mames,M.Ciet and M.Joye,Low-cost solutions for preventing simple side-channel analysis:side-channel atomicity,IEEE Trans.Computers,2004,53(6),pp.760-768.

[23]P.K.Mishra,Pipelined computation of scalar multiplication in elliptic curve cryptosystems,IEEE Transactions on Computers,2006,55(8),pp.1000-1010.

[24]S.Chari,C.S.Jutla,J.R.Rao and P.Rohatgi,Towards sound approaches to counteract power-analysis attacks,CRYPTO 1999,LNCS 1666,pp.398-412.

[25]C.Clavier,M.Joye,Universal exponentiation algorithm:A first step towards provable SPA-resistance,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.300-308.

[26]E.Trichina,A.Bellezza,Implementation of elliptic curve cryptography with built-in countermeasures against side channel attacks,Cryptographic Hardware and Embedded Systems-CHES 2002,LNCS2523,pp.98-113.

[27]K.Okeya,T.Takagi,The width-w NAF method provides small memory and fast elliptic scalar multiplications secure against side channel attacks,CT-RSA 2003,New York:Springer-Verlag,2003,pp.328-343.

[28]K.Okeya,K.Sakura,Power analysis breaks elliptic curve cryptosystems even secure against the timing attack,INDOCRYPT2000,New York:Springer-Verlag,2001,pp.178-l90.

[29]M.Joye,J.J. Quisquater,Protections against differential analysis for elliptic curve cryptography,Cryptographic Hardware and Embedded Systems-CHES 2001,LNCS 2162,pp.377-390.

[30]J.Taverne,A.Faz-Hernandez,D.F.Aranha,F.Rodriguez-Henriquez,D.Hankerson,and J.Lopez,Software Implementation of Binary Elliptic Curves:Impact of the Carry-Less Multiplier on Scalar Multiplication,Cryptographic Hardware and Embedded Systems-CHES 2011,LNCS 6917,pp.108-123.

[31]J.W.Lee,S.C.Chung,H.C.Chang,and C.Y.Lee,An Efficient Countermeasure against Correlation Power-Analysis Attacks with Randomized Montgomery Operations for DF-ECC Processor,Cryptographic Hardware and Embedded Systems-CHES 2012,LNCS 7428,pp.548-564.

The trade-off between security and efficiency in chips of Elliptic curve cryptosystems

WU Keke,ZHANG Pingan,YAN Xia
（Shenzhen Institute of Information Technology,School of Computers,Shenzhen 518172,P.R.China）

Elliptic curve cryptosystems (ECC) have been widely used in the portable cryptographic equipment,such as financial IC cards and USB Keys.Although the security level for the ECC is high,but in the implementation of cryptographic devices are vulnerable to side channel attacks (SCA).On the ECC side channel analysis technology research focuses on finding new methods of attacks and defenses.This paper analyzes and summarizes the security and the computation efficiency of these defensive measures,the rich algebraic properties based on elliptic curve itself has,put forward the prospects for future research directions.

elliptic curve cryptosystems;side channel attacks;cryptographic chips.

TN918.1

：A

1672-6332（2014）03-0018-06

【责任编辑：高潮】

2014-08-30

邬可可（1980-），男（汉），江西九江人，高级工程师，博士。主要研究方向：信息安全与密码算法设计。E-mail:wukk@sziit.com.cn