Алгебраические, комбинаторные и криптографические свойства параметров аффинных ограничений булевых функций тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат физико-математических наук Буряков, Михаил Леонидович

• Буряков, Михаил Леонидович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Буряков, Михаил Леонидович

Введение

1 Общие свойства уровня аффинности

1.1 Обозначения, определения и общие сведения.

1.2 Уровень аффинности некоторых классов булевых функций

1.3 Класс функций с максимально возможным уровнем аффинности

1.4 Уровень аффинности булевой функции и преобразование Мёбиуса

1.5 Уровень аффинности булевой функции и спектральные коэффициенты

2 Связь с криптографическими параметрами

2.1 Уровень аффинности и нелинейность.

2.2 Уровень аффинности и корреляционная иммунность

2.3 Уровень аффинности и алгебраическая иммунность.

2.4 Другие криптографические параметры.

3 Асимптотические оценки уровня аффинности

3.1 Нижняя асимптотическая оценка обобщённого уровня аффинности

3.2 Верхняя асимптотическая оценка частичного уровня аффинности для функций с заданной степенью

3.3 Асимптотическое значение уровня аффинности квадратичных булевых функций.

4 Алгоритмы определения уровня аффинности

4.1 Алгоритм определения уровня аффинности для булевых функций общего вида.

4.2 Алгоритм определения уровня аффинности для симметрических булевых функций.

4.3 Сложность задачи определения уровня аффинности.

Введение диссертации (часть автореферата) на тему «Алгебраические, комбинаторные и криптографические свойства параметров аффинных ограничений булевых функций»

Обеспечение информационной безопасности является одной из важнейших государственных задач наряду с обеспечением обороноспособности страны, развитием экономики, образования и здравоохранения. Основополагающим документом, регламентирующим политику России в области информационной безопасности, является Доктрина информационной безопасности Российской Федерации [ДИБ], утвержденная в сентябре 2000 года Президентом РФ. Секция Научного совета при Совете Безопасности РФ на основе Доктрины разработала Перечень приоритетных проблем научных исследований, связанных с информационной безопасностью [ППНИ]. Он включает в себя направления в областях развития общей теории обеспечения информационной безопасности и, в частности, защиты информации различными методами, в том числе с использованием криптографических механизмов, разработку методов и средств защиты в системах электронного документооборота включая использование электронной цифровой подписи. Одним из наиболее важных направлений в Перечне является «разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики» (п. 54 Перечня).

Качество криптографических методов защиты определяется криптографической стойкостью системы защиты. Основной количественной мерой стойкости является вычислительная сложность решения задачи преодоления криптографической защиты. Количественная оценка уровня защиты информации с использованием криптосистемы определяется как вычислительная сложность наиболее эффективного из известных алгоритмов вскрытия криптосистемы.

Разработка алгоритмов преодоления криптографической защиты основана на использовании математических моделей, адекватно описывающих процесс функционирования системы защиты. Математическая формализация работы криптосистем в процессе криптоанализа во многих случаях приводит к задачам решения уравнений в различных алгебраических системах. Системы нелинейных булевых уравнений являются одной из распространённых моделей описания функционирования различных дискретных устройств. Необходимость изучения и решения систем булевых уравнений возникает в ряде задач теории конечных автоматов, теории кодирования и криптологии. В частности, в криптологии это направление относится к синтезу и анализу традиционных криптографических систем с секретным ключом, где системы нелинейных булевых уравнений, связывают элементы неизвестного ключа криптосистемы с известными данными. Основные криптографические примитивы, являющиеся источниками систем булевых уравнений в криптоанализе, — это комбинирующие генераторы (см. рис. 1) и фильтрующие генераторы (см. рис. 2) потоковых шифров, а также s-боксы блоковых шифров. На этих рисунках: РСЛОС-г, г = 1,., п, PCJIOC — регистры сдвига с линейными обратными связями; / — комбинирующая (фильтрующая) булева функция от п переменных; gi{v), i = 1,2,., п, g(v) — полиномы обратных связей регистров сдвига.

