论文部分内容阅读
作为一类特殊的代数曲线,超椭圆曲线是椭圆曲线的一种推广。与其他公钥密码体制相比,超椭圆曲线密码体制具有更短的操作长度,特别适合在受限系统中使用。由于结构复杂,所以超椭圆曲线密码体制实现速度较慢,目前对它的研究仍处于理论阶段。如何提高超椭圆曲线除子标量乘的计算速度是提高该密码体制实现速度,并使它早日走向实用的一个亟待解决的问题,本文对超椭圆曲线除子标量乘的快速算法作了深入的研究,主要工作如下:1.讨论了使用双基链计算超椭圆曲线除子标量乘的方法,给出了亏格为2的超椭圆曲线上2D1+D2,3D1,3D1+D2,4D1,4D1+D2的除子计算公式、他们的变体公式以及他们与变体公式之间联系的临界点,分析了公式的运算量。将2D1+D2公式用于非邻接形(NAF)和标准倍点加(double-and-add)标量乘算法中,比使用Lange的公式在平均单比特运算量上分别减少6.8%和9.2%,比使用Fan的改进公式则分别减少2.7%和2%。2.通过分析所给出的除子运算公式的运算量,结合大素数域上常见的实现环境,提出了适合我们应用的高效的超椭圆曲线双基链标量乘算法,并对该算法进行了复杂度分析。经过测算,我们的双基链标量乘算法与标准倍点加和NAF标量乘算法相比,效率分别提高25%和15.8%。该除子标量乘算法能够抵抗某些边信道攻击而且不需要任何预计算。3.给出了亏格为2的超椭圆曲线除子5D1公式、它的变体公式以及它与变体公式之间联系的临界点,并分析了它们的运算量。给出了椭圆曲线有理点的5倍点公式以及多基链标量乘算法。4.给出了快速有效的亏格为3的超椭圆曲线退化除子运算的运算公式。将它用于总是倍点加(double-and-add-always)标量乘算法中,一次和二次退化除子标量乘分别比标准除子标量乘快25.4%和13%。该算法能够抗击简单能量分析攻击(SPA)和时间攻击(TA),主要用于使用固定基点进行标量乘的运行环境中,如ElGamal型加密算法、Diffie-Hellman协议的发送方以及数字签名算法HECDSA中。由于退化除子特殊的结构,一次和二次除子的表示长度分别仅为标准除子的三分之一和三分之二。5.给出了求超椭圆曲线除子加法和倍点并行算法的一个易于实现的一般性方法,使用这个方法得到的并行算法的特点是:①需要运行的轮数最少;②在满足①的情况下,所需的并行运算乘法处理器的个数最少;③在满足①和②的情况下,一次需要存储的变量的最大个数最少。利用这个方法给出了亏格为3的超椭圆曲线除子加法和倍点运算的并行算法,分析结果表明,加法运算使用9个乘法处理器至少需要进行15轮运算(其中包含一个求逆轮),倍点运算使用7个乘法处理器也至少需要进行15轮运算(其中包含一个求逆轮)。6.给出了一个有效的同时求多个域元素逆的求逆算法。将其应用到Mishra的亏格为2的超椭圆曲线除子标量乘算法中,得到了一个高效的抗简单能量分析攻击的标量乘算法。该算法比总是倍点加标量乘算法快24%~26%,比Mishra的两种标量乘算法分别快33%~35%和6%~7%。我们给出的这个求逆算法可以在任何需要求多个元素逆的应用环境中使用。