EFFICIENT OPERATIONS IN LARGE FINITE FIELDS FOR ELLIPTIC CURVE CRYPTOGRAPHIC

  • Yan-Haw Chen Department of Department of Information Engineering I-Shou University, Kaohsiung, Taiwan 84008, Republic of China.
  • Chien-Hsing Huang Department of Information Engineering, I-Shou University, Kaohsiung city 84001, Taiwan https://orcid.org/0000-0002-6785-070X
Keywords: Elliptic Curve, Encryption, Finte Field, Horner Rule, Dynamic Lookup Table, Multiplication.

Abstract

An efficient method to compute the finite field multiplication for Elliptic Curve point multiplication at high speed encryption of the message is presented. The methods of the operations are based on dynamic lookup table and modified Horner rule method. The modified Horner rule method is not only to finite field operations but also to Elliptic curve scalar multiplication in the encryption and decryption. By comparison with using Russian Peasant method and in the new proposed method, one of the advantages of utilizing the proposed algorithm is that in the Elliptic Curve point addition are reduced by a factor of three in GF (2163). Therefore, using the Algorithm 1 running on Intel CPU, computation cost of the multiplication method is above 70% faster than using standard multiplication by Russian Peasant method. Ultimately, the proposed Algorithm 1 for evaluating multiplication can be made regular, simple and suitable for software implementations.

 

Downloads

Download data is not yet available.

References

Y. H. Chen, C. F. Huang, J. Chang, Decoding of binary quadratic residue codes with hash table, IET Communications, Vol. 10, No. 1, 2016, 122-130. DOI: https://doi.org/10.1049/iet-com.2015.0546

N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, Issue 48, 1987, 203-209. DOI: https://doi.org/10.1090/S0025-5718-1987-0866109-5

M. Scott, Optimal irreducible polynomials for GF(2m) arithmetic. Cryptology ePrint Archive, Report 2007/192.

A. Hasan, M. Z. Wang, and V. K. Bhargava, Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields GF(2m), IEEE Trans. Comput., Vol. 41, No. 8, 1992, 962-971. DOI: https://doi.org/10.1109/12.156539

E. Savas and C. Ko_c, Finite Field Arithmetic for Cryptography, IEEE Journals, Circuits and Systems Magazine, Vol. 10, No 2, 2010, 40-56. DOI: https://doi.org/10.1109/MCAS.2010.936785

B. Ansari and M. Hasan, High-Performance Architecture of Elliptic Curve Scalar Multiplication, IEEE Transactions on Computers, Vol. 57, No 11, 2011, 1443-1453. DOI: https://doi.org/10.1109/TC.2008.133

Kobayashi and N. Takagi, A Combined Circuit for Multiplication and Inversion in GF(2m), IEEE Transactions on Circuits and Systems, Vol 55, No 11,2008, 1144-1148. DOI: https://doi.org/10.1109/TCSII.2008.2003347

Jing, J. Chen, Z. Chen and Y. Chen, Low Complexity Architecture for Multiplicative Inversion in GF(2m), IEEE Asia Pacific Conference on Circuits and Systems (APCCAS 2006), 2006, 1492-1495. DOI: https://doi.org/10.1109/APCCAS.2006.342505

Luo, J., Bowers, K. D., Oprea, A., and Xu, L. Efficient software implementations of large finite fields GF (2n) for secure storage applications. ACM Transactions on Storage (TOS), Vol 8, No1, 2012, 2 DOI: https://doi.org/10.1145/2093139.2093141

C. C. Wang, T. K. Truong, H. M. Shao and L. J. Deutsch, VLSI Architectures for computing Multiplications and Inverses in GF(2m), TDA Progress Report 42-75, 1983, 52-63.

Mahboob and N. Ikram, Lookup table-based multiplication technique for GF(2m) with cryptographic significance, IEE Proc.-Commun, Vol. 152, No. 6, 2005, pp. 965-974. DOI: https://doi.org/10.1049/ip-com:20050022

W. S. Brwon, On Euclid’s Algorithm and the computation of polynomial greatest common divisors, Journal of the Association for Computing Machinery, Vol. 18, 1971, 478-504. DOI: https://doi.org/10.1145/321662.321664

F. Dong and Y. Li, A Novel Shortest Addition Chains Algorithm Based on Euclid Algorithm, 4th International Conference on Wireless Communications, Networking and Mobile Computing, 2008, pp. 1-4. DOI: https://doi.org/10.1109/WiCom.2008.1138

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, 2002, 1573-7586. DOI: https://doi.org/10.1023/A:1013860532636

G. B. Agnew, R. C. Mullin, and S. A. Vanstone, An Implementation of Elliptic Curve Cryptosystems over F2155, IEEE J. Selected Areas in Comm., Vol. 11, 1993, 804-813. DOI: https://doi.org/10.1109/49.223883

Y. Choi, H. W. Kim, and M. S. Kim, Implementation of elliptic curve cryptographic coprocessor over GF (2163) for ECC protocols, in Proceedings of the 2002 International Technical Conference on Circuits/Systesm, Computers, and Communications, 2002, 674-677.

S. Kumar Elliptic Curve Cryptography for constrained devices, Bochum Research Bibliography, 2006.

W. Diffie and M. E. Hellman, New Directions in Cryptography, IEEE Trans. Inf. Theory, vol 22, 1976 664-654. DOI: https://doi.org/10.1109/TIT.1976.1055638

D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curves Cryptogra-phy. Springer, 2004.

P. Gaudry, F. Hess and N.P., Smart. Constructive and destructive facets of Weil descent on elliptic curves. Preprint, 2000.

Published
2020-07-03
How to Cite
Chen, Y.-H., & Huang, C.-H. (2020). EFFICIENT OPERATIONS IN LARGE FINITE FIELDS FOR ELLIPTIC CURVE CRYPTOGRAPHIC. International Journal of Engineering Technologies and Management Research, 7(6), 141-151. https://doi.org/10.29121/ijetmr.v7.i6.2020.712