同源密码中Montgomery模型的w-坐标研究

作者：陶铮; 胡志^*

来源：信息安全学报, 2021, 6(06): 92-101.

DOI：10.19363/J.cnki.cn10-1380/tn.2021.11.08

• 后量子密码
• 同源
• Montgomery曲线
• w-坐标

椭圆曲线群律计算是传统椭圆曲线密码(ECC)的核心运算,同时也是基于同源的后量子密码计算中的重要组成部分。Montgomery曲线上的Montgomeryladder算法是一种高效(伪)群律计算方法,且经常用于预防侧信道攻击。Farashahi和Hosseini在ACISP2017提出了Edwards曲线模型上的w-坐标可得到类似Montgomeryladder算法以进行群律计算,Kim等人在ASIACRYPT 2019将其用于优化奇数次同源计算。随后,不同曲线模型上的w-坐标陆续被提出用于优化同源计算。本质上, w-坐标是关于传统椭圆曲线有理点(x, y)-坐标的有理函数。与标准(x, y)-坐标相比, w-坐标不仅可以节约椭圆曲线群律和同源计算的计算量,还可以减少带宽。Hisil和Renes在ACM TOMS 2019提出可利用加2阶点得到更多的w-坐标。受此启发,本文提出利用Montgomery曲线上的2-同源构造出3类新的w-坐标,与x-坐标相同的是,均可应用于Montgomery ladder算法和奇数次同源计算的优化。同时, w-坐标在计算奇数次同源中,同源映射像曲线系数计算公式与像点公式类似,可利用SIMD指令集将两者并行化处理,从而得到相关计算的进一步加速。最后,由于Edwards,Huff,Jacobi等曲线模型在某些条件下可与Montgomery模型建立双有理等价,因此可由Montgomery曲线上新的w-坐标开发出其他曲线模型上更多的w-坐标,它们将有可能支持同源密码实现中更有效的算法。