一种基于模板的RSA-CRT模约减攻击方法

马向亮; 乌力吉; 王宏; 张向民; 黄克振; 刘玉岭

doi:10.12263/DZXB.20220175

您当前的位置：

首页 >

文章列表页 >

一种基于模板的RSA-CRT模约减攻击方法

学术论文 | 更新时间：2025-12-11

- 一种基于模板的RSA-CRT模约减攻击方法
- An Attack Method Against the Modular Reduction Within a RSA-CRT Implementation Based on Template Attack
- 电子学报 2024年52卷第3期页码：689-695
- 作者机构：
  
  1.清华大学集成电路学院，北京 100084
  2.清华大学北京信息科学与技术国家研究中心，北京 100084
  3.北京邮电大学集成电路学院，北京 100876
  4.国家信息技术安全研究中心，北京 100084
  5.中国科学院软件研究所可信计算与信息保障实验室，北京 100190
  6.中国科学院信息工程研究所，北京 100093
  7.中国科学院大学网络安全学院，北京 101408
- 作者简介：
  
  [ "马向亮男， 1986年3月生于山西省临汾市，博士，博士后，主要研究方向为信息安全、侧信道和故障攻击与防御. E-mail: maxiangliang@tsinghua.edu.cn" ]
  [ "乌力吉男， 1965年9月生于内蒙古呼和浩特市，工学博士，清华大学集成电路学院博士生导师，主要研究方向为信息安全芯片设计与安全性研究、汽车电子芯片设计与可靠性研究.中国电子学会会员编号：E190035434M.E-mail: lijiwu@tsinghua.edu.cn" ]
  [ "王宏男， 1972年9月生于江西省玉山县，博士，高级工程师，主要研究方向为密码学、信息安全、网络安全测评.中国电子学会会员编号：E190012458S.E-mail: wh@nitsc.cn" ]
  [ "张向民男， 1966年2月生于北京市，硕士，清华大学集成电路学院助理研究员，主要研究方向为信息安全、汽车电子.E-mail: zhxm@tsinghua.edu.cn" ]
  [ "黄克振男，1988年9月生于山东省德州市，博士，正高级工程师，主要研究方向为信息安全、网络安全态势感知、网络安全威胁行为智能化认知. E-mail: kezhen@iscas.ac.cn" ]
  [ "刘玉岭男，1982年1月生于山东省济南市，博士，正高级工程师，主要研究方向为网络安全测评技术. E-mail: liuyuling@iie.ac.cn" ]
- 基金信息：
- DOI：10.12263/DZXB.20220175
  中图分类号： TP309.1
- 收稿：2022-02-15，
  
  修回：2022-04-25，
  
  纸质出版：2024-03-25
- 稿件说明：
移动端阅览
马向亮,乌力吉,王宏,等.一种基于模板的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 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于线性判别分析的模幂掩码模板攻击方法

基于减轮故障的SM2解密算法选择密文组合攻击

一种基于门限与感染技术的SM4算法综合防护实现