Рис. 1: комбинирующий генератор

V) рслос х jt) -W xw\

V 1 Iх2 > ■ • •'Xn }

Рис. 2: фильтрующий генератор

Задача решения произвольной системы нелинейных булевых уравнений является iVP-трудной (см. [ГДж82]) и на данный момент для решения подобных систем в общем случае не известно алгоритма со сложностью, по порядку меньше, чем

2о(п) где п — число неизвестных в системе. Вместе с

Zt = f тем, анализ конкретных систем уравнений для криптосистем с секретным ключом (при п « 100-200 и более) является актуальной научной проблемой (см., например, [eSTREAM]).

В криптоанализе разработаны различные подходы к решению нелинейных систем булевых уравнений. В ряде случаев для нахождения решения системы используются теоретико-вероятностные, статистические методы (см. [Sieg84, MSt89]) и теоретико-кодовые методы (см. [ChJohSmOO]). В ряде случаев предлагается погружать систему уравнений в действительную область (см. [БН94, Нат68, Рыб02, РХ02]) и находить её решение системы с помощью соответствующей системы псевдобулевых неравенств. Кроме того, в случае использования итераций в процессе шифрования возможна линеаризация исходной криптографической задачи (например, определения ключа) с использованием определённых степеней итерируемого отображения, являющихся аффинными отображениями (см. [ФомОб, Фом08]).

В работах [КЛО'ШиОО, AFIKS04] рассматриваются алгебраические методы решения систем нелинейных булевых уравнений над конечными полями на основе базисов Грёбнера.

Наиболее эффективными, как показывает практика криптоанализа, являются методы, использующие линеаризацию исходной системы. Эти методы можно условно разбить на два класса. Первый класс составляют методы линеаризации нелинейной системы булевых уравнений с введением новых переменных, эффективным решением полученной линейной системы и нахождением решения (решений) исходной системы. В практике криптоанализа этот метод называют алгебраической атакой (algebraic attack). Подробную библиографию, относящуюся к этому методу, можно найти, например, в [Баев07].

Второй класс объединяет методы линеаризации нелинейных систем булевых уравнений без введения новых переменных. В этом случае речь идёт о рассмотрении ограничений булевых функций (иногда этот приём называют сужением), обладающих свойствами аффинных функций.

Подфункцией данной булевой функции (см. [ЛСЯ04]) называют ограничение этой функции на некоторое подмножество её области определения (формальное определение нужного нам понятия подфункции будет дано позднее). Тесно связано с понятием подфункции булевой функции понятие частично определённой булевой функции. Использование в криптоанализе подфункции определило интерес исследователей к изучению совместных криптографических свойств булевых функции и их подфункций (см. [ССЬОЗ, DDL03, CDDL03, КЯщОО, КЯщ01, Куз02-1, Куз02-2, Саг92]), а также к наследованию свойств булевой функции её подфункциями (см., например, [ЛСЯ02]).

Как было отмечено выше, в настоящей работе рассматриваются ограничения булевых функций, совпадающие с аффинными функциями. При этом характер области ограничения определят конкретный вид рассматриваемого нами параметра.

Основные понятия, исследуемые в диссертации, будут формально введены в главе 1. Во введении будем использовать неформальный язык для описания этих понятий.

Понятие уровня аффинности (1а(/)) булевой функции / как минимальное число фиксаций переменных этой функции, переводящих исходную функцию в аффинную функцию от меньшего числа переменных, было введено в [ЛСЯОЗ-2]. Понятие частичного уровня аффинности (1а° (/)) было введено в [JIor05] и определяется как минимальное число нулевых фиксаций переменных булевой функции /, превращающих исходную функцию в аффинную. Понятие обобщённого уровня аффинности (£а(/)) булевой функции / определяется как минимальная разность между числом переменных функции / и размерностью плоскости (смежного класса по подпространству), ограничение на которую совпадает с аффинной функцией. Различные виды уровня аффинности связаны между собой естественным соотношением а(/)<1а(/)^1а°(/), которое используется для вывода ряда соотношений.

Естественным образом указанные выше параметры линеаризации могут быть распространены и на булевы отображения.

Понятие сильной £;-аффинности рассмотрено в [ЛСЯОЗ-2]. Аналогичное понятие линеаризационного множества, определяемое в других терминах, введено в [Тим05-1, Тим05-2].

Кратко сформулируем криптографическую задачу восстановления ключей комбинирующего генератора. Рассмотрим комбинирующий генератор (см. рис. 1), построенный с помощью п регистров сдвига 'с линейными обратными связями — РСЛОС-г, г — 1 ,.,п. Длины регистров будем обозначать ki, i — 1, .,п соответственно. Псевдослучайная последовательность получается с помощью комбинирующей булевой функции / , • • •, — / (х) от п переменных.

Будем считать, что полиномы обратных связей регистров сдвига gi(v), г = 1, 2,., п примитивны, и регистры порождают линейные реккурентные последовательности максимального периода 2ki — 1, г = 1,2,., п.

Обозначим для натурального числа n и фиксированного г,

1 о ( (1) (2) (N)\ Г (t)\N г — 1,2,.,п, Xj = ,х\ , .,х\ J — j i ~ последовательность длины N, вырабатываемую регистром сдвига с номером г, находившимся (!) (2) (кг)\ гр . в начальном состоянии ( х\ , х\ ,., х\ ). 1о есть, в такт t регистр с номером г вырабатывает элемент xf^ последовательности х;, а "комбинирующий генератор вырабатывает знак z^ = f ., Хп^ шифрующей последовательности z

Пусть известна последовательность z, выработанная комбинирующим генератором. Задача состоит в определении начальных состояний \ \ • • • ) ^ j \ х2 > • • • » ^ ) ■ • ■ ) (^п > З^п \ • • • } Хп ^ регистров, при которых была получена последовательность z. Другими словаГ ми, задача состоит в восстановлении последовательностей xi ., xn

