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

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

Мелузов Антон Сергеевич

ПОСТРОЕНИЕ И АНАЛИЗ ЭФФЕКТИВНЫХ КОМБИНАТОРНЫХ АЛГОРИТМОВ РЕШЕНИЯ СИСТЕМ БУЛЕВЫХ УРАВНЕНИЙ

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

си

005011575

1 6 ОЕЗ 2С12

АВТОРЕФЕРАТ

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

Москва - 2012

005011575

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

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

старший научный сотрудник Логачев Олег Алексеевич;

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

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

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

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

гуманитарный университет

Защита диссертации состоится «29» февраля 2012 года в 1645 на заседании диссертационного совета Д.501.002.16 при Московском государственном университете имени М.В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Главное здание, механико-математический факультет, аудитория 14-08.

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

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

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

A.A. Корнев

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

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

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

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

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

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

2J.-C. Faugére. A new efficient algorithm for computation Groebner bases (F4). Journal of pure and applied algebra, 1999.

3J.-C. Faugére. A new efficient algorithm for computation Groebner 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.

Семейство комбинаторных методов решения разреженных систем булевых уравнений было предложено И. Семаевым и Г. Рад-

4N. Courtois, A. Klimov, J. Patarin, A. Shamir. Efficient Algorithms for Solving Overdeflned Systems of Multivariate Polynomial Equations. Advances in Cryptology, EUROCRYPT 2000, p. 392-407, 2000.

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

6N. 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.

7F. Massacci, L. Marraro. Logical Cryptanalysis as a SAT Problem. .Journal of Automated Reasoning, Springer Netherlands, p. 165-203, 2000.

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

9A. 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.

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

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

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

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

20(п)

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

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

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

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

1. Разработка методов решения систем булевых уравнений с ис-

12 Н. Raddum, I. Semaev. New technique for Solving Sparse Equation Systems. Cryptology ePrint Archive, http://eprint.iacr.org/2006/475, 2006.

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

14L 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, САМ), когда операции с ячейками памяти осуществляются в зависимости от записанной в них информации. Такой подход к организации памяти эффективен, например, в задачах поиска. Подобные устройства активно используются в современных информационных технологиях. Например, в сетевых коммутаторах, позволяя за одну операцию по IP-адресу определять физический порт, по которому следует передать пакет.

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

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

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

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

Pagiamtzis, A. Sheikholeslami. Content-addressable memory (САМ) circuits and architectures: A tutorial and survey. IEEE Journal of Solid-State Circuits, vol. 41, no. 3, 200G.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— Научной конференции «Тихоновские чтепия-2010»;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сывающих функционирование блочных шифров.

Для каждого множества В(Хi, Хг,..., Хт) всех систем булевых уравнений с заданными количеством уравнений ш, количеством переменных п = и множествами Х^Хъ, ■ ■ ■ ,Хт суще-

ственных переменных для каждого уравнения системы может быть однозначно определена последовательность {di,¿2,..., dm}, задающая количество переменных в каждом уравнении, от которых не зависело ни одно из предыдущих уравнений системы. Каждое множество В(Хь-Хг, • •., Хт) задает тип систем булевых уравнений с такими параметрами.

Доказана Лемма 2.5, утверждающая, что если в случайной системе булевых уравнений последовательность {<fi,c?2, • • • >dm} является невозрастающей и, кроме того, число уравнений системы превышает число переменных, то существует номер ко € [1,т) такой, что математическое ожидание количества решений системы уравнений, составленной из первых к = ко уравнений исходной системы, является наибольшим для всех возможных к. В утверждении Леммы 2.6 определено максимальное значение математического ожидания количества решений системы уравнений, составленной из первых к — ко уравнений исходной системы, через функцию 6(х), ограничивающую сверху последовательность {<ii, ¿2,..., dm} и принимающую значение 1 хотя бы в одной точке xq отрезка [1, т), как

хо

J 5(x)dx - жо-

о

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

