【作者】 顾海华；

【导师】 谷大武；

【作者基本信息】 上海交通大学 ， 计算机科学与技术， 2010， 博士

【摘要】 标量乘和双线性对的计算以及离散对数问题是椭圆曲线密码的基础问题。标量乘和双线性对的计算速度决定了椭圆曲线密码的实现效率,离散对数问题决定了椭圆曲线密码的安全性。对标量乘和双线性对的研究有助于使椭圆曲线密码效率更高、应用更广。对椭圆曲线离散对数问题的跟踪研究可以及时评估椭圆曲线密码的安全强度,有助于降低密码系统被破译的风险。本文研究了椭圆曲线的标量乘、双线性对和离散对数等问题,主要工作如下:1.二元域上椭圆曲线可以用仿射坐标、标准射影坐标、Jacobian射影坐标或L′opez-Dahab射影坐标表示。其中L′opez-Dahab射影坐标下的点加和倍点运算具有最快的速度,其次是Jacobian射影坐标。我们在L′opez-Dahab射影坐标下推导出了3P的一个快速计算公式。于是用双基链计算标量乘时,L′opez-Dahab射影坐标比Jacobian射影坐标快12%左右。2.在2007年亚洲密码会议上,Avanzi等人针对Koblitz曲线提出了用复数双基链计算标量乘。但是该方法把标量表示成复数双基过程中使用了大量的复数除法。我们利用同构的方法减少了复数除法,从而加快了标量的有效表示算法。3.在椭圆曲线签名方案中,对签名的验证需要计算多标量乘。在2009年的欧洲密码会议上,Doche等人提出了用双基链来计算多标量乘的方法。我们给出了计算多标量乘的多基链方法,理论分析表明:标量的有效表示长度降低了大约10%,从而提高了多标量乘的计算速度。4.双线性对在密码学中有着广泛应用:基于身份的加密、三方Di?e Hellman协议等。实现这些方案的关键是快速计算双线性对。Miller首先给出了在Weierstrass曲线上计算双线性对的方法。2009年,Ar`ene等人给出了计算Edwards曲线上Tate双线性对的方法。但是目前绝大部分标准中的椭圆曲线都不能映射到Edwards曲线。而Smart指出IEEE,SECG标准中的部分椭圆曲线可以映射到Hessian曲线上。为此我们首先提出了在Hessian曲线上计算Tate双线性对的算法。分析表明:除了a4 = 0,a6 = b2的特殊Weierstrass曲线外,我们提出的算法在计算Tate双线性对的所有已知算法中是最快的。5.针对二元域上的椭圆曲线,GHS方法把椭圆曲线离散对数问题归约为超椭圆曲线离散对数问题,而超椭圆曲线离散对数问题是可以在亚指数时间内解决。推广的GHS具有更强的攻击能力,它的思想是寻找一条新的同种曲线,使得它在GHS攻击下是脆弱的。针对ANSI X9.62标准中定义在有限域GF（2N）上的椭圆曲线,我们给出了另外一个寻找脆弱同种曲线的方法。6.在推广的GHS攻击中需要计算同种映射。但是对于一般椭圆曲线,目前计算同种映射的时间复杂度是指数的。微软公司的研究员针对素数域上的椭圆曲线提出了一个多项式时间的算法来计算同种映射,只是该算法要求椭圆曲线的自同态环所在虚二次域的类数较小。由此可见,虚二次域的类数也是椭圆曲线密码中的一个重要问题。我们在推广的Riemann假设下,证明了Cohen-Sonn猜想:虚二次域Q(d^1/2)的类数等于3当且仅当Onod=3且-d≡3 （mod 4）是一个素数。更多还原

【Abstract】 Scalar multiplication, pairing computation and discrete logarithm problemare fundamental problems in elliptic curve cryptography. Scalar multiplicationand pairing computation are key to the efficiency of elliptic curve cryptosystemswhile discrete logarithm problem is key to the security of elliptic curve cryptosystems.Researches on scalar multiplication and pairing computation makecryptosystems more efficient and wider utilization. Track down investigations ondiscrete logarithm problem can estimate the security of cryptosystems in timewhich reduces the risk of being broken. In this thesis, we consider such problemsas scalar multiplication, pairing computation and discrete logarithm problem.1. Elliptic curves over binary fields can be represented by affine coordinates,standard projective coordinates, Jacobian projective coordinates and Lop′ez-Dahab projective coordinates. Point addition and doubling are fastest inLop′ez-Dahab projective coordinates, and then in Jacobian projective coordinates.We propose efficient formulas to compute 3P in Lop′ez-Dahabprojective coordinates. This leads scalar multiplication using double basechain in Lop′ez-Dahab projective coordinates to be about 12% faster thanin Jacobian projective coordinates.2. In Asiacrypt’07, Avanzi et.al. proposed complex double base chain tocompute scalar multiplication for Koblitz curves. However, their scalarrecoding algorithm needs a lot of divisions in complex field. We reduce thedivisions via isomorphism to speed up the scalar recoding algorithm.3. In elliptic curve signature schemes, verifers have to compute multi-scalarmultiplication. Doche et.al. presented a method of using double base chainto compute multi-scalar multiplication in Eurocrypt’09. We give a wayto compute multi-scalar multiplication by multi-base chain. Theoreticalanalysis shows that the length of scalar recoding can be reduced about10% which speeds up the multi-scalar multiplication. 4. Pairings have many applications in a lot of cryptographic protocols suchas identity-based encryption, the tripartite Diffie Hellman protocols. Forimplementing such protocols, it is essential to have an efficient algorithmof pairing computation. Miller proposed the first algorithm for computingpairings on Weierstrass curves. In 2009, Ar`ene et.al. showed how tocompute the Tate pairing on Edwards curves. But elliptic curves in moststandards can’t be mapped to Edwards curves at present. However, Smartpointed out that some elliptic curves from IEEE, SECG standards can betransformed into Hessian curves. So we develop explicit formulas for computingTate pairings on Hessian curves originally. Analysis shows that ouralgorithm is fastest among all known algorithms for Tate pairing computationexcept for special Weierstrass curves with a4 = 0,a6 = b2.5. For elliptic curves over binary fields, the GHS method reduces the ellipticcurve discrete logarithm problem to a discrete logarithm problem forhyperelliptic curves and the hyperelliptic curve discrete logarithm problemcan be solved within subexponential time. The extended GHS attack hasstronger power, and the idea is to find an isogenous curve which is vulnerableunder the GHS attack. For elliptic curves over finite fields GF(2N),we give an alternative algorithm to find such isogenous curves.6. It is necessary to compute isogeny in the extended GHS attack. However,for general elliptic curves, the complexity of computing isogeny is exponential.Researcheres from Microsoft proposed a polynomial time algorithmto compute isogeny for elliptic curves over prime fields, only if the imaginequadratic field containing the endomorphism ring has small class number.Thus, the class number problem for imagine quadratic fields is an importantissue in cryptography. We prove the Sohen-Sonn conjecture assuming theextended Riemann hypothesis: the class number of an imagine quadraticfield is 3 if and only if Onod=3 and ?d≡3 (mod 4) is prime.更多还原