Computational Sciences and Engineering

Current Issue

By Issue

By Author

By Subject

Author Index

Keyword Index

About Journal

Aims and Scope

Editorial Board

Publication Ethics

Indexing and Abstracting

Related Links

FAQ

Peer Review Process

Journal Metrics

News

Algorithm Design and Theoretical Analysis of a New Bit Forwarding Large Integer Modular Exponentiation Algorithm

Document Type : Original Article

Authors

1 Department of Electrical Engineering, University of Science and Culture, Tehran, Iran

2 ACECR Institute of Higher Education, Isfahan Branch, Isfahan, Iran

Abstract

One of the most principal operations in many PKCs is Modular Exponentiation (ME). This operation is usually performed by successive modular multiplications. So, the efficiency of these PKCs is released on the efficiency of the Modular Multiplication (M2) and modular exponentiation implementation. Therefore, it is essential to minimize the execution time of the M2 and the number of required M2 for performing the ME operation. This paper proposes a novel ME algorithm. In the developed algorithm, the Bit Forwarding (BF) and multibit-scan-multibit-shift techniques are employed for the performance improvement in the ME operation. The complexity analysis is accomplished to show that the developed exponentiation algorithm has benefit in the number of required multiplications. The results indicate that the presented algorithm improves the results compared to other modular exponentiation algorithms by about 11%-85%.

Keywords

References
[1] R. Dusse and B. S Kaliski, A cryptographic library for the Motorola DSP 56000. Proc. Of Adv. Cryptol. EUROCRYPT’90. 73 (1990) 230–244.
[2] Egecioglu and C. K. Koc, Exponentiation using Canonical Recoding. Theoret. Comput.Sci. 129 (1994) 407–417.
[3] Daniel M.Gordon, A survey of fast exponentiation methods. Journal of algorithms. 27(1998) 129-146.
[4] C. Ha and S. J. Moon, A common-multiplicand method to the Montgomery algorithm for speeding up exponentiation. Inf. Process. Lett. 66 (1998) 105–107.
[5] Huang, K. Gaj and T. El-Ghazawi, New hardware architectures for Montgomery modular multiplication algorithm. IEEE Trans. Comput. 60 (2011) 923-936.
[6] S.-R. Kuang, J. P. Wang, K. C. Chang, and H. W. Hsu, Energy-efficient high-throughput Montgomery modular multipliers for RSA cryptosystems. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21(2013) 1999–2009.
[7] P.L. Montgomery, Modular multiplication without trial division. Math. Comput. 44 (1985) 519–521.
[8] Miyamoto, N. Homma, T. Aoki and A. Satoh, Systematic design of RSA processors based on high-radix Montgomery multipliers. IEEE Trans. Very Large Scale Integr. (VLSI) Syst.19 (2011) 1136–1146.
[9] L.M. Mourelle and N. Nedjah, Fast reconfigurable hardware for the m-ary modular exponentiation. Proc. Euromicro Symp. on Digital System Design: Architectures, Methods and Tools . (2004) 516–523.
[10] Nedjah and L. M. Mourelle, Efficient hardware for modular exponentiation using the sliding-window method with variable-length partitioning. in Proc. 9th Int. Conf. Young Comput. Sci. (2008) 1980–1985.
[11] A.Rezai and P.Keshavarzi, A new CMM-NAF modular exponentiation algorithm by using a new modular multiplication algorithm. Trends in applied sciences research. 7(2012) 240-247.
[12] A.Rezai and P.Keshavarzi, Algorithm design and theorical analysis of a novel CMM modular exponentiation algorithm for large integers.RAIRO, Theor, Inf. appl. 49(2015) 255-268.
[13] Rezai and P. Keshavarzi, High-Throughput Modular Multiplication and Exponentiation Algorithm Using Multibit-Scan-Multibit-Shift technique. IEEE Trans. VLSI syst. 23(2015) 1710-1719.
[14] Rezai and P. Keshavarzi, Compact SD: A New Encoding Algorithm and Its Application in Multiplication. Int. j. comput. Math.94 (2017) 554-569.
[15] A.Rezai and P.Keshavarzi, high-performance scalable architecture for modular multiplication using a new digit-serial computation, Microelectronics journal. 55 (2016) 169-178.
[16] A.Rezai and P.Keshavarzi, High-perormance modular exponentiation algorithm by using a new modified modular multiplication algorithm and common-multiplicand multiplication method, 2011 World Congress on Internet Security (WorldCIS-2011), London.(2011) 192-197.
[17] D. Sutter, J. P. Deschamps and J. L. Imana, Modular multiplication and exponentiation architecture for fast RSA cryptosystem based on digit serial computation, IEEE Trans. Ind. Electron. 58 (2011) 3101-3109.
[18] S.Vollala, K.Geetha and N.Ramasubramanian, Efficient modular exponential algorithms compatible with hardware implementation of public-key cryptography. Security Comm. Networks. 9(2016)  3105–3115
[19] D. Walter, Systolic modular multiplication, IEEE Trans. Comput.42 (1993) 376-378.
[20] L. Wu, D. C. Lou and T. J. Chang, An Efficient Montgomery Exponentiation Algorithm for Public-key Cryptosystem. In Proc. of IEEE. Int. Conf. Intell. Security Inform., Taipei,Taiwan (2008) 284–285
[21] L. Wu, D. C. Lou and T. J. Chang, Fast modular multiplication based on complement representation and canonical recoding. Int. J. comput. Math. 87 (2010) 2871–2879
[22] C.L. Wu, An efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation. Inform. Sci. 179 (2009) 410-421.
[23] Wu, S. Li, and L. Liu, Fast, compact and symmetric modular exponentiation architecture by common-multiplicand Montgomery modular multiplications. Integr., VLSI J. 36(2013) 323–332.
[24] Xie, J. J. He and P. K. Meher, Low latency systolic Montgomery multiplier for finite field GF(2m) based on pentanomials, IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21 (2013) 385-389.
Computational Sciences and Engineering
Volume 2, Issue 2
September 2022
Pages 227-238
Files
Share
How to cite
Statistics