МЕТОД ПОБУДОВИ ПРИМІТИВНИХ ПОЛІНОМІВ ДЛЯ КРИПТОГРАФІЧНИХ ПІДСИСТЕМ ГАРАНТОЗДАТНИХ АВТОМАТИЗОВАНИХ СИСТЕМ

Гулак Геннадій Миколайович, кандидат технічних наук, доцент, зав. лабораторією Інституту проблем математичних машин і систем НАН України, м Київ

pages 120–125

DOI: 10.1615/JAutomatInfScien.v52.i12.50

Запропоновано метод побудови примітивних поліномів, які використовуються під час проектування радіотехнічних систем, підсистем криптографічного захисту інформації в гарантоздатних автоматизованих системах перетворення інформації та управління на об’єктах критичної інфраструктури, а також в інших суспільно значущих інформаційних системах. Зокрема, такі поліноми можуть застосовуватися для створення елементів криптографічних схем, включаючи джерела псевдовипадкових чисел, вузли гарантованого періоду, вузли (підстановки) заміни. Із застосуванням критерію Рабіна для незвідних поліномів та рекурсивної конструкції  запропоновано метод побудови на основі відомих примітивних поліномів над полем із двох елементів примітивних поліномів над полями порядку 2k, де. Для обчислення коефіцієнтів поліномів наведено необхідні рівності. Цей метод є актуальним у випадку створення підсистем криптографічного захисту інформації у сучасних комп’ютерних системах, що використовують мікроконтролери та мікропроцесори на основі 32- або 64-бітних форматів подання даних. Вказаний метод побудови примітивних поліномів над непростими полями за відомими примітивними поліномами над полем із двох елементів має поліноміальну складність. Наведено означення основних понять, а також необхідні допоміжні результати, що використовуються при обґрунтуванні алгоритму, на якому базується пропонований метод, та можуть бути корисними при його реалізації, надано детальний опис алгоритму та наведено приклад його застосування.

Ключові слова: підсистема криптографічного захисту, примітивний поліном, незвідний поліном, мінімальний поліном елемента, примітивний елемент, скінченне поле, фактор-кільце, критерій Рабіна.

  1. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М. : КУДИЦ-ОБРАЗ, 2001. 368 с.
  2. Rueppel R.A. Analysis and design of stream ciphers. Springer communications and control engineering series, 1986. 244 p.
  3. Гилл А. Линейные последовательностные машины. Анализ, синтез и применение. Пер. с англ. М. : Наука, 1974. 288с.
  4. Берлекэмп Э. Алгебраическая теория кодирования. М. : Мир, 1971. 480 с.
  5. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М. : Мир, 1986. 576 с.
  6. Ленг С. Алгебра. М. : Мир, 1968. 564 с.
  7. Лидл Р., Нидеррайтер Г. Конечные поля: в 2-х т. М. : Мир, 1988. Т. 1. 430 с.; Т. 2. 390 с.
  8. Von zur Gathen J., Gerhard J. Modern computer algebra. New-York : Cambridge Univ. Press, 1999. 40. 755 p.
  9. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: в 2-х т. Т.II. М. : Гелиос АРВ, 2003. 416 c.
  10. Fitzgerald R.W. A characterization of primitive polynomials over finite fields. Finite Fields and Their Appl. 2003. 9. P. 117–121.
  11. Валицкий Ю.Н. Один способ решения системы линейных уравнений с матрицей Вандермонда. Научно-методический сборник «Математика сегодня». Киев: Вища школа, 1989. С. 39–47.