КНФ представления для задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Дулькейт Владимир Игоревич

КНФ ПРЕДСТАВЛЕНИЯ ДЛЯ ЗАДАЧ ФАКТОРИЗАЦИИ,

ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ И ЛОГАРИФМИРОВАНИЯ НА ЭЛЛИПТИЧЕСКОЙ КРИВОЙ

01.01.09 Дискретная математика и математическая кибернетика

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

Екатеринбург, 2010

1 ЛПР

004600233

Работа выполнена в Институте математики и информационных технологий Омского государственного университета им. Ф.М. Достоевского

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Файзуллин Рашит Тагирович

доктор физико-математических наук, доцент Хачай Михаил Юрьевич

кандидат физико-математических паук Рыбалов Александр Николаевич

Институт систем обработки изображений (ИСОИ) РАН, г. Самара

Защита состоится 14 апреля 2010 года в 14 часов на заседании диссертационного совета Д 004.006.04 по защите докторских и кандидатских диссертаций при Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан 12 марта 2010 года.

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

В.Д. Скарии

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Однако, относительно недавно возникло и получило развитие совершено повое, альтернативное алгебраическому подходу, направление криптоанализа - логический криптоанализ. Суть подхода заключается в рассмотрении криптографического алгоритма как программы для машины Тыориига. Подстановка открытого и шифрованного текстов в эту программу естественным образом приводит к задаче «ВЫПОЛНИМОСТЬ» для конъюнктивной нормальной формы, часть выполняющего набора которой является ключом шифра. Идея такого подхода была впервые предложена Куком С. в 1997 году при поиске сложных задач для тестирования решателей КНФ4.

В последующих работах по логическому криптоанализу (Massacci F.,

'Lenstra А. К., Lenstra Н. W. The development, of the number field sieve // Lect. Not.es in Math. 1993. -Vol. 1554.

2Pollard .1. M. Monte-carlo method for factorization // BIT. - 1974. - Vol. 15.

:tPollard J. M. Monte carlo methods for index computation (mod p) // Math. Comp. - 1978. -■ Vol. 32.

''Cook 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.

Marrara L.5, Srebrny M.6, Семенова A.A., Беспалова Д.В.7 и др.) основное внимание исследователей было сосредоточено на криптоанализе блочных и потоковых шифров, генераторов двоичных последовательностей, атак же некоторых аспектах криптоанализа RSA (криптостойкость основана на сложности задачи факторизации). При этом за границами исследований остались такие важные задачи как дискретное логарифмирование и логарифмирование в группе точек эллиптической кривой, на основе которых строятся современные системы шифрования, протоколы обмена ключами и цифровой подписи (DSA, ECDSA и другие). В вопросе применения логического криптоанализа для задачи факторизации недостаточно полно освещены такие аспекты, как использование параллельных алгоритмов для поиска выполняющего набора КНФ, кодирующей исходную задачу, и адаптация алгоритмов кодирования иод требования современных алгоритмов поиска выполняющего набора КНФ.

Таким образом, актуальность данной диссертационной работы определяется необходимостью разработки подхода для сведения задач дискретного логарифмирования и логарифмирования в группе точек эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ», что предоставит возможность качественного анализа стойкости этих задач против методов логического криптоанализа.

Сведение к задаче «ВЫПОЛНИМОСТЬ» позволяет не только применять для решения изначально алгебраических задач алгоритмы решения задачи «ВЫПОЛНИМОСТЬ», но и получать качественно новые результаты, недоступные для алгебраических методов. Так, например, выделять наиболее вероятные биты ключа, распознавать определенные последовательности бит и полностью восстанавливать ключ по некоторым известным его фрагментам.

Целью работы является построение и исследование свойств алгоритмов консервативного сведения задач факторизации, дискретного логарифмирования и логарифмирования на эллиптических кривых к задаче «ВЫПОЛНИМОСТЬ»; анализ работы современных алгоритмов решения задачи «ВЫПОЛНИМОСТЬ» (SAT-решателей) на полученных КНФ; разработка алгоритма пост-роения КНФ, пригодных для решателей, использующих параллельную модель вычислений; адаптация алгоритмов кодирования в соответствии с требованиями современных алгоритмов поиска выполняющего набора КНФ (построение 3-КНФ, проекции вещественного вектора приближений па пространство булевых переменных, построение КНФ с учетом пало-

sM;issacci F., Marrara L. Towards the formal verification of ciphers: Logical cryptanalysis of dea // Proc. Third LfCS Workshop ou Formal Methods and Security Protocols, Federated Logic Conferences. 1999.

"Srebrny M. Factorization with sat - classical propositional calculus as a programming environment // Faculty of Mathematics Informatics and Mechanics at the University of Warsaw. 20Ü4, URL: littp://www.mimuw.edu.pl/mati/fsat-20040420.pdf (дата обращения: 06.07.2009).

'Беспалов Д. В., Семенов А. А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. - 2002. - Т.7.

жения дополнительных условий - требований ЭАТ-решателей); исследование стойкости рассматриваемых задач к восстановлению полного ключа по его известным фрагментам.

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

1. Предложены алгоритмы полиномиального консервативного сведения задач дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

2. Предложены алгоритмы полиномиального консервативного сведения задачи факторизации к задаче «3-ВЫПОЛНИМОСТЬ» и к набору различных экземпляров задачи «ВЫПОЛНИМОСТЬ».

3. Разработана система тестов для выделения наиболее вероятных значений битов сомножителей в задаче факторизации.

4. С помощью ассоциированных КНФ исследована стойкость рассматриваемых задач к восстановлению полного клгоча по его известным фрагментам.

Теоретическая и практическая ценность. Диссертационная работа имеет теоретическую и практическую значимость. В работе построены и обоснованы новые алгоритмы сведения задач асимметричной криптографии к задаче «ВЫПОЛНИМОСТЬ». Практическая значимость работы обусловлена тем, что предложенные в ней алгоритмы могут быть использованы как мри решении задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой, так и для построения тестовых примеров задачи «ВЫПОЛНИМОСТЬ».

