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

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

I. A. Dychka, V. P. Legeza, M. V. Onai, A. I. Severin

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. 


Keywords


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

Full Text:

PDF

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.


GOST Style Citations


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

2. Benvenuto C. J. Galois field in cryptography / Christoforus Juan Benvenuto. // University of Washington. – 2012.

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

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

5. Болотов А. А. Алгоритмические основы эллиптической криптографии [Text] / А. А. Болотов, С. Б. Гашков, А. Б. Фролов, А.Б. Часовских. – М. : Изд-во РСГУ, 2004. – 499 с.

6. Болотов А. А. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы [Text] / А. А. Болотов, С. Б. Гашков, А. Б. Фролов, А. А. Часовских. – Москва : КомКнига, 2006. – 328 с. ISBN 5-484-00443-8.

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

8. Westall, J. An Introduction to Galois Fields and ReedSolomon Coding / J. Westall, J. Martin // School of Computing Clemson University Clemson, SC 29634– 1906. – 2010.

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

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

11. Gao S. Normal Bases over Finite Fields / Shuhong Gao // University of Waterloo. – 1993.

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

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

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

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







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.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.