The International Arab Journal of Information Technology (IAJIT)


An Integrated Radix-4 Modular Divider/Multiplier

The increasing importance of security in computers and communication systems introduces the need for several public$key cryptosystems. The modular division and multiplication arithmetic operations in GF (p) and GF (2n) are extensively used in many public key cryptosystems, such as El$Gamal cryptosystem, Elliptic Curve Cryp tography (ECC), and the Elliptic Curve Digital Signature Algorithm (ECD SA). Processing these cryptosystems involves complicated computations, therefore, it is recommended to develop specialized hardware to speed up these computations. In this w ork, we propose efficient hardware design to compute both operation s (division and multiplication) in the binary extension finite filed (GF (2 n). The common points in both operations are utilized i n our design to reduce the design area and delay. m aking the proposed architecture faster than other previously proposed designs. The FPGA implementation of the proposed de sign shows better results compared with other designs in this field.  

[1] Bajard J., Didier L., and Kornerup P., An RNS Montgomery Modular Multiplication Algorithm, IEEE Transactions on Computers , vol. 47, no. 7, pp.766.776, 1998.

[2] Brent R. and Kung H., Systolic VLSI Arrays for Polynomial GCD Computation, IEEE Transactions on Computers , vol. 33, no. 8, pp. 731.736, 1984.

[3] ElGamal T., A Public Key Cryptosystem and Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory , vol. 31, no. 4, pp. 469.472, 1998.

[4] Gutub A., New Hardware Algorithms and Designs for Montgomery Modular Inverse Computation in Galois Fields GF(p) and GF(2 n), PhD Thesis , Oregon state University, USA, 2002.

[5] Gutub A., Fast 160.Bits GF(P) Elliptic Curve Crypto Hardware of High.Radix Scalable Multipliers, The International Arab Journal of Information Technology , vol. 3, no. 4, pp. 342. 349, 2006.

[6] Hasan M. and Bhargava V., Bit.Serial Systolic Divider and Multiplier for Finite Fields GF(2 m), IEEE Transaction on Computers , vol. 41, no. 8, pp. 972.980, 1992.

[7] Hellman M. and Difie W., New Directions in Cryptography, IEEE Transactions Information Theory , vol. 22, no. 6, pp. 644.654, 1976.

[8] Itoh T. and Tsujii S., A Fast Algorithm for Computing Multiplicative Inverses in GF(2 m) using Normal Bases, Information and Computation , vol. 78, no. 3, pp.171.177, 1988.

[9] Jararwah Y., A Hardware Architecture of an Efficient Modular Division Algorithm for Cryptographic Applications, Master s Thesis, Jordan University of Science and Technology, Jordan, 2007.

[10] Kaihara M. and Takagi N., A VLSI Algorithm for Modular Multiplication/Division, in Proceedings the IEEE 16 th Symposium on Computer Arithmetic , Japan, pp. 220.227, 2003.

[11] Montgomery P., Modular Multiplication without Trial Division, Mathematics of Computation , vol. 44, no. 170, pp. 519.521, 1985.

[12] Savas E., Tenca A., and Koc C., A Scalable and Unified Multiplier Architecture for Finite Fields GF(p) and GF(2 m), in Proceedings of Cryptographic Hardware and Embedded Systems , USA, pp. 281.296, 2000.

[13] Stallings W., Cryptography and Network Security Principles and Practices , Prentice Hall, USA, 2005.

[14] Tawalbeh L. and Tenca A., An Algorithm and Hardware Architecture for Integrated Modular Division and Multiplication in GF(p) and GF(2 n), in Proceedings of IEEE International Conference on Application$Specific Systems, Architectures, and Processors , USA, pp. 247. 257, 2004.

[15] Tawalbeh L., Tenca A., and Koc C., A Radix.4 Scalable Design, IEEE Potentials Magazine , vol. 24, no. 2, pp. 16.19, 2005.

[16] Tenca A. and Tawalbeh L., An Algorithm for Unified Modular Division in (GF(p) and (GF(2 n)) Suitable for Cryptographic Hardware, IEE Electronics Letters , vol. 40, no. 5, pp. 304. 306, 2004.

[17] Tenca A., Todorov G., and Koc C., High. Radix Design of a Scalable Modular Multiplier, in Proceedings of Cryptographic Hardware and Embedded Systems , pp.189.206, 2001.

[18] Hsing.Wu C., Ming.Wu C., Shieh M., and Hwang Y., High.Speed, Low Complexity 290 The International Arab Journal of Information Techn ology, Vol. 9, No. 3, May 2012 Systolic Designs of Novel Iterative Division Algorithms in GF(2m), IEEE Transactions on Computers , vol. 53, no. 3, pp. 375.380, 2004. Lo'ai Ali Tawalbeh is an assistant professor of Computer Engineering at Jordan University of Science and Technology (JUST), and a part time professor at the New York institute of Technology (NYIT).Jordan s campus. He received his BS in Electrical and Computer Engineering from Jordan University of Science and Technology in June of 200 0. Then he worked as a research and development engineer in a leading company, and then as a Teachi ng Assistant in JUST before he joined the graduate program at Oregon State University (OSU) in September 2001. He received his MS degree in electrical and computer engineering from Oregon Sta te University in October 2002, and his PhD MSc. He research interests include network and computer security. Intrusion detection and computer forensic s. Hardware implementations for cryptography, and cryptographic co.processor design using scalable modules, Elliptic Curve Cryptography, network security and embedded systems, FPGA design, VLSI design, computer architecture and finite field arit hmetic algorithms. Dr. Lo ai has many journal publications and conference proceedings in the above research topics. He received many grants and research awards . Yaser Jararweh received his Bsc and Msc from Jordan University of Science and Technology, Jordan in 2005, and 2007 respectively. He is now a PhD student at the Department of Electrical and Computer Engineering, The University of Arizona, USA. His research interest a re in Power and Performance Management of Large.scale Data Centers. Abidalrahman Mohammad is currently a PhD candidate in Engineering Mathematics and Internetworking Department at Dalhousie University MSc. His main research concern is to develop high throughput security protocols and cryptographic algorithms for bandwidth.intensiv e multimedia applications, as well as, energy efficie nt and low.power architectures such as wireless sensor networks. He received both his BSc and MSc Degrees in computer engineering under the supervision of Dr . Loai Tawalbeh, from Jordan University of Science and Technology in February, 2006 and July, 2007 respectively.