An Attack Method Against the Modular Reduction Within a RSA-CRT Implementation Based on Template Attack

MA Xiang-liang; WU Li-ji; WANG Hong; ZHANG Xiang-min; HUANG Ke-zhen; LIU Yu-ling

doi:10.12263/DZXB.20220175

您当前的位置：

首页 >

文章列表页 >

An Attack Method Against the Modular Reduction Within a RSA-CRT Implementation Based on Template Attack

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

- An Attack Method Against the Modular Reduction Within a RSA-CRT Implementation Based on Template Attack
- ACTA ELECTRONICA SINICA Vol. 52, Issue 3, Pages: 689-695(2024)
- 作者机构：
  
  1.清华大学集成电路学院，北京 100084
  2.清华大学北京信息科学与技术国家研究中心，北京 100084
  3.北京邮电大学集成电路学院，北京 100876
  4.国家信息技术安全研究中心，北京 100084
  5.中国科学院软件研究所可信计算与信息保障实验室，北京 100190
  6.中国科学院信息工程研究所，北京 100093
  7.中国科学院大学网络安全学院，北京 101408
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20220175
  CLC： TP309.1
- Received：15 February 2022，
  
  Revised：2022-04-25，
  
  Published：25 March 2024
- 稿件说明：
移动端阅览
马向亮,乌力吉,王宏,等.一种基于模板的RSA-CRT模约减攻击方法[J].电子学报,2024,52(03):689-695.

MA Xiang-liang, WU Li-ji, WANG Hong, et al.An Attack Method Against the Modular Reduction Within a RSA-CRT Implementation Based on Template Attack[J].Acta Electronica Sinica, 2024, 52(03): 689-695.
马向亮,乌力吉,王宏,等.一种基于模板的RSA-CRT模约减攻击方法[J].电子学报,2024,52(03):689-695. DOI：10.12263/DZXB.20220175

MA Xiang-liang, WU Li-ji, WANG Hong, et al.An Attack Method Against the Modular Reduction Within a RSA-CRT Implementation Based on Template Attack[J].Acta Electronica Sinica, 2024, 52(03): 689-695. DOI：10.12263/DZXB.20220175

摘要

目前针对RSA-CRT的建模类攻击研究较少，本文以模约减操作为研究对象，提出了一种针对RSA-CRT实现的模板攻击方法.该方法的核心是解决了如何由模约减后中间值的汉明重量恢复RSA-CRT私钥的难题.该方法的特点是基于模约减后中间值的汉明重量模型建模，通过采集选择密文模约减的能量迹进行模板匹配获取模约减后中间值的汉明重量，由汉明重量变化值恢复中间值，进一步恢复RSA-CRT算法的私钥.另外，该方法的优点在于理想情况下，基于中间值汉明重量模型建立的模板之间可以共用，且对中间值以多少位大小建模没有限制，可以选择字节大小，64位大小，甚至私钥

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

2.87866688

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

1.94733346

相同大小，实际环境中可根据泄露信息情况进行选取.最后，本文选择对中间值的最低字节进行建模，验证了该方法的可行性，并给出了防护建议.

Abstract

At present

there are few researches on profile attacks against RSA-CRT implementation. This paper takes modular reduction operation as the research object

and a template attack method against RSA-CRT implementation is proposed. The core of this method is to solve the difficulty to recover the RSA-CRT private key from the Hamming weight of the intermediate value of ciphertext modular reduction. The characteristic of this method is to build a model based on the Hamming weight of the intermediate value derived from modular reduction. The Hamming weight can be obta

ined by collecting the power traces of chosen ciphertext modular reduction for template matching

and the intermediate value is recovered from the Hamming weight variation

the private key of the RSA-CRT algorithm can be further inferred based on the intermediate value. In addition

the advantage of this method is that ideally

templates based on the intermediate Hamming weight model can be shared

and there is no limit on the number of bits of the intermediate value for modelling

which can be in byte size

64 bit size

or even the bit size of

. In the actual environment

it can be selected according to the leaked information. Finally

in this paper

the lowest byte of the intermediate value is selected to model to verify the feasibility of this method

and the defense suggestions are also provided.

关键词

Keywords

references

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

MA X L , LI B , WANG H , et al . Non-profiled deep-learning-based power analysis of the SM4 and DES algorithms [J ] . Chinese Journal of Electronics , 2021 , 30 ( 3 ): 500 - 507 .

CHARI S , RAO J R , ROHATGI P . Template attacks [C ] // Cryptographic Hardware and Embedded Systems - CHES 2002 . Berlin : Springer Berlin Heidelberg , 2003 : 13 - 28 .

MANGARD S , OSWALD E , POPP T . Power Analysis Attacks: Revealing the Secrets of Smart Cards [M ] . Berlin : Springer Science & Business Media , 2008 .

BRIER E , CLAVIER C , OLIVIER F . Correlation power analysis with a leakage model [M ] // Lecture Notes in Computer Science . Berlin, Heidelberg : Springer Berlin Heidelberg , 2004 : 16 - 29 .

马向亮 , 王宏 , 李冰 , 等 . 基于能量分析技术的芯片后门指令分析方法 [J ] . 电子学报 , 2019 , 47 ( 3 ): 686 - 691 .

MA X L , WANG H , LI B , et al . A power analysis method against backdoor instruction in chips [J ] . Acta Electronica Sinica , 2019 , 47 ( 3 ): 686 - 691 . (in Chinese)