В криптоанализе данная криптографическая задача соответствует атаке по открытому и шифрованному тексту на комбинирующий генератор потокового шифра с угрозой вскрытия ключа. В работе [ЛСЯОЗ-1] был предложен метод реализации данной атаки, основанный на частичном опробовании ключей и использующий ранговый критерий. При этом уровень аффинности 1а (/) комбинирующей функции / (см. рис. 1) определяет (наряду с другими параметрами) трудоёмкость этого метода.

Другим важным направлением исследований является изучение криптографических свойств булевых функций и связей между этими свойствами. Достаточное число математически содержательных соотношений между параметрами, описывающими различные (в том числе и конфликтующие) криптографические свойства, облегчает решение сложной оптимизационной задачи выбора булевых функций (отображений) при синтезе стойких криптосистем. Примерами могут служит изучение пар криптографических свойств «корреляционная иммунность-нелинейность» [Тар02, SM00-2], «корреляционная иммунность-алгебраическая иммунность» [Бот05], «нелинейность-алгебраическая иммунность» [DGM04, Lob05], а также использование локальных аффинностей для изучения криптографических свойств булевых функций [С1НМ07, НоиОб, CDDL06, LYashD07].

Целью данной диссертации является развитие математического аппарата для совершенствования методов анализа и синтеза криптосистем с секретным ключом.

Заключение диссертации по теме «Методы и системы защиты информации, информационная безопасность», Буряков, Михаил Леонидович

Основные результаты работы состоят в следующем.

- найдены параметры линеаризации и их оценки для различных (в том числе криптографических) классов булевых функций;

- доказаны свойства параметров, характеризующие методы линеаризации булевых функций в целом;

- получены соотношения, связывающие параметры линеаризации с основными криптографическими свойствами булевых функций;

- доказаны верхние и нижние асимптотические оценки уровня аффинности для почти всех булевых функций;

- доказана ./VP-трудность задачи определения уровня аффинности булевых функций с ограничением на количество мономов.

