An Improved Montgomery Window Algorithm on Modular Exponentiation Secure against Side Channel Attacks

Abstract:

As one of the core algorithms in most public key cryptography, modular exponentiation has a flaw of its efficiency, which often uses the Montgomerys algorithm to realize the fast operation. But the Montgomerys algorithm has the issue of side channel leakage from the final conditional subtraction. Aiming at this problem, this paper presents an improved fast Montgomery window algorithm. The new algorithm generates the remainder table with odd power to reduce the amount of pre-computation, and combines with the improved Montgomerys algorithm to realize modular exponentiation, which can accelerate the speed and reduce the side channel leakage. The new algorithm cant only thwart side channel attacks, but also improve the efficiency.

• Periodical: Applied Mechanics and Materials (Volume 392)
• Pages: 862-866
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.392.862
• Online since: September 2013
• Authors: Mu Han, Jia Zhao, Shi Dian Ma
• Keywords: Modular Exponentiation Computation, Montgomery’s Algorithm, Side Channel Attacks

References

[1] P. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[C] /Proc. of CRYPTO'96. Berlin Heidelberg: Springer-Verlag, 1996: 104-113.

DOI: 10.1007/3-540-68697-5_9

[2] P. Kocher, J. Jaffe, B. Jun. Differential Power Analysis[C] /Proc. of CRYPTO'99. Berlin Heidelberg: Springer-Verlag, 1999: 388-397.

[3] J Han, XY Zeng, TA Tang. Power Trace Analysis Attack and Countermeasures for RSA Cryptographic Circuits [J]. Chinese Journal of Computers, 2006, 29(4): 590-596.

[4] Y Chen, Z Wu, J Chen, et al. Implementation of Equivalent Power Consumption Coding Secure Against Side Channel Attack[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(2): 168-171.

[5] Z Wu, Y Chen, M Wang, et al. Improvement of Equivalent Power Consumption Coding Secure Against Power Analysis Attacks[J]. Journal on Communications, 2010, 31(8): 26-30.

[6] W. Schindler. A Timing Attack against RSA with the Chinese Remainder Theorem[C] /Proc. of Cryptographic Hardware and Embedded Systems (CHES'00). Berlin Heidelberg: Springer-Verlag, 2000: 109-124.

DOI: 10.1007/3-540-44499-8_8

[7] Y .J. Baek. Regular 2w-ary right-to-left exponentiation algorithm with very efficient DPA and FA countermeasures[C] /Proc. of International Journal of Information Security 2010. Berlin Heidelberg: Springer-Verlag, 2010: 363-370.

DOI: 10.1007/s10207-010-0118-x

[8] C. D. Walter. Leakage from Montgomery Multiplication[C] /Proc. of Cryptographic Engineering LLC 2009, Springer Science+Business Media: 431-449.

DOI: 10.1007/978-0-387-71817-0_16

[9] C. D. Walter, S. Thompson. Distinguishing Exponent Digits by Observing Modular Subtractions[C]/Proc. of Topics in Cryptology – CT-RSA 2001. Berlin Heidelberg: Springer-Verlag, 2001: 192-207.

DOI: 10.1007/3-540-45353-9_15

[10] T .S. Denis. Big Num Math: Implementing Cryptographic Multiple Precision Arithmetic [M]. Beijing: China Water Power Press, 2008: 155-157.