Modified change-of-basis conversion method in GF(2m)

Abstract

EN: 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. UK: Актуальність. При реалізації криптографічних додатків та систем контролю передачі даних виникає потреба у швидких методах виконання операцій над елементами скінченних полів. Об’єктом дослідження є процеси шифрування, дешифрування та передачі інформації з використанням полів Галуа. Предметом дослідження є методи та алгоритми виконання обчислень у полях Галуа в поліноміальному й нормальному базисах. Мета роботи. Метою даного дослідження є аналіз методів виконання операцій у полі Галуа залежно від обраного базису (поліноміальний, нормальний) та модифікація методу перетворення елементів з поліноміального базису у нормальний і навпаки, а також розроблення нового методу генерування нормальних поліномів для поліпшення часових характеристик. Метод. У даній статті виконано порівняльний аналіз процесів виконання основних операцій у поліноміальному і нормальному базисах (додавання, множення, обчислення мультиплікативно оберненого елемента, ділення, піднесення до степеня, операція Фробеніуса), а також розглянуто та проаналізовано процес переходу з одного базису в інший. Досліджено способи переходу між базисами залежно від різних вхідних даних, зокрема, параметрів p та m поля. Запропоновано метод пошуку нормальних поліномів серед незвідних та модифікований підхід для побудови матриці переходу між базисами. Результати. Існуючі та запропоновані алгоритми реалізовано мовою програмування C# у середовищі розробки Visual Studio 2015. Для проведення експериментальних досліджень розроблено програмну систему, яка дозволяє виконувати обчислення, використовуючи поліноміальне й нормальне представлення елементів поля GF(pm), задавати різні вхідні параметри p та m, а також отримувати різні множини тестових даних залежно від нормальних поліномів поля Галуа. Висновки. Отримані експериментальні результати роботи методів та алгоритмів виконання операцій над елементами поля GF(2m) у заданих базисах показали, що запропонований метод пошуку нормальних поліномів для міжбазисних перетворень бінарних полів дає приріст швидкодії у понад 15 разів для параметра m > 14; запропонований підхід побудови матриці переходу дає приріст швидкодії у понад 5 разів для параметра m > 12.