• Articles • Previous Articles     Next Articles

Cryptanalysis of a Type of CRT-Based RSA Algorithms

Bao-Dong Qin{1,*, Ming Li{2,3, and Fan-Yu Kong{2,3   

  1. 1College of Computer Science and Technology, Southwest University of Science and Technology, Mianyang 621010, China 2Institute of Network Security, Shandong University, Jinan 250100, China 3Key Laboratory of Cryptographic Technology and Information Security, Jinan 250100, China
  • Received:2007-08-22 Revised:2007-11-19 Online:2008-03-15 Published:2008-03-10

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\"{o}mer, Otto, and Seifert at CCS 2003 and its modified scheme proposed by Liu {\it et al.} at DASC 2006. We first demonstrate that if some special signed messages such as $m = 0, \pm1$ are dealt carelessly, they can be exploited by an adversary to completely break the security of both the BOS scheme and Liu {\it 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 {\it et al.}'s CRT-RSA algorithm, which combines physical fault injection and lattice reduction techniques when the public exponent is short.

Key words: routing protocol; multicast; unicast; uni-directional network;

[1]Boneh D, DeMillo R A, Lipton R J. On the importance of checking cryptographic protocols for fault. In -\it Proc. EUROCRYPT'97}, Konstanz, Germany, Springer-Verlag, 1997, pp.37--51.

[2] Christian Aum\"-u}ller, Peter Bier, Wieland Fischer, Peter Hofreiter, Jean-Pierre Seifert. Fault attacks on RSA with CRT: Concrete results and practical countermeasures. In -\it 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 -\it 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. -\it 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. -\it IEEE Transactions on Computers}, April 2003, 52: 461--472.

[6] Ross J Anderson, Markus G Kuhn. Low cost attacks on tamper resistant devices. In -\it 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 -\it 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 -\it Proc. FDTC'05}, Edinburgh, Scotland, September 2, 2005, pp.124--131.

[10] Johannes Bl\"-o}mer, Martin Otto. Wagner's attack on a secure CRT-RSA algorithm reconsidered. In -\it 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. -\it Journal of Cryptology}, 1999, 12(4): 241--245.

[13] Johannes Bl\"-o}mer, Martin Otto, Jean-Pierre Seifert. A new CRT-RSA algorithm secure against bellcore attacks. In -\it 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 -\it 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 -\it Proc. DASC'06}, Indianapolis, USA, 2006, pp.51--66.

[16] David Wagner. Cryptanalysis of a provably secure CRT-RSA algorithm. In -\it 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 -\it Proc. EUROCRYPT'96}, Saragossa, Spain, Springer-Verlag, 1996, pp.155--165.

[18] Coppersmith D. Finding a small root of a bivariate integer equation. In -\it Proc. EUROCRYPT'96}, Saragossa, Spain, Springer-Verlag, 1996, pp.178--189.

[19] Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. -\it Journal of Cryptology}, 1997, 10: 233--260.

[20] Howgrave-Graham N. Finding small roots of univariate modular equations revisited. In -\it Proc. Cryptography and Coding}, Cirencester, UK, Springer-Verlag, 1997, pp.131--142.

[21] A Lenstra, H Lenstra, Jr., L Lov\,-a}sz. Factoring polynomials with rational coefficients. -\it 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 -\it Proc. EUROCRYPT'94}, Springer-Verlag, Berlin, 1995, pp.92--111.
[1] Ibrahim S. Alsukayti. Quality of Service Support in RPL Networks: Standing State and Future Prospects [J]. Journal of Computer Science and Technology, 2022, 37(2): 344-368.
[2] Manas Ranjan Kabat, Manoj Kumar Patel, and Chita Ranjan Tripathy. A Heuristic Algorithm for Core Selection in Multicast Routing [J]. , 2011, 26(6): 954-961.
[3] Shao-Liang Peng, Shan-Shan Li, Lei Chen, Yu-Xing Peng, and Nong Xiao. Scalable Base-Station Model-Based Multicast in Wireless Sensor Networks [J]. , 2008, 23(5 ): 780-791 .
[4] Wei-Sheng Si and Cheng-Zhi Li. RMAC: A Reliable MAC Protocol Supporting Multicast for Wireless Ad Hoc Networks [J]. , 2005, 20(5): 702-712 .
[5] Yuan Zhou, Guang-Sheng Li, Yong-Zhao Zhan, Qi-Rong Mao, and Yi-Bin Hou. DRMR: Dynamic-Ring-Based Multicast Routing Protocol for Ad Hoc Networks [J]. , 2004, 19(6): 0-0.
[6] Alberto Apostolico, Fang-Cheng Gong, and StefanoLonardi. Verbumculus and the Discovery of Unusual Words [J]. , 2004, 19(1): 0-0.
[7] SONG JianPing , HOU ZiFeng and XU Ming . Pseudo-Cycle-Based Multicast Routing in Wormhole-Routed Networks [J]. , 2003, 18(6): 0-0.
[8] LIN Yu (林 宇), WU HaiTao (邬海涛), WANG ChongGang (王重钢) and CHENG ShiDuan (程时端). Dynamic Retransmission Control for Reliable Mobile Multicast [J]. , 2003, 18(3): 0-0.
[9] LI Xianxian (李先贤) and HUAI Jinpeng (怀进鹏). Efficient Non-Repudiation Multicast Source Authentication Schemes [J]. , 2002, 17(6): 0-0.
[10] MA Huadong (马华东) and Kang G. Shin. Hybrid Broadcast for the Video-on-Demand Service [J]. , 2002, 17(4): 0-0.
[11] ZHAO Yixin(赵邑新),WU Jianping(吴建平) and YIN Xia(尹霞). From Active to Passive—Progress in Testing Internet Routing Protocols [J]. , 2002, 17(3): 0-0.
[12] WU Jie(吴杰)and CHEN Xiao. Fault-Tlerant Tree-Based Multicasting in Mesh Multicomputers [J]. , 2001, 16(5): 0-0.
[13] SONG Jianping(宋建平),HOU Zifeng(侯紫峰)and SHI Yuntao(史云涛). An Optimal Multicast Algorithm for Cube-Connected Cycles [J]. , 2000, 15(6): 0-0.
[14] SONG Jianping; HOU Zifeng; SHI Yuntao;. An Optimal Multicast Algorithm for Cube-Connected Cycles [J]. , 2000, 15(6): 572-583.
[15] HUANG Hao; CHEN Guihai; XIE Li; SUN Zhongxiu;. Multicast Protocol for Uni-Directional Networks [J]. , 2000, 15(2): 158-168.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved