Содержание к диссертации
Введение
ГЛАВА 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
- Задача дискретного логарифмирования
- Сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ».
- Сложение точек эллиптической группы
- Проекция вещественного вектора приближений на пространство булевых переменных
Введение к работе
Актуальность темы. В современной информатике огромную роль играют надежные и гарантированно стойкие алгоритмы шифрования, обеспечивающие безопасность каналов связи в телекоммуникационных, финансовых и многих других информационных системах. Это обуславливает большое практическое значение такой области науки, как криптографический анализ. Прогресс в области криптографического анализа, в свою очередь, сопровождается бурным развитием смежных областей математики: алгебры, теории чисел, дискретной математики.
Одним из основных направлений криптографического анализа является проверка криптографической стойкости алгоритмов асимметричного шифрования, поскольку на базе этих алгоритмов работает подавляющее большинство криптографических протоколов обмена ключами, цифровой подписи и других. В настоящее время для проверки криптографической стойкости асимметричных шифров применяются в основном методы решета в поле чисел общего вида1 и различные модификации р- и Л-методов Полларда, базирующиеся на псевдослучайном блуждании по группе2,3. Последние достижения в этой области свидетельствуют о стойкости известных алгоритмов, поскольку для решения задач «рабочих» размерностей (т.е. регламентированных требованиями безопасности) требуется на несколько месяцев задействовать вычислительные системы, относящиеся к верхним позициям списка «Тор-500». Таким образом, увеличение длины ключа в полтора или два раза принципиально решает вопрос криптографической стойкости шифров.
Однако, относительно недавно возникло и получило развитие совершено новое, альтернативное алгебраическому подходу, направление криптоанализа - логический криптоанализ. Суть подхода заключается в рассмотрении криптографического алгоритма как программы для машины Тьюринга. Подстановка открытого и шифрованного текстов в эту программу естественным образом приводит к задаче «ВЫПОЛНИМОСТЬ» для конъюнктивной нормальной формы, часть выполняющего набора которой является ключом шифра. Идея такого подхода была впервые предложена Куком С. в 1997 году при поиске сложных задач для тестирования решателей КНФ4.
В последующих работах по логическому криптоанализу (Massacci F.,
^enstra А. К., Lenstra Н. W. The development of the number field sieve // Lect. Notes in Math. - 1993. -Vol. 1554.
2Pollard J. M. Monte-carlo method for factorization // BIT. - 1974. - Vol. 15.
3Pollard J. M. Monte carlo methods for index computation (mod p) // Math. Сотр. - 1978. - Vol. 32.
4Cook S. A., Mitchel D. G. Finding hard instances for the satisfiability problem // A survey. DIMACS series in discrete mathematics and theoretical computer science. - 1997. - Vol. 5. - P. 151.
Marraro L.5, Srebrny M.6, Семенова А.А., Беспалова Д.В.7 и др.) основное внимание исследователей было сосредоточено на криптоанализе блочных и потоковых шифров, генераторов двоичных последовательностей, а так же некоторых аспектах криптоанализа RSA (криптостойкость основана на сложности задачи факторизации). При этом за границами исследований остались такие важные задачи как дискретное логарифмирование и логарифмирование в группе точек эллиптической кривой, на основе которых строятся современные системы шифрования, протоколы обмена ключами и цифровой подписи (DSA, ECDSA и другие). В вопросе применения логического криптоанализа для задачи факторизации недостаточно полно освещены такие аспекты, как использование параллельных алгоритмов для поиска выполняющего набора КНФ, кодирующей исходную задачу, и адаптация алгоритмов кодирования под требования современных алгоритмов поиска выполняющего набора КНФ.
Таким образом, актуальность данной диссертационной работы определяется необходимостью разработки подхода для сведения задач дискретного логарифмирования и логарифмирования в группе точек эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ», что предоставит возможность качественного анализа стойкости этих задач против методов логического криптоанализа.
Сведение к задаче «ВЫПОЛНИМОСТЬ» позволяет не только применять для решения изначально алгебраических задач алгоритмы решения задачи «ВЫПОЛНИМОСТЬ», но и получать качественно новые результаты, недоступные для алгебраических методов. Так, например, выделять наиболее вероятные биты ключа, распознавать определенные последовательности бит и полностью восстанавливать ключ по некоторым известным его фрагментам.
Целью работы является построение и исследование свойств алгоритмов консервативного сведения задач факторизации, дискретного логарифмирования и логарифмирования на эллиптических кривых к задаче «ВЫПОЛНИМОСТЬ»; анализ работы современных алгоритмов решения задачи «ВЫПОЛНИМОСТЬ» (SAT-решателей) на полученных КНФ; разработка алгоритма построения КНФ, пригодных для решателей, использующих параллельную модель вычислений; адаптация алгоритмов кодирования в соответствии с требованиями современных алгоритмов поиска выполняющего набора КНФ (построение 3-КНФ, проекции вещественного вектора приближений на пространство булевых переменных, построение КНФ с учетом нало-
5Massacci F., Marraro L. Towards the formal verification of ciphers: Logical cryptanalysis of des // Proc. Third LICS Workshop on Formal Methods and Security Protocols, Federated Logic Conferences. - 1999.
6 Srebrny M. Factorization with sat - classical propositional calculus as a programming environment // Faculty of Mathematics Informatics and Mechanics at the University of Warsaw. 2004. URL: (дата обращения: 06.07.2009).
7Беспалов Д. В., Семенов А. А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. - 2002. - Т.7.
жения дополнительных условий - требований SAT-решателей); исследование стойкости рассматриваемых задач к восстановлению полного ключа по его известным фрагментам.
Научная новизна работы заключается в том, что в ней впервые получены приведенные ниже результаты.
Предложены алгоритмы полиномиального консервативного сведения задач дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».
Предложены алгоритмы полиномиального консервативного сведения задачи факторизации к задаче «3-ВЫПОЛНИМОСТЬ» и к набору различных экземпляров задачи «ВЫПОЛНИМОСТЬ».
Разработана система тестов для выделения наиболее вероятных значений битов сомножителей в задаче факторизации.
С помощью ассоциированных КНФ исследована стойкость рассматриваемых задач к восстановлению полного ключа по его известным фрагментам.
Теоретическая и практическая ценность. Диссертационная работа имеет теоретическую и практическую значимость. В работе построены и обоснованы новые алгоритмы сведения задач асимметричной криптографии к задаче «ВЫПОЛНИМОСТЬ». Практическая значимость работы обусловлена тем, что предложенные в ней алгоритмы могут быть использованы как при решении задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой, так и для построения тестовых примеров задачи «ВЫПОЛНИМОСТЬ».
Апробация результатов работы. Основные результаты диссертационной работы докладывались на международной научной конференции «Параллельные Вычислительные Технологии» (ПаВТ'2007) (Челябинск, 29 января - 2 февраля 2007 г.); 38-ой Региональной молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 29 января - 2 февраля 2007 г.); 13-ой Всероссийской конференции «Математические методы распознавания образов» (Санкт-Петербург, 31 сентября - 4 октября 2007 г.); 39-ой Региональной молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 28 января - 1 февраля 2008 г.); международной научной конференции «Параллельные Вычислительные Технологии» (ПаВТ'2009) (Нижний Новгород, 30 марта - 3 апреля 2009 г.); научном семинаре кафедры математической логики и логического программирования Омского государственного университета им. Ф.М. Достоевского; научном семинаре отдела математического программирования Института математики и механики УрО РАН.
Публикации. Основные результаты диссертации опубликованы в 15 работах (см. список в конце автореферата), из которых 3 работы - в журналах, входящих в перечень ВАК. В совместных работах научному руководителю Р.Т. Файзуллину принадлежат постановка задач и общее руководство исследованиями по теме диссертации, И.Г. Хныкину - разработка и реализация алгоритмов поиска выполняющих наборов КНФ, а диссертанту разработка и реализация алгоритмов представления задач асимметричной криптографии в виде КНФ, а также ряд усовершенствований алгоритмов поиска выполняющих наборов КНФ. В ходе выполнения научного исследования диссертантом была разработана программа для ЭВМ, зарегистрированная в Отраслевом Фонде Алгоритмов и Программ (Per. № 9396, 2007 г.).
Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации составляет 131 страницу. Библиографический список содержит 72 наименования.
Задача дискретного логарифмирования
Дискретное логарифмирование это задача о нахождении в некоторой мультипликативной абе-левой группе G решения уравнения Это решение х называется дискретным логарифмом элемента Ъ по основанию а и обозначается loga b , если основание а фиксировано и если решение существует. На практике наиболее интересными являются случаи, когда G -простое поле или поле Галуа. Рассмотрим уравнение в группе Z\j?Z, где р - простое число. Если порядок a (mod р) равен р — 1, тогда уравнение разрешимо, и решение х является элементом Ъ\(р — 1)Z. Простейший известный метод решения - метод перебора имеет трудоемкость 0(р) арифметических операций. Несколько ниже трудоемкость алгоритма, предложенного в работе [25]. Идея этого алгоритма основана на следующем равенстве: Алгоритм согласования [68], имеет сложность 0(р1/2 log р) арифметических операций. Основная идея - двигаться к решению с двух точек, составляя две таблицы чисел: где Н = \_р1 2\ + 1. Поскольку любое решение (1.3) можно представить в виде х = иН — v , совпадение двух элементов таблиц между собой позволяет найти решение в виде х = щН — VQ (mod р) , где щ и VQ отвечают совпавшим элементам таблиц. В [68] приводится также ряд оптимизаций для этого алгоритма, однако, все они имеют экспоненциальную трудоемкость. Следующий детерминированный алгоритм, разработанный Полигом и Хеллманом [26], основан на знании разложения на простые множители числа р-1: S Сначала составляется таблица чисел вида: полагаем, что: где 0 Хк qi — 1 Тогда по малой теореме Ферма из (1.3) следует, что Далее по таблице rqj находим XQ И, используя малую теорему Ферма, получаем следующее сравнение: Из сравнения (1.5) по таблице rqj вычисляем Xi .
Повторяя данную процедуру, найдем все коэффициенты х разложения (1.4) для всех дг- . После этого дискретный логарифм в виде logab (mod р — 1) находится по китайской теореме об остатках. Сложность данного алгоритма оценивается как Рассмотрение недетерминированных методов начнем с аналога /э-метода Полларда для задачи дискретного логарифмирования в простом поле. Данный метод был предложен в [28]. Рассматриваются 3 числовые последовательности: определенные следующим образом: Если окажется, что (и2г — щ,р — 1) = 1 , то рассмотрим Z, такое что и получим: откуда искомый логарифм равен loga Ъ — l(v{ — V2i) (mod р — 1). Эвристическая оценка сложности данного алгоритма 0(р1 2) . В работе [44] описывается некоторое усовершенствование /э-метода Полларда, с помощью которого удалось вычислить дискретный логарифм по простому модулю, записываемому 22 десятичными цифрами. В настоящее время наиболее эффективным методом решения задачи дискретного логарифмирования является метод решета числового поля. Как и в случае задачи факторизации, этот метод не дает законченного алгоритма, а определяет лишь общий подход к вычислениям, состоящий из определенной последовательности шагов. Для каждого шага существуют несколько реализующих его алгоритмов. Что обусловливает наличие достаточно большого числа реализаций данного метода, отличающихся теоретическими оценками сложности. В 1993 году в работе [13]
Гордон предложил первый алгоритм решения задачи дискретного логарифмирования в простом поле, основанный на идее решета числового поля. Данный алгоритм имеет эвристическую оценку сложности Lp(l/3,32/3) , но оказался непрактичным в реализации (Lp(7 с) = e(c+o(i))(iogiV)7(iogiog./v) т _ стаНдарТНЫИ вид функции сложности субэкспоненциальных алгоритмов, где 0 7 1ис — const). Позднее Широкауе-ром была предложена другая версия алгоритма, имеющая оценку сложности 1/р(1/3, (64/9)1//3) [37]. Этот алгоритм был реализован Вебером и в серии работ [43, 38, 44, 46] было проведено логарифмирование по модулям р 1040,
Сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ».
Ранее были рассмотрены алгоритмы для представления в виде КНФ операции умножения двух чисел, отношения нестрого порядка и устранения тривиальных решений. Все эти алгоритмы - составные части алгоритма сведения задачи факторизации к задаче «ВЫПОЛНИМОСТЬ», который будет описан в данном подпараграфе. Алгоритм 2.1.4. Сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ». Вход: факторизуемое целое число п. Выход: КНФ такая, что задача факторизации числа п консервативно сводится к задаче поиска выполнимого набора этой КНФ. В этой КНФ литералы х\,... ,Xpj отвечают битам искомого делителя п, где - размерность делителя, вычисленная в предположении, что п имеет всего два простых делителя с близкие по порядку величины. Шаг 1. Определить размерность сомножителей: Шаг 2. Генерировать КНФ, эквивалентную операции умножения двух чисел размерности iV, используя алгоритм 2.1.2. Шаг 3. В полученную КНФ подставить значения литералов, отвечающие числу п. Шаг 4. Генерировать КНФ, упорядочивающую сомножители, используя алгоритм 2.1.3. Шаг 5. Соединить конъюнкцией КНФ, построенные на двух предыдущих шагах, и добавить дизъюнкт (2.13) для устранения тривиальных решений. Конец Алгоритма 2.1.4. Теорема 2.1.2. Алгоритм 2.1.4 является консервативным, полиномиальным сведением задачи факторизации числа п к задаче «ВЫПОЛНИМОСТЬ». При этом предполагается, что п содержит в своем разложении на простые числа всего два делителя кратности один. В предположении, что п содержит не более 2N знаков в двоичном представлении, данный алгоритм обладает следующими свойствами: 1. Время работы алгоритма есть О {N2). 2. Количество литералов в КНФ есть О (Л 2). 3. Количество скобок в КНФ есть О (-/V2).
Доказательство. По лемме 2.1.4, в результате шагов 1, 2 и 3 получим КНФ, эквивалентную следующему выражению: Приняв во внимание то, что по построению КНФ хну- неотрицательные, а п по условию леммы содержит в своем разложении всего два простых делителя р и q (р q) единичной кратности, получаем что уравнение (2.14) имеет всего 4 решения: 1. х = 1, г/ = п - противоречит условию добавленному на шаге 5, 2. х = п, у = 1 - противоречит условиям добавленным на шагах 4 и 5, 3. х = q,y = р - противоречит условию добавленному на шаге 4, 4. х = р,у = q - единственное решение, удовлетворяющее всем условиям представленными в виде КНФ. Поскольку все шаги алгоритма 2.1.4 выполняются последовательно и по одному разу, значения рассматриваемых параметров алгоритма будет складываться из суммы значений соответствующих параметров для шагов алгоритма. Отбросив члены низших порядков значимости, получаем, что в данном случае генерация КНФ для операции умножения имеет наибольшие оценки для всех рассматриваемых параметров алгоритма, следовательно, время работы алгоритма, количество литералов и количество скобок в КНФ оценивается величиной О (N2). чисел. Алгоритм 2.1.4 обладает следующим свойством: если на его вход подавать одно и тоже факторизуемое число, на выходе всегда будут получены одинаковые КНФ. Однако, алгоритмы некоторых решателей, особенно применяющих параллельные вычисления, предполагают наличие нескольких КНФ с разной структурой, эквивалентных одной и той же задаче (одному и тому же факторизуемому числу) [70]. Для обеспечения этой возможности предлагается модифицировать алгоритм 2.1.4. Основная идея модификации заключается в замене алгоритма генерации КНФ, эквивалентной операции умножения (алгоритм 2.1.2), на алгоритм, поддерживающий генерацию нескольких КНФ для одной задачи (одного факторизуемого числа). Это достигается за счет введения элемента случайного выбора, который на практике может быть реализован с помощью генератора псевдослучайных чисел.
В работе следующего алгоритма будут применяться шаблоны КНФ, описанные ранее (см. алгоритм 2.1.2), а так же два новых достаточно простых шаблона: 1. sumixi(r: x, у) - шаблон КНФ, эквивалентной равенству г = хфу. Для построения шаблонов используется алгоритм 2.1.1, при этом в выраже нии (2.1) полагаем: 2. sumixixi(r,x,y,z) - шаблон КНФ для г = xy@z. Используется сле дующая подстановка: В алгоритме можно выделить два этапа: 1. Попарное сложение промежуточных векторов, составленных из произ ведений двух литералов. 2. Сложение двух, произвольно выбранных векторов. Алгоритм 2.1.5. Генерация различных КНФ, эквивалентных одной операции умножения. Вход: число N - количество бит в одном сомножителе. Выход: КНФ /(#1,... ,XL)I эквивалентная операции умножения. При этом первые N литералов (х\,Х2, , #JV) будут отвечать битам первого сомножителя, вторые N литералов (x +i, ЛГ+2, , #2лг) - битам второго сомножителя. Предложение 2.3. Данный алгоритм не дает гарантии относительно нумерации бит результата и в общем случае их номера будут распределены в произвольном порядке. Однако, для задачи факторизации это несущественное ограничение.
Сложение точек эллиптической группы
Для того чтобы представить в виде КНФ операцию сложения точек эллиптической группы по модулю р необходимо закодировать в виде КНФ операции (2.30), (2.31) и (2.32). Данные выражения содержат в себе такие операции как сложение и деление в простом поле. Поэтому в начале данного подпараграфа будут рассмотрены алгоритмы генерации эквивалентных КНФ для этих операций. Алгоритм 2.3.1. Генерация КНФ, эквивалентной операции сложения чисел. Вход: вектора литералов и, v, г, отвечающие числам U,V,R соответственно. Размерности первых двух векторов N, третьего - N + 1. Выход: КНФ, эквивалентная выражению: Обозначение: Sum Nn} 1, {щ}?=і, { )wj. Шаг 1. Применить шаблоны: 1. sumixi(ri,tii,vi); 2. and2(ci,ui,vi). Шаг 2. Для і = 2,..., N — 1 применять следующие шаблоны: 1. suml х 1 х 1(гг,Сг-1,щ,У{); 2. carryixixife, и, Сі-і, щ, и{). Шаг 3. Применить следующие шаблоны: 1. suml х 1 х l(rjv, CJV-I, им, VN)\ 2. саггг/іхіхі(глг+і, nv, c v-i, гллг, v ). Конец Алгоритма 2.3.1. Лемма 2.3.1. Ллгормтл 5.3.1 генерирует КНФ, эквивалентную операции сложения двух чисел и обладает следующими свойствами: 1. Время работы алгоритма есть O(N). 2. Количество литералов в КНФ есть O(N). 3. Количество скобок в КНФ есть 0{N). Доказательство. Покажем корректность алгоритма 2.3.1, т.е. докажем что КНФ, которую он строит действительно эквивалентна операции сложения двух чисел. Воспользуемся теоремой 2.1.1 и перейдем от шаблонов КНФ к эквивалентным арифметическим выражениям. При этом шаги алгоритма перепишутся в виде следующей системы равенств (для наглядности сохраним разбиение по шагам исходного алгоритма): Шаг 1. 2ci + г\ = щ + vi Шаг 2. 2с; + ГІ = сг-_1 + щ + v , при і = 2,.... N — 1 Шаг 3. 2rN+i + rN = cjv-i + UN + vN Прибавим к уравнению для первого шага уравнения шага 2, умноженные на 2г_1, и уравнение шага 3, умноженное на 2N 1:
После приведения подобных получаем выражение (2.34), записанное в двоичной системе исчисления. Далее оценим трудоемкость алгоритма и количество дизъюнктов в построенной КНФ. Для этого воспользуемся леммой 2.1.1 и дадим оценку количеству использованных шаблонов КНФ. Поскольку при выполнении любого шага алгоритма применяются два шаблона, следовательно наибольший вклад вносит шаг 2, т.к. этот шаг выполняется N — 2 раза, следовательно трудоемкость алгоритма и количество дизъюнктов в построенной КНФ оцениваются величиной O(N). Количество литералов в построенной КНФ оценивается аналогично. Поскольку шаг 2 выполняется N — 2 раза и каждый раз вводится по одному новому литералу, общее количество литералов оцениваются величиной O(N). Сложение в поле 1\рЪ. На базе рассмотренного выше алгоритма генерации КНФ, эквивалентной операции сложения чисел, строится алгоритм генерации КНФ, эквивалентной операции сложения в простом поле. Идея построения КНФ заимствована из алгоритма 2.2.1 рассматривается следующая система уравнений и неравенства: где X,Y,P- входные параметры, Т - внутренняя неременная в алгоритме в которой хранится сумма X+Y, q — внутренняя переменная алгоритма принимающая значения 0 и 1.
Очевидно, что при таком ограничении на значения q величина Г не может превосходить 2Р. Однако, для операции сложения это вполне достаточно, т.к. X и Y - элементы поля Z\pZ, а значит меньше Р. Кроме того как в случае с умножением в поле, используется нестрогое неравенство Р R, хотя R не может равняться Р. Но применительно к логарифмированию на эллиптической кривой можно считать, что равенство нулю (или равенство Р) промежуточной суммы является частным случаем, который мы не рассматриваем т.к. это может привести к ослаблению криптографических свойств задачи. Алгоритм 2.3.2. Генерация КНФ, эквивалентной операции суммирования в поле 1\рЪ. Вход: векторы литералов размерности N, отвечающие: 1. Результату операции R - вектор г. 2. Слагаемым X, Y - векторы х, у 3. Характеристике поля Р - вектор р.
Проекция вещественного вектора приближений на пространство булевых переменных
Для нахождения решающих наборов полученных КНФ существует множество алгоритмов [35, 48, 34, 32, 36, 33]. Одним из возможных вариантов является применение методов, основанных на минимизации ассоциированного функционала. Эффективность таких методов достаточно детально освещена в работах [70, 74, 60]. Ключевой особенностью методов, основанных на минимизации ассоциированного функционала, является то, что они способны выдавать приближения искомого решающего набора. Т.е. на выходе очередной итерации формируется вещественный вектор, который в результате специальной процедуры -«проектирования» преобразуется в булев вектор (проекцию), соответствую щий найденному решению Простейшим вариантом проекции является следующее преобразование: 1. если Х{ 1/2, то положить у І равным «истина», 2. иначе, положить уі равным «ложь», где ХІ — исходное приближение, у І - проекция. Приведенный вариант проекции способен исправить только локальные неточности приближения, не учитывая связи между переменными. Рассмотрим более сложные варианты проекции применительно к алгоритму 2.1.4, в котором для генерации КНФ, эквивалентной операции умножения, используется алгоритм 2.1.5. Напомним, что в соответствии с теоремой 2.1.3 данный алгоритм осуществляет консервативное сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ». Таким образом предложенные далее варианты построения проекций, есть составляющее звено алгоритма решения задачи факторизации. Обратимся к доказательству леммы 2.1.6 и рассмотрим уравнения, эквивалентные первому шагу алгоритма 2.1.5, при і = 1,..., N/2 получаем: щ j = 0, при j = 1,..., 2г - 2 и j = 2г + N + 1,..., 2iV; Щ2І-1 = Х1У2І-Ї, 2Cji +Ui2i = Х2У2І-1 + ХІУ2Ґ, (2-41) 2ci j+i + щ 2i+j = СІ j + xj+2y2i-i + xj+1y2i, при j = 1,..., N -2; 2Щ 2i+N -+- Щ 2i+N-l = ci N-l + Х-НУ2І Далее просуммируем все уравнения с одинаковыми значениями индекса г: N-1 N N-l N N Щ 2i+N + 2J 2с 3 + zZ Щ 2i+J = z2 Ci 3 + 5J Хі2/2г-1 + 2Z ХзУ2і После приведения подобных получаем следующее выражение: JV-l N N Щ 2i+N + /2 Сі І + zZUi 2І+І = (2/2 —1 + У2і) 2 ХІ 3=1 і=-і 3=1 Предположив, что единичные и нулевые биты входят в оба сомножителя в равных долях, можно считать, что N 3=1 Отсюда получаем следующее правило для проектирования y2i и У2і-і 1. вычисляем значение Si г- для і = 1,..., N/2: где щ j и СІ j компоненты вещественного вектора приближений решающего набора, полученные после итерации алгоритма-решателя задачи «ВЫПОЛНИМОСТЬ». 2. если Si І a\N, то положить г/2і и г/2і-і равным «истина», 3. если Si І PiN, то положить У2І и У2І-І равным «ложь», 4. иначе значение у2і и y2i-i не определено. Параметры с і и / подбираются в зависимости от свойств конкретного алгоритма решения задачи «ВЫПОЛНИМОСТЬ».
Условно для них можно определить следующие допустимые диапазоны: 1/2 аі 1и0 /?і 1/2. Полученное правило позволяет от суммы «по строкам» (по индексу j) переносов Q j и промежуточных сумм щ j строить проекции для битов второго сомножителя. Рассмотрим следующее правило, позволяющее строить проекции для бит первого сомножителя. Просуммируем предпоследнее уравнение системы (2.41) при фиксированном j и і меняющемся от 1 до N/2: Таким образом можно построить процедуру проектирования аналогичную описанной выше: N/2 S2j = Y2 (2 j+1 + Wj 2i+j - Ci j) (2.43) г=1 где Wj j и сі j компоненты вещественного вектора приближений решающего набора, полученные после итерации алгоритма-решателя задачи «ВЫПОЛНИМОСТЬ». 2. если »S2j C12N, то положить Xj+2 и xj+i равным «истина», 3. если . j faN, то положить Xj+2 и Xj+i равным «ложь», 4. иначе значение Xj+2 и Xj+\ не определено. Параметры с 2 и / подбираются в зависимости от свойств конкретного алгоритма решения задачи «ВЫПОЛНИМОСТЬ». Условно для них можно определить следующие допустимые диапазоны: 1/4 «2 1/2 и 0 / 1/4. Ранее были рассмотрены алгоритмы сведения различных задач к задаче «ВЫПОЛНИМОСТЬ», но все построенные алгоритмы в итоговую КНФ добавляли лишь минимально необходимую информацию о задаче. С одной стороны это обеспечивало уменьшение размеров КНФ, но с другой стороны приводило к тому, что частота вхождения литералов, отвечающих искомым битам недостаточно высока. Например для задачи факторизации в алгоритмах 2.1.5 и 2.1.6 литералы, отвечающие искомым битам сомножителей, присутствуют только на первых шагах, когда формируется множество U для алгоритма 2.1.5 и матрица mij для алгоритма 2.1.6. В связи с этим вполне целесообразным выглядит искусственное введение в построенные КНФ избыточных условий, повышающих частоту вхождения в КНФ литералов, отвечающих искомым битам.
Продемонстрируем данный подход на примере задачи факторизации. В подавляющем большинстве случаев сомножители факторизуемого числа должны быть простыми, это обеспечивает наибольшую сложность задачи факторизации и требуется многими руководящими документами по эксплуатации соответствующих криптосистем [31]. Поэтому в качестве дополнительного условия будем использовать утверждение о неделимости искомых сомножителей на малые простые числа. Таким образом, целью данного параграфа является построение алгоритма генерации КНФ, эквивалентной условию «U не делится нацело на \Л , т.е. U (mod V) ф 0. Алгоритм 2.5.1. Генерация КНФ, эквивалентной условию неделимости нацело. Вход: вектор литералов щ і = 1,..., 2N + 1, отвечающих битам числа U. Число V размерности не превышающей N бит. Выход: КНФ, эквивалентная выражению: U (mod V) ф 0. (2.44) Шаг 1. [Г = VQ] Ввести литералы ij г = 1,..., 2iV и qj j = 1,..., N, отвечающие вспомогательным числовым переменным Т и Q соответственно. Шаг 2. Используя алгоритм 2.1.2, построить КНФ, эквивалентную выражению Т = VQ: MtdaT}ZdV}tlt{Q}lx) Шаг 3. [U = Т + R] Ввести литералы гг- г = 1,..., iV, отвечающие вспомогательному числовой переменной R.
Похожие диссертации на КНФ представления для задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой
