Article

Cryptanalysis of a provably secure CRT-RSA algorithm

Author:

David WagnerAuthors Info & Claims

CCS '04: Proceedings of the 11th ACM conference on Computer and communications security

Pages 92 - 97

https://doi.org/10.1145/1030083.1030097

Published: 25 October 2004 Publication History

Get Access

Abstract

We study a countermeasure proposed to protect Chinese remainder theorem (CRT) computations for RSA against fault attacks. The scheme was claimed to be provably secure. However, we demonstrate that the proposal is in fact insecure: it can be broken with a simple and practical fault attack. We conclude that the proposed countermeasure is not safe for use in its present form.

References

[1]

R. Anderson, M. Kuhn, "Tamper resistance---a cautionary note," 2nd USENIX Workshop on Electronic Commerce, pp.1--11, 1996.

Digital Library

Google Scholar

[2]

R. Anderson, M. Kuhn, "Low cost attacks on tamper resistant devices," 1997 Security Protocols Workshop.

Digital Library

Google Scholar

[3]

H. Bar-El, H. Choukri, D. Naccache, M. Tunstall, C. Whelan, "The sorcerer's apprentice guide to fault attacks," Workshop on Fault Detection and Tolerance in Cryptography, June 2004.

Google Scholar

[4]

J. Blࣆmer, M. Otto, J.-P. Seifert, "A new CRT-RSA algorithm secure against Bellcore attacks," ACM CCS 2003, ACM Press, pp.311--320, 2003.

Digital Library

Google Scholar

[5]

D. Boneh, R.A. DeMillo, R.J. Lipton, "On the importance of checking cryptographic protocols for fault," EUROCRYPT'97, Springer-Verlag, LNCS 1233, pp.37--51, 1997.

Digital Library

Google Scholar

[6]

M. Joye, A.K. Lenstra, J.-J. Quisquater, "Chinese remaindering based cryptosystems in the presence of faults," Journal of Cryptology, vol. 12, no. 4, pp.241--245, 1999.

Digital Library

Google Scholar

[7]

A.K. Lenstra, "Memo on RSA signature generation in the presence of faults," Sept. 1996.

Google Scholar

[8]

S.-M. Yen, M. Joye, "Checking before output may not be enough against fault-based cryptanalysis," IEEE Transactions on Computers, vol. 49, no. 9, pp.96--970, 2000.

Digital Library

Google Scholar

[9]

S.-M. Yen, S. Kim, S. Lim, S. Moon, "RSA Speedup with Residue Number System Immune against Hardware Fault Cryptanalysis," ICICS 2001, Springer-Verlag, LNCS 2288, pp.397--413, 2002.

Digital Library

Google Scholar

Cited By

View all

Barbu GGiraud C(2023)All Shall FA-LLL: Breaking CT-RSA 2022 and CHES 2022 Infective Countermeasures with Lattice-Based Fault AttacksTopics in Cryptology – CT-RSA 202310.1007/978-3-031-30872-7_17(445-468)Online publication date: 19-Apr-2023
https://doi.org/10.1007/978-3-031-30872-7_17
Gao PXie HSong FChen T(2021)A Hybrid Approach to Formal Verification of Higher-Order Masked Arithmetic ProgramsACM Transactions on Software Engineering and Methodology10.1145/342801530:3(1-42)Online publication date: 11-Feb-2021
https://dl.acm.org/doi/10.1145/3428015
Kong FYang GLiu HJiang YHu CZhou D(2019)Fault-injection Attack and Improvement of a CRT-RSA Exponentiation AlgorithmProceedings of the 2019 9th International Conference on Communication and Network Security10.1145/3371676.3371699(123-127)Online publication date: 15-Nov-2019
https://dl.acm.org/doi/10.1145/3371676.3371699
Show More Cited By

Index Terms

Cryptanalysis of a provably secure CRT-RSA algorithm

Recommendations

A new CRT-RSA algorithm secure against bellcore attacks
CCS '03: Proceedings of the 10th ACM conference on Computer and communications security

In this paper we describe a new algorithm to prevent fault attacks on RSA signature algorithms using the Chinese Remainder Theorem (CRT-RSA). This variant of the RSA signature algorithm is widely used on smartcards. Smartcards on the other hand are ...
CRT RSA algorithm protected against fault attacks
WISTP'07: Proceedings of the 1st IFIP TC6 /WG8.8 /WG11.2 international conference on Information security theory and practices: smart cards, mobile and ubiquitous computing systems