В целом результаты работы направлены на развитие криптографических методов и средств обеспечения информационной безопасности. Результаты диссертации позволяют в процессе синтеза потоковых шифров обосновать рекомендации по выбору их параметров, а в процессе анализа шифров выявить их «слабые» с точки зрения защиты информации преобразования.

Заключение

В диссертации исследован уровень аффинности булевых функций — параметр, определяющий эффективность методов криптоанализа, основанных на использовании аффинных ограничений булевых функций.

Список литературы диссертационного исследования кандидат физико-математических наук Буряков, Михаил Леонидович, 2008 год

1. AFIKS04. Ars G., Faugere J-С., Imai H., Kawazoe M., Sugita M. Comparsion between XL and Grobner basis Algorithms. Advances in Cryptology: ASIACRYPT'04, LNCS V. 3329., pp. 338-353, Springer-Verlag, 2004.

2. CCChS91. Camion P., Carlet C., Charpin P., Sendrier N. On correlation immune functions. Crypto 1991, LNCS V. 576, pp. 86-100, Springer-Verlag, 1991.

3. CCh03. Canteaut A., Charpin P. Decomposing bent functions. IEEE Transactions on Information Theory, V. 49, № 8, pp. 2004-2009, 2003.

4. CDDL03. Canteaut A., Daum M., Dobbertin H., Leandr G. Normal and nonnormal bent functions. Proc. Int. Workshop on Coding and Cryptography — WCC'2003, Versailles, Mar. 2003, pp. 91-100.

5. CV05. Canteaut A., Videau M. Symmetric boolean functions. IEEE Transactions on Information Theory, V. 51, № 8, pp. 2791-2811, 2005.

6. CDDL06. Canteaut A., Daum М., Dobbertin Н., Leander G. Finding nonnormal bent functions. Discrete Applied Mathematics archive, v. 154 , Issue 2, pp 202-218, 2006.

7. Car92. Carlet C. Partially-bent functions. Proc. Crypto 92, pp. 280-291, Springer, 1992.

8. Car94. Carlet C. Two new classes of bent functions. Advances in Cryptology: EUROCRYPT'93, LNCS V. 765., pp. 77-101, Springer-Verlag, 1994.

9. Car02. Carlet C. A large class of cryptographic Boolean functions via a study of the Maiorana-McFarland constructions. Advances in Cryptology: CRYPTO'02, LNCS V. 2442., pp. 549-564, Springer-Verlag, 2002.

10. Car04. Carlet C. On the secondary constructions of resilient and bent functions. Progress in Computer Science and Applied Logic 23 (2004), pp. 3-28.

11. C1HM07. Clark W. E., Hou X. D., Mihailovs A. The affinity of permutations of a finite vector space. Finite Fields and Their Applications V. 13, Issue 1, pp. 80-112, 2007.

12. ChSm91. Chepyzhov V., Smeets B. On a fast correlation attacks on certain stream ciphers. Advances in Cryptology: EUROCRYPT'91, LNCS V. 547, pp. 176-185, Springer-Verlag, 1991.

13. ChJohSmOO. Chepyzhov V., Johansson Т., Smeets В. A simple algorithm for fast correlation attacks on stream ciphers. Advances in Cryptology: FSE'2000, LNCS V. 1978, pp. 181-195, Springer-Verlag, 2000.

14. CP02. Courtois N., Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations. Advances in Cryptology: ASIACRYPT'02, LNCS V. 2501, Springer-Verlag, 2002.

15. CP03. Courtois N, Patarin J. About the XL algorithm over GF(2). Cryptographers' Track RSA 2003, San Francisco, April 13-17 2003, LNCS V. 2612, Springer, 2003.

16. CM03. Courtois N., Meier W. Algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology: EUROCRYPT'03, LNCS V. 2656, Springer-Verlag, 2003.

17. DGM04. Dalai D. K., Gupta К. C., Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions. Progress in Cryptology: INDOCRYPT'04, LNCS V. 1880, pp. 92-106, Springer-Verlag, 2004.

