Построение и анализ эффективных комбинаторных алгоритмов решения систем булевых уравнений

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

Мелузов Антон Сергеевич ПОСТРОЕНИЕ И АНАЛИЗ ЭФФЕКТИВНЫХ КОМБИНАТОРНЫХ АЛГОРИТМОВ РЕШЕНИЯ СИСТЕМ БУЛЕВЫХ УРАВНЕНИЙ Специальность 05.13.19.

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

АВТОРЕФЕРАТ

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

Mосква 2012

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

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

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

доктор физико-математических наук профессор Бабаш Александр Владимирович;

кандидат физико-математических наук Сергеев Игорь Сергеевич.

Ведущая организация: Российский государственный гуманитарный университет

Защита диссертации состоится 29 февраля 2012 года в 1645 на заседании диссертационного совета Д.501.002.16 при Московском государственном университете имени М.В. Ломоносова по адресу:

РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Главное здание, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-ма тематического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 2012 г.

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

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

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

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

Среди известных методов решения систем булевых уравнений можно выделить несколько направлений, по которым велись иссле дования различными авторами. Универсальным методом решения систем полиномиальных уравнений, который может быть применен и для решения булевых систем, является метод построения мини мального редуцированного базиса Грёбнера идеала, образованного полиномами, входящими в систему уравнений. Для построения ба зиса Грёбнера идеала известны алгоритм Бухбергера1 и алгоритмы F4, F5, предложенные Ж.-К. Фажере23.

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

1 B. Buchberger. Grbner-Bases: An Algorithmic Method in Polynomial o Ideal Theory. Reidel Publishing Company, Dodrecht - Boston - Lancaster, 1985.

2 J.-C. Faug`re. A new ecient algorithm for computation Grebner e o bases (F4 ). Journal of pure and applied algebra, 1999.

3 J.-C. Faug`re. A new ecient algorithm for computation Grebner e o bases without reduction to zero (F5 ). Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.75–83, 2002.

Группой ученых под руководством Н. Куртуа были предложены усовершенствования XL4 и XSL5 метода линеаризации для случа ев, когда количество уравнений в системе недостаточно для эффек тивного применения линеаризации в классическом виде. Суть дан ных методов состоит в дополнении системы новыми уравнениями, которые не меняют множества решений системы, но увеличивают размер системы и ранг линеаризованной системы. Позднее Н. Кур туа и Г.В. Бардом был предложен еще один метод, основанный на методе линеаризации ElimLin6.

Поскольку задача выполнимости конъюнктивной нормальной формы (КНФ) является актуальной и её исследованию посвящено значительное количество научных работ, кроме того постоянно со вершенствуются алгоритмы решения задачи выполнимости КНФ, важным направлением в решении систем булевых полиномиальных уравнений стало сведение задачи поиска решения системы к задаче выполнимости КНФ7 8 9 10 11.

Семейство комбинаторных методов решения разреженных си стем булевых уравнений было предложено И. Семаевым и Г. Рад 4 N. Courtois, A. Klimov, J. Patarin, A. Shamir. Ecient Algorithms for Solving Overdened Systems of Multivariate Polynomial Equations.

Advances in Cryptology, EUROCRYPT 2000, p. 392–407, 2000.

5 N. Courtois, J. Pieprzyk. Cryptanalysis of block chiphers with overdened systems of equations. Proc. 8th Int. Conf. on the Theory and Application of Cryptology and Information Security, Springer, p. 267–287, 2002.

6 N. Courtois, G. V. Bard Algebraic cryptanalysis of the data encryption standard. IMA International Conference on Cryptography and Coding Theory, Lecture Notes in Computer Science, Springer-Verlag, p. 152 169, 2007.

7 F. Massacci, L. Marraro. Logical Cryptanalysis as a SAT Problem.

Journal of Automated Reasoning, Springer Netherlands, p. 165-203, 2000.

8 C. Fiorini, E. Martinelli, F. Massacci. How to fake an RSA signature by encoding modular root nding as a SAT problem. Discrete Applied Mathematics, p. 101-127, 2003.

9 A. K. Abdel, Y. M. Amr. Applications of SAT Solvers to AES key Recovery from Decayed Key Schedule Images. Cryptology ePrint Archive, http://eprint.iacr.org/, vol. 324, 2010.

10 I. Mironov, L. Zhang. Applications of SAT Solvers to Cryptanalysis of Hash Functions. Cryptology ePrint Archive, http://eprint.iacr.org/, vol. 254, 2006.

11 О. А. Логачев, С. В. Смышляев. Логический криптоанализ потоково го шифра LILI-128. Материалы 8-й Общероссийской конференции МаБИТ– 09, МЦНМО, 2009.

думом12 13 14. Принципиальным отличием методов данного семей ства от известных ранее является то, что объектами рассмотре ния являются множества решений отдельных уравнений системы, из которых, путем последовательного согласования и склеивания, строится множество решений исходной системы.

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

В такой ситуации актуальными направлениями исследований яв ляются: поиск классов систем булевых уравнений, которые могут быть решены с субэкспоненциальной от числа переменных трудо емкостью;

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

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

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

Целью диссертационной работы является разработка и ис следование эффективных алгоритмов решения систем булевых урав нений, а также поиск классов систем булевых уравнений, допуска ющих сокращение трудоемкости их решения по сравнению с мето дом полного перебора. Это научное направление соответствует об ластям исследований, перечисленным в пп. 7, 9, 10 и 14 Паспорта специальности 05.13.19 методы и системы защиты информации, информационная безопасность.

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

1. Разработка методов решения систем булевых уравнений с ис 12 H. Raddum, I. Semaev. New technique for Solving Sparse Equation Systems. Cryptology ePrint Archive, http://eprint.iacr.org/2006/475, 2006.

13 I. Semaev. Sparse Boolean equations and circuit lattices. Designs, Codes and Cryptography, Springer Netherlands, p.349-364, 2011.

14 I. Semaev. Improved Agreeing-Gluing algorithm. Proceedings of SCC’10, Royal Holloway, University of London, p.73–88, 2010.

пользованием ассоциативных принципов обработки информа ции.

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

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

4. Применение полученных результатов в криптографическом анализе потокового шифра LILI-128.

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

Методологической основой и научно-теоретической ба зой диссертации являются работы Б. Бухбергера, Ж.-К. Фажере, Н. Куртуа, И. Семаева о методах решения систем булевых уравне ний, а также работы В.Ф. Колчина, В.Н. Сачкова и Г.В. Балакина, посвященные исследованию случайных систем булевых уравнений.

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

Научная новизна исследования заключается в следующем. В диссертации предложены новые подходы к решению систем буле вых уравнений. Впервые предложено использовать для решения систем булевых уравнений специальные ассоциативные вычислите ли. Помимо адресной организации памяти вычислительных машин, возможна организация доступа к ячейкам памяти по их содержи мому. Организованная таким образом память называется ассоциа тивной (Content-addressable memory, CAM), когда операции с ячей ками памяти осуществляются в зависимости от записанной в них информации. Такой подход к организации памяти эффективен, на пример, в задачах поиска. Подобные устройства активно исполь зуются в современных информационных технологиях. Например, в сетевых коммутаторах, позволяя за одну операцию по IP–адресу определять физический порт, по которому следует передать пакет.

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

Для поиска решений системы булевых уравнений с использова нием преимуществ ассоциативных вычислителей разработан алго ритм ассоциативного обхода дерева решений (АОДР). Предложе на теоретико–вероятностная модель случайной системы булевых уравнений, характерная для систем, моделирующих работу блоч ных шифров. В рамках этой модели получена оценка математи ческого ожидания трудоемкости решения систем булевых уравне ний с использованием ассоциативных вычислителей, основанная на связности уравнений системы по переменным и зависящая от ха рактера этой связности. Найдены множества типов систем бу левых уравнений на которых асимптотика математического ожи дания трудоемкости решения систем булевых уравнений является субэкспоненциальной.

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

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

15 K. Pagiamtzis, A. Sheikholeslami. Content-addressable memory (CAM) circuits and architectures: A tutorial and survey. IEEE Journal of Solid-State Circuits, vol. 41, no. 3, 2006.

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

На защиту выносятся:

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

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

алгоритм, реализующий метод ЧОМС решения систем буле вых полиномиальных уравнений с опробованием переменных и исследованием редуцированных систем на мономиальную совместность и верхняя асимптотическая оценка математи ческого ожидания трудоемкости поиска всех решений систем булевых полиномиальных уравнений, а также верхняя асимп тотическая оценка математического ожидания трудоемкости поиска всех решений для квадратичных систем булевых по линомиальных уравнений;

метод ЧОМС(L) определения ключа потокового шифра LILI– 128 по известным открытому и шифрованному текстам и оцен ки его трудоемкости для различных объемов исходных дан ных;

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

Теоретическая и практическая значимость. Диссертаци онная работа имеет теоретический характер. Полученные в диссер тации результаты могут найти применение:

при анализе и синтезе средств обеспечения информационной безопасности;

при разработке методов криптографического анализа и оцен ки их эффективности;

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

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

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

VI Молодежной научной школе по дискретной математике и её приложениям;

XVII Международной научной конференции студентов, аспи рантов и молодых ученых Ломоносов–2010 ;

Научной конференции Тихоновские чтения–2010 ;

Семинаре кафедры Математической кибернетики ВМК МГУ им. М.В. Ломоносова Дискретная математика и математи ческая кибернетика, неоднократно (2010–2011гг.);

Семинаре кафедры Математической кибернетики ВМК МГУ им. М.В. Ломоносова Математические проблемы криптогра фического анализа, 2011г.;

Семинаре по криптографии Института проблем информаци онной безопасности МГУ им. М.В. Ломоносова, 2011г.

Публикации. Основные положения и выводы диссертации опуб ликованы в 7 печатных работах [1–7], из них 2 статьи [1, 2] в изда ниях из перечня ВАК РФ ведущих рецензируемых журналов.

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

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

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

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

Кратко описан метод решения систем полиномиальных уравне ний, основанный на построении минимального редуцированного ба зиса Грёбнера идеала, описываемого системой уравнений. Приведе ны известные оценки трудоемкости классического алгоритма Бух бергера построения базиса Грёбнера, а также метод оценки трудо емкости построения базиса Гребнера идеала для почти всех систем булевых полиномиальных уравнений с помощью нового алгоритма F5, предложенного Ж.–К. Фажере.

Другим важным направлением является решение систем буле вых полиномиальных уравнений с помощью линеаризации и с по мощью методов, основанных на линеаризации (XL, FXL и XSL).

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

Кратко рассмотрены возможности применения алгоритмов ре шения задач выполнимости КНФ (SAT) для решения систем буле вых уравнений. Приведены примеры использования существующих SAT–решателей для решения систем булевых уравнений в работах отечественных и зарубежных ученых.

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

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

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

Для каждого множества B(X1, X2,..., Xm ) всех систем булевых уравнений с заданными количеством уравнений m, количеством m переменных n = | i=1 Xi | и множествами X1, X2,..., Xm суще ственных переменных для каждого уравнения системы может быть однозначно определена последовательность {d1, d2,..., dm }, задаю щая количество переменных в каждом уравнении, от которых не зависело ни одно из предыдущих уравнений системы. Каждое мно жество B(X1, X2,..., Xm ) задает тип систем булевых уравнений с такими параметрами.

Доказана Лемма 2.5, утверждающая, что если в случайной си стеме булевых уравнений последовательность {d1, d2,..., dm } яв ляется невозрастающей и, кроме того, число уравнений системы превышает число переменных, то существует номер k0 [1, m) та кой, что математическое ожидание количества решений системы уравнений, составленной из первых k = k0 уравнений исходной си стемы, является наибольшим для всех возможных k. В утвержде нии Леммы 2.6 определено максимальное значение математическо го ожидания количества решений системы уравнений, составлен ной из первых k = k0 уравнений исходной системы, через функцию (x), ограничивающую сверху последовательность {d1, d2,..., dm } и принимающую значение 1 хотя бы в одной точке x0 отрезка [1, m), как x (x) dx x0.

С использованием лемм 2.5 и 2.6 доказано следующее утвержде ние.

Теорема 2.7. Пусть множество B(X1, X2,..., Xm ) таково, что: d1 1, m n, последовательность d1, d2,..., dm невозрас тает, существует невозрастающая функция (x): (x) d(x), x (0, k0 ] и существует x0 : (x0 ) = 1.

Тогда математическое ожидание трудоемкости поиска всех решений случайной системы булевых уравнений из такого мно жества B(X1, X2,..., Xm ) с помощью алгоритма АОДР не пре восходит x (x) dxx c·m·2, где c константа, которая не зависит от параметров системы.

Далее во второй главе определены классы множеств типов си стем уравнений (Определения 2.8 и 2.9), для которых функция (x) такова, что становятся верны верхние субэкспоненциальные асимп тотические оценки математического ожидания трудоемкости реше ния систем из такого набора типов систем уравнений (Теоремы 2. и 2.11) при стремлении числа переменных и количества уравнений в системе к бесконечности. Доказанные верхние оценки асимптотики 2 n математического ожидания трудоемкости составляют O(n·2C · log n ) и O(n · 2D n(log D+log n1) ) при n для ограничивающих по n следовательность {d1, d2,..., dm } функций (x) = C · log n · x и n (x) = D · x+1 соответственно. Здесь C и D любые константы.

Также в главе 2 рассмотрен алгоритм АОДР(S), являющийся модификацией алгоритма АОДР, предназначенной для примене ния в случаях ограниченности ёмкостных характеристик ассоци ативных вычислителей. Получено Следствие 2.14 из Теоремы 2.7, доказывающее верхнюю оценку математического ожидания трудо емкости для модифицированного алгоритма АОДР(S), равную x (x) dxx c · n · l · m · 20, где c константа, которая не зависит от параметров системы, а l максимальное количество переменных в одном уравнении.

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

По результатам экспериментов удалось продемонстрировать, что трудоемкость в среднем при решении разреженных по переменным систем булевых уравнений у алгоритмов АОДР и АОДР(F) ниже, чем у алгоритма полного перебора. Полученные эксперименталь ные данные не противоречат теоретическим результатам, получен ным в диссертации.

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

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

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

Теорема 3.6. Все коэффициенты при мономах в случайной си стеме, полученной из системы, случайно равновероятно выбран ной из множества элементарных исходов (m, s, d), в результате опробования переменных из множества X значениями некоторо го двоичного вектора a, являются независимыми в совокупности случайными величинами, принимающими значения 0 и 1 с веро ятностью p = 2.

С помощью известного критерия Кронекера–Капелли совмест ности систем линейных алгебраических уравнений, а также дока занных в работах В.Ф. Колчина 16, В.Н. Сачкова 17 и Г.В. Балаки на 18 утверждений, характеризующих распределение ранга случай ной системы линейных булевых уравнений и вероятность совмест ности случайной системы линейных булевых уравнений, доказано следующее утверждение о характере изменения вероятности сов местности случайной системы линейных булевых уравнений, при изменении размеров системы.

Лемма 3.10. Для любых целых z 0, l 1, T 1 верно:

PT (l + z) · PT (l), 2z где PT (x) вероятность совместности системы линейных алгеб раических уравнений, заданной матрицей [A|b], причем A слу чайная двоичная матрица с размерами T (T +x), а b случайный двоичный вектор–столбец правых частей длины T.

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

Для определения оптимального числа k опробуемых в алгорит ме ЧОМС переменных используется выражение k = s n, где n наибольшее не превосходящее s целое положительное решение d неравенства m i=1 n n + 2, m количество уравнений в i системе, s количество переменных в системе, а d наибольшая алгебраическая степень полиномов системы. Доказано следующее утверждение, задающее верхнюю асимптотическую оценку матема 16 В.Ф. Колчин. Случайные графы. Москва:Физматлит, 2006, С. 256.

17 В.Н. Сачков. Системы случайных уравнений над конечными поля ми. Труды по дискретной математике, № 8, 2004.

18 Г.В. Балакин. Системы случайных уравнений над конечным полем.

Труды по дискретной математике, № 2, 1998.

тического ожидания трудоемкости алгоритма ЧОМС поиска всех решений систем булевых полиномиальных уравнений.

