автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Комбинаторные свойства совершенно уравновешенных булевых функций

Московский государственный университет имени М.В.Ломоносова

На правах рукописи

Смышляев Станислав Витальевич

КОМБИНАТОРНЫЕ СВОЙСТВА СОВЕРШЕННО УРАВНОВЕШЕННЫХ БУЛЕВЫХ ФУНКЦИЙ

Специальность 05.13.19. —

Методы и системы защиты информации, информационная безопасность

диссертации на соискание ученой степени кандидата физико-математических наук

АВТОРЕФЕРАТ

6 ДЕК 2012

Москва — 2012

005056301

005056301

Работа выполнена на кафедре математической кибернетики факультета Вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный руководитель: кандидат физико-математических наук, старший научный сотрудник, Логачев Олег Алексеевич;

Официальные оппоненты:

Михайлов Владимир Гаврилович доктор физико-математических наук, старший научный сотрудник (ФГБУН "Математический институт имени В.А. Стеклова Российской академии наук")

Таранников Юрий Валерьевич кандидат физико-математических наук, доцент (ФГБОУ ВПО "Московский государственный университет имени М.В .Ломоносова")

Ведущая организация: ОАО <?Концерн "Автоматика

Защита диссертации состоится 19 декабря 2012 года в 16 ч. 45 м. на заседании диссертационного совета Д.501.002.16 при Московском государственном университете имени М.В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Главное здание, механико-математический факультет, аудитория 14-08. С диссертацией можно ознакомиться в библиотеке Мсханико-ма-тематического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан «19» ноября 2012 г.

Ученый секретарь диссертационного совета Д 501.002.16 при МГУ, доктор физико-математических наук, профессор Корпев

Андрей Алексеевич

Общая характеристика работы

Актуальность темы.

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

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

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

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

1 Hedlund G. A. Endomorphisms and automorphisms of the shift dynamical system. Theory of Computing Systems. 1969. Vol. 3(4). Pp. 320-375.

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

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

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

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

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

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

Длительное время свойство совершенной уравновешенности булевой функции связывали с линейностью ее по первой (или по-

2Huffman D. A. Canonical forms for information-lossless finite-state logical machines IRE TVansactions on Circuit Theory. 1959. Vol. 5. Pp. 41-59.

3Adler Д., Coppersmith D., Hassner M. Algorithms for sliding block codes — an application of symbolic dynamics to information theory IEEE Transactions on Information Theory. 1983. Vol. 29(1). Pp. 5-22.

следней) переменной. Серьезные продвижения в исследовании совершенно уравновешенных булевых функций были сделаны Хэд-лундом1 и Сумароковым4. В частности, в них были сформулированы и доказаны необходимые и достаточные условия, связывающие свойство совершенной уравновешенности булевой функции со свойствами быть функцией без запрета и без потери информации. Было также показано, что свойства совершенной уравновешенности, отсутствия запрета и отсутствия потери информации эквивалентны. Кроме того, впервые был приведен пример совершенно уравновешенной булевой функции, не являющейся линейной по первой или последней переменной.

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

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

И. Голичем6 был рассмотрен класс совершенно уравновешенных функций линейных по первой и/или последней переменной, было продемонстрировано негативное криптографическое свойство кодирующих устройств с такими функциями усложнения в случае использования их в системах потокового шифрования; более того, позднее Голичем был предложен метод криптоанализа («инверсионная атака»), существенно использующий это свойство. Была также показана достаточность линейной зависимости булевой функции от крайней переменной для того, чтобы функция оставалась совершенно уравновешенной при добавлении/изъятии произвольного числа несущественных переменных.

4 Сумароков С. Н. Запреты двоичных функций и обратимость для

одного класса кодирующих устройств. Обозрение прикладной и промышленной математики. 1994. 1(1). 33-55.

3Anderson R. J. Searching for the optimum correlation attack. Lecture

Notes in Computer Science. 1995. Vol. 1008. Pp. 137-143.

Golic J. D. On the security of nonlinear filter generators. Lecture Notes

in Computer Science. 1996. Vol. 1039. Pp. 173-188.

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

О. А. Логачевым8 была введена (аналогично введенной Хэдлун-дом в операции композиции эндоморфизмов символических динамических систем) специальная операция композиции функций усложнения и было доказано, что данная операция сохраняет класс совершенно уравновешенных функций; был приведен пример, демонстрирующий возможность с помощью данной операции получать совершенно уравновешенные функции, нелинейно зависящие от первой и последней существенной переменной.

А. Гуже и X. Сибер9 провели исследование связи свойств функций в модели с равномерным распределением на множестве входных последовательностей кодирующего устройства10 и в модели с рекуррентной последовательностью небольшого периода. При анализе оптимального в определенном смысле класса функций в первой из моделей (класса совершенно уравновешенных функций) Гуже и Сибер столкнулись с существенными трудностями. По этой причине Гуже и Сибер уделили большее внимание рассмотрению класса функций, обладающих положительными свойствами во второй из рассматриваемых ими моделей, — класса квази-иммунных функций, который был описан в терминах свойств полиномов Же-галкина и оказался значительно более удобным для анализа.

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

7Dichtl М. On nonlinear filter generators. Lecture Notes in Computer Science. 1997. Vol. 1267. Pp. 103-106.

8Логачев О. А. Об одном классе совершенно уравновешенных булевых функций. Материалы Третьей Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму (МаБИТ-2007). 2008. 137-141.

