论文部分内容阅读
标量乘和双线性对的计算以及离散对数问题是椭圆曲线密码的基础问题。标量乘和双线性对的计算速度决定了椭圆曲线密码的实现效率,离散对数问题决定了椭圆曲线密码的安全性。对标量乘和双线性对的研究有助于使椭圆曲线密码效率更高、应用更广。对椭圆曲线离散对数问题的跟踪研究可以及时评估椭圆曲线密码的安全强度,有助于降低密码系统被破译的风险。本文研究了椭圆曲线的标量乘、双线性对和离散对数等问题,主要工作如下: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(d1/2)的类数等于3当且仅当Onod=3且-d≡3 (mod 4)是一个素数。