一种基于模乘相等检测的标量乘碰撞攻击方法  

A Collision Detection Method Based Similarity Detection of Modular Multiplication on Scalar Multiplication

作　　者：韩绪仓 曹伟琼 陈华[1] 李昊远 HAN Xu-cang;CAO Wei-qiong;CHEN Hua;LI Hao-yuan(Trusted Computing and Information Assurance Laboratory,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]中国科学院软件研究所可信计算与信息保障实验室,北京100190 [2]中国科学院大学,北京100049

出　　处：《电子学报》2024年第11期3865-3876,共12页Acta Electronica Sinica

基　　金：国家自然科学基金(No.62172395)。

摘　　要：碰撞攻击是针对椭圆曲线密码的主要分析技术之一,其关键取决于对点加、倍点碰撞检测的正确率.由于随机操作数和分支语句的影响,对点加、倍点的碰撞检测几近于随机猜测,因而如何对点加、倍点进行碰撞检测成为亟需解决的问题.本文以Weierstrass曲线中基于雅可比坐标的点加、倍点为分析对象,提出了基于模乘相等的标量乘碰撞攻击方法.首先,结合点加和倍点的运算流程,从中识别出了有助于碰撞检测的模乘,并在模乘间构造了新的碰撞关系,将攻击转化为模乘碰撞检测.其次,本文发现在雅可比坐标中存在由坐标Z完全决定的模乘,基于此首次提出了模乘相等检测,将攻击转化为判断模乘两个操作数是否相同,从而避免了随机操作数的影响.最后,本文对一款硬件实现芯片进行碰撞检测实验,通过对曲线基于主成分分析进行压缩处理,将点加和倍点碰撞检测的准确率提高到了99%.本文提出的碰撞检测方法对采用了随机掩码和分支平衡的标量乘实现仍有效.Collision attack is one of the main analysis techniques for scalar multiplication,and its success rate de⁃pends on the correction rate of collision detection in operations such as point addition and multiplication.Due to the influ⁃ence of random operands and branching statements,collision detection almost approaches random guessing.How to detect collisions for point addition and point doubling effectively has become an urgent problem to be solved.To solve this prob⁃lem,we focus on point addition and doubling on Jacobian coordinates in Weierstrass curves,and propose a collision detec⁃tion method for scalar multiplication based on modular similarity detection.Firstly,according to the operation process of point addition and point doubling,the modular multiplication used in collision detection are identified,and a new collision relationship is constructed between the modular multiplications,which converts attack into modular multiplication collision detection.Secondly,we find that there are modular multiplications which are completely determined by the coordinate Z in the Jacobi coordinates.With the help of this finding,we propose modular similarity detection,and convert attack into de⁃tecting whether the two modular multiplication operations are the same,thereby avoiding the influence of random operands on the collision detection.Finally,we conduct collision detection experiments on a hardware-implemented scale multiplica⁃tion.By compressing the curve based on principal component analysis,the accuracy of collision detection for point addi⁃tion and doubling is improved to 99%.The proposed collision detection method remains effective for scalar multiplications with masking and branch balancing measures.

关 键 词：标量乘 雅可比坐标 模乘碰撞检测 模乘相等检测 

分 类 号：TN918[电子电信—通信与信息系统] TP309[电子电信—信息与通信工程]