计算Montgomery形式椭圆曲线上标量乘kPmQlR的新算法

计算Montgomery形式椭圆曲线上标量乘kP+mQ+lR的新算法刘铎 戴一奇摘要：基于Montgomery形式椭圆曲线上的密码体制具有速度快、安全性高、形式简单和适于并行的优点，现在是椭圆曲线密

1 MontgomerykP+mQ+lR 计算形式椭圆曲线上标量乘的新算法 23 刘铎戴一奇 摘要： Montgomery 基于形式椭圆曲线上的密码体制具有速度快、安全性高、形式简 单和适于并行的优点，现在是椭圆曲线密码学研究的一个热点。但是对于在 MontgomerykP 形式的椭圆曲线上的标量乘的算法还长期停留在只能计算的阶段。 [9] ToruAkishita kP+lQ 给出了计算的方法，主要是为了解决协议中的问题。在本文 kP+mQ+lR 中将这个方法扩展到计算的方法，这样不仅仅在一些协议中可以使用，而 [13] SMEMontgomery 且也可以将基于预计算的算法等应用到形式的椭圆曲线上，加快 标量乘的速度，同时达到抵抗计时攻击的效果。在文章的最后对于新的算法与传统的 算法，在时间复杂度上做了一些比较。 关键词： Montgomery 椭圆曲线；密码学；形式椭圆曲线；标量乘 TP391A 中图分类号：文献标识码： 1． 简介 [1][2] NealKoblitzVictorMiller 椭圆曲线密码体制首先由和两人独立地提出，近来得到越 Weierstrass 来越广泛地关注，进行了很多算法和实际实现方面的研究。椭圆曲线的标准形式 3Montgomery 是（对于特征大于的域），而则引入了另一种形式的椭圆 [3] Weierstrass 曲线，并提出了一种和曲线上标量乘完全不同的 计算方法，与原有的方法相比有如下的优点：它不需要预计算（原始的算法），所以可以在 存储空间有限的条件下实现（例如智能卡等）；利于并行计算；它的运算时间可以认为是固 Hamming 定的，而不依赖于的重量等。而且在研究椭圆曲线上的标量乘的算法的同时，很 [6,12,17][3][4] Montgomery 多研究者还独立地发现算法可以有效地抵抗计时攻击。这更使得它成为 现在椭圆曲线密码学中最热门的课题之一。 LopezDahabMontgomery2- 与将算法扩展到了特征为的域上，并且提出了一个有恢复 [6] KatsuyukiOkeyaKouichiSakurai2 坐标过程的标量乘的算法。和给出了在特征不是的有限 [8] MontgomeryyKatsuyukiOkeyaHiroyuki 域上的形式椭圆曲线上的恢复坐标的方法。、 KurumataniKouichiSakuraiMontgomery-Weierstrass- 和对于形式椭圆曲线和形式椭圆曲线之 [5] Montgomery- 间的相互转化进行了研究。他们给出了具有形式的椭圆曲线的充要条件，还 4Montgomery 提出了一个选取阶恰好是光滑的曲线的算法。 ——ECDSA——KatsuyukiOkeyaKouichi 一些协议如的验证部分需要计算。和 SakuraiMontgomeryy 建议先用普通的方法计算，再使用的方法计算，并且恢复的 1 90304014 本研究得到国家自然科学基金资助项目资助。 2 100084Email: bat01@mails.tsinghua.edu.cn 清华大学计算机科学与技术系，北京，。 3 100084Email: dyq@theory.cs.tsinghua.edu.cn 清华大学计算机科学与技术系，北京，。