Abstract
We present modular reduction algorithms over finite fields of large characteristic that allow the use of redundant modular arithmetic. This technique provides constant time reduction algorithms. Moreover, it can also be used to strengthen the differential side-channel resistance of asymmetric cryptosystems. We propose modifications to the classic Montgomery and Barrett reduction algorithms in order to have efficient and resistant modular reduction methods. Our algorithms are called dynamic redundant reductions as random masks are intrinsically added within each reduction for a small overhead. This property is useful in order to thwart recent refined attacks on public key algorithms.
Chapter PDF
Similar content being viewed by others
Keywords
- Base Multiplication
- Reduction Algorithm
- Advance Encryption Standard
- Modular Reduction
- Modular Exponentiation
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
Amiel, F., Feix, B., Tunstall, M., Whelan, C., Marnane, W.P.: Distinguishing Multiplications from Squaring Operations. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 346–360. Springer, Heidelberg (2009)
Amiel, F., Feix, B., Villegas, K.: Power Analysis for Secret Recovering and Reverse Engineering of Public Key Algorithms. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 110–125. Springer, Heidelberg (2007)
Amiel, F., Villegas, K., Feix, B., Marcel, L.: Passive and Active Combined Attacks: Combining Fault Attacks and Side Channel Analysis. In: FDTC 2007, pp. 92–102. IEEE (2007)
ATMEL: ATmega 2561 Data Sheet, http://www.atmel.com/dyn/resources/prod_documents/doc2549.pdf
Barrett, P.: Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 311–323. Springer, Heidelberg (1987)
Bosselaers, A., Govaerts, R., Vandewalle, J.: Comparison of Three Modular Reduction Functions. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 175–186. Springer, Heidelberg (1994)
Clavier, C., Joye, M.: Universal Exponentiation Algorithm A First Step towards Provable SPA-Resistance. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 300–308. Springer, Heidelberg (2001)
Comba, P.: Exponentiation Cryptosystems on the IBM PC. IBM Syst. J. 29, 526–538 (1990)
Dhem, J.F.: Design of an efficient public-key cryptographic library for RISC-based smart cards. Ph.D. thesis, Université Catholique de Louvain (1998)
Golić, J.D., Tymen, C.: Multiplicative Masking and Power Analysis of AES. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 198–212. Springer, Heidelberg (2003)
Kocher, P.C.: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Menezes, A.J., Vanstone, S.A., Van Oorschot, P.C.: Handbook of Applied Cryptography. CRC Press, Inc. (1996)
Messerges, T.S., Dabbish, E.A., Sloan, R.H.: Power Analysis Attacks of Modular Exponentiation in Smartcards. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 144–724. Springer, Heidelberg (1999)
Montgomery, P.: Modular Multiplication Without Trial Division. Mathematics of computation 44(170), 519–521 (1985)
Schmidt, J.-M., Tunstall, M., Avanzi, R., Kizhvatov, I., Kasper, T., Oswald, D.: Combined Implementation Attack Resistant Exponentiation. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 305–322. Springer, Heidelberg (2010)
Scott, M., Szczechowiak, P.: Optimizing Multiprecision Multiplication for Public Key Cryptography. Cryptology ePrint Archive, Report 2007/299 (2007)
Smart, N., Oswald, E., Page, D.: Randomised Representations. Information Security IET 2(2), 19–27 (2008)
Solinas, J.: Generalized Mersenne Numbers. Technical report (1999)
Walter, C.: Montgomery Exponentiation Needs no Final Subtractions. Electronics letters 35(21), 1831–1832 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 IFIP International Federation for Information Processing
About this paper
Cite this paper
Dupaquis, V., Venelli, A. (2011). Redundant Modular Reduction Algorithms. In: Prouff, E. (eds) Smart Card Research and Advanced Applications. CARDIS 2011. Lecture Notes in Computer Science, vol 7079. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27257-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-27257-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27256-1
Online ISBN: 978-3-642-27257-8
eBook Packages: Computer ScienceComputer Science (R0)