MODIFIED CHANGE-OF-BASIS CONVERSION METHOD IN GF(2m)

Authors

  • I. A. Dychka National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine
  • V. P. Legeza National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine
  • M. V. Onai National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine
  • A. I. Severin National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2020-2-12

Keywords:

Finite field, Galois field, polynomial basis, normal basis, irreducible polynomial, normal polynomial.

Abstract

Context. When cryptographic applications and data transmission control systems are implementing, there is a need for quick methods for performing operations on finite field elements. The object of the study is the processes of encryption, decryption and transmission of information using the Galois fields. The subject of the study is the methods and algorithms for calculations in the Galois fields in polynomial and normal bases.

Objective. The purpose of this study is to analyze the methods of performing operations in the Galois field depending on the chosen basis (polynomial, normal) and modification of the element conversion method from the polynomial basis to the normal and vice versa, as well as the development of a new method for generating normal polynomials in order to improve the time characteristics.

Method. In this paper, a comparative analysis of the processes of performing basic operations in the polynomial and normal bases is performed (addition, multiplication, multiplicative inverse element calculation, division, exponentiation, Frobenius operation), and the process of conversion from one basis to another is considered and analyzed. The methods of conversion between bases depending on different input data, in particular, parameters p and m of the field, are investigated. A method for the finding normal polynomials among the irreducible and modified approach for constructing a conversion matrix between bases are proposed. 

Results. Existing and proposed algorithms are implemented in the C# programming language in the Visual Studio 2015 development environment. For experimental research, a software has been developed that allows performing calculations using the polynomial and normal representation of GF(pm) elements, to specify different input parameters p and m, and also receive different sets of test data depending on the normal polynomials of the Galois field.

Conclusions. The obtained experimental results of the methods and algorithms for performing operations on the elements of GF(2m) in the given bases showed that the proposed method for finding normal polynomials for the conversion between bases of binary fields gives an increase in speed over 15 times for the parameter m > 14; the proposed approach for constructing a conversion matrix gives an increase in the speed of more than 5 times for the parameter m > 12. 

Author Biographies

I. A. Dychka, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

Dr. Sc., Professor, Dean of the Faculty of Applied Mathematics

V. P. Legeza, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

Dr. Sc., Professor of the Computer Systems Software Department

M. V. Onai, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

PhD, Associate Professor of the Computer Systems Software Department

A. I. Severin, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

student of the Computer Systems Software Department

References

Lidl R., Niederreiter H. Finite Fields. Cambridge: Cambridge University Press, 1996, 755 p. DOI: 10.1017/CBO9780511525926.

Benvenuto C. J. Galois field in cryptography, University of Washington, 2012.

Advanced Encryption Standard (AES), Federal Information Processing Standards, 2001, DOI: 10.6028/NIST.FIPS.197.

Oliynykov R., Gorbenko I., Kazymyrov O. et. al. A New Encryption Standard of Ukraine: The Kalyna Block Cipher, IACR Cryptology ePrint Archive, 2015, Vol. 2015, №650.

Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskih A. B. Algoritmicheskie osnovy ellipticheskoj kriptografii. Moscow, Izd-vo RSGU, 2004, 499 p.

Bolotov, A. A., Gashkov S. B., Frolov A. B., Chasovskih A. A. Elementarnoe vvedenie v ellipticheskuyu kriptografiyu: algebraicheskie i algoritmicheskie osnovy [Text]. Moscow, KomKniga, 2006, 328 p. ISBN 5-48400443-8.

Shrivastava P., Singh U. P. Error Detection and Correction Using Reed Solomon Codes, International Journal of Advanced Research in Computer Science and Software Engineering, 2013, Vol. 3, № 8, pp. 965–969 ISSN: 2277128X.

Westall J., Martin J. An Introduction to Galois Fields and Reed-Solomon Coding, School of Computing Clemson University Clemson, SC 29634-1906, 2010.

Cohen H., Frey G., Avanzi R. et. al. Handbook of Elliptic and Hyperelliptic Curve Cryptography, 2005, 842 p. (Discrete Mathematics and Its Applications) ISBN 158488-518-1.

Algebraic structures [Electronic resource]. Access mode: http://faculty.bard.edu/belk/math332/AlgebraicStructures.pdf.

Gao S. Normal Bases over Finite Fields, University of Waterloo, 1993.

Gashkov S. B., Sergeev I. S. Complexity of computation in finite fields, Journal of Mathematical Sciences. – 2013. – Vol. 191, P. 661–685 DOI: 10.1007/s10958-013-1350-5.

Bolotov A. A., Gashkov S. B. On a quick multiplication in normal bases of finite fields, Discrete Mathematics and Applications, 2001, Vol. 11, №4, pp. 327–356 DOI 10.1515/DMA.2001.

Zindros D. A Gentle Introduction to Algorithm Complexity Analysis [Electronic resource]. Access mode: https://discrete.gr/complexity/.

Lassak M., Porubsky S. Fermat-Euler Theorem in Algebraic Number Fields, Journal of number theory, 1996. №60, pp. 254–290.

Downloads

How to Cite

Dychka, I. A., Legeza, V. P., Onai, M. V., & Severin, A. I. (2020). MODIFIED CHANGE-OF-BASIS CONVERSION METHOD IN GF(2m). Radio Electronics, Computer Science, Control, (2), 117–128. https://doi.org/10.15588/1607-3274-2020-2-12

Issue

No. 2 (2020): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2020 I. A. Dychka, V. P. Legeza, M. V. Onai, A. I. Severin

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal 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 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  • Authors are able to 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 publish it in a book), with an acknowledgement 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) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.