Теорема 3.11. Пусть, в условиях Теоремы 3.6, задана случай ная система булевых полиномиальных уравнений из m полиноми альных уравнений степени не выше d от s неизвестных. Пусть n наибольшее не превосходящее s целое положительное решение неравенства m Sn,d n + 2.

Пусть случайная величина, равная трудоемкости решения с помощью алгоритма ЧОМС случайной системы булевых уравне ний при опробовании k = sn переменных, заданных множеством X, |X| = k.

Тогда математическое ожидание случайной величины имеет верхнюю асимптотическую оценку O(2k · m3 ) при m.

На основании утверждения Теоремы 3.11 доказана верхняя асимп тотическая оценка математического ожидания трудоемкости поис ка всехрешений квадратичных систем булевых уравнений, равная 8m O(2s · m3 ) при m, где s число неизвестных, а m число уравнений в квадратичной системе булевых полиномиальных уравнений (Теорема 3.13).

В главе 4 рассмотрен потоковый шифр LILI 128, построен ный на основе фильтрующего генератора с нерегулярным движени ем. Для него разработан комбинаторный метод определения ключа ЧОМС(L) основанный на использовании алгоритма ЧОМС. Полу чены оценки трудоемкости восстановления ключа шифра LILI 128 по известным открытому и шифрованному тексту. При длине известной шифрующей последовательности 217,5 бит, трудоемкость в среднем восстановления ключа составляет 2100 битовых опера ций, а необходимый для этого объем памяти составляет 242,6 бит.

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

В отличие от известных ранее методов анализа потокового шиф ра LILI 128, предложенный в главе 4 метод ЧОМС(L) применим при меньших объемах известной шифрующей последовательности.

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

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

В приложении Б приведены численные результаты эксперимен тов по исследованию средней трудоемкости работы алгоритмов пол ного перебора, АОДР и АОДР(F).

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

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

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

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

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

4. Разработан метод и алгоритм ЧОМС решения систем буле вых полиномиальных уравнений с опробованием переменных и исследованием редуцированных систем на мономиальную совместность, получены верхняя асимптотическая оценка ма тематического ожидания трудоемкости поиска всех решений систем булевых полиномиальных уравнений и верхняя асимп тотическая оценка математического ожидания трудоемкости поиска всех решений для квадратичных систем булевых по линомиальных уравнений.

5. Разработан метод ЧОМС(L) определения ключа потокового шифра LILI–128 по известным открытому и шифрованному текстам и получены оценки его трудоемкости для различных объемов исходных данных.

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

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

Список литературы [1] А.С. Мелузов. Использование ассоциативных принци пов обработки информации для построения алгорит мов решения систем булевых уравнений. Журнал вы числительной математики и математической физики, 50, № 11, 2010, С.2028–2044.

[2] А.С. Мелузов. Построение эффективных алгоритмов решения систем полиномиальных булевых уравнений методом опробования части переменных. Дискретная математика, 23, № 4, 2011, С.66–79.

[3] А.С. Мелузов. Оценка сложности применения символьных ме тодов в криптоанализе алгоритма ГОСТ 28147-89. Сборник ра бот молодых ученых факультета ВМК МГУ, № 4, 2007, С.109– 112.

[4] А.С. Мелузов. Сложность применения символьных методов в криптоанализе алгоритма ГОСТ 28147-89. Материалы VI на учной школы по дискретной математике и её приложениям (Москва, 16-21 апреля 2007 г.), 2007, С.20–26.

[5] А.С. Мелузов. Алгоритмы решения систем булевых уравне ний с использованием ассоциативных принципов обработки ин формации. Материалы Международного молодежного научно го форума ЛОМОНОСОВ-2010, 2010, С.35–36.

[6] А.С. Мелузов. Построение эффективных алгоритмов решения систем полиномиальных уравнений над полем GF(2) методом частичного опробования переменных. Научная конференция Тихоновские чтения, 2010, С.12–13.

[7] А.С. Мелузов. О криптоанализе LILI-128, основанном на ча стичном опробовании и мономиальной совместности систем по линомиальных уравнений. Сборник работ молодых ученых фа культета ВМК МГУ, № 8, 2011, С.99–107.