A Collision Detection Method Based Similarity Detection of Modular Multiplication on Scalar Multiplication
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.