EFFICIENT OPERATIONS IN LARGE FINITE FIELDS FOR ELLIPTIC CURVE CRYPTOGRAPHIC
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.
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.
Copyright (c) 2020 Yan-Haw Chen, Chien-Hsing Huang
This work is licensed under a Creative Commons Attribution 4.0 International License.
License and Copyright Agreement
In submitting the manuscript to the journal, the authors certify that:
- They are authorized by their co-authors to enter into these arrangements.
- The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal.
- That it is not under consideration for publication elsewhere.
- That its release has been approved by all the author(s) and by the responsible authorities – tacitly or explicitly – of the institutes where the work has been carried out.
- They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
- They agree to the following license and copyright agreement.
Authors who publish with International Journal of Engineering Technologies and Management Research agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors can enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or edit it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) before and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
For More info, please visit CopyRight Section