9 Gouget A., Sibert Я. Revisiting correlation immunity in filter generators Lecture Notes in Computer Science. 2007. Vol. 4876. Pp. 378-395.

10Golic J. D. Conditional correlation attack on combiners with memory.Electronics Letters. 1996. Vol. 32(24). Pp. 2193-2195.

щихся совершенно уравновешенными11.

Несмотря на немалое количество работ, в которых уделялось большое внимание совершенной уравновешенности булевых функций, большинство исследований и рассмотрений, за небольшим исключением, касались функций, линейных по первой и/или последней существенной переменной — узкого и наименее интересного подмножества совершенно уравновешенных функций. Исследование совершенно уравновешенных функций, нелинейных по крайним (первой и последней) существенным переменным, ограничивалось исключительно примерами таких функций. Одним из неприятных следствий такого подхода стал ряд неверных результатов, полученных при попытках обобщения свойств функций линейных по крайним переменным на все совершенно уравновешенные функции.

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

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

Цель диссертационной работы заключается

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

2) в исследовании связей между совершенной уравновешенностью булевых функций и возможностью обращения соответствующих кодирующих устройств в различных моделях;

11 Бабаш А. В. Запреты автоматов и двоичных функций. Труды по дискретной математике. 2006. 9. 7-20.

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

Методологической основой и научно-теоретической базой диссертации являются работы С.Н. Сумарокова, O.A. Логачева, Й. Голича, М. Дихтла, Кс. Лэя и Дж. Мессн о свойствах совершенно уравновешенных булевых функций.

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

Научная новизна. Все результаты диссертации являются новыми. Основные результаты диссертационной работы состоят в следующем.

1) Разработан эффективный алгоритм распознавания свойства совершенной уравновешенности булевой функции по вектору значений. С помощью программной реализации данного алгоритма получено полное описание совершенно уравновешенных булевых функций от 4 и 5 переменных.

2) Для класса булевых функций с барьером длины 3 доказан критерий принадлежности произвольной функции данному классу. Получены новые верхняя и нижняя асимптотические оценки логарифма мощности данного класса. Получены новые нижние асимптотические оценки логарифма числа совершенно уравновешенных булевых функций, ire являющихся линейными по крайним существенным переменным.

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

4) Доказаны свойства локально обратимых булевых функций, позволившие установить критерий локальной обратимости булевой функции; установлены связи между различными модификациями свойства локальной обратимости, а также определенные достаточные условия отсутствия у функции свойства локальной обратимости.

G

5) Установлена асимптотика логарифма числа булевых функций с левым барьером длины 1 без правого барьера. Получены новые нижние асимптотические оценки логарифма числа совершенно уравновешенных булевых функции без барьера.

Теоретическая и практическая значимость. Полученные в диссертации результаты могут быть использованы для развития и совершенствования математических моделей аппаратно-программных средств защиты информации, что будет способствовать повышению обоснованности методов оценки защищенности информации. Эти результаты могут найти применение также при разработке новых принципов создания аппаратно-программных средств защиты информации. В частности:

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

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

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

4) в научных центрах, проводящих исследования в области защиты информации.

Апробация работы. Основные результаты диссертации докладывались на следующих научных конференциях и семинарах:

• семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета Вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова:

• семинаре «Булевы функции в криптологии» кафедры дискретной математики Механико-математического факультета Московского государственного университета имени М.В. Ломоносова;

• семинаре отдела дискретной математики Математического института имени В.А. Стеклова РАН;

• IV международной научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2008), 2008 год;

• V международной научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2009), 2009 год;

• VI международной научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2010), 2010 год;

• VII международной научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2011), 2011 год;

• VIII международной конференции «Дискретные модели в теории управляющих систем», 2009 год;

• XVI международной конференции «Проблемы теоретической кибернетики», 2011 год;

• международной конференции «Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes», Велико-Тырново, Болгария, 2008 год;

Публикации. Основное содержание диссертации опубликовано в 18 работах [1-18], список которых приведён в конце диссертации.

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

Структура работы. Диссертация состоит из введения, 4 глав, заключения, библиографии и приложения. Объем диссертации 164 страницы, включая 8 рисунков. Библиография включает 45 наименований.

Содержание работы

Во введении обосновывается актуальность темы, формулируются цель и задачи исследования, указывается научная новизна,

структура и практическая значимость работы, указаны публикации и апробация работы.

Глава 1 посвящена общим свойствам совершенно уравновешенных булевых функций. В разделе 1.1 вводятся используемые в работе понятия и обозначения, а также основные используемые в работе ранее известные результаты: приводится понятие совершенно уравновешенной булевой функции, приводятся основные утверждения о данном классе функций, в частности, утверждение об эквивалентности понятий функции без запрета и совершенно уравновешенной функции. Определяется отображение /г : Vr —► Vr+n_x, описывающее функционирование кодирующего устройства, построенного с помощью регистра сдвига и функции п переменных / в течение г тактов.

Раздел 1.2 посвящен методам исследования свойств совершенно уравновешенных функций с помощью множеств начальных фрагментов прообразов последовательностей относительно отображений /г. В терминах свойств таких множеств доказывается критерий совершенной уравновешенности (Лемма 1.2.1), следствие из которого (Следствие 1.2.1) оказывается полезным при исследовании булевых функций с барьером и используется в разделе 4.3. Кроме того, доказывается утверждение (Теорема 1.2.1) о существовании для всякого п > 2 булевых функций от п переменных, не являющихся совершенно уравновешенными, но при этом не имеющих запретов длины менее 2п~1. Для всякого п > 2 строится широкий класс таких функций.

В разделе 1.3 рассматриваются вопросы построения алгоритмов распознавания совершенной уравновешенности по вектору значений булевой функции п переменных. Наилучший из ранее известных алгоритмов был предложен М. И. Рожковым12 и позволяет распознать совершенную уравновешенность булевой функции за 0(N - 2n/2) операций, где N = 2п — длина вектора значений. Данный алгоритм основан на результате о совершенной уравновешенности всякой булевой функции /, для которой верно, что отображение /,,(„) является уравновешенным при /х(п) = 2п~1.

Далее в этом разделе рассматривается утверждение, полученное ранее И. Голичем с определенным пробелом в доказательстве, аналогичное утверждению Рожкова, но снижающее ц(п) до величины

12 Рожков М. И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм III.

Обозрение прикладной и промышленной математики. 2009. 16(1). 35-60.

п. Следовательно, данное утверждение Голича предположительно позволяет построить более быстрый алгоритм распознавания совершенной уравновешенности. Далее в разделе 1.3 работы приводятся ряд утверждений, следствием из которых становится Теорема 1.3.2, опровергающая утверждение Голича, а также целый класс возможных ослаблений данного утверждения — доказывается, что для всякого сколь угодно большого с найдется такое п и такая функция /, что отображение /п+с является уравновешенным, но при этом функция / совершенно уравновешенной не является.

Для построения существенно более быстрого, чем алгоритм М. И. Рожкова, алгоритма распознавания свойства совершенной уравновешенности далее в разделе 1.3 работы вводится понятие графа сдвигов булевой функции. В терминах графа сдвигов доказывается критерий совершенной уравновешенности булевой функции (Теорема 1.3.4). на основе которого строится алгоритм распознавания свойства совершенной уравновешенности по вектору значений булевой функции за 0(Ы2) операций. Таким образом, впервые получен полиномиальный алгоритм распознавания свойства совершенной уравновешенности по вектору значений.

Как следует из результатов С. Н. Сумарокова, символы выходной последовательности кодирующего устройства являются независимыми равномерно распределенными (в предположении, что таковы символы входной последовательности) в том и только в том случае, когда функция усложнения данного кодирующего устройства совершенно уравновешена. В разделе 1.4 исследуются свойства преобразований, осуществляемых кодирующими устройствами в случае, когда ни в какой из возможных входных последовательностей не встречаются определенные поднаборы. Доказывается Теорема 1.4.1, представляющая критерий совершенной уравновешенности, описывающий особенности поведения кодирующих устройств на таких множествах входных последовательностией в зависимости от совершенной уравновешенности функций усложнения.

Ранее, за исключением единичных примеров, не было известно каких-либо множеств совершенно уравновешенных функций, нелинейно существенно зависящих от крайних переменных. Данное обстоятельство существенно осложняло как исследование свойств совершенно уравновешенных булевых функций (что продемонстрировано в разделах 2.2 и 4.1 опровержениями полученных ранее утверждений о совершенно уравновешенных функциях), так и синтез совершенно уравновешенных функций для использования в прак-

тических приложениях (зачастую свойство линейности по одной из крайних переменных является нежелательным). С целью развития данного направления исследований в главе 2 вводится класс функций с барьером.

В разделе 2.1 вводится понятие барьера булевой функции, устанавливаются простейшие свойства функций с барьером: обосновывается достаточность наличия у функции барьера для совершенной уравновешенности, описываются классы сохраняющих свойство барьера преобразований, вводятся простейшие классы совершенно уравновешенных булевых функций с барьером. Доказывается (Теорема 2.1.1) существование булевых функций, которые не имеют барьера, но при этом являются совершенно уравновешенными. Строится метод, позволяющий получать (с ростом числа переменных) булевы функции со сколь угодно большой длиной барьера. Доказывается утверждение (Теорема 2.1.3) о существовании для сколь угодно большого натурального с таких совершенно уравновешенных булевых функций, длина барьера которых превосходит число переменных не менее, чем на с. В заключение раздела приводится описание строения множества функций с барьером длины 1 (линейные по крайней переменной функции) и 2 (не зависящие существенно от одной из крайних переменных и линейные по соседней с ней).

Как следует из результатов раздела 2.1, совершенно уравновешенные функции с барьером, зависящие нелинейно от крайних существенных переменных, следует искать во множестве функций с барьером длины не менее 3. В разделе 2.2 проводится изучение множества существенно зависящих от крайних переменных функций с барьером длины 3. С помощью разработанного аппарата помеченных графов де Брейна формулируется и доказывается критерий наличия у функции правого барьера длины 3 (Теорема 2.2.1). Этот критерий позволяет для определения наличия данного свойства у функции переходить от проверки выполнимости системы булевых уравнений к проверке некоторого конечного набора свойств подфункций. Он оказывается удобным для проверки наличия у булевой функции барьера длины 3 — с помощью него далее в разделе 2.2 обосновывается некорректность результата Кс. Лэя и Дж. Месси о достаточном условии кодирующего устройства быть 2-обратимым13.

13Lai X., Massey ./. Some connections between scramblers and invertible automata Proceedings of 1988 Beijing International Workshop on Information Theory. 1988. Pp. DI 5.1 - DI 5.5.

Далее также с помощью полученного критерия наличия у булевой функции барьера длины 3 строится опровержение доказанного (с пробелом в доказательстве) Маркусом Дихтлом неверного результата о необходимом условии совершенной уравновешенности. Строится булева функция с барьером длины 3, не удовлетворяющая необходимому условию Дихтла.

В разделе 2.3 рассматриваются свойства частично определенной булевой функции, определяющей процедуру частичного восстановления входной последовательности кодирующего устройства с функцией, обладающей правым барьером. С помощью развития аппарата помеченных графов де Брейна формулируется и доказывается утверждение (Теорема 2.3.1) об уравновешенности упомянутой частично определенной булевой функции на своей области определения. В заключение раздела рассматриваются примеры, демонстрирующие существенность свойств кодирующего устройства с функцией с барьером для уравновешенности частично определенной функции описанного вида в случае ее существования.

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

В разделе 3.1 разрабатывается аппарат исследования булевых функций с барьером с помощью множеств начальных состояний. Устанавливается (Теорема 3.1.1) свойство булевых функций с барьером, определяющее структуру множества прообразов произвольного набора достаточно большой длины относительно отображения /г- Доказывается критерий наличия у булевой функции барьера фиксированной длины (Теорема 3.1.2), позволяющий ввести для произвольной функции с правым (левым) барьером целочисленный параметр е^ (соответственно, через который выражаются мощности таких множеств, как образ отображения /т при фиксированном начале (конце) входной последовательности, множества начал фиксированной длины и окончаний (окончаний фиксирован-

ной длины и начал) входных последовательностей в прообразе любой выходной последовательности. Устанавливаются неравенства на параметры ej? и e'j, а также критерии равенств в данных неравенствах.

С помощью разработанного аппарата в разделе 3.2 устанавливается критерий принадлежности функции классу функций без предсказывания (Теорема 3.2.2): свойство булевой функции быть функцией без предсказывания оказывается эквивалентно свойству наличия у функции правого барьера, причем величина отрезка выходной последовательности, после которой каждый последующий символ (в естественной вероятностной модели, предполагающей независимость и равномерное на множестве 0, 1 распределение всех символов входной последовательности, за исключением известных) не может быть предсказан с вероятностью, отличной от даже при наличии полной информации о начале входной последовательности, оказывается находящейся в прямой зависимости от длины правого барьера данной функции, а при сокращении отрезка существуют ситуации, при которых предсказывание символов с отличной от ^ вероятностью всегда возможно.

Полученные результаты оказываются чрезвычайно полезными для исследования поставленной в качестве открытого вопроса14 задачи о мощности множества так называемых инверсионных функций для произвольной функции с барьером. В завершение раздела 3.2 приводится утверждение (Теорема 3.2.3), представляющее решение данной задачи.

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

14Lai X., Massey J. Some connections between scramblers and invertible automata Proccedings of 1988 Beijing International Workshop on Information Theory. 1988. Pp. DI 5.1 - DI 5.5.

щего устройства оставшиеся символы входной последовательности можно восстанавливать однозначно по последующим символам выходной последовательности.

Данное понятие было формализовано О. А. Логачевым как понятие локальной обратимости булевой функции15, посвященной изучению соответствующих свойств функций, линейных по последней переменной. В той же работе был получен критерий локальной обратимости порождаемых такими функциями отображений, связывающий данное понятие с так называемым возвратным свойством булевой функции.

В разделе 3.3 проводится исследование свойства локальной обратимости произвольных булевых функций. Устанавливается ряд необходимых свойств локальной обратимости, в частности, совершенная уравновешенность и наличие барьера. Доказывается критерий (Теорема 3.3.6), связывающий локальную обратимость произвольной булевой функции с характеристиками булевых функций с барьером, описанными в разделе 3.2. Следствиями из полученных результатов являются методы построения булевых функций с положительными криптографическими свойствами, не допускающих локального обращения: в частности, для недопущения наличия у булевой функции свойства локальной обратимости достаточно выбирать ее из класса булевых функций без барьера.

В главе 4 исследуются методы построения определенных классов совершенно уравновешенных булевых функций. Описывается операция композиции функций, соответствующая композиции соответствующих кодирующих устройств и приводится полученное О. А. Логачевым утверждение о совершенной уравновешенности функций, полученных такой композицией. В разделе 4.1 доказывается ряд утверждений о свойствах операции композиции кодирующих устройств, позволяющих доказать утверждение (Теорема 4.1.1), которое содержит конструктивное описание широкого класса совершенно уравновешенных булевых функций, нелинейным существенным образом зависящих от обеих крайних переменных. Мощность данного класса представляет собой новую, существенно превосхо-дящую^все ранее полученные, нижнюю оценку числа таких функций: 2 - 5 • 22 .С использованием данного класса строится

1аЛогачев О. А. О локальной обратимости одного класса булевых отображений. Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова. 2007. 440-442.

(Теорема 4.1.2) последовательность классов совершенно уравновешенных булевых функций (при всяком п ^ 7 имеющих мощность не менее 22" 6—22" ), не удовлетворяющих необходимому условию совершенной уравновешенности, предложенному Дихтлом.

Раздел 4.2 посвящен получению верхних и нижних оценок числа функций с правым барьером длины 3. Известной нижней оценкой логарифма числа таких функций п переменных, полученной Лэем и Месси, является 0.75 • 2п~2. С использованием критерия барьера длины 3 и представления функций с барьером длины 3 с помощью троек помеченных графов де Брейна, а также результатов Н. Лихи-ардопола16, оценки размеров максимальных по мощности независимых множеств в определенных модификациях графов де Брейна в разделе 4.2 получена (Теорема 4.2.3) новая нижняя асимптотическая оценка логарифма класса функций с правым барьером длины 3:

(1 + (log2 5)/4 - 0(1/л/п)) • 2П~2 > 1,58048 • 2П~2.

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

Далее в разделе 4.2 с помощью развития аппарата представления булевых функций с правым барьером длины 3 тройками помеченных графов де Брейна и дальнейшего анализа критерия барьера длины 3 устанавливается (Теорема 4.2.5) верхняя оценка логарифма числа таких функций: 2,100641 ■ 2"~2.

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

16Lichiardopol N. Independence number of de Bruijn graphs. Discrete Mathematics. 2006. Vol. 306(12). Pp. 1145 - 1160.

вого барьера и отсутствием левого.

В терминах полиномиального представления приводится (Теорема 4.3.2) конструктивное описание широкого класса совершенно уравновешенных булевых функций без правого барьера, устанавливается асимптотика логарифма его мощности: д-2""1. Разрабатывается аппарат представления булевых функций с помощью пометок ациклических подграфов графа сдвигов булевой функции, в терминах данного представления описываются необходимые и достаточные условия отсутствия у функции правого барьера. Полученные утверждения используются для исследования класса функций с односторонним барьером — функций с правым барьером длины 1 без левого барьера. С использованием данных результатов оказывается возможным (Теорема 4.3.3 и Следствие 4.3.2) установить асимптотику логарифма данного класса. В заключительной части раздела 4.3 устанавливается (Теорема 4.3.4 и Следствие 4.3.4) новая нижняя оценка числа совершенно уравновешенных булевых функций без барьера, представляющая также и нижнюю оценку числа совершенно уравновешенных булевых функций, не являющихся локально обратимыми.

В заключении перечислены основные результаты диссертации.

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

Благодарности. Автор диссертации выражает благодарность своему научному руководителю кандидату физико-математических наук, старшему научному сотруднику Логачеву Олегу Алексеевичу за постановку задач, постоянное внимание к работе и поддержку. Также автор выражает благодарность доктору физико-математических наук, профессору Алексееву Валерию Борисовичу, доктору физико-математических наук, профессору Вороненко Андрею Анатольевичу, кандидату физико-математических наук, доценту Селезневой Светлане Николаевне, кандидату физико-математических наук, доценту Применко Эдуарду Андреевичу, кандидату физико-математических наук, доценту Карпунину Григорию Анатольевичу, кандидату физико-математических наук Ященко Валерию Владимировичу, Варновскому Николаю Павловичу, а также всем сотрудникам кафедры математической кибернетики факультета ВМК МГУ имени М.В. Ломоносова за доброжелательное отношение и творческую атмосферу.

Публикации автора по теме диссертации

Публикации в изданиях из Перечня ВАК

1. O.A. Логачев, C.B. Смышляев. В.В. Ященко. Новые методы изучения совершенно уравновешенных булевых функций. Дискретная математика. Том 21, выпуск 2, 2009, с. 51-74. (C.B. Смышляеву принадлежат следующие результаты: алгоритм распознавания свойства совершенной уравновешенности, описание свойств функций с барьером, доказательство существования функций без барьера, критерий наличия у булевой функции барьера длины 3, описание совершенно уравновешенных булевых функций от п ^ 5 переменных.)

2. C.B. Смышляев. Барьеры совершенно уравновешенных булевых функций. Дискретная математика. Том 22, выпуск 2, 2010, с. 66-79.

3. C.B. Смышляев. Булевы функции без предсказывания. Дискретная математика. Том 23, выпуск 1, 2011, с.102-118.

4. O.A. Логачев, C.B. Смышляев, В.В. Ященко. Ро-уравпове-шенные булевы функции. Дискретная математика. Том 24, выпуск 2, 2012, с. 154-159. (C.B. Смышляеву принадлежат следующие результаты: нижние оценки параметра ß(n), определяющего нижнюю границу М, при которой свойство рм-уравновешенности функции п переменных эквивалентно ее совершенной уравновешенности.)

5. C.B. Смышляев. О числе совершенно уравновешенных булевых функций с барьером длины 3. Прикладная дискретная математика. Выпуск 1(11), 2011, с.26-33.

С. C.B. Смышляев. Локально обратимые булевы функции. Прикладная дискретная математика. Выпуск 4, 2011, с. 11-22.

7. S.V. Smyshlyaev. Perfectly Balanced Boolean Functions and Golic Conjecture. Journal of Cryptology, 25(3): 464-483, 2012.

Публикации в изданиях не из Перечня ВАК

8. C.B. Смышляев. О криптографических слабостях некоторых классов преобразований двоичных последовательностей. Прикладная дискретная математика. Выпуск 1(7), 2010, с. 5-15.

9. C.B. Смышляев. Построение классов совершенно уравновешенных булевых функций без барьера. Прикладная дискретная математика. Выпуск 3(9), 2010, с. 41-50.

10. C.B. Смышляев. О некоторых свойствах совершенно уравновешенных булевых функций. Материалы Четвертой Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму. МГУ имени М.В.Ломоносова, Москва, 30-31 октября 2008 года. МЦНМО, М., 2009, с. 57-64.

11. C.B. Смышляев. О преобразовании двоичных последовательностей с помогцыо совершенно уравновешенных булевых функций. Материалы Пятой Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму. МГУ имени М.В.Ломоносова, Москва. 29-30 октября

2009 года. МЦНМО, М., 2010, с. 31-41.

12. C.B. Смышляев. О свойствах булевых функций без предсказывания. Материалы Шестой Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму. МГУ имени М.В.Ломоносова, Москва. 11-12 ноября

2010 года. МЦНМО, М., 2011, с. 47-56.

13. C.B. Смышляев. О совершенно уравновешенных булевых функциях без барьера. Материалы Восьмой Международной конференции «Дискретные модели в теории управляющих систем», МГУ имени М.В.Ломоносова, Москва, 6-9 апреля 2009 года. МАКС Пресс, М., с. 278-284.

14. O.A. Логачев, C.B. Смышляев, В.В. Ященко. Ро-уравнове-шенные булевы функции и их свойства. Материалы Шестнадцатой Международной Конференции «Проблемы Теоретической Кибернетики», с. 272-276. (C.B. Смышляеву принадлежат следующие результаты: опровержение утверждения Го-лича о достаточном условии совершенной уравновешенности.)

15. C.B. Смышляев. Совершенная уравновешенность дискретных функций н условие Голича. Прикладная дискретная математика. Приложение 5, 2012, с. 28-30.

16. C.B. Смышляев. О некоторых классах булевых функций дефекта нуль. Сборник тезисов XV Международной научной

конференции студентов, аспирантов и молодых ученых «Ломоносов — 2008». Секция «Вычислительная математика и кибернетика». 8—11 апреля, Москва, МГУ имени М.В.Ломоносова. М.: МАКС Пресс, 2008. С. 44-45.

17. C.B. Смышляев. Построение классов совершенно уравновешенных булевых функций без барьера. Сборник тезисов лучших дипломных работ факультета ВМиК МГУ за 2011 год, с. 89-90.

18. O.A. Logachev, A.A. Salnikov, S.V. Smyshlyaev, V.V. Yashchenko. Symbolic Dynamics. Codes and Perfectly Balanced Functions. Proceedings of the NATO Advanced Research Workshop on Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes, Veliko Tarnovo, Bulgaria, 6-9 October 2008. IOS Press, 2009, 222-233. (C.B. Смышляеву принадлежат следующие результаты: описание класса совершенно уравновешенных булевых функций без правого барьера, теорема о сохранении барьеров при операции суперпозиции специального вида, доказательство несуществования не являющихся линейными ни но одной переменной булевых функций, сохраняющих совершенную уравновешенность при введении произвольного набора фиктивных переменных.)

Подписано в печать 15.11.2012 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1268 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

Введение

Глава 1. Общие свойства совершенно уравновешенных булевых функций.

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

1.2. Методы исследования совершенно уравновешенных булевых функций.

1.3. Распознавание свойства совершенной уравновешенности

1.4. Совершенная уравновешенность и недопустимые слова во входной последовательности.

Глава 2. Барьеры булевых функций.

2.1. Понятие барьера булевой функции

2.2. Функции с барьером длины

2.3. Восстановление символов входной последовательности

Глава 3. Функции без предсказывания и локально обратимые функции.

3.1. Критерий наличия барьера у булевой функции

3.2. Булевы функции без предсказывания.

3.3. Локально обратимые булевы функции

Глава 4. Классы совершенно уравновешенных булевых функций

4.1. Построение функций из множества (РВп П Фп) \ и

4.2. Булевы функции с правым барьером длины 3.

4.3. Классы совершенно уравновешенных булевых функций без барьера.

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

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

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

Одним из таких важных свойств булевых функций является свойство совершенной уравновешенности. С помощью совершенно уравновешенных функций можно синтезировать средства обеспечения информационной безопасности, обладающие необходимыми статистическими, теоретико-кодовыми и криптографическими свойствами. Совершенно уравновешенные функции (в соответствующей интерпретации) исследовались рядом авторов в рамках таких разделов математики, как теория дискретных функций, теория кодирования, символическая динамика и крипто-логия. В теории динамических систем в разделе, называемом символической динамикой, они исследуются как «блоковые отображения», порождающие сюръективные эндоморфизмы символических динамических систем (см. [20]). В теории кодирования они рассматриваются как основные элементы «кодирующих устройств», реализующих скользящие блоковые коды без потери информации (см. [12, 21]). В математической криптографии и криптоанализе совершенно уравновешенные булевы функции изучаются как «функции усложнения» таких криптографических примитивов, как комбинирующие и фильтрующие генераторы (см. [3, 24, 26]). Соответствующее дискретное устройство, состоящее из проходного двоичного регистра сдвига и булевой функции, определяющей элементы выходных наборов, в различных источниках называют регистром сдвига с функцией усложнения, кодером, кодирующим устройством и т.п. Далее мы остановимся на термине "кодирующее устройство", использованном, например, в [10].

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

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

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

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

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

Длительное время свойство совершенной уравновешенности булевой функции связывали с линейностью ее по первой (или последней) переменной. Серьезные продвижения в исследовании совершенно уравновешенных булевых функций были сделаны в работах [10, 20]. В частности, в них были сформулированы и доказаны необходимые и достаточные условия, связывающие свойство совершенной уравновешенности булевой функции со свойствами быть функцией без запрета и без потери информации.

Теорема 0.1 ([10, 20]). Пусть / — булева функция. Следующие условия эквивалентны:

1. / совершенно уравновешена; — функция без запрета;

3- I ~ функция без потери информации.

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

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

Р. Андерсоном в работе [13] были выявлены определенные криптографические слабости у ряда функций усложнения, используемых или предлагаемых для использования в системах потокового шифрования. Им же было сформулировано требование к функции усложнения, гарантирующее отсутствие слабостей данного вида и эквивалентное совершенной уравновешенности булевой функции, в связи с чем была поставлена задача построения классов таких функций и изучения их свойств.

В работе [16] Й. Голичем был рассмотрен класс совершенно уравновешенных функций линейных по первой и/или последней переменной, было продемонстрировано негативное криптографическое свойство кодирующих устройств с такими функциями усложнения в случае использования их в системах потокового шифрования; более того, в работах [16, 18] Голичем был предложен метод криптоанализа («инверсионная атака»), существенно использующий это свойство. В [16] была также показана достаточность линейной зависимости булевой функции от крайней переменной для того, чтобы функция оставалась совершенно уравновешенной при добавлении/изъятии произвольного числа несущественных переменных.

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

O.A. Логачевым в [5] была введена (аналогично введенной Хэдлун-дом в [20] операции композиции эндоморфизмов символических динамических систем) специальная операция композиции функций усложнения и было доказано, что данная операция сохраняет класс совершенно уравновешенных функций; был приведен пример, демонстрирующий возможность с помощью данной операции получать совершенно уравновешенные функции, нелинейно зависящие от первой и последней существенной переменной.

А. Гуже и X. Сибер в работе [19] провели исследование связи свойств функций в модели с равномерным распределением на множестве входных последовательностей кодирующего устройства (см. [17]) и в модели с рекуррентной последовательностью небольшого периода. При анализе оптимального в определенном смысле класса функций в первой из моделей (класса совершенно уравновешенных функций) Гуже и Сибер столкнулись с существенными трудностями. По этой причине Гуже и Сибер уделили большее внимание рассмотрению класса функций, обладающих положительными свойствами во второй из рассматриваемых ими моделей, — класса квази-иммунных функций, который был описан в терминах свойств полиномов Жегалкина и оказался значительно более удобным для анализа.

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

Несмотря на немалое количество работ, в которых уделялось большое внимание совершенной уравновешенности булевых функций, большинство исследований и рассмотрений, за небольшим исключением, касались функций, линейных по первой и/или последней существенной переменной — узкого и наименее интересного подмножества совершенно уравновешенных функций. Исследование совершенно уравновешенных функций, нелинейных по крайним (первой и последней) существенным переменным, ограничивалось исключительно примерами таких функций. Одним из неприятных следствий такого подхода стал ряд неверных результатов, полученных при попытках обобщения свойств функций линейных по крайним переменным на все совершенно уравновешенные функции.

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

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

Цель диссертационной работы заключается:

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

2) в исследовании связей между совершенной уравновешенностью булевых функций и возможностью обращения соответствующих кодирующих устройств в различных моделях;

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

Диссертационная работа состоит из четырёх глав, заключения и приложения.

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

1) Разработан эффективный алгоритм распознавания свойства совершенной уравновешенности булевой функции по вектору значений. С помощью программной реализации данного алгоритма получено полное описание совершенно уравновешенных булевых функций от 4 и 5 переменных.

2) Для класса булевых функций с барьером длины 3 доказан критерий принадлежности произвольной функции данному классу. Получены новые верхняя и нижняя асимптотические оценки логарифма мощности данного класса. Получены новые нижние асимптотические оценки логарифма числа совершенно уравновешенных булевых функций, не являющихся линейными по крайним существенным переменным.

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

4) Доказаны свойства локально обратимых булевых функций, позволившие установить критерий локальной обратимости булевой функции; установлены связи между различными модификациями свойства локальной обратимости, а также определенные достаточные условия отсутствия у функции свойства локальной обратимости.

5) Установлена асимптотика логарифма числа булевых функций с левым барьером длины 1 без правого барьера. Получены новые нижние асимптотические оценки логарифма числа совершенно уравновешенных булевых функций без барьера.

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

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

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

3) в учебном процессе студентов-математиков, проходящих обучение в рамках специализации «Математические и программные методы обеспечения информационной безопасности»; в научных центрах, проводящих исследования в области защиты информации.

Заключение

1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. Москва: Мир, 1979.

2. Бабаш А. В. Запреты автоматов и двоичных функций // Труды по дискретной математике. 2006. Т. 9. С. 7-20.

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

4. Логачев О. А. О локальной обратимости одного класса булевых отображений // Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова. 2007. С. 440-442.

5. Логачев О. А. Об одном классе совершенно уравновешенных булевых функций // Материалы Третьей Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму (МаБИТ-2007). 2008. С. 137-141.

6. Рожков М. И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных т-грамм I // Обозрение прикладной и промышленной математики. 2008. Т. 15(4). С. 613-630.

7. Рожков М. И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных т-грамм II // Обозрение прикладной и промышленной математики. 2008. Т. 15(5). С. 786-806.

8. Рожков М. И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм III // Обозрение прикладной и промышленной математики. 2009. Т. 16(1). С. 35-60.

9. Рысцов И. К. Возвратные слова для разрешимых автоматов // Кибернетика и системный анализ. 1994. Т. 6. С. 21-26.

10. Сумароков С. Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств // Обозрение прикладной и промышленной математики. 1994. Т. 1(1). С. 33-55.

11. Холл М. Комбинаторика. Москва: Мир, 1970.

12. Adler R., Coppersmith D., Hassner M. Algorithms for sliding block codes — an application of symbolic dynamics to information theory // IEEE Transactions on Information Theory. 1983. Vol. 29(1). Pp. 5-22.

13. Anderson R. J. Searching for the optimum correlation attack // Lecture Notes in Computer Science. 1995. Vol. 1008. Pp. 137-143.

14. Ash R. Information Theory. New York-London-Sydney: John Wiley and Sons Inc., 1967.

15. Dichtl M. On nonlinear filter generators // Lecture Notes in Computer Science. 1997. Vol. 1267. Pp. 103-106.

16. Golic J. D. On the security of nonlinear filter generators // Lecture Notes in Computer Science. 1996. Vol. 1039. Pp. 173-188.

17. Golic J. D. Conditional correlation attack on combiners with memory // Electronics Letters. 1996. Vol. 32(24). Pp. 2193-2195.

18. Golic J. D., Clark A., Dawson E. Generalized inversion attack on nonlinear filter generator // IEEE Trans. Comput. 2000. Vol. C-49. Pp. 1100-1109.

19. Gouget A., Sibert H. Revisiting correlation immunity in filter generators // Lecture Notes in Computer Science. 2007. Vol. 4876. Pp. 378-395.

20. Hedlund G. A. Endomorphisms and automorphisms of the shift dynamical system // Theory of Computing Systems. 1969. Vol. 3(4). Pp. 320-375.

21. Huffman D. A. Canonical forms for information-lossless finite-state logical machines // IRE Transactions on Circuit Theory. 1959. Vol. 5. Pp. 41-59.

22. Lai X., Massey J. Some connections between scramblers and invertible automata // Proceedings of 1988 Beijing International Workshop on Information Theory. 1988. Pp. DI 5.1 DI 5.5.

23. Lichiardopol N. Independence number of de Bruijn graphs // Discrete Mathematics. 2006. Vol. 306(12). Pp. 1145- 1160.

24. Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. CRC Press, 1996.

25. Preparata F. P. Convolutional transformations of binary sequences: Boolean functions and their resynchronizing properties / / IEEE Transactions on Electronic Computers. 1966. Vol. 15. Pp. 898-909.

26. Schneier B. Applied cryptography. Wiley, 1995.

27. Shannon С. E. Communication theory of secrecy systems // Bell System Technical Journal. 1949. Vol. 28. Pp. 656-715.

28. Публикации автора по теме диссертации Публикации в изданиях из Перечня ВАК

29. Логачев О. А., Смышляев С. В., Ященко В. В. Новые методы изучения совершенно уравновешенных булевых функций // Дискретная математика. 2009. Т. 21(2). С. 51-74.

30. Смышляев С. В. Барьеры совершенно уравновешенных булевых функций // Дискретная математика. 2010. Т. 22(2). С. 66-79.

31. Смышляев С. В. Булевы функции без предсказывания // Дискретная математика. 2011. Т. 23(1). С. 102-118.

32. Логачев О. А., Смышляев С. В., Ященко В. В. Ро-уравновешенные булевы функции // Дискретная математика. 2012. Т. 24(2). С. 154-159.

33. Смышляев С. В. О числе совершенно уравновешенных булевых функций с барьером длины 3 // Прикладная дискретная математика. 2011. Т. И. С. 26-33.

34. Смышляев С. В. Локально обратимые булевы функции // Прикладная дискретная математика. 2011. Т. 14. С. 11-21.

35. Smyshlyaev S. V. Perfectly Balanced Boolean Functions and Golic Conjecture // Journal of Cryptology. 2012. Vol. 25(3). Pp. 464-483.

36. Публикации в изданиях не из Перечня ВАК

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

38. Смышляев С. В. Построение классов совершенно уравновешенных булевых функций без барьера // Прикладная дискретная математика. 2010. Т. 9. С. 41-50.

39. Смышляев С. В. О некоторых свойствах совершенно уравновешенных булевых функций // Материалы Четвертой Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму (МаБИТ-2008). 2009. С. 57-64.

40. Смышляев С. В. О преобразовании двоичных последовательностей с помощью совершенно уравновешенных булевых функций // Материалы Пятой Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму (МаБИТ-2009). 2010. С. 31-41.

41. Смышляев С. В. О свойствах булевых функций без предсказывания // Материалы Шестой Международной Научной Конференции по Проблемам Безопасности и Противодействия Терроризму (Ма-БИТ-2010). 2011. С. 47-56.

42. Смышляев С. В. О совершенно уравновешенных булевых функциях без барьера // Труды Восьмой Международной научной конференции «Дискретные модели в теории управляющих систем». 2009. С. 278-284.

43. Логачев О. А., Смышляев С. В., Ященко В. В. Ро-уравновешенные булевы функции и их свойства // Материалы Шестнадцатой Международной Конференции «Проблемы Теоретической Кибернетики». 2011. С. 272-276.

44. Смышляев С. В. Ро-уравновешенные булевы функции и их свойства // Прикладная дискретная математика. 2012. Т. Приложение 5. С. 28-30.

45. Смышляев С. В. О некоторых классах булевых функций дефекта нуль // Сборник тезисов XV Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов 2008». Секция «Вычислительная математика и кибернетика». 2008. С. 44-45.

46. Смышляев С. В. Построение классов совершенно уравновешенных булевых функций без барьера // Сборник тезисов лучших дипломных работ факультета ВМиК МГУ за 2011 год. 2011. С. 89-90.