18. Ham68. Hammer P. L. Boolean elements in combinatorial optimization. Combinatorial Programming: Methods and Applications, Dordrecht-Boston, 1968.

19. Mats93. Matsui M. Linear cryptanalysis method for DES cipher. Advanced in Cryptology: EUROCRYPT'93, LNCS V. 765, pp. 386-397, Springer-Verlag, 1993.

20. Mat76. Matula D. W. The Largest clique size in random graph. Technical Report CS 7608, Department of Computer Science, Southern Methodist University, 1976.

21. Meier04. Meier W., Pasalic E., Carlet C. Algebraic attacks and decomposition of Boolean fucntions. Advances in Cryptology: EUROCRYPT'04, LNCS V. 3027, Springer-Verlag, 2004.

22. MSt89. Meier W., Staffelbach O. Fast correlation attacks on certain stream ciphers. Journal of Cryptology V. 1, № 3, pp. 159-1762, 1989.

23. MOV97. Menezes A., P. van Oorschot, Vanstone S. Handbook of applied cryptography. CRC Press Inc., 1997

24. NESSIE. Проект разработки новых европейских схем шифрования, цифровой подписи и проверки целостности NESSIE, https: //www. cosic. esat.kuleuven.be/nessie/

25. Pas03. Pasalic E. Degree optimized resilient Boolean functions from Maiorana-McFarland class. Cryptography and Coding — 9th IMA International Conference, LNCS V. 2898, pp. 93-114, Springer-Verlag, 2003.

26. Roth76. Rothaus O. On bent function. J. Combin. Theory Ser. A, V. 20, pp. 300-305, 1976.

27. SM00-1. SarkarP., MaitraS. Construction of nonlinear Boolean functions with important cryptographic properties, EUROCRYPT'2000, LNCS V. 1807, pp. 488-511, Springer-Verlag, 2000.

28. SM00-2. Sarkar P., Maitra S. Nonlinearity bounds and constructions of resilient Boolean functions, CRYPTO'2000, LNCS V. 1880, pp. 515-532, Springer-Verlag, 2000.

29. Sieg84. Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans, on Information Theory V. IT-30.5, pp. 776-780, 1984.

30. ZZ99. Zheng Y., Zhang X. M. Plateaued functions. ICICS'99, LNCS V. 1726, pp. 284-300, Springer-Verlag, 1999.

31. Ал02. В. Б. Алексеев. Введение в теорию сложности алгоритмов (учебное пособие для студентов). — М.: Издательский отдел факультета ВМиК МГУ, 2002.

32. Баев07. В. В. Баев. Эффективные алгоритмы получения оценок алгебраической иммунности булевых функций. Диссертация на соискание учёной степени кандидата физико-математических наук, специальность 01.01.09, Москва, 2007.

33. БН94. Г. В. Балакин, В. Г. Никонов. Методы сведения булевых уравнений к системам пороговых соотношений. Обозрение прикладной и промышленной математики., т. 1, вып. 3, сс. 389-401, 1994.

34. Бот05. А. А. Ботев. О свойствах корреляционно-иммунных функций с высокой нелинейностью. Диссертация на соискание учёной степени кандидата физико-математических наук, специальность 01.01.09, Москва, 2005.

35. Бур05-1. М. Л. Буряков. О некоторых свойствах уровня аффинности комбинирующих булевых функций. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г., сс. 136-141 М.: МЦНМО, 2005.

36. Бур05-2. М. Л. Буряков. Об уровне аффинности комбинирующих булевых функций. Сборник тезисов лучших дипломных работ 2005 года, сс. 62-64 — М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2005.

37. Бур07. М. Л. Буряков. Об уровне аффинности симметрических булевых функций. Материалы IX Международного семинара «Дискретная математика и её приложения», сс. 421-423 — М.: Издательство механико-математического факультета МГУ, 2007.

