Метод построения примитивных полиномов для криптографических подсистем гарантоспособных автоматизированных систем

Abstract

Запропоновано метод побудови примітивних поліномів, які використовуються під час проектування радіотехнічних систем, підсистем криптографічного захисту інформації в гарантоздатних автоматизованих системах перетворення інформації та управління на об’єктах критичної інфраструктури, а також в інших суспільно значущих інформаційних системах. Зокрема, такі поліноми можуть застосовуватися для створення елементів криптографічних схем, включаючи джерела псевдовипадкових чисел, вузли гарантованого періоду, вузли (підстановки) заміни. Із застосуванням критерію Рабіна для незвідних поліномів та рекурсивної конструкції запропоновано метод побудови на основі відомих примітивних поліномів над полем із двох елементів примітивних поліномів над полями порядку 2k , де k  2 . Для обчислення коефіцієнтів поліномів наведено необхідні рівності. Цей метод є актуальним у випадку створення підсистем криптографічного захисту інформації у сучасних комп’ютерних системах, що використовують мікроконтролери та мікропроцесори на основі 32- або 64-бітних форматів подання даних. Вказаний метод побудови примітивних поліномів над непростими полями за відомими примітивними поліномами над полем із двох елементів має поліноміальну складність. Наведено означення основних понять, а також необхідні допоміжні результати, що використовуються при обґрунтуванні алгоритму, на якому базується пропонований метод, та можуть бути корисними при його реалізації, надано детальний опис алгоритму та наведено приклад його застосування.The paper proposes a method for constructing primitive polynomials that are used in the design of radio engineering systems, subsystems of cryptographic information protection in reliable automated information processing and control systems at critical infrastructure facilities, as well as in other socially significant information systems. In particular, such polynomials can be used to create elements of cryptographic schemes, including pseudo-random number generators, guaranteed period nodes, substitution nodes (substitution). Using the Rabin criterion for irreducible polynomials and a recursive construction, the paper proposes a method for constructing, based on well-known primitive polynomials over a field of two elements, primitive polynomials over fields of order 2k , where k  2 . The necessary equalities for calculating the coefficients of polynomials are given. This method is relevant in the case of creating subsystems for cryptographic protection of information in modern computer systems that use microcontrollers and microprocessors based on 32 or 64 bit data presentation formats. The indicated method for constructing primitive polynomials over non-simple fields based on the known primitive polynomials over a field of two elements has polynomial complexity. The article provides definitions of the basic concepts, as well as the necessary auxiliary results, which are used to substantiate the algorithm on which the proposed method is based, which can be useful in its implementation, a detailed description of the algorithm is presented and an example of its application is given.