Comparative Study of Efficient Modular Exponentiation Algorithms
Keywords:
Modular Exponentiation, Left-to-Right, Right-to-Left, Montgomery Ladder, Sliding Window, NonAdjacent Form, Mutual Opposite FormAbstract
This paper presents description on the efficient modular multiplication techniques with numerical examples and flowchart diagrams. This review will help cryptoprocessor designers to in the effective selection of the underlying modular exponentiation unit to improve the hardware cost complexity such as area and speed. We found that conventional techniques of Modular Exponentiation (i.e. L-R binary, R-L binary Montgomery ladder, and Sliding window) proved its efficiency for many years with average cost complexity of 0(Log(Exponent)) with possibility of saving to k - 1 multiplications operations for all k - bits of the exponent in the case of sliding window. However, the enhanced modular exponentiation based w-NAF and w-MOF are quite up-to-date and will replace all other algorithms as they have the minimum non-zero representation for the exponent. It was shown that NAF representation minimizes the number of nonzero digits in the binary representation, with an average of one third of nonzero digits while the average non-zero density on n - bit MOF has been reduced to the half for n tends to infinity.
References
. G. Santucci. The Internet of Things: Between the Revolution of the Internet and the Metamorphosis of Objects. European Commission Community Research & Development Information Service, 2016. https://pdfs.semanticscholar.orgadb703eb4c53ccba53a8973fbff2f30563363a58.pdf
. Q. Abu Al-Haija, M. Smadi, M. Jaffri and A. Shua'ibi. Efficient FPGA Implementation of RSA Coprocessor Using Scalable Modules. 9th
International Conference on Future Networks and Communications (FNC-2014). by Elsevier. Ontario. Canada. 17-20, Aug-2014. https://doi.org/10.1016/j.procs.2014.07.092
. Q. Abu Al-Haija, M. Al-Ja'fari and M. Smadi. A comparative study up to 1024-bit Euclid's GCD algorithm FPGA implementation and synthesizing. 2016 5th International Conference on Electronic Devices, Systems and Applications (ICEDSA), Ras Al Khaimah, United Arab Emirates, pp. 1-4. https://DOI.10.1109/ICEDSA.2016.7818535
. M. M. Asad, I. Marouf and Q. Abu Al-Haija. Review of Fast Multiplication Algorithms for Embedded Systems Design. International Journal of Scientific & Technology Research, Volume 6, Issue 08, 2017. http://www.ijstr.org/research- aperpublishing.php?month=aug2017
. W. Trappe and L. C. Washington. Introduction to Cryptography with Coding Theory. By Prentice Hall, 2002, 1: 1-176. http://calclab.math.tamu.edu/~rahe/2014a_673_700720/Trappe_2006.pdf
. A. Jakubski and R. Perliński. Review of General Exponentiation Algorithms. Scientific Research of the Institute of Mathematics and Computer Science, 2(10), 87-98, (2011)
. C. D. Walter. Right-to-Left or Left-to-Right Exponentiation?. 1st International Workshop on Constructive Side-Channel Analysis and Secure Design, Darmstadt, Germany, February 4-5, (2010).
. N. Nedjah, L. M. Mourelle and R. M. Silva. Efficient Hardware for Modular Exponentiation Using the Sliding-Window Method. 4th
International Conference on Information Technology, 2007. ITNG '07.
. E. Dahmen, K. Okeya, T. Takagi. Efficient Leftto-Right Multi-Exponentiations. Technical Report TI-2/05, 2005.
. A. Weimerskirch. Fixed-Exponent Exponentiation. Encyclopedia of Cryptography and Security, Springer, pp 485-486, 2011.
. A. Weimerskirch. Fixed-Base Exponentiation. Encyclopedia of Cryptography and Security, Springer, pp 482-485, 2011.
. C.L. Wu, D.C. Lou and T.J. Chang. Fast modular multiplication based on complement representation and canonical recoding. International Journal of Computer Mathematics 87:13, Pp. 2871-2879, (2010)
. K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi. Signed Binary Representations Revisited. Annual International Cryptology Conference CRYPTO: Advances in Cryptology – CRYPTO 2004 pp 123-139, (2004).
. Blake, I., Seroussi, G., and Smart, N. Elliptic Curves in Cryptography. Cambridge University Press New York, NY, USA, 1999, ISBN:0-521-65374-6.
. J.A. Solinas. Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography, Springer, Volume 19, Issue 2–3, pp 195–249,
(2000).
. J. Jedwab and C.J. Mitchell. Minimum Weight Modified Signed-digit Representations and Fast Exponentiation. Electronics Letters, IET, 25, 1989.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2017 COMPUSOFT: An International Journal of Advanced Computer Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
©2023. COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY by COMPUSOFT PUBLICATION is licensed under a Creative Commons Attribution 4.0 International License. Based on a work at COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY. Permissions beyond the scope of this license may be available at Creative Commons Attribution 4.0 International Public License.
