A Survey on Inversion over Prime and Binary Fields
Subject Areas : electrical and computer engineeringReza Roohghalandari 1 , Hatameh Mosanaei Boorani 2 , s. bayat sarmadi 3
1 -
2 -
3 -
Keywords: Inversion algorithmsfinite fieldsFermat little theoremextended Euclidean algorithm,
Abstract :
Public key cryptography is one of the common cryptosystems mainly because it does not have key agreement issue. One important operation in these cryptosystems is inversion. Therefore, improving its performance gains significant attention. In this paper, inversion operation over binary and prime fields are surveyed considering time and area complexity. Moreover, the implementation results on FPGA and ASIC platforms are investigated and analyzed.
[1] E. Wenger and M. Hutter, "Exploring the design space of prime field vs. binary field ECC-hardware implementations," in Proc. Nordic Conf. on Secure IT Systems, pp. 256-271, Tallinn, Estonia, 26-28 Oct. 2011.
[2] J. P. Deschamps, J. L. Imana, and G. D. Sutter, Hardware Implementation of Finite-Field Arithmetic, New York: McGraw- Hill, 2009.
[3] Q. Liao, "The Gaussian normal basis and its trace basis over finite fields," Number Theory, vol. 132, no. 7, pp. 1507-1518, Jul. 2007.
[4] A. Brauer, "On addition chains," Bulletin of the American Mathematical Society, vol. 45, no. 10, pp. 736-739, 1939.
[5] D. E. Knuth, The Art of Computer Programming: Sorting and Searching: Volume 3, 1973.
[6] P. L. Montgomery, "Modular multiplication without trial division," Mathematics of Computation, vol. 44, no. 170, pp. 519-521, Dec. 1985.
[7] A. A. Gutub, A. F. Tenca, and C. K. Koc, "Scalable VLSI architecture for GF(p) montgomery modular inverse computation," in Proc. of IEEE Computer Society Annual Symp.on VLSI, pp. 53-58, Pittsburgh, PA, USA, 25-26 Apr. 2002.
[8] A. Daly, W. Marnane, T. Kerins, and E. Popovici, "Fast modular division for application in ECC on reconfigurable logic," Lecture Notes in Computer Science, pp. 786-795, Sept. 2003.
[9] J. Bucek and R. Lorencz, "Comparing subtraction-free and traditional AMI," in Proc. of 9th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, DDECS'06, pp. 95-97, Prague, Czech Republic, 18-21 Apr. 2006.
[10] R. P. Brent and H. T. Kung, "Systolic VLSI arrays for polynomial GCD computation," IEEE Trans. on Computers, vol. 33, no. 8, pp. 731-736, Aug. 1984.
[11] H. T. Kung, "Why systolic arrays?" Computer, vol. 15, pp. 37-46, Jan. 1982.
[12] J. Stein, "Computational problems associated with Racah Algebra," J. of Computational Physics, vol. 1, no. 3, pp. 397-405, Feb. 1967.
[13] C. H. Wu, C. M. Wu, M. D. Shieh, and Y. T. Hwang, "High-speed, low complexity systolic designs of novel iterative division algorithms in GF (2m)," IEEE Trans. on Computers, vol. 53, no. 3, pp. 375-380, Mar. 2004.
[14] H. Brunner, A. Curiger, and M. Hofstette, "On computing multiplicative inverses in GF (2m)," IEEE Trans. on Computers, vol. 42, no. 8, pp. 1010-1015, Aug. 1993.
[15] J. H. Guo and C. L. Wang, "Systolic array implementation of Euclid's algorithm for inversion and division in GF (2m)," IEEE Trans. on Computers, vol. 47, no. 10, pp. 1161-1167, May 1998.
[16] Z. Yan and D. B. Sarwate, "High-speed systolic architectures for finite field inversion," Integration: The VLSI J., vol. 38, no. 3, pp. 383-398, Jan. 2005.
[17] M. Mozaffari-Kermani, R. Azarderakhsh, C. Y. Lee, and S. Bayat-Sarmadi, "Reliable concurrent error detection architectures for extended euclidean-based division over GF (2m)," IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 22, no. 5, pp. 995-1003, May 2014.
[18] S. Kim, N. S. Chang, C. H. Kim, Y. H. Park, and J. Lim, "A fast inversion algorithm and low-complexity architecture over GF (2m)," In: Hao Y. et al. (eds) Computational Intelligence and Security, CIS'05, 8 pp., Lecture Notes in Computer Science, vol 3802. Springer, Berlin, Heidelberg ,2005.
[19] Z. Yan, D. V. Sarwate, and Z. Liu, "Hardware-efficient systolic architectures for inversions in GF (2m)," IEE Proceedings-Computers and Digital Techniques., vol. 145, no. 4, pp. 272-278, Jul. 1998.
[20] Z. Yan, "Digit-serial systolic architectures for inversions over GF (2m)," in Proc. IEEE Workshop on Signal Processing Systems Design and Implementation, pp. 77-82, Banff, Canada, 2-4 Oct. 2006.
[21] A. K. Daneshbeh and M. A. Hasan, "A class of unidirectional bitserial systolic architectures for multiplicative inversion and division over GF (2m)," IEEE Trans. Computer, vol. 54, no. 3, pp. 370-380, Mar. 2005.
[22] J. H. Guo and C. L. Wang, "Bit-serial systolic array implementation of Euclid's algorithm for inversion and division in GF (2m)," in Proc. of Technical Papers. Int. Symp. on VLSI Technology, Systems, and Applications, pp. 113-117, Taipei, Taiwan, 3-5 Jun. 1997.
[23] J. Fan, L. Batina, and I. Verbauwhede, "Design and design methods for unified multiplier and inverter and its application for HECC," Integration, VLSI J., vol. 44, no. 4, pp. 280-289, Sept. 2011.
[24] K. Kobayashi and N. Takagi, "Fast hardware algorithm for division in G (2m) based on the extended euclid's algorithm with parallelization of modular reductions," IEEE Trans. on Circuits and Systems II: Express Briefs, vol. 56, no. 8, pp. 644-648, Aug. 2009.
[25] A. Ibrahim, T. F. Al-Somani, and F. Gebali, "New systolic array architecture for finite field inversion," Canadian J. of Electrical and Computer Engineering, vol. 40, no. 1, pp. 23-30, Winter 2017.
[26] C. C. Wang, et al., "VLSI architectures for computers multiplications and inverses in GF (2m)," IEEE Trans. on Computers, vol. 34, no. 8, pp. 709-717, Aug. 1985.
[27] T. Itoh and S. Tsujii, "A fast algorithm for computing multiplicative inverses in GF (2m) using normal bases," Information and Computation, vol. 78, no. 3, pp. 171-177, Sept. 1988.
[28] N. Takagi, "A fast algorithm for multiplicative inversion in GF (2m) using normal basis," IEEE Trans. on Computers, vol. 42, no. 9, pp. 1141-1146, May 1993.
[29] V. Dimitrov and K. Jarvinen, "Another look at inversions over binary fields," in Proc. IEEE Symp. on Computer Arithmetic, ARITH’13, pp. 211-218, Austin, TX, USA, 7-10 Apr. 2013.
[30] R. Azarderakhsh and A. Reyhani-Masoleh, "Low-complexity multiplier architectures for single and hybrid-double multiplications in Gaussian normal bases," IEEE Trans. on Computers, vol. 62, no. 4, pp. 744-757, Apr. 2013.
[31] R. Azarderakhsh, K. Jarvinen, and V. Dimitrov, "Fast inversion in GF (2m) with normal basis using hybrid-double multipliers," IEEE Trans. on Computers, vol. 63, no. 4, pp. 1041-1047, Apr. 2014.
[32] J. Hu, W. Guo, J. Wei, and R. C. Cheung, "Fast and generic inversion architectures over GF (2m) using modified Itoh-Tsujii algorithms," IEEE Trans. on Circuits and Systems II: Express Briefs, vol. 62, no. 4, pp. 367-371, Apr. 2015.
[33] K. Jarvinen, V. Dimitrov, and R. Azarderakhsh, "A generalization of addition chains and fast inversions in binary fields," IEEE Trans. on Computers, vol. 64, no. 9, pp. 2421-2432, Sept. 2015.
[34] M. Nocker, Data Structures for Parallel Exponentiation in Finite Fields, Ph.D Diss., 2001.
[35] B. Rashidi, "High-speed hardware implementation of Gaussian normal basis inversion algorithm over F2m," Microelectronics J., vol. 63, pp. 138-147, May 2017.
[36] J. Guajardo and C. Paar, "Itoh-Tsujii inversion in standard basis and its application in cryptography and codes," Designs, Codes and Cryptography, vol. 25, no. 2, pp. 207-216, Nov. 2002.
[37] F. Rodriguez-Henriquez, N. Cruz-Cortes, and N. A. Saqib, "A fast implementation of multiplicative inversion over GF (2m)," in Proc. Int. Conf. on Information Technology: Coding and Computers, ITCC’05, vol. 1, pp. 574-579, Covtat, Croatia, 20-23 Jun. 2005.
[38] F. Rodriguez-Henriquez, G. Morales-Luna, N. A. Saqib, and N. Cruz-Cortes, "Parallel Itoh-Tsujii multiplicative inversion algorithm for a special class of trinomials," Designs, Codes and Cryptography, vol. 45, no. 1, pp. 19-37, Jan. 2007.
[39] C. Rebeiro, S. S. Roy, S. S. Reddy, and D. Mukhopadhyay, "Revisiting the Itoh-Tsujii inversion algorithm for FPGA platforms," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 19, no. 8, pp. 1508-1512, Aug. 2011.
[40] V. R. Venkatasubramani, N. Murali, and S. Rajaram, "An improved quad Itoh-Tsujii algorithm for FPGAs," IEICE Electronics Express, vol. 10, no. 18, 10 pp., Article -20130612, Jan. 2013.
[41] S. S. Roy, C. Rebeiro, and D. Mukhopadhyay, "Theoretical modeling of the Itoh-Tsujii inversion algorithm for enhanced performance on k-LUT based FPGAs," in Proc.Design, Automation and Test in Europe Conf. and Exhibition, DATE’16, 6 pp., Grenoble, France, 14-18 Mar. 2011.
[42] S. S. Roy, C. Rebeiro, and D. Mukhopadhyay, "Generalized high speed Itoh-Tsujii multiplicative inversion architecture for FPGAs," Integration, The VLSI J., vol. 45, no. 3, pp. 307-315, Jun. 2012.
[43] L. Parrilla, A. Lloris, E. Castillo, and A. Garcia, "Minimum-clock-cycle Itoh-Tsujii algorithm hardware implementation for cryptography applications over GF (2m) fields," Electronics Letters, vol. 48, no. 18, pp. 1126-1128, Aug. 2012.
[44] L. Li and S. Li, "Fast inversion in GF (2m) with polynomial basis using optimal addition chains," in Proc. IEEE Int Symp. in Circuits and Systems, ISCAS’17, 4 pp., Baltimore, MD, USA, 28-31 May 2017.
[45] J. Maitin-Shepard, "Optimal software-implemented Itoh-Tsujii inversion for GF (2m)," Designs, Codes and Cryptography, vol. 82, no. 2, pp. 301-318, Aug. 2017.
[46] F. Rodriguez-Henriquez, N. A. Saqib, A. D. Perez, and C. K. Koc, Cryptographic Algorithms on Reconfigurable Hardware, Springer-Verlag US, 2007.
[47] J. Li, Z. Li, C. Xue, J. Zhang, W. Gao, and S. Cao, "A fast modular inversion FPGA implementation over GF (2m) using modified x2n unit," in Proc. IEEE Int. Symp. on Circuits and Systems, ISCAS'18, 5 pp., Florence, Italy, 27-30 2018.
[48] G. M. de Dormale and J. J. Quisquater, "High-speed hardware implementations of elliptic curve cryptography: a survey," J. of Systems Architecture, vol. 53, no. 2-3, pp. 72-84, Feb./Mar. 2007.
[49] B. Vallee, "Dynamics of the binary Euclidean algorithm: functional analysis and operators," Algorithmic, vol. 22, no. 4, pp. 660-685, Mar. 1998.
[50] A. Akhavi and B. Vallee, "Average bit-complexity of Euclidean algorithms," in Proc. Int. Colloquium on Automata, Languages, and Programming, pp. 373-387, Ceneva, Switzerland, 14-21 Jul. 2000.
[51] H. Mahdizadeh and M. Masoumi, "Novel architecture for efficient FPGA implementation of elliptic curve cryptographic processor over GF (2163)," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 21, no. 12, pp. 2330-2333, Dec. 2013.
[52] N. Takagi, "A VLSI algorithm for modular division based on the binary GCD algorithm," IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E81-A, no. 5, pp. 724-728, 1998.
[53] L. A. Tawalbeh, A. F. Tenca, S. Park, and C. K. Koc, "A dual-field modular division algorithm and architecture for application specific hardware," in Proc. IEEE the 38th Asilomar on Signals, Systems and Computers Conf., vol. 1, pp. 483-487, Nov. 2004.
[54] A. Mrabet, N. El-Mrabet, B. Bouallegue, S. Mesnager, and M. Machhout, "An efficient and scalable modular inversion/division for public key cryptosystems," in Proc. Int. Conf. on Engineering & MIS, ICEMIS’17, 6 pp., Astana, Kazakhstan, 6-8 Jun. 2017.
[55] E. Savas and C. K. Koc, "Montgomery inversion," J. of Cryptographic Engineering, vol. 8, no. 3, pp. 201-210, Apr. 2018.
[56] J. W. Bos, "Constant time modular inversion," J. of Cryptographic Engineering, vol. 4, no. 4, pp. 275-281, Aug.. 2014.
[57] D. J. Bernstein, "Curve25519: new Diffie-Hellman speed records," in Proc. Int. Workshop on Public Key Cryptography, pp. 207-228, New York, NY, USA, 5-7 Nov. 2006.
