一种高效安全的椭圆曲线标量乘算法 .pdfVIP

一种高效安全的椭圆曲线标量乘算法

陈熹;祝跃飞

【摘要】MostsecureEllipticCurveScalarMultiplication(ECSM)algorithms

basedonPointVerification(PV)andCoherencyCheck(CC)havelow

efficiency.Aimingattheproblem,thispaperproposesanewsecure

algorithmbasedonternaryrepresentationandprovesitscorrectness.The

analysisaboutitsefficiencyintheaffinecoordinatesandJacobian

coordinatesispresented,whoseresultshowsthatthecomputational

efficiencyisimprovedwhileguaranteeingthesecurity.%基于点验证和基于一

致性检测的椭圆曲线标量乘安全算法一般运算效率低下.为此,通过对错误探测方法

进行改进,提出一种基于三进制的椭圆曲线标量乘算法,给出算法的正确性证明,并在

仿射坐标和Jacobian坐标下对其进行分析,结果表明,在保证安全性的前提下,该算

法的效率有较大提高.

【期刊名称】《计算机工程》

【年(卷),期】2012(038)018

【总页数】4页(P103-106)

【关键词】点验证;一致性检测;椭圆曲线标量乘;错误分析攻击;三进制表示;仿射坐

标;Jacobian坐标

【作者】陈熹;祝跃飞

【作者单位】解放军信息工程大学信息工程学院,郑州450002;解放军信息工程大

学信息工程学院,郑州450002

【正文语种】中文

【中图分类】TP301.6

1概述

椭圆曲线密码体制(EllipticCurveCryptosystem,ECC)是由文献[1-2]分别提出的，

而ECC独特的优势使其成为公钥密码学研究的热点之一。ECC的安全性基于求解

椭圆曲线离散对数问题(EllipticCurveDiscreteLogarithmProblem,ECDLP)的

困难性，已有的研究表明：椭圆曲线离散对数问题的困难性高于大数分解和有限域

上的离散对数问题，且椭圆曲线所基于的域的运算位数远小于传统离散对数的运算

位数，很容易在软件和硬件上实现。与其他的公钥密码体制相比，ECC具有安全

性更高、计算量小、处理速度快、存储空间占用少、带宽要求低等优点。因此，

ECC特别适用于计算能力和集成电路空间受限、带宽受限、实现速度要求较高的

情况，比如AdHoc、无线传感器网络。

椭圆曲线标量乘法(EllipticCurveScalarMultiplication,ECSM)是椭圆曲线密码

体制中最核心的操作，如何快速计算ECSM也是目前的一个研究热点[3-4]。但是

随着技术的发展，快速的椭圆曲线标量乘算法越来越容易受到各种攻击，如侧信道

攻击(SideChannelAttack,SCA)、错误分析攻击(FaultAnalysisAttack,FAA)。

随着各种攻击方法的提出，相应的对抗措施也渐渐发展起来，其中，点验证(Point

Verification,PV)和一致性检测(CoherencyCheck,CC)方法能够对抗多种类型的

错误分析攻击。然而，在保证算法安全性的前提下，所采用的算法变得不再高效，

所以，如何在保证安全的同时提高算法的效率是一个值得研究的问题。本文在点验

证和一致性检测方法的基础上，提出了一种高效的基于三进制的安全算法。

2相关知识

2.1有限域上的椭圆曲线

定义在域K上的Weierstrass方程：

所确定的平面曲线称为域K上的椭圆曲线，其中，a1,a2,a3,a4,a6∈K，K为有

限域。椭圆曲线E上的点连同其上所定义的一个特殊的无穷远点O对椭圆曲线上

点的加法构成一个交换群。

当域K的特征p大于3时，方程可以简化为：

设P、Q是椭圆曲线E上的2点，k是整数，且满足Q=kP。已知P、Q求k的问

题称为椭圆曲线离散对数问题，kP就是椭圆曲线上的标量乘法。

标量乘法的实现可以采用简单的循环迭代方法，但是这样做复杂度比较高，一种比