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

• Автор: Мелузов, Антон Сергеевич
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 164 с. : ил.

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

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

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

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

1.4. Использование iпателей.

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. Применение алгоритмов решения систем булевых уравнений для анализа потокового шифра ЛТЛ8.
4.1. Потоковый шифр 1ЛЫ8
4.2. Атака па основе открытого и шифрованного текстов
4.3. Существующие методы криптоанализа ЫЫ8
4.4. Метод ЧОМСЬ для определения ключа шифра ЛЛ8 .
4.5. Расчет трудоемкости метода ЧОМСЬ.
Литература


С помощью критерия Кронекера-Капелли. В.Ф. Колчина [8], В. Н. Сачкова [] и Г. В. Валакина [3] утверждений, характеризующих распределение ранга случайной системы линейных булевых уравнений и вероятность совместности случайной системы линейных булевых уравнений, доказана Лемма ЗЛО о характере изменения вероятности совместности случайной системы линейных булевых уравнений, при изменении размеров системы. Данная лемма утверждает, что при увеличении разности между количеством уравнений и количеством переменных в линейной системе булевых уравнений на число г, вероятность совместности линейной системы уменьшается не менее чем в "2 раз. На основании полученных результатов построена формула для определения оптимального числа к опробуемых в алгоритме ЧОМС переменных: к — в - п, где п — наибольшее не превосходящее . I — наибольшая степень полиномов системы. Доказана Теорема 3. ЧОМС составляет 0(2к • га:з). На основании доказанной верхней асимптотической оценки доказана Теорема 3. В главе 4 рассмотрен потоковый шифр ЫЫ - 8, и для него предложен комбинаторный метод определения ключа ЧОМС(Ь), основанный на формировании системы булевых полиномиальных уравнений и применении алгоритма ЧОМС для её решения. ЫЫ - 8 по известным открытому и шифрованному тексту. При длине известной шифрующей последовательности 7,5 бит, трудоемкость в среднем восстановления ключа составляет битовых операций, а необходимый для этого объем памяти составляет 2,6 бит. При этом, наилучший известный на сегодняшний день метод алгебраического анализа требует би товых операций и 0 бит памяти, а количество известной шифрующей последовательности не должно быть меньше, чем 8. В отличие от известных ранее методов криптографического анализа потокового шифра ЫЫ — 8, предложенный в главе 4 метод ЧОМС(Б) может быть применен при меньших объемах известной шифрующей последовательности. Кроме того, при соответствующем изменении подготовительного этапа, на котором формируется система булевых полиномиальных уравнений, метод ЧОМС(Ь) может быть применен для криптографического анализа любого потокового шифра. В приложении А приведен алгоритм АОДР(У8), являющийся модификацией алгоритма АОДР для применения в случаях, когда размеры ячеек ассоциативных вычислителей меньше, чем максимальное количество переменных, задействованных в отдельном уравнении решаемой системы. Также в приложении А приведен алгоритм ЧОМС(А) поиска всех решений систем булевых полиномиальных уравнений. Алгоритм ЧОМС(А) повторяет подход, реализованный в алгоритме ЧОМС, но помимо опробования переменных и использования промежуточных критериев истинности решений, дополнительно использует возможности ассоциативных вычислителей. В приложении Б приведены численные результаты экспериментов по исследованию средней трудоемкости работы алгоритмов АОДР, АОДР (Б) и полного перебора. На защиту выносятся следующие результаты. Алгоритм АОДР поиска всех решений систем булевых уравнений с использованием ассоциативных вычислителей и оценка математического ожидания трудоемкости поиска решений системы булевых уравнений с помощью алгоритма АОДР, а также модифицированный алгоритм АОДР(8) поиска всех решений систем булевых уравнений с использованием ассоциативных вычислителен, размеры ячеек которых меньше числа переменных в системе уравнений. Верхние асимптотические оценки средней трудоемкости поиска всех решений систем булевых уравнений из наборов типов систем булевых уравнений, для которых последовательности {гД, (,. Алгоритм, реализующий метод ЧОМС решения систем булевых полиномиальных уравнений с опробованием переменных и исследованием редуцированных систем на мономиальную совместность и верхняя асимптотическая оценка математического ожидания трудоемкости поиска всех решений систем булевых полиномиальных уравнений, а также верхняя асимптотическая оценка математического ожидания трудоемкости поиска всех решений для квадратичных систем булевых полиномиальных уравнений. Метод ЧОМС(Ь) определения ключа потокового шифра ЫЫ-8 но известным открытому и шифрованному текстам.