Введение
ГЛАВА 1. Обзор 10
1.1 Логический криптоанализ 10
1.2 Методы теории чисел 13
1.2.1 Задача факторизации 13
1.2.2 Задача дискретного логарифмирования 19
1.2.3 Задача логарифмирования на эллиптической кривой 24
ГЛАВА 2. Генерация эквивалентных КНФ . 27
2.1 КНФ представления для задачи факторизации 27
2.1.1 КНФ представление операции умножения двух чисел 32
2.1.2 Обеспечение консервативности преобразований 46
2.1.3 Сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ». 52
2.1.4 Эквивалентные КНФ представления операции умножения двух чисел 54
2.1.5 Сведение задачи факторизации к набору эквивалентных задач «ВЫПОЛНИМОСТЬ» 62
2.1.6 3-КНФ представление операции умножения двух чисел 63
2.2 КНФ представление задачи дискретного логарифмирования 71
2.2.1 Кодирование базовых операций 72
2.2.2 Сведение задачи дискретного логарифмирования к задаче «ВЫПОЛНИМОСТЬ» 77
2.3 КНФ представление задачи логарифмирования на эллиптической кривой 80
2.3.1 Базовые операции 81
2.3.2 Сложение точек эллиптической группы 82
2.3.3 Корректировка результатов суммирования точек кривой с учетом их возможного равенства точке 0 93
2.3.4 Сведение задачи логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ» 97
2.4 Проекция вещественного вектора приближений на пространство булевых переменных 101
2.5 КНФ представления для отношения неделимости на малые простые числа 104
ГЛАВА 3. Вычислительные эксперименты 108
3.1 Генерация КНФ для задач практически значимых размерностей. 109
3.2 Решение полученных экземпляров задачи «ВЫПОЛНИМОСТЬ» 111
3.3 Определение наиболее вероятных значений битов сомножителей для задачи факторизации 114
3.4 Исследование стойкости рассматриваемых задач к восстановлению полного ключа по его известным фрагментам 115
Заключение 118
Список таблиц 119
Литература 120
