ELECTROTECHNIC AND COMPUTER SYSTEMS, Odessa national polytechnic university

FPGA CORES FOR FAST MULTIPLICATIVE INVERSE CALCULATION IN GALOIS FIELDS

Abstract:

There are two common methods for division in a Galois Field GF(2^m): extended Euclidean algorithm for polynomial basis and exponentiation method for normal basis. The disadvantage of first is dependence of division time on the value of operands. So in the study some undependable on operand values methods based on fast multiplication are tested to select ones with the best hardware and time complexity for polynomial basis. All methods were implemented as FPGA cores, their work was verified by simulation.

Authors:

Elias Rodrigue M., PhD ( rodrigue.elias@liu.edu.lb, ORCID ID: 0000-0003-4506-0368 )
Hlukhov Valerij S., Dr. of Science, Professor ( glukhov@polynet.lviv.ua, ORCID ID:0000-0002-0542-7447 )
Ivan Zholubak, ( ivanzholubak7@ukr.net, ORCID ID: 0000-0001-8871-7222 )
Rahma Mokhammed K., ( muhamed_kadhem@yahoo.com, ORCID ID: 0000-0002-8377-1833 )

Keywords

binary Galois Field, fast multiplication, multiplicative inverse, extended Euclidean algorithm, exponentiation, FPGA

DOI

http://dx.doi.org/ 10.15276/eltecs.27.103.2018.26

References

1. DSTU 4145-2002 (2003), Cryptographic Techniques. Digital Signatures Based on Elliptic Curves. Generation and Verification [DSTU 4145-2002. Informatsiini tekhnolohii. Kryptohrafichnyi zakhyst informatsii. Tsyfrovyi pidpys, shcho gruntuietsia na eliptychnykh kryvykh. Formuvannia ta perevirka]. State Committee of Ukraine for Technical Regulation and Consumer Policy, Kyiv, Ukraine (In Ukrainian).

2. Hankerson, D., Menezes, A., Vanstone, S. (2004), Guide to Elliptic Curve Cryptography, Springer-Verlag New York: ISBN 0-387-95273-4.

4. Deschamps, J.-P., Imaña, J. L., Sutter, G. (2009), Hardware Implementation of Finite-Field Arithmetic. McGraw Hill. ISBN: 978-0-0715-4581‑5.

6. Itoh, T., Teechai, O., and Tsujii, S. (1986), “A Fast Algorithm for Computing Multiplicative Inverses in GF(2^t) Using Normal Bases,” J. Society for Electronic Communications (Japan) 44, pp. 31 ‑ 36.

7. Kadhim Rahma, M., Hlukhov, V. (2017), Computing Square Roots and Solve Equations of ECC over Galois Fields. 7th International Youth Science Forum LITTERIS ET ARTIBUS 2017, Computer Science & Engineering (CSE-2017). Proceedings. Pp. 437 – 440. November 23–25 2017, Lviv, Ukraine.

8. Hlukhov, V. S. (2007), Comparison of polynomial and normal bases of Galois fields elements presentation [Porivniannia polinomialnoho ta normalnoho bazysiv predstavlennia elementiv poliv Halua]. Scientific Bulletin of Lviv Polytechnic National University. Сomputer-aided design systems. Theory and practice. vol. 591, Lviv, Ukraine, pp. 22 – 27 (In Ukrainian).

9. Hlukhov, V. S., Elias, R., Rahma, M. (2017), Structural Complexity of Multipliers for Galois Fields Elements in Normal and Polynomial Bases [Strukturna skladnist pomnozhuvachiv elementiv poliv Halua u normalnomu ta polinomialnomu bazysakh]. Electrotechnic and Computer Systems. – Odessa. Astroprint. – № 25(101). – pp. 324 – 331 (In Ukrainian).

10. Hlukhov, V., Rahma, M., Zholubak, I (2018), Devices for multiplicative inverse calculation in binary Galois Fields. DESSERT'2018. 9th International IEEE Conference Dependable Systems, Services and Technologies.
UKRAINE, KYIV, MAY 24-27, 2018, unpublished.

Hlukhov, V., Zholubak, I., Kostyk, A., Rahma M. (2017), Galois Fields Elements Processing Units for Cryptographic Data Protection in Cyber-Physical Systems. Advances in Cyber-Physical Systems.Volume II, Number 2, 2017. © Lviv Polytechnic National University, pp. 9-18, in press.

12.Password cracking. https://en.wikipedia.org/wiki/Password_cracking.

Published:

№ 27(103), 2018

Last download:

8 Feb 2020