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

  • 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
Keywords: Modular Arithmetic, Extended Euclidian's GCD, Field Programmable Gate Array (FPGA), Hardware Synthesize, Coprime numbers, Public Key Cryptography.


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.


[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.