Апробация результатов работы. Основные результаты диссертационной работы докладывались на международной научной конференции «Параллельные Вычислительные Технологии» (ПаВТ'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 наименования.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

В первой главе диссертации приводятся основные понятия и обзор известных результатов для задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой. Рассматриваются наиболее известные алгоритмы и общие схемы методов решения. Далее в отдельном параграфе рассматривается общий подход к решению некоторых задач дискретной математики, основанный на сведении к задаче «ВЫПОЛНИМОСТЬ» и связанному с ним направлению криптоанализа - «логический криптоанализ». Приводятся основные результаты, известные в рамках данного направления. В заключительной части главы формулируется ключевая идея данной работы о целесообразности применения методов логического криптоанализа для решения рассматриваемых задач.

Во второй главе приводится описание разработанных алгоритмов консервативного сведения рассматриваемых задач к задаче «ВЫПОЛНИМОСТЬ», а так же предлагается ряд улучшений для гибридного метода последовательных приближений с «инерцией» разработанного Р.Т. Файзулли-

ным и И.Г. Хныкииым8.

Перш.1й параграф посвящен вопросам сведения задачи факторизации к задаче «ВЫПОЛНИМОСТЬ». В начале параграфа вводится понятие о примитиве КНФ, с помощью которого формализуется процесс генерации КНФ. Основной операцией для всех построенных в работе алгоритмов генерации КНФ является операция применения примитива, включающая в себя следующую последовательность действий:

1) выбор примитива КНФ для кодирования конкретной вычислительной операции;

2) подстановка в выбранный примитив литералов, отвечающих контексту использования операции;

3) упрощение полученных дизъюнктов и вставка в итоговую КНФ.

Для алгоритмов, использующих примитив КНФ, справедлива следующая лемма:

Лемма 2.1.1. Нижней оценкой для трудоемкости построения КНФ и количества полученных дизъюнктов является количество операций применения примитива КНФ.

Для построения примитивов КНФ используются следующие равенства, полученные из свойств совершенных КНФ:

N / N \

Ф*<= А V*?' •

>=1 МеМм \«=1 /

где в левой части сумма по модулю 2, Мм - множество двоичных векторов длины Ы, содержащих четное число нулей.

А ({/^уетУ (2)

г=1 «=1 {*)е}е2'-/{0,0.....0} \г=1 3=1 )

Для перехода от задачи факторизации к задаче «ВЫПОЛНИМОСТЬ» основной операцией, которую необходимо закодировать в виде КНФ, является операция умножения двух чисел. Для построения соответствующих примитивов КНФ в работе представлен алгоритм перехода от суммы по модулю два к КНФ. Данный алгоритм базируется на равенствах (1) и (2), атак же правиле де Моргана. С помощью этого же алгоритма осуществляется кодирование в виде КНФ операции переноса в старший разряд, которая представляется как сумма по модулю 2 в следующем виде:

с = в(Вх/\уЛг(Вх/\уЛг, (3)

яДулькейт В. И., Файзуллни Р. Т., Хныкин И. Г. Непрерывные аппроксимации решения задачи ВЫПОЛНИМОСТЬ применительно к криптографическому анализу асимметричных шифром // Компьютерная оптика. 2009. Т.ЗЗ. № 1. - С. 86-91.

где а литерал равный сумме х@у®г,&с~ бит переноса от этой суммы.

В работе предложено три различных алгоритма кодирования операции умножения чисел в виде КНФ:

1) алгоритм на основе схемы умножения «столбиком»;

2) алгоритм, использующий датчик псевдослучайных чисел для генерации нескольких КНФ, представляющих одну задачу факторизации;

3) алгоритм генерации 3-КНФ.

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

Второй алгоритм строит несколько КНФ, представляющих одну задачу факторизации, что позволяет использовать параллельные схемы решателей задачи «ВЫПОЛНИМОСТЬ»9. В таких схемах параллельно работает несколько независимых решателей, каждый из которых ищет выполняющий набор своей индивидуальной КНФ. По окончании каждой итерации происходит циклический обмен решениями между решателями и начинается следующая итерация, в которой полученные решения являются начальными приближениями.

Генерация КНФ происходит в два этапа:

1) Попарное сложение промежуточных векторов, составленных из произведений битов сомножителей:

где Xi,yi - биты первого и второго сомножителя соответственно, Щ - вектор, содержащий промежуточную сумму.

2) Сложение двух произвольно выбранных векторов Щ,Щ.

Представление операции умножения в виде 3-КНФ также базируется на алгоритме умножения «столбиком», при этом для кодирования сложения в одном разряде используется следующая система уравнений, каждое уравнение которой представляется в виде фрагмента 3-КНФ:

9Салаен Е. В., Файзуллин Р. Т. Применение метода последовательных приближений с инерцией к решению задачи Выполнимость // Вестник Томского Государственного Университета. - 2006. - Т.17.

5 = «1 ®У, с' = С1 © С2.

= X ф С,

— X А С, С2 = «1 Л У,

Достоинством представленных схем кодирования является отсутствие дополнительных, не имеющих смысла с точки зрения исходной задачи, литералов в построенных КНФ.

Консервативность сведения задачи факторизации к задаче «ВЫПОЛНИМОСТЬ» обеспечивается путем включения в итоговую КНФ фрагментов, фиксирующих порядок сомножителей (условие q > р) и устраняющих тривиальные решения (1 х п).

Все рассмотренные алгоритмы являются консервативным сведением задачи факторизации к задаче «ВЫПОЛНИМОСТЬ» и обладают следующими свойствами (см. ниже теоремы 2.1.2, 2.1.3, 2.1.4):

1) трудоемкость есть 0(N2)\

2) количество литералов в КНФ есть 0{N2)\

3) количество дизъюнктов в КНФ есть 0(N2)\

4) количество различных КНФ представлений одной задачи факторизации, которые могут быть построены алгоритмом генерации нескольких КНФ, представляющих одну задачу факторизации, есть (у) ! (у — 1) !.

Во втором параграфе строится алгоритм консервативного сведения задачи дискретного логарифмирования к задаче «ВЫПОЛНИМОСТЬ». Исходная задача формулируется следующим образом:

АХ = В (mod Р), (5)

где Р - большое простое число; А - такое, что (А, Р) = 1.

Требуется найти число X, удовлетворяющее сравнению (5).

Представим левую часть сравнения (5) в следующем виде:

Л* (mod Р) = ^ • ■ ((А? х А%2) х А?) • • • j xAtf, (6)

где Ai =f A2"' (mod Р), а операция х - умножение в поле GF(P) :

UxVAiuV (mod Р)

При кодировании выражения (6) в виде КНФ определяются численные значения Ai и соответствующие биты подставляются в КНФ. Следовательно, требуется закодировать N — 1 (N - разрядность числа Р) операций умножения в поле GF(P) .

Итак, требуется реализовать кодирование следующих операций:

1) возведения числа в степень, показатель которой может принимать только значения 0 или 1 (возведением в «однобитовую» степень);

2) умножения в поле GF(P) :

UVsR (mod Р). (7)

Для кодирования первой операции предлагается следующий алгоритм, принимающий на вход число А, содержащее N двоичных разрядов, литерал Ь, отвечающий показателю экспоненты, и вектор с* (г = 1,..., JV) литералов, соответствующих битам результата.

1. Если младший бит А равен 0, то добавить в КНФ два дизъюнкта:

(EIVb)A (ClVb),

иначе добавить в КНФ дизъюнкт (cj).

2. Для г = 2,..., N. Если г-ый бит А (биты нумеруются с единицы, начиная с младшего) равен 1, то положить а = Ь, иначе добавить в КНФ дизъюнкт (q).

Умножение в поле GF(P) представляется в виде следующей системы:

'UV-QP + R

Р > R, W

где ¡7 и V сомножители, Р - модуль поля GF(P) , R результат умножения, Q - целая часть от деления UV/P. Без ограничения общности используется нестрогое неравенство, т.к. с одной стороны его проще закодировать в виде КНФ, с другой - в рассматриваемой задаче UV ф 0 (mod Р).

Перепишем систему (8) так, чтобы в каждом уравнении содержалось не более одной бинарной операции:

UV=T, QP = Y, (9)

Т = У + Л, Р > Л,

где Т и Y дополнительные переменные связи между уравнениями.

Кодирование операции умножения в поле GF(P) осуществляется на основе системы (9) с использованием генераторов КНФ для операций умножения, сложения и отношения «больше или равно».

Сведение задачи дискретного логарифмирования к задаче «ВЫПОЛНИМОСТЬ» осуществляется следующим алгоритмом, принимающим па вход 3 числа А, В и Р, имеющих N двоичных разрядов и связанных соотношением (5), и вектор литералов Х{ (г = 1,..., N), отвечающий искомой экспоненте.

1. Вычислить Ai = A2'" (mod Р), при г = 1,..., N.

2. При г = 1,..., N — 1 и 5\ = Ai1 генерировать КНФ представления для выражений вида:

Si+i = SixA? (mod Р).

3. В полученную КНФ подставить биты Р, а также биты В в качестве значений 5дг.

Теорема 2.2.1. Приведенный выше алгоритм является консервативным сведением задачи дискретного логарифмирования в простом ноле по модулю, содержащему N двоичных разрядов, к задаче «ВЫПОЛНИМОСТЬ» и обладает следующими свойствами:

1) время, работы алгоритма есть О (jV3) ;

2) количество литералов в построенной КНФ есть О (Аг3);

3) количество скобок в построенной КНФ есть О (N,i).

В третьем параграфе главы приводится алгоритм сведения задачи логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ». Исходная задача формулируется следующим образом: дано две точки 71, Q некоторой эллиптической кривой Е(А, В,Р). Необходимо найти число К такое, что при умножении на него точки Q получим заданную точку 7Z.

Tl = KQ, Tl,Qe Е{А,В,Р)

В теории эллиптических групп применяются следующие правила вычисления суммы двух точек10:

1. (х,У) + д = (х,У),

2. (X,Y) + (X,-Y) = 0,

3. (X1,Y1) + (X2,Y2) = (X3,YJ), где

X-i = А2 — Х\- Х2 (mod Р), (10)

У3 = A(Xl - Х3) - Y: (mod Р), (11)

f (mod Р), при (XuYi) ф (X-2,Y2),

A s 3*4 А (12)

[ -щ- (mod р)> =

Точка О - нулевой элемент группы точек эллиптической кривой.

Для сведения данной задачи к задаче «ВЫПОЛНИМОСТЬ» воспользуемся следующим разложением:

П = KQ = (• ■ • (hQ + к2 {2 Q}) + ---)+kN {2n-'Q} , (13)

где к{ (i = 1,..., N) - биты искомой экспоненты.

Выражения, заключенные в фигурные скобки, не завися'!' от неизвестных величин, поэтому нет необходимости кодировать алгоритм их вычисления в виде КНФ. Без ограничения общности можно считать, что точки 2'Q отличны от точки О. Если бы это было не так, то, начиная с некоторого номера тп (0 < rn < N), все слагаемые в левой части (13) были бы равны О, что

,0Jurisic A., Menezes A. Elliptic curves and cryptography. // Dr. Dobb's .Journal. April 1997. Vol. 22. no. 4.

существенно упрощало бы решаемую задачу. Однако, в сумме (13) возможно появление О за счет того, что отдельные обращаются в нуль.

Итак, для представления правой части (13) в виде КНФ необходимо закодировать следующие операции:

1) суммирование двух точек эллиптической группы;

2) деление в поле СР(Р) (12);

3) линейная комбинация точек кривой: аЫ + ЬУ = сП, где а, Ь и с переменные, принимающие значения 0 и 1, а ЫЛХ> и 71 - точки эллиптической кривой.

Кодирование первой операции осуществляется на основе следующей системы уравнений, эквивалентных равенствам (10), (11), (12):

YK = M-YU (mod Р),

где Хи, Yu, Xv, Vy, Х%, Y-ц координаты точек, W, Т, L, S, К, D, М вспомогательные числовые переменные.

При этом для кодирования операции деления в поле GF(P) предлагается следующий подход: строится КНФ представление операции умножения в поло GF(P) (7). Далее в построенную КНФ подставляются значения битов U, R и Р. Полученная КНФ, очевидно, является КНФ представлением для операции деления.

Для кодирования в виде КНФ линейной комбинации двух точек используется примитив КНФ, представимый в следующем виде:

Данный примитив обладает следующими свойствами:

1) если литерал с имеет значение «истина», то литерал г принимает зна-

2) если литерал с имеет значение «ложь», то литерал г принимает значение

Далее в работе приводится один из возможных способов представления выражения (14) в виде КНФ, основанный на использовании равенства (2) и правила де Моргана.

Алгоритм сведения задачи логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ» принимает на вход параметры эллиптической кривой: числа А, В и Р, имеющие N двоичных разрядов, точки данной кривой 2 и а также литералы к\,к2,..., км, соответ-

W = XV-XU (mod Р), L = T/W (mod Р), К = L2 (mod Р), DsXu-Xu (mod Р),

T = YV-YU (mod Р), S = Xu + Xv (mod Р), Xn = K-S (mod P), M = DL (mod P),

r = (t Ac) V (/Ac).

(14)

чение t\

стиующие битам искомой экспоненты. Алгоритм состоит из описанных ниже этап о и.

1. Вычислить точки 2'~1<2 при г = 1N.

2. При г = 1, •.., N— 1, = 2 и С'1 = к{ генерировать КНФ представления для выражений вида = сД + ¿¿2,_12.

3. В полученную КНФ подставить биты Р и 2' при г = В качестве значений литералов, отвечающих 5/у, подставить биты 71.

Теорема 2.3.1. Приведенный алгоритм, является консервативным, сведением. задачи логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ», обладающим следующими свойствами:

1) время работы алгоритма есть 0(УУ4), при этом, основной вклад вносит вычисление точек 21-12, сама генерация КНФ за счет эффективного кодирования деления в поле СР(Р) имеет трудоемкость

2) количество литералов в построенной КНФ есть О

3) количество дизъюнктов в построенной КНФ есть О (Л^).

В четвертом параграфе приводится описание разработанной для задачи факторизации системы тестов, позволяющей осуществлять переход от вещественного вектора, полученного на выходе алгоритма минимизации функционала, ассоциированного с задачей «ВЫПОЛНИМОСТЬ», к б.улевому вектору - приближению выполняющего набора КНФ. Данные тесты предполагается использовать как дополнение к простой пороговой схеме по значению вещественных переменных, которая не позволяет учитывать связи между литералами, проистекающие из сути исходной задачи.

В основе теста лежит схема формирования промежуточных сумм и-^, используемая в рамках первого этапа алгоритма генерации нескольких КНФ для задачи факторизации (4). Обратим внимание па тот факт, что если но втором сомножителе (биты у,) встречаются подряд два единичных бита, то большая часчъ битов промежуточной суммы и.^ и переносов с;будут также единичными. Если предположить, что пулевые и единичные биты в сомножителях распределены равномерно, то алгебраическая сумма вещественных приближений для литералон, отвечающих битам переноса и компонентам вектора промежуточной суммы, будет сравнима с размерностью сомножителей N. Аналогично можно выделять два подряд встречающихся пуля но втором сомножителе - соответствующая алгебраическая сумма будет существенно меньше N. Таким образом, получаем тест «по строкам» для выделения двух подряд идущих одинаковых битов второго сомножителя, основанный на выделении максимальных и минимальных значений суммы:

О(^);

N-1

N

где щ и с,: вещественные переменные, отвечающие битам промежуточной суммы и переносам соответственно.

Далее, рассуждая аналогично, можно построить тест «по столбцам» для выделения двух подряд идущих одинаковых битов первого сомножителя:

где щ j и с,: j вещественные переменные, отвечающие битам промежуточной суммы и переносам соответственно.

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

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

1. Генерация КНФ для задач практически значимых размерностей (т.е. используемых в действующих криптосистемах). Полученные результаты представлены в таблице 1. Полученные данные позволили уточнить теоретические оценки параметров построенных алгоритмов (определить коэффициенты при старших степенях) и сравнить алгоритмы сведения задачи факторизации с известным аналогом алгоритмом, предложенным Srebrny11. Было установлено, что алгоритм сведения к задаче «3-ВЫПОЛНИМОСТЬ» дает трехкратный выигрыш по количеству дизъюнктов и литералов относительно алгоритма Srebrny, а алгоритм сведения к набору экземпляров задачи «ВЫПОЛНИМОСТЬ» дает выигрыш в 2 раза по количеству литералов, но уступает в 3 раза по количеству дизъюнктов.

2. Решение полученных экземпляров задачи «ВЫПОЛНИМОСТЬ» небольших размерностей с помощью современных SAT-решателей (победителей конкурса SAT-Competition 200712). Полученные результаты представлены в таблице 2.

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

1'Srebrny М. Factori'/.at.ion wit.li sat. cla.4sir.al prepositional calculus as a programming environment // Faculty of Mathematics Informatics and Mechanics at the University of Warsaw. 2004. URL: http.'//www.j)iiiiiiiw.Hr|]i.|jl/iiMti/fsat.-2()04n42D.prlf (лата обращения: 06.07.2003).

'"Sat. competition |Сайт|. URL: http://www.satcoinpet.ition.org (дата обращения: 10.08.2009)

/V/2

Таблица 1

Результаты генерации КНФ

Размерность задачи Количество литералов Количество дизъюнктов Время генерации (час : мин : сек)

Задача факторизации

2048 6,5Е5 1,6Е7 00:08:05

8192 1,0Е7 2,6Е8 05:59:50

Задача факторизации (3-КНФ)

2048 1,5Е6 6,ЗЕ6 0:01:01

3072 3,5Е6 1,4Е7 0:04:27

Задача дискретного логарифмирования

128 1.0Е7 1,8Е8 02:18:08

152 1,7Е7 3,0Е8 07:12:06

Задача логарифмирования на эллиптической кривой

70 5,ЗЕ6 8,9Е7 03:06:16

