Combining and filtering functions in the framework of nonlinear-feedback shift register

Authors

  • A.A. Kuznetsov
  • A.V. Potii
  • N.A. Poluyanenko
  • S.G. Vdovenko

DOI:

https://doi.org/10.30837/rt.2018.4.195.10

Keywords:

generators of the pseudorandom sequence, filtering function, combining function, cryptanalysis, nonlinear polynomials

Abstract

Strong cryptography of stream ciphers is determined, among other things, by the ability of a generated pseudorandom sequence to resist analytical attacks. One of the main components of the pseudorandom stream cipher sequence generating algorithm are Boolean functions for combining and filtering. The paper considers the possibility of applying nonlinear-feedback shift registers that generate a maximum length sequence as a combining or filtering function. This work examines the main indicators of cryptographic strength of such functions, as: balance, the prohibitions presence, correlation immunity and nonlinearity. The study analyzes and demonstrates correlation immunity’s and nonlinearity’s experimental values for all nonlinear feedback shift registers, that generate a maximum length sequence, for register sizes up to 6 cells inclusively, and registers sizes up to 9 cells inclusively with algebraic degree of the polynomial under 2. The possibility of optimizing the process of selecting Boolean functions according to the criteria of maximum correlation immunity and nonlinearity with various algebraic degree and minimization of the number of monomials in the polynomial are studied.

References

Городилова А.А. От криптоанализа шифра к криптографическому свойству булевой функции // При-кладная дискретная математика. – 2016. – № 3(33). – С.16–44

Панкратова И.А. Булевы функции в криптографии : учеб. пособие. – Томск : Изд. Дом Томск. гос. ун-та, 2014. – 88 с.

Мухачев В.А., Хорошко В.А. Методы практической криптографии. – К. : ООО «Полиграф-Консалтинг», 2005. – 215 c

Потий А.В., Полуяненко Н.А. Расчет числа образующих полиномов для регистров сдвига с нелинейной обратной связью с нелинейностью произвольного порядка // Міжнар. наук. конф. питання оптимізації обчислень (ПОО-XLІV) Інституту кібернетики імені В.М. Глушкова НАН України, 26–29 вересня 2017 року. Хмельницька область, м. Кам'янець-Подільський.

Хачатрян Л.Г. Методы построения последовательностей де Брейна // Дискретна математика. – 1991. – Т. 3, вып. 4. – С. 62–78

Knuth D. The Art of Computer Programming. Vol. II. Seminumerical Algorithms. — USA, Commonwealth of Massachusetts: Addison-Wesley, 1969. – Р.634.

Логачев О.А., Сальников А.А., Смышляев С.В., Ященко В.В. Булевы функции в теории кодирования и криптологии ; 2-е изд. – Москва : МЦНМО, 2012. – 584с.

Смышляев С.В. О криптографических слабостях некоторых классов преобразований двоичных последовательностей // Прикладная дискретная математика. – 2010. – № 1. – С. 5–15.

Токарева Н. Н. Обобщения бент-функций. Обзор работ // Дискретный анализ и исследование операций. – 2010. – Т. 17, №1. – С.33-62

Токарева Н.Н. Нелинейные булевы функции : бент-функции и их обобщения. Издательство LAP LAMBERT Academic Publishing (Saarbrucken, Germany), 2011. – 180 с. ISBN: 978-3-8433-0904-2.

Агафонова И.В. Криптографические свойства нелинейных булевых функций. Семинар по дискрет. гармон. анализу и геометр. моделированию. – СПб. : DHA & CAGD, 2007. – С. 1–24.

Шевелев Ю.П. Дискретная математика. Ч. 1: Теория множеств. Булева алгебра (Автоматизированная технология обучения «Символ») : учеб. пособие. – Томск. гос. ун-т систем управления и радиоэлектроники, 2003. –118 с. ; Молдовян А.А. Криптография. Скоростные шифры. – БХВ-Петербург, 2002. – 496 с.

Таранников Ю.В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики. – Москва : Физматлит, 2002. – Вып. 11. – С. 91–148.

Published

2018-12-28

How to Cite

Kuznetsov, A., Potii, A., Poluyanenko, N., & Vdovenko, S. (2018). Combining and filtering functions in the framework of nonlinear-feedback shift register. Radiotekhnika, 4(195), 101–112. https://doi.org/10.30837/rt.2018.4.195.10

Issue

Section

Articles