Modular exponentiation is an important operation in public-key cryptography. The Common-Multiplicand-Multiplication (CMM) modular exponentiation is an efficient exponentiation algorithm. This paper presents a novel method for speeding up the CMM modular exponentiation algorithm based on a Modified Montgomery Modular Multiplication (M4) algorithm. The M4 algorithm uses a new multi bit scan-multi bit shift technique by employing a modified encoding algorithm. In the M4 algorithm, three operations (the zero chain multiplication, the required additions and the nonzero digit multiplication) are relaxed to a multi bit shift and one binary addition in only one clock cycle. Our computational complexity analysis shows that the average number of required multiplication steps (clock cycles) is considerably reduced in comparison with other CMM modular exponentiation algorithms.
Accepté le :
DOI : 10.1051/ita/2015007
Mots-clés : Modular multiplication, canonical recoding, modular exponentiation, public-key cryptosystem, high speed arithmetic
@article{ITA_2015__49_3_255_0,
author = {Rezai, Abdalhossein and Keshavarzi, Parviz},
title = {Algorithm design and theoretical analysis of a novel {CMM} modular exponentiation algorithm for large integers},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {255--268},
publisher = {EDP-Sciences},
volume = {49},
number = {3},
year = {2015},
doi = {10.1051/ita/2015007},
mrnumber = {3434601},
zbl = {1404.68211},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2015007/}
}
TY - JOUR AU - Rezai, Abdalhossein AU - Keshavarzi, Parviz TI - Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2015 SP - 255 EP - 268 VL - 49 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2015007/ DO - 10.1051/ita/2015007 LA - en ID - ITA_2015__49_3_255_0 ER -
%0 Journal Article %A Rezai, Abdalhossein %A Keshavarzi, Parviz %T Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2015 %P 255-268 %V 49 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2015007/ %R 10.1051/ita/2015007 %G en %F ITA_2015__49_3_255_0
Rezai, Abdalhossein; Keshavarzi, Parviz. Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 255-268. doi : 10.1051/ita/2015007. http://www.numdam.org/articles/10.1051/ita/2015007/
and , Signed digit representations of minimal Hamming weight. IEEE Trans. Comput. 42 (1993) 1007–1010. | DOI
and , High-radix Montgomery multiplication on reconfigurable hardware. IEEE Trans. Comput. 50 (2001) 759–764. | DOI
, A signed binary multiplication technique. J. Mech. Appl. Math. 4 (1951) 236–240. | DOI | MR | Zbl
S.R. Dusse and B.S Kaliski, A cryptographic library for the Motorola DSP 56000. Proc. of Adv. Cryptol. EUROCRYPT’90. In vol. 73 of Lect. Notes Comput. Sci. (1990) 230–244. | Zbl
and , Exponentiation using Canonical Recoding. Theoret. Comput. Sci. 129 (1994) 407–417. | DOI | MR
Y. Fan, T. Ikenaga and S. Goto, A high-speed design of Montgomery multiplier. IEICE Trans. Fundam. Electron., Commun. Computers E91-A (2008) 971–977.
A.P. Fournaris and O. Koufopavlou, A new RSA encryption architecture and hardware implementation based on optimized Montgomery multiplication. In Proc. of IEEE ISCAS (2005) 4645–4648.
and , A common-multiplicand method to the Montgomery algorithm for speeding up exponentiation. Inf. Process. Lett. 66 (1998) 105–107. | DOI | MR | Zbl
, and , Low-power, high-speed unified and scalable word-based radix-8 architecture for Montgomery modular multiplication. Arab J. Sci. Eng. 39 (2014) 7847–7863. | DOI
P. Keshavarzi and C. Harrison, A New Modular Multiplication Algorithm for VLSI Implementation of Public-Key Cryptography. In Proc. of 1st Int. Symp. Commun. Syst. Digit. signal Process. CSDSP98, Sheffield, UK (1998) 516–519.
and , Parallel exponentiation using common-multiplicand-multiplication and signed-digit-folding techniques. Int. J. Comput. Math. 81 (2004) 1187–1202. | DOI | MR | Zbl
, Modular multiplication without trial division. Math. Comput. 44 (1985) 519–521. | DOI | MR | Zbl
and , High-performance hardware of the sliding-window method for parallel computation of modular exponentiations. Int. J. Parallel program. 37 (2009) 537–555. | DOI | Zbl
and , A hardware/software co-design versus hardware-only implementation of modular exponentiation using the sliding-window method. J. Circuits Syst. Comput. 18 (2009) 295–310. | DOI
, and , A parallel and uniformly k-partition method for Montgomery multiplication. IEEE Trans. Comput. 63 (2014) 2122–2133. | DOI | MR | Zbl
A. Rezai and P. Keshavarzi, High-Performance Implementation Approach of Elliptic Curve Cryptosystem for Wireless Network Applications. In Proc. of IEEE. Int. Conf. Consum. Electron. Commun. Netw. (CECNet 2011). Xianning, China (2011) 1323–1327.
A. Rezai and P. Keshavarzi, High-performance modular exponentiation algorithm by using a new modified modular multiplication algorithm and common-multiplicand-multiplication method. In Proc. of IEEE. World Congr. Internet Secur. London, UK (2011) 192–197.
and , CCS Representation: A new non-adjacent form and its application in ECC. J. Basic. Appl. Sci. Res. 2 (2012) 4577–4586.
and , A new finite field multiplication algorithm to improve elliptic curve cryptosystem implementations. J. Inf. Syst. Telecom. 1 (2013) 119–129.
and , High-throughput modular multiplication and exponentiation algorithms using multibit-scan-multibit-shift technique. IEEE Trans. Very Large Scale Integr. Syst. 23 (2015) 1710–1719. | DOI
, Binary arithmetic. Adv. Comput. 1 (1960) 231–308. | DOI | MR
, and , Modular multiplication and exponentiation architectures for fast RSA cryptosystem based on digit serial computation. IEEE Trans. Indust. Electron. 58 (2011) 3101–3109. | DOI
and , Improving the computational efficiency of modular operations for embedded systems. J. Syst. Arch. 60 (2014) 440–451. | DOI
and , The distributions of individual bits in the output of multiplicative operations. Crypto. Commun. 7 (2015) 71–90. | DOI | MR | Zbl
, and , A radix-4 scalable design. IEEE Potentials. 24 (2005) 16–18. | DOI
A.F. Tenca and L. Tawalbeh, An Efficient and Scalable Radix-4 Modular Multiplier Design using Recoding Techniques. In Proc. of IEEE. Asilomar Conf. signals, syst., comput., Monterey, CA (2003) 1445–1450.
and , Parallelized radix-4 scalable Montgomery multipliers. J. Integr. Sysyt. 3 (2008) 39–45.
, Systolic modular multiplication. IEEE Trans. Comput. 42 (1993) 376–378. | DOI
, and , Fast, compact and symmetric modular exponentiation architecture by common-multiplicand Montgomery modular multiplication. Integr. VLSI J. 36 (2013) 323–332. | DOI
C.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.
, An efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation. Inform. Sci. 179 (2009) 410-421. | DOI | MR | Zbl
, and , Fast modular multiplication based on complement representation and canonical recoding. Int. J. comput. Math. 87 (2010) 2871–2879. | DOI | MR | Zbl
, and , Low latency systolic Montgomery multiplier for finite field GF(2 based on pentanomials. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21 (2013) 385–389. | DOI
, and , Bipartite modular multiplication with twice the bit-length of multipliers. Int. J. Inform. Security 8 (2009) 13–23. | DOI
Cité par Sources :
