Abstract
At CT-RSA 2009, a new principle to secure RSA (and modular/group exponentiation) against fault-analysis has been introduced by Rivain. The idea is to perform a so-called double exponentiation to compute a pair (m d, m ϕ(N) − d) and then check that the output pair satisfies the consistency relation: \(m^d \cdot m^{\varphi(N)-d} \equiv 1 \bmod N\). The author then proposed an efficient heuristic to derive an addition chain for the pair (d, ϕ(N) − d). In this paper, we revisit this idea and propose faster methods to perform a double exponentiation. On the one hand, we present new heuristics for generating shorter double addition chains. On the other hand, we present an efficient double exponentiation algorithm based on a right-to-left sliding window approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aumüller, C., Bier, P., Fischer, W., Hofreiter, P., Seifert, J.-P.: Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 260–275. Springer, Heidelberg (2003)
Baek, Y.J.: Regular 2w-ary right-to-left exponentiation algorithm with very efficient dpa and fa countermeasures. International Journal of Information Security 9(5), 363–370 (2010)
Bao, F., Deng, R., Han, Y., Jeng, A., Narasimhalu, A.D., Ngair, T.-H.: Breaking Public Key Cryptosystems an Tamper Resistance Devices in the Presence of Transient Fault. In: Christianson, B., Crispo, B., Lomas, M., Roe, M. (eds.) Security Protocols 1997. LNCS, vol. 1361, pp. 115–124. Springer, Heidelberg (1998)
Berzati, A., Canovas, C., Goubin, L.: Perturbating RSA Public Keys: An Improved Attack. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 380–395. Springer, Heidelberg (2008)
Blömer, J., Otto, M., Seifert, J.P.: A New RSA-CRT Algorithm Secure against Bellcore Attacks. In: Jajodia, S., Atluri, V., Jaeger, T. (eds.) ACM Conference on Computer and Communications Security, CCS 2003, pp. 311–320. ACM Press (2003)
Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking Cryptographic Protocols for Faults. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)
Boreale, M.: Attacking Right-to-Left Modular Exponentiation with Timely Random Faults. In: Breveglieri, L., Koren, I., Naccache, D., Seifert, J.-P. (eds.) FDTC 2006. LNCS, vol. 4236, pp. 24–35. Springer, Heidelberg (2006)
Boscher, A., Naciri, R., Prouff, E.: CRT RSA Algorithm Protected Against Fault Attacks. In: Sauveron, D., Markantonakis, K., Bilas, A., Quisquater, J.-J. (eds.) WISTP 2007. LNCS, vol. 4462, pp. 229–243. Springer, Heidelberg (2007)
Brier, E., Chevallier-Mames, B., Ciet, M., Clavier, C.: Why one should also secure rsa public key elements. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 324–338. Springer, Heidelberg (2006)
Ciet, M., Joye, M.: Practical Fault Countermeasures for Chinese Remaindering Based RSA. In: Breveglieri, L., Koren, I. (eds.) Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2005, pp. 124–132 (2005)
Coron, J.-S.: Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)
Downey, P., Leong, B., Sethi, R.: Computing Sequences with Addition Chains. SIAM Journal on Computing 10(3), 638–646 (1981)
Garner, H.L.: The residue number system. IRE Transactions on Electronic Computers (2), 140–147 (1959)
Giraud, C.: An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis. IEEE Transactions on Computers 55(9), 1116–1120 (2006)
Joye, M.: Highly Regular m-Ary Powering Ladders. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 350–363. Springer, Heidelberg (2009)
Joye, M.: A Method for Preventing “Skipping” Attacks. In: 2012 IEEE Symposium on Security and Privacy Workshops, pp. 12–15. IEEE Computer Society (2012)
Joye, M., Karroumi, M.: Memory-Efficient Fault Countermeasures. In: Prouff, E. (ed.) CARDIS 2011. LNCS, vol. 7079, pp. 84–101. Springer, Heidelberg (2011)
Koc, C.K.: Analysis of Sliding Window Techniques for Exponentiation. Computers and Mathematics with Applications 30, 17–24 (1995)
Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V.: Handbook of Applied Cryptography, 1st edn. CRC Press, Inc. (1996)
Montgomery, P.L.: Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation 48(177), 243–264 (1987)
Quisquater, J.J., Couvreur, C.: Fast decipherment algorithm for rsa public-key cryptosystem. Electronics Letters 18(21), 905–907 (1982)
Rivain, M.: Securing RSA against Fault Analysis by Double Addition Chain Exponentiation. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 459–480. Springer, Heidelberg (2009)
Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
Schmidt, J., Herbst, C.: A Practical Fault Attack on Square and Multiply. In: Breveglieri, L., Gueron, S., Koren, I., Naccache, D., Seifert, J.P. (eds.) Fault Diagnosis and Tolerance in Cryptography – FDTC 2008, pp. 53–58 (2008)
Seifert, J.-P.: On authenticated computing and rsa-based authentication. In: Atluri, V., Meadows, C., Juels, A. (eds.) Proceedings of the 12th ACM Conference on Computer and Communications Security, CCS 2005, Alexandria, VA, USA, November 7-11, pp. 122–127. ACM (2005)
Shamir, A.: Improved Method and Apparatus for Protecting Public Key Schemes from Timing and Fault Attacks. Patent WO9852319 (November 1998); Also presented to EUROCRYPT 1997 rump session
Sun Microsystems: Application Programming Interface – Java CardTM Plateform, Version 2.2.2 (March 2006), http://java.sun.com/products/javacard/specs.html
Vigilant, D.: RSA with CRT: A New Cost-Effective Solution to Thwart Fault Attacks. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 130–145. Springer, Heidelberg (2008)
Yao, A.C.C.: On the evaluation of powers. SIAM Journal on Computing 5(1), 100–103 (1976)
Yen, S.M., Joye, M.: Checking Before Output May Not Be Enough Against Fault-Based Cryptanalysis. IEEE Transactions on Computers 49(9), 967–970 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Le, DP., Rivain, M., Tan, C.H. (2014). On Double Exponentiation for Securing RSA against Fault Analysis. In: Benaloh, J. (eds) Topics in Cryptology – CT-RSA 2014. CT-RSA 2014. Lecture Notes in Computer Science, vol 8366. Springer, Cham. https://doi.org/10.1007/978-3-319-04852-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-04852-9_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04851-2
Online ISBN: 978-3-319-04852-9
eBook Packages: Computer ScienceComputer Science (R0)