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

HAN Xu-cang; CAO Wei-qiong; CHEN Hua; LI Hao-yuan

doi:10.12263/DZXB.20230795

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-11

- A Collision Detection Method Based Similarity Detection of Modular Multiplication on Scalar Multiplication
- ACTA ELECTRONICA SINICA Vol. 52, Issue 11, Pages: 3865-3876(2024)
- 作者机构：
  
  1.中国科学院软件研究所可信计算与信息保障实验室，北京 100190
  2.中国科学院大学，北京 100049
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62172395)
- DOI：10.12263/DZXB.20230795
  CLC： TN918;TP309
- Received：10 August 2023，
  
  Revised：2024-02-18，
  
  Published：25 November 2024
- 稿件说明：
移动端阅览
韩绪仓, 曹伟琼, 陈华, 等. 一种基于模乘相等检测的标量乘碰撞攻击方法[J]. 电子学报, 2024, 52(11): 3865-3876.

HAN Xu-cang, CAO Wei-qiong, CHEN Hua, et al. A Collision Detection Method Based Similarity Detection of Modular Multiplication on Scalar Multiplication[J]. Acta Electronica Sinica, 2024, 52(11): 3865-3876.
韩绪仓, 曹伟琼, 陈华, 等. 一种基于模乘相等检测的标量乘碰撞攻击方法[J]. 电子学报, 2024, 52(11): 3865-3876. DOI：10.12263/DZXB.20230795

HAN Xu-cang, CAO Wei-qiong, CHEN Hua, et al. A Collision Detection Method Based Similarity Detection of Modular Multiplication on Scalar Multiplication[J]. Acta Electronica Sinica, 2024, 52(11): 3865-3876. DOI：10.12263/DZXB.20230795

摘要

碰撞攻击是针对椭圆曲线密码的主要分析技术之一，其关键取决于对点加、倍点碰撞检测的正确率.由于随机操作数和分支语句的影响，对点加、倍点的碰撞检测几近于随机猜测，因而如何对点加、倍点进行碰撞检测成为亟需解决的问题.本文以Weierstrass曲线中基于雅可比坐标的点加、倍点为分析对象，提出了基于模乘相等的标量乘碰撞攻击方法.首先，结合点加和倍点的运算流程，从中识别出了有助于碰撞检测的模乘，并在模乘间构造了新的碰撞关系，将攻击转化为模乘碰撞检测.其次，本文发现在雅可比坐标中存在由坐标

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=70840820&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=70840834&type=

1.94733346

2.28600001

完全决定的模乘，基于此首次提出了模乘相等检测，将攻击转化为判断模乘两个操作数是否相同，从而避免了随机操作数的影响.最后，本文对一款硬件实现芯片进行碰撞检测实验，通过对曲线基于主成分分析进行压缩处理，将点加和倍点碰撞检测的准确率提高到了99%.本文提出的碰撞检测方法对采用了随机掩码和分支平衡的标量乘实现仍有效.

Abstract

Collision attack is one of the main analysis techniques for scalar multiplication

and its success rate depends on the correction rate of collision detection in operations such as point addition and multiplication. Due to the influence 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 problem

we focus on point addition and doubling on Jacobian coordinates in Weierstrass curves

and propose a collision detection 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

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=70840825&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=70840840&type=

1.94733346

2.28600001

in the Jacobi coordinates. With the help of this finding

we propose modular similarity detection

and convert attack into detecting 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 multiplication. By compressing the curve based on principal component analysis

the accuracy of collision detection for point addition and doubling is improved to 99%. The proposed collision detection method remains effective for scalar multiplications with masking and branch balancing measures.

关键词

Keywords

references

KOBLITZ N . Elliptic curve cryptosystems [J ] . Mathematics of Computation , 1987 , 48 ( 177 ): 203 .

Chinese Cryptography Administration . SM2 elliptic curve public key cryptographic algorithms: GM/T 0003-2012 [S ] . China , 2010 .

PAPACHRISTODOULOU L , BATINA L , MENTENS N . Recent developments in side-channel analysis on elliptic curve cryptography implementations [M ] // Hardware Security and Trust . Cham : Springer , 2017 : 49 - 76 .

FAN J F , GUO X , DE MULDER E , et al . State-of-the-art of secure ECC implementations: A survey on known side-channel attacks and countermeasures [C ] // 2010 IEEE International Symposium on Hardware-Oriented Security and Trust . Piscataway : IEEE , 2010 : 76 - 87 .

CORON J S . Resistance against differential power analysis for elliptic curve cryptosystems [C ] // Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems . New York : ACM , 1999 : 292 - 302 .

KOCHER P , JAFFE J , JUN B . Differential power analysis [M ] // Advances in Cryptology-CRYPTO 99 . Berlin : Springer , 1999 : 388 - 397 .

GOUBIN L . A refined power-analysis attack on elliptic curve cryptosystems [M ] // Public Key Cryptography — PKC 2003 . Berlin : Springer , 2002 : 199 - 211 .

AKISHITA T , TAKAGI T . Zero-value point attacks on elliptic curve cryptosystem [M ] // Lecture Notes in Computer Science . Berlin : Springer , 2003 : 218 - 233 .

DE MULDER E , HUTTER M , MARSON M E , et al . Using Bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: Extended version [J ] . Journal of Cryptographic Engineering , 2014 , 4 ( 1 ): 33 - 45 .

RYAN K . Return of the hidden number problem [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2019 ( 1 ): 146 - 168 .

JANCAR J , SEDLACEK V , SVENDA P , et al . Minerva: The curse of ECDSA nonces [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2020 ( 4 ): 281 - 308 .

MOGHIMI D , SUNAR B , EISENBARTH T , et al . TPM-Fail: TPM meets timing and lattice attacks [C ] // Proceedings of the 29th USENIX Conference on Security Symposium . New York : ACM , 2020 : 2057 - 2073 .

韩晓薇 , 乌力吉 , 王蓓蓓 , 等 . 抗简单功耗攻击的SM2原子算法 [J ] . 计算机研究与发展 , 2016 , 53 ( 8 ): 1850 - 1856 .

HAN X W , WU L J , WANG B B , et al . Atomic algorithm against simple power attack of SM2 [J ] . Journal of Computer Research and Development , 2016 , 53 ( 8 ): 1850 - 1856 . (in Chinese)

JOYE M , YEN S M . The montgomery powering ladder [M ] // Cryptographic Hardware and Embedded Systems- CHES 2002 . Berlin : Springer , 2003 : 291 - 302 .

MAMIYA H , MIYAJI A , MORIMOTO H . Efficient countermeasures against RPA, DPA,and SPA [C ] // Cryptographic Hardware and Embedded Systems - CHES 2004 . Berlin : Springer , 2004 : 343 - 356 .

BAUER A , JAULMES E , PROUFF E , et al . Horizontal collision correlation attack on elliptic curves [J ] . Cryptography and Communications , 2015 , 7 ( 1 ): 91 - 119 .

HANLEY N , KIM H , TUNSTALL M . Exploiting collisions in addition chain-based exponentiation algorithms using a single trace [C ] // Topics in Cryptology-CT-RSA 2015 . Cham : Springer , 2015 : 431 - 448 .

JIN S , LEE S , CHO S M , et al . Novel key recovery attack on secure ECDSA implementation by exploiting collisions between unknown entries [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2021 ( 4 ): 1 - 26 .

NASCIMENTO E , CHMIELEWSKI L . Applying horizontal clustering side-channel attacks on embedded ECC implementations [C ] // Smart Card Research and Advanced Applications - CARDIS 2017 . Cham : Springer , 2018 : 213 - 231 .

JIN S , CHO S M , KIM H , et al . Enhanced side-channel analysis on ECDSA employing fixed-base comb method [J ] . IEEE Transactions on Computers , 2022 , 71 ( 9 ): 2341 - 2350 .

ABARZÚA R , VALENCIA C , LÓPEZ J . Survey on performance and security problems of countermeasures for passive side-channel attacks on ECC [J ] . Journal of Cryptographic Engineering , 2021 , 11 ( 1 ): 71 - 102 .

MURDICA C , GUILLEY S , DANGER J L , et al . Same values power analysis using special points on elliptic curves [C ] // International Workshop on Constructive Side-Channel Analysis and Secure Design . Berlin : Springer , 2012 : 183 - 198 .

HEYSZL J , IBING A , MANGARD S , et al . Clustering algorithms for non-profiled single-execution attacks on exponentiations [C ] // International Conference on Smart Card Research and Advanced Applications . Cham : Springer , 2014 : 79 - 93 .

PERIN G , CHMIELEWSKI L . A semi-parametric approach for side-channel attacks on protected RSA implementations [C ] // International Conference on Smart Card Research and Advanced Applications . Cham : Springer , 2016 : 34 - 53 .

ZAID G , BOSSUET L , HABRARD A , et al . Efficiency through diversity in ensemble models applied to side-channel attacks: A case study on public-key algorithms [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2021 ( 3 ): 60 - 96 .

SAITO K , ITO A , UENO R , et al . One truth prevails: A deep-learning based single-trace power analysis on RSA-CRT with windowed exponentiation [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2022 ( 4 ): 490 - 526 .

HANKERSON D R , VANSTONE S A , MENEZES A J . Guide to Elliptic Curve Cryptography [M ] . New York : Springer-Verlag , 2004 : 75 - 109 .

PERIN G , CHMIELEWSKI L , BATINA L , et al . Keep it unsupervised: Horizontal attacks meet deep learning [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2021 ( 1 ): 343 - 372 .

SCHINDLER W , WIEMERS A . Power attacks in the presence of exponent blinding [J ] . Journal of Cryptographic Engineering , 2014 , 4 ( 4 ): 213 - 236 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

GLV/GLS Scalar Multiplication on Jacobi Quartic Curves

A New Method of Scalar Multiplication of Elliptic Curve over OEF

Related Author

WENG Jiang

JI Wei-feng

WU Xuan

LI Ying-qi

ZHANG Lin-feng

MENG Hao

LIU Duo

DAI Yi-qi

Related Institution

School of Network and Information Security, Xidian University

Information and Navigation College, Air Force Engineering University

Unit 10, Courtyard 14, Fuxing Road

Department of Computer Science and Technology, Tsinghua University

⁰