38. Бур08-1. М. JL Буряков. О связи уровня аффинности с криптографическими параметрами булевых функций. Дискретная математика, том 20, вып. 2, 2008, сс. 3-15.

39. Бур08-2. М. JI. Буряков. Асимптотические оценки уровня аффинности для почти всех булевых функций. Дискретная математика, том 20, вып. 3, 2008, сс. 73-79.

40. БЛ05-1. М. JT. Буряков, О. А. Логачев. Об уровне аффинности булевых функций. Дискретная математика, том 17, вып. 4, 2005, сс. 98-107.

41. БЛ05-2. М. Л. Буряков, О. А. Логачев. О распределении уровня аффинности на множестве булевых функций. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г., сс. 141-146 М.: МЦНМО, 2005.

42. ГДж82. М. Гэри, Д. Джонсон. Вычислительные машины и труднореша-емые задачи. — М.: Мир, 1982.

43. ДИБ. Доктрина информационной безопасности Российской Федерации. В сб. «Научные и методологические проблемы информационной безопасности». Под ред. В. П. Шерстюка, сс. 149-197 — М.: МЦНМО, 2004.

44. КЛО'ШиОО. Д. Кокс, Дж. Литтл, Д. О'Ши. Идеалы многообразия и алгоритмы. — М.: Мир, 2000.

45. Куз96. Ю. В. Кузнецов. Коды Рида-Маллера (обзор публикаций). Математические вопросы кибернетики, № 6, сс. 5-50 — М.: Наука, 1996.

46. КЯщОО. Ю. В. Кузнецов, В. В. Ященко. О частичных бент-функциях. Вестник МГУ. Сер. 1. Математика. Механика. № 5, сс. 3-6, 2000.

47. Лог05. О. А. Логачев. Нижняя границауровня аффинности для почти всех булевых функций. Дискретная математика,т. 20,вып. 4 — М.,2008.

48. ЛСЯ02. О. А. Логачев, А. А. Сальников, В. В Ященко. О наследовании свойств при сужении булевых функций, Дискретная математика, т. 14, вып. 2, сс. 9-19 — М., 2002.

49. ЛСЯОЗ-1. О. А. Логачев, А. А. Сальников, В. В Ященко. Корреляционная иммунность и реальная секретность, Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 165-170 М.: МЦНМО, 2004.

50. ЛСЯОЗ-2. О. А. Логачев, А. А. Сальников, В. В Ященко. Комбинирующие k-аффинные функции, Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 176-178 М.: МЦНМО, 2004.

51. ЛСЯ04. О. А. Логачев, А. А. Сальников, В. В. Ященко. Булевы функции в теории кодировании и криптологии. М.: МЦМНО, 2004.

52. МакВСл79. Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн. Теория кодов, исправляющих ошибки. М.: «Связь», 1979.

53. ППНИ. Приоритетные проблемы научных исследований в области информационной безопасности Российской Федерации. Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 21-28 М.: МЦНМО, 2004.

54. Рыб02. К. К. Рыбников. Оценка сложности некоторых схем метода разоделяющих плоскостей при решении систем булевых уравнений. Обозрение прикладной и промышленной математики, т. 9, вып. 2, сс. 442443, 2002.

55. РХ02. К. К. Рыбников, А. С. Хохлушин. О взаимосвязях различных алгоритмических методов погружения множества решений системы булевых уравнений в действительную область. Вестник МГУЛ. Лесной вестник, № 5 (25), сс. 189-194, 2002.

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

57. Тим05-1. Н. Е. Тимошевская. О линеаризационных множествах. Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Пенза, 23-28 мая 2005), с. 154 — М.: Издательство механико-математического факультета МГУ, 2005.

58. Тим05-2. Н. Е. Тимошевская. Задача о кратчайшем линеаризационном множестве. Вестник Томского государственного университета, № 14, август 2005 (приложение), сс. 79-83.

59. ШенбЗ. К. Шеннон. Синтез двухполюсных переключательных схем. Работы по теории информации и кибернетике, сс. 59-105 — М.: ИЛ, 1963.