Abstract
We introduce a new type of timing attack which enables the factorization of an RSA-modulus if the exponentiation with the secret exponent uses the Chinese Remainder Theorem and Montgomery’s algorithm. Its standard variant assumes that both exponentiations are carried out with a simple square and multiply algorithm. However, although its effciency decreases, our attack can also be adapted to more advanced exponentiation algorithms. The previously known timing attacks do not work if the Chinese Remainder Theorem is used.
Chapter PDF
Similar content being viewed by others
References
D. Boneh, R.A. Demillo, R.J. Lipton: On the Importance of Checking Cryptographic Protocols for Faults. In: W. Fumy (ed.): Advances in Cryptology-Eurocrypt’ 97, Lecture Notes in Computer Science, Vol. 1233. Springer, New York (1997) 37–51.
D. Coppersmith: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology 10 (no. 4) (1997) 233–260.
J.-F. Dhern, F. Koeune, P.-A. Leroux, P.-A. Mestré, J.-J. Quisquater, J.-L. Willems: A Practical Implementation of the Timing Attack. In: J.-J. Quisquater, B. Schneier (eds.): CARDIS 1998, Third Smart Card Research and Advanced Application Conference (PreProceedings). Université catholique de Louvain (1998).
W. Feller: An Introduction to Probability Theory and Its Applications (Vol. 1). 3rd edition, revised printing, Wiley, New York (1970).
G. Hachez, J.-J. Quisquater: Montgomery Exponentiation with no Final Subtractions: Improved Results. To appear in: Ç.K. Koç, C. Paar (eds.): Workshop on Cryptographic Hardware and Embedded Systems, 2000 (Proceedings).
P. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS and Other Systems. In: N. Koblitz (ed.): Advances in Cryptology-Crypto’ 96, Lecture Notes in Computer Science, Vol. 1109. Springer, Heidelberg (1996), 104–113.
A.J. Menezes, P.C. van Oorschot, S.C. Vanstone: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997).
P.L. Montgomery: Modular Multiplication without Trial Division. Math. Comp. 44 (no. 170) (1985) 519–521.
W. Schindler: Optimized Timing Attacks against Public Key Cryptosystems. Submitted.
C.D. Walter: Montgomery’s Exponentiation Needs no Final Subtractions. Electronics letters 35 (no. 21) (1999), 1831–1832.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schindler, W. (2000). A Timing Attack against RSA with the Chinese Remainder Theorem. In: Koç, Ç.K., Paar, C. (eds) Cryptographic Hardware and Embedded Systems — CHES 2000. CHES 2000. Lecture Notes in Computer Science, vol 1965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44499-8_8
Download citation
DOI: https://doi.org/10.1007/3-540-44499-8_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41455-1
Online ISBN: 978-3-540-44499-2
eBook Packages: Springer Book Archive