Embedded devices performing RSA signatures are subject to Fault Attacks, particularly when the Chinese Remainder Theorem is used. In most cases, the modular exponentiation and the Garner recombination algorithms are targeted. To thwart Fault Attacks, we ...
Cryptanalysis of a type of CRT-based RSA algorithms

It is well known that the Chinese Remainder Theorem (CRT) can greatly improve the performances of RSA cryptosystem in both running times and memory requirements. However, if the implementation of CRT-based RSA is careless, an attacker can reveal some ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CCS '04: Proceedings of the 11th ACM conference on Computer and communications security

October 2004

376 pages

ISBN:1581139616

DOI:10.1145/1030083

General Chair:
Vijay Atluri
Rutgers University
,
Program Chairs:
Birgit Pfitzmann
IBM Research, Switzerland
,
Patrick McDaniel
AT&T Labs

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS04

Sponsor:

CCS04: 11th ACM Conference on Computer and Communications Security 2004

October 25 - 29, 2004

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
1,159
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Barbu GGiraud C(2023)All Shall FA-LLL: Breaking CT-RSA 2022 and CHES 2022 Infective Countermeasures with Lattice-Based Fault AttacksTopics in Cryptology – CT-RSA 202310.1007/978-3-031-30872-7_17(445-468)Online publication date: 19-Apr-2023
https://doi.org/10.1007/978-3-031-30872-7_17
Gao PXie HSong FChen T(2021)A Hybrid Approach to Formal Verification of Higher-Order Masked Arithmetic ProgramsACM Transactions on Software Engineering and Methodology10.1145/342801530:3(1-42)Online publication date: 11-Feb-2021
https://dl.acm.org/doi/10.1145/3428015
Kong FYang GLiu HJiang YHu CZhou D(2019)Fault-injection Attack and Improvement of a CRT-RSA Exponentiation AlgorithmProceedings of the 2019 9th International Conference on Communication and Network Security10.1145/3371676.3371699(123-127)Online publication date: 15-Nov-2019
https://dl.acm.org/doi/10.1145/3371676.3371699
Boespflug EGourier RLanet J(2019)Predicting the Effect of Hardware Fault Injection2019 International Workshop on Big Data and Information Security (IWBIS)10.1109/IWBIS.2019.8935864(103-108)Online publication date: Oct-2019
https://doi.org/10.1109/IWBIS.2019.8935864
Bhattacharjya AZhong XLi X(2019)A lightweight and efficient Secure Hybrid RSA (SHRSA) messaging scheme with four-layered authentication stackIEEE Access10.1109/ACCESS.2019.2900300(1-1)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2900300
Hamadouche SLanet JMezghiche M(2019)Hiding a fault enabled virus through code constructionJournal of Computer Virology and Hacking Techniques10.1007/s11416-019-00340-z16:2(103-124)Online publication date: 24-Oct-2019
https://doi.org/10.1007/s11416-019-00340-z
Bhattacharjya AZhong XWang JLi X(2019)A Secure Hybrid RSA (SHRSA)-based Lightweight and Efficient Personal Messaging Communication ProtocolDigital Twin Technologies and Smart Cities10.1007/978-3-030-18732-3_11(191-212)Online publication date: 23-Jul-2019
https://doi.org/10.1007/978-3-030-18732-3_11
Yadav JSheregar APanjri VGharat S(2018)Secure Approach For Encrypting Data2018 International Conference on Smart City and Emerging Technology (ICSCET)10.1109/ICSCET.2018.8537290(1-3)Online publication date: Jan-2018
https://doi.org/10.1109/ICSCET.2018.8537290
Kong FZhou DJiang YShang JYu J(2017)Fault Attack on an Improved CRT-RSA Algorithm with the Modulus Chaining Method22017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC)10.1109/CSE-EUC.2017.174(866-869)Online publication date: Jul-2017
https://doi.org/10.1109/CSE-EUC.2017.174
Dugardin MGuilley SMoreau MNajm ZRauzy P(2017)Using modular extension to provably protect Edwards curves against fault attacksJournal of Cryptographic Engineering10.1007/s13389-017-0167-47:4(321-330)Online publication date: 13-Jun-2017
https://doi.org/10.1007/s13389-017-0167-4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A new CRT-RSA algorithm secure against bellcore attacks

CRT RSA algorithm protected against fault attacks

Cryptanalysis of a type of CRT-based RSA algorithms