LE T H , CLÉDIÈRE J , CANOVAS C , et al . A proposition for correlation power analysis enhancement [C ] // Lecture Notes in Computer Science . Berlin : Springer Berlin Heidelberg , 2006 : 174 - 186 .

RIVEST R L , SHAMIR A , ADLEMAN L . A method for obtaining digital signatures and public-key cryptosystems [J ] . Communications of the ACM , 1978 , 21 ( 2 ): 120 - 126 .

MESSERGES T S , DABBISH E A , SLOAN R H . Power analysis attacks of modular exponentiation in smartcards [C ] // Cryptographic Hardware and Embedded Systems . Berlin : Springer Berlin Heidelberg , 1999 : 144 - 157 .

NOVAK R . SPA-based adaptive chosen-ciphertext attack on RSA implementation [C ] // Public Key Cryptography . Berlin : Springer Berlin Heidelberg , 2002 : 252 - 262 .

YEN S M , LIEN W C , MOON S , et al . Power analysis by exploiting chosen message and internal collisions - vulnerability of checking mechanism for RSA-decryption [C ] // Progress in Cryptology - Mycrypt 2005 . Berlin : Springer Berlin Heidelberg , 2005 : 183 - 195 .

Witteman M . A DPA attack on RSA in CRT mode [EB/OL ] . ( 2009-04-03 )[ 2021-08-10 ] . https://www. riscure. com/archive https://www.riscure.com/archive .

WITTEMAN M F , VAN WOUDENBERG J G J , MENARINI F . Defeating RSA multiply-always and message blinding countermeasures [C ] // Topics in Cryptology - CT-RSA 2011 . Berlin : Springer Berlin Heidelberg , 2011 : 77 - 88 .

DON C . Small solutions to polynomial equations, and low exponent RSA vulnerabilities [J ] . Journal of Cryptology , 1997 , 10 ( 4 ): 233 - 260 .

HOWGRAVE-GRAHAM N . Finding small roots of univariate modular equations revisited [C ] // Crytography and Coding . Berlin : Springer Berlin Heidelberg , 1997 : 131 - 142 .

BONEH D , DURFEE G , FRANKEL Y . An attack on rsa given a small fraction of the private key bits [C ] // Lecture Notes in Computer Science . Berlin : Springer Berlin Heidelberg , 1998 : 25 - 34 .

MAY A . New RSA Vulnerabilities Using Lattice Reduction Methods [D ] . Paderborn : University of Paderborn , 2003 .

CORON J S . Finding small roots of bivariate integer polynomial equations revisited [C ] // Advances in Cryptology - EUROCRYPT 2004 . Berlin : Springer Berlin Heidelberg , 2004 : 492 - 505 .

MILLER S D , NARAYANAN B , VENKATESAN R . Coppersmith's lattices and “focus groups”: An attack on small-exponent RSA [J ] . Journal of Number Theory , 2021 , 222 : 376 - 392 .

XU S , LU X J , ZHANG K Y , et al . Similar operation template attack on RSA-CRT as a case study [J ] . Science China Information Sciences , 2018 , 61 ( 3 ): 1 - 17 .

VUILLAUME C , ENDO T , WOODERSON P . RSA key generation: New attacks [C ] // Constructive Side-Channel Analysis and Secure Design . Berlin : Springer Berlin Heidelberg , 2012 : 105 - 119 .

DE LA FE S , PARK H B , SIM B Y , et al . Profiling attack against RSA key generation based on a euclidean algorithm [J ] . Information , 2021 , 12 ( 11 ): 462 .

DEN BOER B , LEMKE K , WICKE G . A DPA attack against the modular reduction within a CRT implementation of RSA [C ] // Cryptographic Hardware and Embedded Systems - CHES 2002 . Berlin : Springer Berlin Heidelberg , 2003 : 228 - 243 .

KAEDI S , DOOSTARI M A , GHAZNAVI-GHOUSHCHI M B , et al . A new side-channel attack on reduction of RSA-CRT Montgomery method based [J ] . Journal of Circuits, Systems and Computers , 2021 , 30 ( 3 ): 2150038 .

FEIX B , THIEBEAULD H , TORDELLA L . Recovering CRT-RSA secret keys from message reduced values with side-channel analysis [C ] // Progress in Cryptology—INDOCRYPT 2014 . Cham : Springer International Publishing , 2014 : 53 - 67 .

KAEDI S , DOOSTARI M , GHAZNAVI-GHOUSHCHI M B . NEMR: A nonequidistant DPA attack-proof of modular reduction in a CRT implementation of RSA [J ] . Journal of Circuits, Systems and Computers , 2018 , 27 ( 12 ): 1850191 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Linear Discriminant Analysis-Based Template Attack for Masked Im‍ple‍mentation of Modular Exponentiation

Chosen Ciphertext Combined Attack Based on Round-Reduced Fault Against SM2 Decryption Algorithm

A Comprehensive Protection Implementation of SM4 Algorithm Based on Threshold and Infection Technology

Related Author

LIU Yu-ling

MA Xiang-liang

WU Li-ji

ZHANG Xiang-min

CHEN Hua

HAN Xu-cang

CHEN Bo-tao

CAO Wei-qiong

Related Institution

School of Cyber Security， University of Chinese Academy of Sciences

School of Integrated Circuits， Tsinghua University， Beijing National Research Center for Information Science and Technology

University of Chinese Academy of Sciences

CEC Huada Electronic Design Co.， Ltd.

Electric Power Research Institute, China Southern Power Grid

⁰