Frequency Analysis of 32-bit Modular Divider Based on Extended GCD Algorithm for Different FPGA chips

Qasem Abu Al-Hiaja; Abdullah AlShuaibi; Ahmad Al Badawi

doi:10.24297/ijct.v17i1.6992

Authors

Qasem Abu Al-Hiaja Department of Electrical Engineering, King Faisal University, Al-Ahsa, 31982, Saudi Arabia
Abdullah AlShuaibi Materials Science and Engineering Department, Cornell University, Kimball Hall, ithaca, 14850 NY
Ahmad Al Badawi Department of Electrical and Computer Engineering, National University of Singapore, 119077 Singapore

DOI:

https://doi.org/10.24297/ijct.v17i1.6992

Keywords:

Modular Arithmetic, Extended Euclidian's GCD, Field Programmable Gate Array (FPGA), Hardware Synthesize, Coprime numbers, Public Key Cryptography.

Abstract

Modular inversion with large integers and modulus is a fundamental operation in many public-key cryptosystems. Extended Euclidean algorithm (XGCD) is an extension of Euclidean algorithm (GCD) used to compute the modular multiplicative inverse of two coprime numbers. In this paper, we propose a Frequency Analysis study of 32-bit modular divider based on extended-GCD algorithm targeting different chips of field-programmable gate array (FPGA). The experimental results showed that the design recorded the best performance results when implemented using Kintex7 (xc7k70t-2-fbg676) FPGA kit with a minimum delay period of 50.63 ns and maximum operating frequency of 19.5 MHz. Therefore, the proposed work can be embedded with many FPGA based cryptographic applications.

Downloads

References

[1] V. S. Miller. Use of Elliptic Curves in Cryptography. Exploratory Computer Science. IBM Research, Springer-Verlag, 1998.
[2] D. Kahn. The Codebreakers. 1967, ISBN 0684831309.
[3] S. Levy. Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age, 2001, ISBN 0140244328.
[4] R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 1978.
[5] Q. Abu Al-Haija, M. Al-Jaâ€™fari and M. A. Smadi. A Comparative Study up to 1024 bit Euclid's GCD algorithm FPGA Implementation and Synthesizing. IEEE 5th International Conference on Electronic Devices, Systems and Applications (ICEDSA), 2016.
[6] Q. Abu Al-Haija, et. al. Efficient FPGA Implementation of RSA Coprocessor Using Scalable Modules. Procedia Computer Science, Elsevier, 2014.
[7] Bigou, K., Tisserand, A. Improving modular inversion in RNS using the plusminus method. In: Bertoni, G., Coron, J.-S. (eds.) CHES2013. LNCS, vol. 8086, pp. 233â€“249. Springer, Heidelberg, 2013.
[8] A. Cilardo, Modular inversion based on digit-level speculative addition, Electronics Letters ( Volume: 49, Issue: 25, December 5 2013 ), IET.
[9] M.S.Hossain. High-Performance FPGA Implementation of Modular Inversion over F_256 for Elliptic Curve Cryptography, IEEE International Conference on Data Science & Data Intensive Systems, ICDSDIS 2015.
[10] J. HlavÃ¡Ä and R. LÃ³rencz. Arithmetic Unit for Computations in GF(p) with Left-Shifting Multiplicative Inverse Algorithm, Architecture of Computing Systems, ARCS 2013. Lecture Notes in Computer Science, vol 7767. Springer, 2013.
[11] S. Vollala, Hardware design for multiplicative modular inverse based on table look up technique, International Conference on Computing & Network Communications (CoCoNet), 2015.
[12] P. Montague. Method of performing modular inversion. US Patent 6609141, 2003.
[13] T. Koshy. Elementary number theory with applications, 2nd edition. ISBN 9780123724878.