100 1.5Е7 2,6Е8 10:24:00

зации числа размером 512 битов с частотой совпадения не ниже 61% удалось определить значения 161 бита сомножителей (31,45%), а биты с номерами 1, 13, 46, 73, 86, 101, 142, 217, 255 были верно определены в более 80% экспериментов.

4. Исследование стойкости рассматриваемых задач к восстановлению полного ключа по его известным фрагментам. Было установлено, что для задачи факторизации сложность решения соответствующей задачи «ВЫПОЛНИМОСТЬ» существенно уменьшается при подстановке фрагментов ключа. Например, факторизация числа размером 512 битов осуществляется за 8 минут после подстановки и ассоциированную КНФ значений 47% случайно выбранных битов сомножителей. Для задач дискретного логарифмирования и логарифмирования па эллиптической кривой такой закономерности обнаружено пе было. Например, для задачи дискретного логарифмирования размерности 24 бита после подстановки 50% случайно выбранных битов ключа не удалось получить решение за отведанные 4 часа. При этом задача размерности 12 битов решается менее, чем за 10 минут (см. таблицу 2).

Таблица 2

Решение полученных экземпляров задачи «ВЫПОЛНИМОСТЬ»

Алгоритм решателя Время решения КНФ (час : мин : сек)

Сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ»

Размерность задачи 80 96 112

march _к.ч 0:01:45 0:03:26 0:36:20

Сведение задачи факторизации к задаче «3-ВЫПОЛНИМОСТЬ»

Pa.3M.epi 1. о с т ь з а да ч и 88 96 104

vallst, 0:57:28 1:51:50 4:26:34

Сведение задачи дискретного логарифмирования

Размерность задачи. 10 12 Ц

Sat,Elite 0:00:14 0:09:00 1:16:46

rsat, 0:00:33 0:07:56 1:23:23

Сведение задачи логарифмирования па эллиптической кривой

Размерн о с т. ь з адачч i <9 10 12

rsat, 0:06:51 0:49:42 >5:00:00

minisat, 0:00:33 0:07:56 >5:00:00

Основные результаты диссертации

1. Разработаны полиномиальные алгоритмы консервативного сведения задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

2. Сформулирован и доказан ряд теорем относительно корректности построенных алгоритмов, оценок их трудоемкости и параметров генерируем ых КНФ.

3. Экспериментально исследована трудоемкость поиска выполняющего набора построенных КНФ с использованием современных алгоритмов решения задачи «ВЫПОЛНИМОСТЬ».

4. Разработан алгоритм сведения одного экземпляра задачи факторизации к набору различных экземпляров задачи «ВЫПОЛНИМОСТЬ», позволяющий распараллеливать процесс решения.

5. Для задачи факторизации разработаны алгоритмы: сведения к задаче «3-ВЫПОЛНИМОСТЬ»; проектирования вещественного вектора при-

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в ведущих рецензируемых научных журналах, определенных ВАК

1. Дулькейт В. И., Файзуллии Р. Т., Хныкин И. Г. Алгоритм минимизации функционала, ассоциированного с задачей З-sat и его практические применения // Компьютерная оптика. - 2008. - Т. 32, № 1. С. G8 73.

2. Дулькейт В. И., Файзуллии Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа // Доклады Томского государственного университета систем управления и радиоэлектроники. - 2008. - № 2(18). - С. 54-56.

3. Дулькейт В. И., Файзуллии Р. Т., Хныкин И. Г. Непрерывные аппроксимации решения задачи «ВЫПОЛНИМОСТЬ» применительно к криптографическому анализу асимметричных шифров // Компьютерная оптика. - 2009. - Т. 33, № 1. - С. 86-91.

Другие публикации

4. Faixullin R.., Khnykin I., Dulkeit V. Polynomial approximation for sat as applied to crypto ciphers // Polynomial Computer Algebra (April 8-12, 2009). St. Petersburg, Russia: 2009. Pp. 100 104.

5. Алгоритм минимизации функционала, ассоциированного с задачей 3-SAT, и его практические применения / В. И. Дулькейт, Р. Т. Файзуллии, И. Г. Хныкин, Е. Салаев // Параллельные вычислительные технологии (ПаВТ'2007): Труды международной научной конференции (Челябинск, 29 января 2 февраля 2007 г.) / Изд. ЮУрГУ. Т. 2. Челябинск: 2007. - С. 156-167.

6. Дулькейт В. Учебно-исследовательская программа Factor-Sat, 1.0 для генерации логических формул эквивалентных задаче факторизации (ОФАП Рег.М 9396, Информационный Фонд РФ Per. № 50200702415) // Компьютерные учебные программы и инновации. 2008. № 3. С. 131.

7. Дулькейт В., Файзуллин Р. Т., Хныкип И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Таврический вестник информатики и математики.

2008. ,№ 1. С. 178 188.

8. Дулькейт В. И. Построение эквивалентных КНФ для задач факторизации и дискретного логарифмирования // Труды VII всероссийской конференции молодых учет,IX но математическому моделированию и информационным технологиям (с участием иностранных ученых). Красноярск: 2006. С. 85.

9. Дулькейт В. И. КНФ представления для задач факторизации и дискретного логарифмирования // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции / УрО РАН. Екатеринбург: 2007. - С. 350-355.

10. Дулькейт В. И. КНФ представления для задачи логарифмирования на эллиптической кривой // ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ: Труды 39-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН: 2008. С. 360- 364.

11. Дулькейт В. И., Файзуллин Р. Т. Алгоритм построения эквивалентных КНФ для задачи факторизации // Труды III всероссийской конференции: Проблемы оптимизации и экономические приложения.-- Омск: 2006. -С. 89.

12. Дулькейт В. И., Файзуллин Р. Т., Хныкип И. Г. Сведение задач криптоанализа асимметричных шифров к решению ассоциированных задач ВЫПОЛНИМОСТЬ, - М.: МАКС Пресс, 2007.- С. 249-251.

13. Дулькейт В. И., Файзуллин Р. Т., Хныкип И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа. ■ Новосибирск: Институт математики СО РАН: 2008,— С. 484-485.

14. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Прикладная дискретная математика,— 2008.— № 2. С. 113 119.

15. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Параллельные алгоритмы минимизации функционалов, ассоциированных с задачами криптографического анализа // Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции (Нижний Новгород, 30 марта 3 апреля 2009 г.) / Изд. ЮУрГУ. Челябинск:

2009. - С. 463-473.

Отпечатано с оригинал-макета, предоставленного автором

Подписано в печать 04.03.2010 г. Формат 60 х 84/16. Бумага офсетная. Усл. печ. л. 1,5. Заказ № 115. Тираж 100.

Отпечатано в типографии ФГУП «ОНИИП г. Омск, ул. Масленников, 231. тел. (3812J-51-49-25

Введение „

ГЛАВА 1. Обзор

1.1 Логический криптоанализ.

1.2 Методы теории чисел.

1.2.1 Задача факторизации.

1.2.2 Задача дискретного логарифмирования.

1.2.3 Задача логарифмирования на эллиптической кривой.

ГЛАВА 2. Генерация эквивалентных КНФ.

2.1 КНФ представления для задачи факторизации.

2.1.1 КНФ представление операции умножения двух чисел.

2.1.2 Обеспечение консервативности преобразований.

2.1.3 Сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ».

2.1.4 Эквивалентные КНФ представления операции умножения двух чисел.

2.1.5 Сведение задачи факторизации к набору эквивалентных задач

ВЫПОЛНИМОСТЬ».

2.1.6 3-КНФ представление операции умножения двух чисел.

2.2 КНФ представление задачи дискретного логарифмирования.

2.2.1 Кодирование базовых операций.

2.2.2 Сведение задачи дискретного логарифмирования к задаче «ВЫПОЛНИМОСТЬ».

2.3 КНФ представление задачи логарифмирования на эллиптической кривой.

2.3.1 Базовые операции.

2.3.2 Сложение точек эллиптической группы.

2.3.3 Корректировка результатов суммирования точек кривой с учетом их возможного равенства точке 0.

2.3.4 Сведение задачи логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

2.4 Проекция вещественного вектора приближений на пространство булевых переменных.

2.5 КНФ представления для отношения неделимости на малые простые числа.

ГЛАВА 3. Вычислительные эксперименты

3.1 Генерация КНФ для задач практически значимых размерностей.

3.2 Решение полученных экземпляров задачи «ВЫПОЛНИМОСТЬ».

3.3 Определение наиболее вероятных значений битов сомножителей для задачи факторизации.

3.4 Исследование стойкости рассматриваемых задач к восстановлению полного ключа по его известным фрагментам.

Задача поиска выполнимого набора логической формулы - одна из наиболее важных задач математической логики и теории вычислений. Она имеет фундаментальное значение для решения прикладных задач в области искусственного интеллекта, проектирования компьютерных систем, роботостроения, криптографии и других. В настоящее время наблюдается бурное развитие в области сведения задач из различных областей прикладной математики к задаче «ВЫПОЛНИМОСТЬ». В России этому посвящены работы Семенова A.A., Буранова Е.В., и др. [51, 67], за рубежом известны работы Kautz Н. Selman В. [19, 41]. Одна из причин этого — возможность решать задачи, возникающие в самых различных областях, единым алгоритмом решения задачи «ВЫПОЛНИМОСТЬ».

Но, несмотря на столь высокое внимание к этой проблеме, имеется еще достаточно большое количество задач, для которых вопрос их сведения к задаче «ВЫПОЛНИМОСТЬ»до сих пор остается открытым. И это при том, что еще в 1971 году Кук С. в своей работе [2] показал принципиальную возможность такого сведения.

Цель работы.

Целью данной диссертационной работы является построение и исследование алгоритмов сведения задач 2-факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

Актуальность работы.

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

Одним из ключевых направлений криптографического анализа является проверка криптографической стойкости алгоритмов асимметричного шифрования, поскольку на базе этих алгоритмов работает подавляющее большинство криптографических протоколов обмена ключами, цифровой подписи и другие. В настоящее время для проверки криптографической стойкости асимметричных шифров применяются в основном методы решета в поле чисел общего вида [21] и различные модификации р- и Л- методов Полларда, базирующиеся на псевдослучайном блуждании по группе [20]. Последние достижения в этой области свидетельствуют о стойкости известных алгоритмов, поскольку для решения задач «рабочих» размерностей (т.е. регламентированных требованиями безопасности) требуется на несколько месяцев задействовать вычислительный кластер категории самых верхних позиций списка «Топ-500». Таким образом, увеличение длины ключа в полтора или два раза принципиально решает вопрос криптографической стойкости шифров.

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

Подстановка открытого pi шифрованного текстов в эту программу естественным образом приводит к задаче «ВЫПОЛНИМОСТЬ» для конъюнктивной нормальной формы, часть выполняющего набора которой является ключом шифра. Идея такого подхода была впервые предложена Куком С. в 1997 году при поиске сложных задач для тестирования решателей КНФ [3].

В последующих работах по логическому криптоанализу (Massacci F., Marraro L., Srebrny M., Семенова A.A., Беспалова Д.В., Ушакова A.A. и др.) основное внимание исследователей было сосредоточено на криптоанализе блочных и потоковых шифров, генераторов двоичных последовательностей, а так же некоторых аспектах криптоанализа RSA (криптостойкость основана на сложности задачи факторизации). При этом за границами исследований остались такие важные задачи как дискретное логарифмирование и логарифмирование в группе точек эллиптической кривой, на основе которых строятся современные системы шифрования, протоколы обмена ключами и цифровой подписи (DSA, ECDSA и другие). В вопросе применения логического криптоанализа для задачи факторизации недостаточно полно освещены такие аспекты, как использование параллельных алгоритмов для поиска выполняющего набора КНФ, кодирующей исходную задачу, и адаптация алгоритмов кодирования под требования современных алгоритмов поиска выполняющего набора КНФ.

Таким образом, актуальность данной диссертационной работы определяется необходимостью построения подхода для сведения задач дискретного логарифмирования и логарифмирования в группе точек эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ», что предоставит возможность качественного анализа стойкости этих задач против методов логического криптоанализа.

Сведение к задаче «ВЫПОЛНИМОСТЬ» позволяет не только применять для решения изначально алгебраических задач алгоритмы решения задачи

ВЫПОЛНИМОСТЬ», но и получать качественно новые результаты, недоступные для алгебраических методов. Так, например, выделять наиболее вероятные биты ключа, распознавать определенные последовательности бит и полностью восстанавливать ключ по некоторым известным его фрагментам.

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

Диссертационная работа состоит из введения, трех глав, заключения и библиографии.

ЗАКЛЮЧЕНИЕ

В работе проводится исследования вопросов сводимости задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ». Среди основных результатов диссертации можно отметить следующие:

1. Разработаны полиномиальные алгоритмы консервативного сведения задач факторизации, дискретного логарифмирования и логарифмирования па эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

2. Для построенных алгоритмов приведены теоретические оценки трудоемкости и параметров полученных КНФ.

3. Проведены экспериментальные исследования практической сложности решения полученных КНФ с использованием современных алгоритмов решения задачи «ВЫПОЛНИМОСТЬ».

4. Разработан алгоритм сведения одного экземпляра задачи факторизации к набору различных экземпляров задачи «ВЫПОЛНИМОСТЬ», позволяющий использовать параллельные алгоритмы решения задачи «ВЫПОЛНИМОСТЬ».

5. Для задачи факторизации разработаны алгоритмы сведения к задаче «3-ВЫПОЛНИМОСТЬ»; проектирования вещественного вектора приближений на пространство булевых переменных; генерации КНФ, кодирующей условие неделимости на малые простые числа, и генерации КНФ, кодирующей упорядочение сомножителей.

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

1. Brillhart J., Morrison M. A. Method of factoring and factorization of F7 // Mathematics of Computation. — 1975. — Vol. 29, no. 129. — Pp. 183-205.

2. Cook S. A. The complexity of theorem proving procedures // Proceedings Third Annual ACM Symposium on Theory of Computing. — 1971.

3. Cook 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.

4. Coppersmith P., Odlyzko A., Schroeppel R. Discrete logarithms in GF(p).

5. Dantzig G. B. On the significance of solving linear programming problems with some integer variables // Econometrica. — no. 28. — Pp. 30-44.

6. Dantzig G. В., Blattner W. P., Rao M. R. All shortest routes from a fixed origin in a graph // Theory of Graphs: International Symposium. — Gordon and Breach, NY, 1967. Pp. 85-90.

7. National Institute of Standards and Technology. — Data encryption standard. FIPS PUB 46 2, 1997.

8. Dixon J. D. Asymptotically fast factorization of integers // Math. Comput. — 1981. Vol. 36. - Pp. 255-260.

9. Edmonds J. Covers and packings in a family of sets // Bull. Amer. Math Soc.- 1962. no. 68. — Pp. 494-499.

10. Faizullin R., Khnykin I., Dulkeit V. Polynomial approximation for sat as applied to crypto ciphers // Polynomial Computer Algebra (April 8-12, 2009). — St. Petersburg, Russia: 2009. — Pp. 100-104.

11. Galbraith S. P., Smart N. P. A cryptographic application of Weil descent // Codes and cryptography. (Lect. Notes in Comput. Sci.). — 1999. — Vol. 1746. Pp. 191-200.

12. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — New York: W. H. Freeman, 1979.

13. Gordon D- Discrete logarithms in GF(p) using the number field sieve // SIAM J. Disc. Math. 1993. - Vol. 6.

14. Joux A., Lercier R. Discrete logarithms in GF(p). ht t p: //list serv. nodak. edu/archives / nmbrthry. html.

15. Joux A., Lercier R. Improvements to the general number field sieve for discrete logarithms in prime fields, http://www.medicis.polytechnique.fr/ lercier.

16. Jovanovic P., Janicic P. Logical analysis of hash functions // FroCoS 2005 -5th International Workshop on Frontiers of Combining Systems. — Vienna: 2005.

17. Jurisic A., Menezes A. Elliptic curves and cryptography. // Dr. Dobb's Journal. — April 1997. — Vol. 22, no. 4.

18. Karp R. Reducibility among combinatorial problems // Complexity of Computer Computations / Ed. by R. Miller, J. Thatcher. — Plenum Press, 1972. Pp. 85-103.

19. Kautz H., Selman B. Pushing the envelope: Planning, propositional logic, and stochastic search // Proc. AAAI-96. — 1996. — Pp. 1194-1201.

20. Koblitz N., Menezes A., Vanstone S. The state of elliptic curve cryptography // Designs Codes and Cryptography. — 2000. — Vol. 19. — Pp. 173-193.

21. Lenstra A. K., Lenstra H. W. The development of the number field sieve // Lect. Notes in Math. — 1993. —Vol. 1554.

22. Lenstra H. W. Factoring integers with elliptic curves // Ann, of Math. — 1987. Vol. 2, no. 126.

23. Massacci 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.

24. The number field sieve / A. K. Lenstra, H. W. Lenstra, M. S. Manasse, J. M. Pollard // Proc. 22nd ACM Symposium on Theory of Computing.— 1990. Pp. 564-572.

25. Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // Advances in Cryptology: Proceedings of EuroCrypt'84. (Lect. Notes in Comput. Sci.). — 1984. — Vol. 209. Pp. 224-316.

26. Pohlig S., Hellman M. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance // IEEE Trans. Inform. Theory. — 1978. Vol. 24. - Pp. 106-110.

27. Pollard J. Monte-carlo method for factorization // BIT. — 1974. — Vol. 15.

28. Pollard J. M. Monte carlo methods for index computation (mod p) // Math. Comp. 1978.-Vol. 32.

29. Pomerance C. The quadratic sieve factoring algorithm // Advances in cryptology-EUROCRIPT'84 (LNCS'209). 1985. - Pp. 169-183.

30. The ^-function and the complexity of Dixon's factoring algorithm (psi.pdf). http://www.math.ku.dk/~kiming/lecturenotes/2002-cryptography/psi.pdf.

31. RSA Security, http://www.rsasecurity.com.

32. Sat competition, http://www.satcompetition.org/.

33. Sat4j. http://www.sat4j.org/.

34. SATLIB Benchmark Problems, www.cs.ubc.ca/ hoos/SATLIB/benchm.html.

35. Satlive. http://www.satlive.org/.

36. Sato, http://www.cs.uiowa.edu/hzhang/sato/.

37. Schirokauer 0. Discrete logarithms and local units. // Phil. Trans. R. Soc. Lond. A. 1993. - Vol. 345. - Pp. 409-423.

38. Schirokauer P., Weber P., Denny T. Discrete logarithms: the effectiveness of the index calculus method // Proceedings of ANTS-II.(Lect. Notes in Comput. Sei.). — 1996. Vol. 1122. - P. 337-362.

39. Semaev I. A. Evaluation of discrete logarithms in a group of p—torsion points of an elliptic curve in a charactristic p // Mathematics of Computation. — 1998. Vol. 67. - Pp. 353-356.

40. Srebrny M. Factorization with sat classical propositional calculus as a programming environment.— 2004. http://www.mimuw.edu.pl/ mati/fsat-20040420.pdf.

41. Stallman R., Sussman G. J. Forward reasoning and dependency directed backtracking // Artificial Intelligence. — 1977. — no. 9(2). — Pp. 135-196.

42. Susem M., Janicic P. Uniform reduction of cryptographic problems to sat.— Faculty of Mathimatics, University of Belgrade, Serbia.— 2009. http://argo.matf.bg.ac.yu/events/2009/slides/.

43. Weber D. An implementation of the general number field sieve to compute discrete logarithms mod p // Advances in Cryptology EuroCrypt'95 (Lecture Notes in Computer Science). — 1995. — Vol. 921. — P. 95—105.

44. Weber D. On the computation of discrete logarithms in finite prime fields: Ph.D. thesis / Univ. des Saarlandes, Saarbrucken. — 1997.

45. Weber D. Computing discrete logarithms with quadratic number rings // Advances in Cryptology EUROCRYPT^S. Springer-Verlag (Lect. Notes in Comput. Sei.). - 1998. - Vol. 1403. - Pp. 171-183.

46. Weber P., Denny T. The solution of mccurley's discrete log challenge // Advances in Cryptology CRYPTO'98. Springer-Verlag (Lect. Notes in Comput. Sei.). — 1998. — Vol. 1462. — P. 458-471.

47. Wegener I. The Complexity of Boolean Functions. — Wiley and Teubner, 1987.

48. Zchaff. http://www.princeton.edu/ chaff/zchaff.html.

49. Беспалов Д. В., Семёнов А. А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. — 2002. — Т. 7.

50. Буранов Е. В. Программная трансляция процедур логического криптоанализа симметричных шифров // Вестник Томского Государственного Университета. — 2004. — № 9(1).

51. ВАСИЛЕНКО О. Н. ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ В КРИПТОГРАФИИ. 2003.

52. Дулькейт В., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Таврический вестник информатики и математики. —2008. — № 1. — С. 178-188.

53. Дулькейт В. И. КНФ представления для задач факторизации и дискретного логарифмирования // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции / УрО РАН. Екатеринбург: 2007, — С. 350-355.

54. Дулькейт В. И. КНФ представления для задачи логарифмирования на эллиптической кривой // ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ: Труды 39-й Всероссийской молодежной конференции. — Екатеринбург: УрО РАН: 2008. — С. 360-364.

55. Дулькейт В. И., Файзуллин Р. Т. Алгоритм построения эквивалентных КНФ для задачи факторизации // Труды III всероссийской конференции: Проблемы оптимизации и экономические приложения. — Омск: 2006.

56. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Сведение задач криптоанализа асимметричных шифров к решению ассоциированных задач ВЫПОЛНИМОСТЬ. М.: МАКС Пресс, 2007.- С. 249-251.

57. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Алгоритм минимизации функционала, ассоциированного с задачей 3-sat и его практические применения // Компьютерная оптика. — 2008. — Т. 32, № 1. — С. 68-73.

58. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа. — Новосибирск: Институт математики СО РАН: 2008.— С. 484-485.

59. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа // Доклады Томского государственного университета систем управления и радиоэлектроники. — 2008. — № 2(18). — С. 54-56.

60. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Прикладная дискретная математика. — 2008. — № 2.- С. 113-119.'г

61. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Непрерывные аппроксимации решения задачи «ВЫПОЛНИМОСТЬ» применительно к криптографическому анализу асимметричных шифров // Компьютерная оптика. 2009. - Т. 33, № 1. - С. 86-91.

62. Ершов Ю. Л., Палютин Е. А. Математическая логика. — М.: Наука, 1987.

63. Нечаев В. И. Элементы криптографии. — М.: Высшая школа, 1999.

64. Прасолов В. В., Соловьев Ю. П. Эллиптические кривые и алгебраические уравнения. — М.: Факториал, 1997.

65. Салаев Е. В., Файзуллин Р. Т. Применение метода последовательных приближений с инерцией к решению задачи Выполнимость // Вестник Томского Государственного Университета. — 2006. — Т. 17.

66. Семенов А. Трансляция алгоритмов вычисления дискретных функций в выражения пропозициональной логики // Дискретный анализ и информатика. — 2008. — № 2. — С. 70-98.

67. Семенов А. Логико-эвристический подход в криптоанализе генераторов двоичных последовательностей // Труды международной научной конференции ПАВТ'07. — Т. 1. — Челябинск: ЮУрГУ, 2007. С. 170-180.

68. Столингс В. Криптография и защита сетей: принципы и практика. — 2-пс! изд. — М.: Вильяме, 2001.

69. Хныкин И. Модификации КНФ, эквивалентным задачам криптоанализа асимметричных шифров методом резолюции // Информационные технологии моделирования и управления. — 2007. — № 2. — С. 328-337.

70. Цейтин Г. О сложности вывода в исчислении высказываний // Зап. научн. семинаров ЛОМИ АН СССР. 1968. - Т. 8. - С. 234-259.

71. Черемушкин А. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002.