Теорема 2.7. Пусть множество В(Х\, Х^ч •.. ,-^т) таково, что: di > 1, т ^ п, последовательность d\,d^, ■. ■ ,dm невозрастает, существует невозрастающая функция S(x): д(х) > d{x),x £ (О, и существует xq : 5(хо) = 1.

Тогда математическое ожидание трудоемкости поиска всех решений случайной системы булевых уравнений из такого множества B(Xi,X2,...,Хт) с помощью алгоритма АОДР не превосходит

/ 5{х) dx—xо с-тп- 2° ,

где с — константа, которая не зависит от параметров системы.

Далее во второй главе определены классы множеств типов систем уравнений (Определения 2.8 и 2.9), для которых функция 5(х) такова, что становятся верны верхние субэкспоненциальные асимптотические оценки математического ожидания трудоемкости решения систем из такого набора типов систем уравнений (Теоремы 2.10 и 2.11) при стремлении числа переменных и количества уравнений в системе к бесконечности. Доказанные верхние оценки асимптотики математического ожидания трудоемкости составляют 0(п-2с ' 1оеп) и 0(п ■ ПрИ п оо для ограничивающих по-

следовательность {£¿1, £¿2, • • • , ¿т} функций 5(х) — С • • И

5(х) — Б • соответственно. Здесь С и Б — любые константы.

Также в главе 2 рассмотрен алгоритм АОДР (Б), являющийся модификацией алгоритма АОДР, предназначенной для применения в случаях ограниченности ёмкостных характеристик ассоциативных вычислителей. Получено Следствие 2.14 из Теоремы 2.7, доказывающее верхнюю оценку математического ожидания трудоемкости для модифицированного алгоритма АОДР(Э), равную

«о

/ 5(х) йх—хо С' ■ П ■ I • 771 • 2 о . ,

где с' — константа, которая не зависит от параметров системы, а I — максимальное количество переменных в одном уравнении.

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

По результатам экспериментов удалось продемонстрировать, что трудоемкость в среднем при решении разреженных по переменным

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

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

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

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

Теорема 3.6. Все коэффициенты при мономах в случайной системе, полученной из системы, случайно равновероятно выбранной из множества элементарных исходов С1(т, в, (Г), в результате

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

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

Лемма 3.10. Для любых целых г ^ 0,2 ^ 1,Т ^ 1 верно:

гдеТт(я) — вероятность совместности системы линейных алгебраических уравнений, заданной матрицей [Л|6], причем А—случайная двоичная матрица с размерами Т х (Т+х), а Ь — случайный двоичный вектор-столбец правых частей длины Т.

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

Для определения оптимального числа к опробуемых в алгоритме ЧОМС переменных используется выражение к = в — п, где п ~ наибольшее не превосходящее я целое положительное решение неравенства т — (™) > п 2, ш —количество уравнений в системе, я —количество переменных в системе, а в, — наибольшая алгебраическая степень полиномов системы. Доказано следующее утверждение, задающее верхнюю асимптотическую оценку матема-

1вВ.Ф. Колчин. Случайные графы. Москва:Физматлит, 2006, С. 256.

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

1аГ.В. Бала кик. Системы случайных уравнений над конечным полем. Труды по дискретной математике, № 2, 1998.

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

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

т- Sn,d > п + 2.

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

Тогда математическое ожидание случайной величины 7 имеет верхнюю асимптотическую оценку 0(2к • т3) при т —¥ оо.

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

0 i у/Ит — 7—3 i о.

0(2 2 i ■ т°) при т оо, где s — число неизвестных, аш-число уравнений в квадратичной системе булевых полиномиальных уравнений (Теорема 3.13).

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

В отличие от известных ранее методов анализа потокового шифра LILI —128, предложенный в главе 4 метод 40MC(L) применим при меньших объемах известной шифрующей последовательности. Кроме того, при соответствующем изменении подготовительного этапа, на котором формируется система булевых полиномиальных уравнений, метод 40MC(L) может быть применен для криптографического анализа любого потокового шифра данного вида.

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

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

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

Заключение

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

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

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

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

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

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

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

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

Список литературы

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

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

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

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

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

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

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

Отпечатано в отделе оперативной печати Геологического ф-та МГУ ТиражЦв экз. Заказ № £

Введение

Глава 1. Обзор существующих подходов к решению систем уравнений над конечными полями.

1.1. О задаче решения систем булевых уравнений

1.2. Базисы Грёбнера.

1.3. Линеаризация, XL, XSL.

1.4. Использование SAT-решателей.

1.5. Алгоритмы согласования и склеивания.

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

2.1. Параметры и характеристики модели ассоциативного вычислителя

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

2.3. Оценка трудоемкости алгоритма АОДР.

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

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

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

3.1. Опробование переменных в системе булевых полиномиальных уравнений и мономиальная совместность.

3.2. Метод ЧОМС решения систем булевых уравнений.

3.3. Теоретико-вероятностная модель для метода ЧОМС.

3.4. Ранг случайных систем линейных булевых уравнений и вероятность их совместности.

3.5. Оценка трудоемкости метода ЧОМС

Глава 4. Применение алгоритмов решения систем булевых уравнений для анализа потокового шифра ЫЫ-128.

4.1. Потоковый шифр ЫЫ-128.

4.2. Атака на основе открытого и шифрованного текстов.

4.3. Существующие методы криптоанализа ЫЫ-128.

4.4. Метод ЧОМС(Ь) для определения ключа шифра ЫЫ

4.5. Расчет трудоемкости метода ЧОМС(Ь).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Аржанцев И. В. Базисы Грёбиера и системы алгебраических уравнений. Москва: МЦНМО, 2003. С. 86.

2. Бабаш А. В., Шанкин Г. П. Криптография, Под ред. В. П. Шерстюка, Э. А. Применко. Москва: СОЛОН-ПРЕСС, 2007. С. 512.

3. Балакин Г. В. Системы случайных уравнений над конечным полем // Труды по дискретной математике. 1998. Т. 2. С. 21-37.

4. Горшков С. П. Применение теории УУР-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикладной и промышленной математики. 1995. Т. 2, № 3. С. 325-398.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982. С. 416.

6. Ильин В. А., Ким Г. Д. Линейная алгебра и аналитическая геометрия. Москва: Проспект, 2007. С. 400.

7. Кобзарь А. И. Прикладная математическая статистика: Справочник для инженеров и научных работников. Москва: Физматлит, 2006. С. 816.

8. Колчин В. Ф. Случайные графы. Москва: Физматлит, 2004. С. 256.

9. Леонтьев В. К., Тоноян Г. П. Приближенные методы решения систембулевых уравнений // Журнал вычислительной математики и математической физики. 1993. Т. 33, № 9. С. 1383-1390.

10. Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006. Т. 18, № 3. С. 152-159.

11. Логачев О. А., Сальников А. А., Ященко В. В. Корреляционная иммунность и реальная секретность // Математика и безопасность информационных технологий. МЦНМО, 2004. С. 176-178.

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

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

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

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

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

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

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

19. Сачков В. Н. Системы случайных уравнений над конечными полями // Труды по дискретной математике. 2004. Т. 8. С. 289-305.

20. Севастьянов Б. А. Курс теории вероятностей и математической статистики. Наука, 1982. С. 256.

21. Смирнов В. Г. Некоторые классы эффективно решаемых систем булевых уравнений // Труды по дискретной математике. 2000. Т. 3. С. 269-282.

22. Фостер К. Ассоциативные параллельные процессоры. Москва: Энергоиз-дат, 1981. С. 240.

23. Abdel А. К., Amr Y. М. Applications of SAT Solvers to AES key Recovery from Decayed Key Schedule Images // Cryptology ePrint Archive. 2010. Vol. 324. http://eprint.iacr.org/.

24. Armknecht F. On the existence of low-degree equations for algebraic attacks // Cryptology ePrint Archive. 2004. Vol. 185. URL: http : //eprint. iacr.org/2004/185 (дата обращения: 01.06.2011).

25. Babbage S. Cryptanalysis of LILI-128 // Proceedings of the 2nd NESSIE Workshop. 2001. P. 6.

26. Bard G. Algebraic Cryptanalysis. New York: Springer Science+Business Media, 2009. P. 356. ISBN: 978-0-387-88756-2.

27. Bardet M. T., Faugere J.-C., Salvy B. Complexity of Groebner bases computation for semi-regular overdetermined sequences over GF{2) // Institute National de Recherche en Informatique et en Automatique, Rapport de recherche. 2003. Vol. 5049.

28. Buchberger B. Grôbner-Bases: An Algorithmic Method in Polynomial Ideal Theory. Reidel Publishing Company, Dodrecht Boston - Lancaster, 1985. Pp. 184-232.

29. Burks A., H.H.Goldstine, J.Neumann. Preliminary Discussion of the Logical Design of an Electronic Computing Instrument // Papers of John von Neumann on Computing and Computer Theory. 1947. Pp. 97-142.

30. Chen J., Courtois N., Yang B. On Asymptotic Security Estimates in XL and Grôbner Bases-Related Algebraic Cryptanalysis // Lecture Notes in Computer Science. 2004. Vol. 3269. P. 401. URL: http ://dx. doi. org/10.1007/ Ы01042.t

31. Cid C., Leurent G. An Analysis of the XSL Algorithm // Advances in Cryp-tology ASIACRYPT 2005 / Ed. by B. Roy. Springer Berlin / Heidelberg, 2005. Vol. 3788 of Lecture Notes in Computer Science. Pp. 333-352. URL: http://dx.doi.org/10.1007/1159344718.

32. Courtois N., Klimov A., Patarin J., Shamir A. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations // Advances in Cryptology, EUROCRYPT 2000 / Ed. by B. Preneel. Vol. 1807. Springer-Verlag, 2000. Pp. 392-407.

33. Courtois N., Meier W. Algebraic attacks on stream ciphers with linear feedback // Eurocrypt. Vol. 2656. Springer, 2003. Pp. 345-359.

34. Courtois N., Pieprzyk J. Cryptanalysis of block chiphers with overdefined systems of equations // Cryptology ePrint Archive. 2002. Vol. 044. URL: http://eprint.iacr.org/2002/044 (дата обращения: 01.06.2011).

35. Courtois N., Pieprzyk J. Cryptanalysis of block chiphers with overdefined systems of equations // Proc. 8th Int. Conf. on the Theory and Application ofCryptology and Information Security / Ed. by Y. Zheng. Vol. 2501. Springer,2002. Pp. 267-287.

36. Faugère J.-C. A new efficient algorithm for computation Groebner bases (F4) // Journal of pure and applied algebra. 1999. Vol. 139(1). Pp. 61-88.

37. Faugère J.-C. A new efficient algorithm for computation Groebner bases without reduction to zero (F5) // Proceedings of the 2002 international symposium on Symbolic and algebraic computation. 2002. Pp. 75-83.

38. Faugère J.-C., Ars G. An Algebraic Cryptanalysis of Nonlinear Filter Generators using Grôbner bases: Rapport de recherche RR-4739: INRIA, 2003. URL: http : //hal. inria. f r/inria-00071848/en/.

39. Fiorini C., Martinelli E., Massacci F. How to fake an RSA signature by encoding modular root finding as a SAT problem // Discrete Applied Mathematics.2003. Vol. 130, no. 2. Pp. 101 127.

40. Giusti M. Some effectivity problems in polynomial ideal theory // EUROSAMi 84 / Ed. by J. Fitch. Springer Berlin / Heidelberg, 1984. Vol. 174 of Lecture Notes in Computer Science. Pp. 159-171. URL: http://dx.doi.org/10. 1007/BFb0032839.3 *

41. Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications, Ed. by A. Biere, A. Biere, M. Heule ét al. Amsterdam, The Netherlands: IOS Press, 2009. P. 966. ISBN: 978-1-58603-929-5.

42. Jonsson F., Johansson T. A fast correlation attack on LILI-128 // Information Processing Letters. 2002. Vol. 81, no. 3. Pp. 127- 132. URL: http://www. sciencedirect.com/science/article/pii/S0020019001002083.

43. Massacci F., Marraro L. Logical Cryptanalysis as a SAT Problem // Journal of Automated Reasoning. 2000. Vol. 24. Pp. 165-203. 10.1023/A:1006326723002. URL: http: //dx.doi. org/10.1023/A: 1006326723002.

44. Meier W., Pasalic E., Carlet C. Algebraic attacks and decompozition of boolean functions // Eurocrypt. Vol. 3027. Springer, 1968. Pp. 474-491.

45. Mironov I., Zhang L. Applications of SAT Solvers to Cryptanalysis of Hash Functions. 2006. http://eprint.iacr.org/.

46. Pagiamtzis K., Sheikholeslami A. Content-addressable memory (CAM) circuits and architectures: A tutorial and survey // IEEE Journal of Solid-State Circuits. 2006.-March. Vol. 41, no. 3. Pp. 712-727.

47. Raddum H., Semaev I. New technique for Solving Sparse Equation Systems // Cryptology ePrint Archive. 2006. Vol. 475. URL: http: //eprint. iacr. org/ 2006/475 (дата обращения: 01.06.2011).

48. Robshaw M. New Stream Cipher Design. The eSTREAM Finalist, LNCS 4986, Ed. by O. Billet. Berlin Heidelberg: Springer-Verlag, 2008. P. 302.

49. Semaev I. On solving sparse algebraic equations over finite fields I // Proceedings of WCC'07. INRIA, 2007. Pp. 361-370.

50. Semaev I. On solving sparse algebraic equations over finite fields II // Cryp-tology ePrint Archive. 2007. Vol.280. URL: http://eprint.iacr.org/ 2007/280 (дата обращения: 01.06.2011).

51. Semaev I. Improved Agreeing-Gluing algorithm // Proceedings of SCC'10. Royal Holloway, University of London, 2010. Pp. 73-88.

52. Semaev I. Sparse Boolean equations and circuit lattices // Designs, Codes and Cryptography. 2011. Vol. 59. Pp. 349-364. 10.1007/sl0623-010-9465-x. URL: http : //dx. doi. org/10.1007/sl0623-010-9465-x.

53. Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. 1969. Vol. 13. Pp. 354-356.