Cryptanalysis of a type of CRT-based RSA algorithms
Authors: 
Bao-Dong Qin, Ming Li, Fan-Yu KongAuthors Info & Claims
Pages 214 - 221
Abstract
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 secret information by exploiting hardware fault cryptanalysis. In this paper, we present some fault attacks on a type of CRT-RSA algorithms namely BOS type schemes including the original BOS scheme proposed by Blömer, Otto, and Seifert at CCS 2003 and its modified scheme proposed by Liu et al. at DASC 2006. We first demonstrate that if some special signed messages such as m = 0, ±1 are dealt carelessly, they can be exploited by an adversary to completely break the security of both the BOS scheme and Liu et al.'s scheme. Then we present a new permanent fault attack on the BOS scheme with a success probability about 25%. Lastly, we propose a polynomial time attack on Liu et al.'s CRT-RSA algorithm, which combines physical fault injection and lattice reduction techniques when the public exponent is short.
References
[1]
Boneh D, DeMillo R A, Lipton R J. On the importance of checking cryptographic protocols for fault. In Proc. EUROCRYPT'97 , Konstanz, Germany, Springer-Verlag, 1997, pp.37-51.
[2]
Christian Aumüller, Peter Bier, Wieland Fischer, Peter Hofreiter, Jean-Pierre Seifert. Fault attacks on RSA with CRT: Concrete results and practical countermeasures. In Proc. CHES'02, Redwood Shores, USA, August 13-15, 2002, pp.260-275.
[3]
Bar-El H, Choukri H, Naccache D, Tunstall M, Whelan C. The sorcerer's apprentice guide to fault attacks. In Proc. Workshop on Fault Detection and Tolerance in Cryptography , Florence, Italy, June 2004.
[4]
Couvreur C, Quisquater J. Fast decipherment algorithm for RSA public-key cryptosystem. Electronic Letters, 1982, 18(21): 905-907.
[5]
Yen S, Kim S, Lim S, Moon S. RSA Speedup with Chinese remainder theorem immune against hardware fault Cryptanalysis. IEEE Transactions on Computers, April 2003, 52: 461-472.
[6]
Ross J Anderson, Markus G Kuhn. Low cost attacks on tamper resistant devices. In Proc. 5th International Workshop on Security Protocols, Paris, France, April 07-09, 1997, pp.125-136.
[7]
Skorobogatov S, Anderson R. Optical fault induction attacks. In Proc. Workshop on Cryptographic Hardware and Embedded Systems, Hotel Sofitel, San Francisco Bay (Redwood City), USA, August 13-15, 2002.
[8]
Bellcore Press Release. New threat model breaks crypto codes. Sept. 1996, http://www.bellcore.com/PRESS/ADVS-RY96/facts.html.
[9]
Ciet M, Joye M. Practical fault countermeasures for Chinese remaindering based RSA. In Proc. FDTC'05, Edinburgh, Scotland, September 2, 2005, pp.124-131.
[10]
Johannes Blömer, Martin Otto. Wagner's attack on a secure CRT-RSA algorithm reconsidered. In Proc. FDTC'06, Yokohama, Japan, Springer-Verlag, 2006, pp.13-23.
[11]
Shamir A. Method and apparatus for protecting public key schemes from timing and fault attacks. United States Patent, No. 5991415, Nov. 23, 1999.
[12]
Joye M, Lenstra A K, Quisquater J J. Chinese remaindering based cryptosystems in the presence of faults. Journal of Cryptology, 1999, 12(4): 241-245.
[13]
Johannes Blömer, Martin Otto, Jean-Pierre Seifert. A new CRT-RSA algorithm secure against bellcore attacks. In Proc. 10th ACM Conference on Computer and Communications Security, Washington D.C., USA, October 27-30, 2003, pp.311-320.
[14]
Ming Li, Baodong Qin, Fanyu Kong, Daxing Li. Further cryptanalysis of a CRT-RSA algorithm at CCS 2003. In Proc. International Workshop on Network and System Security , Dalian, China, Sept. 18-21, 2007, pp.72-76.
[15]
Sining Liu, Brian King, Wei Wang. A CRT-RSA algorithm secure against hardware fault attacks. In Proc. DASC'06, Indianapolis, USA, 2006, pp.51-66.
[16]
David Wagner. Cryptanalysis of a provably secure CRT-RSA algorithm. In Proc. the 11th ACM Conference on Computer and Communications Security, Washington DC, USA, October 25-29, 2004, pp.92-97.
[17]
Coppersmith D. Finding a small root of a univariate modular equation. In Proc. EUROCRYPT'96, Saragossa, Spain, Springer-Verlag, 1996, pp.155-165.
[18]
Coppersmith D. Finding a small root of a bivariate integer equation. In Proc. EUROCRYPT'96, Saragossa, Spain, Springer-Verlag, 1996, pp.178-189.
[19]
Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 1997, 10: 233-260.
[20]
Howgrave-Graham N. Finding small roots of univariate modular equations revisited. In Proc. Cryptography and Coding, Cirencester, UK, Springer-Verlag, 1997, pp.131-142.
[21]
A Lenstra, H Lenstra, Jr., L Lovasz. Factoring polynomials with rational coefficients. Mathematische Ann, 1982, 261: 513-534.
[22]
Menezes A J, van Oorschot P C, Vanstone S A. Handbook of Applied Cryptography. CRC Press, 1997.
[23]
Bellare M, Rogaway P. Optimal asymmetric encryption. In Proc. EUROCRYPT'94, Springer-Verlag, Berlin, 1995, pp.92-111.
Index Terms
- Cryptanalysis of a type of CRT-based RSA algorithms
Recommendations
Cryptanalysis of a provably secure CRT-RSA algorithm
CCS '04: Proceedings of the 11th ACM conference on Computer and communications securityWe 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 new CRT-RSA algorithm secure against bellcore attacks
CCS '03: Proceedings of the 10th ACM conference on Computer and communications securityIn 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 ...
Multi-asymmetric cryptographic RSA scheme
CISRC '17: Proceedings of the 12th Annual Conference on Cyber and Information Security ResearchIn this paper, we propose a version of RSA encryption that uses the Chinese Remainder Theorem (CRT) for the purpose of concealing multiple plain-texts in one cipher-text. This scheme allows the sender to possibly send different information to multiple ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 March 2008
Revised: 19 November 2007
Received: 22 August 2007
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025