Разработка и оценка эффективности алгоритмов просеивания для факторизации натуральных чисел тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Зиятдинов, Дмитрий Булатович
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Казань
МЕСТО ЗАЩИТЫ
|
||||
|
2012
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Зиятдинов Дмитрий Булатович
Разработка и оценка эффективности алгоритмов просеивания для факторизации натуральных чисел
Специальность 01.01.06 — Математическая логика, алгебра и
теория чисел.
Автореферат диссертации на соискание учёной степени кандидата физико-математических наук
1 5 !.!ДР 2012
Казань — 2012
005013891
005013891
Работа выполнена на кафедре системного анализа и информационных технологий государственного автономного образовательного учреждения высшего профессионального образования «Казанский (Приволжский) федеральный университет»
Научный руководитель: доктор физико-математических наук,
профессор ФГАОУВПО «Казанский (Приволжский) федеральный университет» Ишмухаметов Шамиль Талгатович
Официальные оппоненты: доктор технических наук, профессор
КГТУ (КАИ) им. А.Н. Туполева Захаров Вячеслав Михайлович кандидат физико-математических наук, доцент ФГАОУВПО «Казанский (Приволжский) федеральный университет» Фролов Андрей Николаевич
Ведущая организация: Ульяновский государственный
университет
Защита состоится «29» марта 2012 г. в 1630 часов на заседании диссертационного совета Д 212.081.24 при ФГАОУВПО «Казанский (Приволжский) федеральный университет» по адресу: 420008, г. Казань, ул. Кремлевская, д. 35, конференц-зал научной библиотеки им. Н.И. Лобачевского.
С диссертацией можно ознакомиться в научной библиотеке им. Н.И. Лобачевского.
Автореферат разослан февраля 2012 года.
Ученый секретарь диссертационного совета, к. ф.-м.н., доцент
Еникеев А.И.
Общая характеристика работы
Актуальность темы:
Задача целочисленной факторизации состоит в разложении произвольного натурального числа п на простые множители. Она относится к классу трудных задач, но на сегодняшний день теоретически не доказана принадлежность факторизации ни к классу сложности Р, ни NP (см., например, [24], с.336). Напомним, что в недавней работе [6] показано, что задача определения простоты числа лежит в Р, а значит существует детерминированный алгоритм, за полиномиальное время от длины поданного на его вход целого числа определяющий, является ли оно простым или нет. В то же время на практической трудоемкости решения задачи факторизации с помощью современных вычислительных средств в настоящее время основывается чрезвычайно широко распространенный метод шифрования с открытым ключом RSA, а также некоторые алгоритмы цифровой подписи.
Существование классического алгоритма, решающего задачу факторизации за полиномиальное время, заставило бы полностью отказаться от RSA в будущем, и скомпрометировало бы большое количество уже существующих систем. Однако, самый быстрый алгоритм факторизации произвольных натуральных чисел, известный на сегодняшний день, имеет субэкспоненциальную оценку времени работы. Это значит, что он работает медленнее полиномиального, но все-таки значительно быстрее экспоненциального. Благодаря этому приемлемый уровень безопасности в схеме шифрования RSA достигается при использовании ключей достаточно небольшого размера. Но прогресс в области компьютерных технологий и алгоритмов факторизации постоянно увеличивает нижнюю границу размера для ключа, который считался бы на текущий момент безопасным.
Согласно отчету о последнем достигнутом рекорде факторизации (см. [17]), который был установлен 12 декабря 2009 г., с помощью алгоритма решета числового поля на простые множители было разложено 768-битное 232-значное число RSA-768. Общее потраченное на выполнение этой работы время составило два с половиной года. При этом распределенные вычисления на сотнях компьютеров потребовали более Ю20 операций, что эквивалентно 2000 годам вычислений на компьютере класса 2.2GHz AMD Opteron. Однако авторы исследования справедливо оценивают затраченные усилия по факторизации 768-битного модуля как достаточно малые, чтобы рекомендовать больше не использовать модули такого размера даже для кратковременной защиты данных. Кроме того, выдвигается предположение, что факторизация 1024-битного RSA модуля, хоть и будет примерно в тысячу раз более слож-
ной задачей, но ее решение, в рамках схожего академического проекта, может быть получено уже в течение следующего десятилетия.
Можно привести следующие аргументы в пользу дальнейшего использования и изучения алгоритмов RSA, а значит и решения задачи факторизации на классическом компьютере:
1. Высокая эффективность RSA на текущий момент, и низкая эффективность альтернативных алгоритмов. Например, устойчивому к взлому с помощью квантового компьютера алгоритму шифрования с открытым ключом Мак-Элис (см. [7]) требуется размер ключа порядка n2/4 « b2(log2 b)2 бит. Поскольку допускается, что на момент взлома не существует лучшего алгоритма факторизации, чем алгоритм решета числового поля, и реальный уровень безопасности имеет выглядящий разумным на сегодняшний день порядок b = 128, размеры ключей RSA будут исчисляться тысячами бит, в то время как размеры ключей Мак-Элис — миллионами. Также имеет значение скорость работы алгоритма. Алгоритмы цифровой подписи, широко распространенные на текущий момент, допускают подпись и верификацию информации за полиномиальное время. Алгоритмы, устойчивые к возможности взлома на большом квантовом компьютере, работают более медленно. Использование их в настоящее время в сети Интернет повлекло бы за собой существенное снижение производительности сети.
2. Более 20 лет поисков алгоритмов полиномиальной факторизации и безуспешных попыток значительно улучшить асимптотическое время факторизации решета числового поля (см. [16], [14], [12]) позволяют надеяться, что этот алгоритм действительно представляет собой быстрейшую схему факторизации произвольного составного числа на классическом компьютере. Однако, поскольку невыгодно без необходимости увеличивать размер ключа шифрования до бесконечности, а также поскольку алгоритм РЧП обладает сложной структурой, мы полагаем, что все еще возможно локально улучшить его производительность для некоторого класса практически разрешимых задач.
Таким образом, задача исследования классических алгоритмов факторизации является по-прежнему актуальной. Рассматриваемые в диссертации алгоритмы квадратичного решета (КР) и решета числового поля (РЧП) — сложные, состоящие из нескольких этапов, современные алгоритмы, наиболее эффективные для факторизации целых чисел размером от 50 десятичных знаков и более. Одним го важнейших этапов обоих алгоритмов является просеивание — процедура поиска достаточного количества так называемых гладких чисел для получения нетривиальной факторизации на последнем этапе.
Как показано в [12] (стр. 268-277, 294-300) эффективность алгоритма факторизации в целом разумно оценивать исходя из того, насколько эффективно возможно выполнить именно этап просеивания. Однако, особенно для алгоритма РЧП, очень важен еще и этап выбора полинома (см. докторскую диссертацию Б.Мерфи, 1999 г. [20] и статью 2004 г. Т.Кляйнюнга [18]).
Отметим, что на сегодняшний день не существует строгого математического обоснования для оценки эффективности работы КР и РЧП в общем случае, все имеющиеся оценки получены при условии ряда эвристических предпосылок. Тем не менее, алгоритмы КР и РЧП достаточно хорошо исследованы. Уже в публикации [23[ 1984 г. предлагаются ряд значительных модификаций базового алгоритма КР, без которых эффективное его применение на практике становится уже почти невозможным. Прежде всего это так называемое мультиполиномиальное квадратичное решето (МПКР), позволяющее решать задачу факторизации в параллельных процессах. Подробная публикация [8] 1995 г. описывает важную стратегию просеивания, в результате которой для факторизации могут быть использованы не только найденные гладкие числа (которых в результате однократной работы базового алгоритма может быть найдено недостаточное количество), но и так называемые полугладкие. Такая же стратегия применима для алгоритма РЧП. Но еще большее значение имеет сформулированная для РЧП методика решеточного просеивания (см. [16], с.43-49), позволяющая, с помощью особым образом подобранных параметров р, просеивать только выборочные значения полиномов, и при этом получать лишь незначительно меньший выход гладких чисел относительно простого просеивания по всем элементам факторной базы.
В данной работе осуществляется теоретический вывод, обоснование и оценка эффективности одного из возможных алгоритмов просеивания, делающих процедуру факторизации более эффективной — алгоритма просеивания цо подинтервалам для КР, а также исследуется процедура выбора эффективного полинома для алгоритма РЧП, связанного с особой областью просеивания. Кроме того исследуется гибридный алгоритм факторизации, полученный с помощью объединения идей КР и РЧП, обнаруживающий при ближайшем рассмотрении большое сходство с алгоритмом, известным как модификация КР Занга (см. [26]). Подобные теоретические обоснования вместе с некоторыми подтверждающими их экспериментальными оценками позволяют получить лучшее представление о границах эффективности процедуры просеивания в алгоритмах КР и РЧП, а значит, в определенном смысле, и об эффективности процедуры факторизации в целом.
Основной целью работы является исследование алгоритмов просеивания в методе квадратичного решета и решета числового поля и оценка их
5
эффективности, построение оценок для сходимости алгоритма просеивания по подинтервалам.
Для достижения поставленной цели были решены следующие основные задачи:
1. Исследованы современные алгоритмы целочисленной факторизации квадратичного решета и числового поля;
2. Построены оценки для частот появления гладких чисел для алгоритма просеивания по подинтервалам, оценена его эффективность относительно стратегии расширения интервала просеивания;
3. Исследованы процедуры выбора эффективных полиномов просеивания для алгоритма решета числового поля;
Основные положения, выносимые на защиту:
1. Разработка алгоритма просеивания по подинтервалам (АПП);
2. Получение оценки выигрыша для выхода гладких при использовании АПП;
3. Разработка программного комплекса для численной проверки полученных оценок;
4. Исследование метода Занга и оценка его эффективности;
5. Разработка алгоритма выбора эффективного полинома для алгоритма решета числового поля и проверка его эффективности;
Методы исследования. При выполнении работы использовались методы теории чисел, теории алгоритмов и компьютерного моделирования;
Научная новизна состоит в решении следующих задач:
1. Разработка и оценка эффективности алгоритма просеивания по подинтервалам, обеспечивающего более эффективный поиск гладких пар в методах целочисленной факторизации квадратичного решета и решета числового поля;
2. Анализ и развитие специального метода Занга целочисленной факторизации;
3. Разработка алгоритма выбора оптимального полинома просеивания в методе решета числового поля;
Практическая значимость: Разработка и анализ алгоритмов просеивания, которые могут быть использованы для построения более эффективных алгоритмов факторизации.
Достоверность изложенных в работе результатов обеспечивается строгостью постановки задач и математических методов их решения, а также системным подходом к разработке и тестированию программного комплекса, экспериментально подтверждающего теоретические оценки.
Апробация работы. Основные результаты работы докладывались на конференциях:
1. Конференция аспирантов и молодых преподавателей КГУ, 2009, Казань
2. 7-я международная научно-практическая конференция «Инфокоммуни-кационные технологии глобального информационного общества» Казань, 2009;
3. международная школа-конференция молодых ученых - Турку, Финляндия, июнь 2009;
4. научно-практическая конференции и выставка «Инновации РАН - 2010;
5. III Всероссийской научно-практической конференции «Информационные технологии в системе экономической безопасности России и ее регионов», Казань, 2010.
Личный вклад. Автор принимал активное участие в теоретических разработках и анализе предложенных методик, а также разработал и реализовал программные средства, необходимые для получения статистически достоверных численных оценок рассматриваемых в работе алгоритмов.
Публикации. Основные результаты по теме диссертации изложены в 5 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 2 — в тезисах докладов.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложения. Основной текст диссертации изложен на 86 страницах с 12 рисунками и 10 таблицами. Список литературы содержит 74 наименования.
Содержание работы
Во введении обосновывается актуальность исследований, проводимых в рамках данной диссертационной работы, приводится обзор научной литературы по изучаемой проблеме, формулируется цель, ставятся задачи
7
работы, сформулированы научная новизна и практическая значимость представляемой работы.
Первая глава посвящена описанию наиболее быстрых из существующих в настоящее время алгоритмов факторизации произвольных больших натуральных чисел — алгоритмов квадратичного решета и решета числового поля. Вводится понятие гладких чисел и другие основные понятия, общие для всех методов факторизации, использующих процедуру просеивания. Обсуждается возможности улучшения оценки времени факторизации в целом и оптимизации отдельных этапов в известных алгоритмах для получения более оптимальных методов. Также вводится стандартная субэкспоненциальная функция сложности Ln\a, с] = exp((c + o(l))(lnn)a(lnlnn)1-™), и обсуждаются результаты численных экспериментов, отражающих степень ее адекватности для оценки эффективности факторизации с помощью алгоритмов КР и РЧП на практике.
Класс алгоритмов факторизации, в котором удалось разработать наиболее быстрые на сегодняшний день алгоритмы, в своей основе содержит прием, который был известен еще в 17 в. Пьеру Ферма.
Так, пусть для произвольного нечетного натурального п нам известна такая пара чисел {А, В), что выполняется
А2 — В2 =п (1)
тогда задача факторизации п решается элементарно: п = {А — В)(А + В).
Все алгоритмы факторизации, построенные на этой идее, используют некоторые полиномы, которые в дальнейшем будут называться порождающие полиномы или полиномы просеивания, среди значений которых происходит поиск чисел, которые могут быть использованы для построения выражения вида (I)1.
Алгоритм факторизации квадратичного решета использует порождающий полином Q(x) = х2 — п, обладающий свойством Q(x) = х2 mod п. Это значит, что все значения Q(x) уже являются квадратами по модулю п, и для успешной факторизации достаточно найти некоторое а:, для которого Q(x) являлось бы полным квадратом. Однако есть и более эффективный способ: найти среди всех аргументов Q(x) некоторое подмножество S, такое что JJO(x) являлось бы квадратом в Z. Эффективность такого приема свя-16 s
зана с открытой в конце 70-х, начале 80-х годов процедурой просеивания, позволяющей быстро найти такое подмножество S.
'На самом деле используется немного более общее выражение А2 — В2 ~0 mod (п), тогда, при известных А и В, факторы п находятся как (А - В,п) и (Л + В,п)
Определение 1. Число называется В-гладким, если среди его делителей нет чисел, превосходящих некоторой границы В.
Определение 2. Просеиванием полинома по некоторому радиусу Ь называется процедура, аналогичная процедуре Эратосфенова решета, определяющая какие из значений <2(а;), где х е [-£,; Ь], являются В-гладкими.
Определение 3. Полином, чьи значения исследуются на гладкость в алгоритме факторизации называется порождающим полиномом или полиномом просеивания.
Имея в своем распоряжении В + 1 гладкое число, всегда возможно найти такое подмножество этих чисел, произведение элементов которого было бы полным квадратом. Таким образом, при заданном В, основная цель алгоритма факторизации сводится к поиску достаточного количества гладких значений порождающего полинома.
Суть процедуры просеивания заключается в следующем. Если для некоторого простого р верно, что р\Я(хр) = х\ - п, то также будет верно, что р\С^{хр + кр) для любого целого к. Такое свойство порождающего полинома фактически позволяет определить В-гладкость каждого отдельного числа из области значений <2(х) за О(ЫпВ) шагов (подробнее об этом см. [12], стр.121-131). Просеивание происходит в три этапа: сначала генерируется массив значений х) на некотором интервале [|_\/ч) ~ + Ь], затем для каждого простого р из факторной базы происходит просеивание, то есть элемент массива делится нар, и на последнем этапе происходит поиск элементов массива, обратившихся после процедуры просеивания в единицу; значения <5(ж), соответствующие этим элементам и будут искомыми гладкими2.
Определение 4. Факторной базой в алгоритме квадратичного решета называется набор простых чисел, ограниченных сверху некоторой константой В и при этом являющихся квадратичными вычетами по модулю п. Последнее условие необходимо для того, чтобы для любого р из факторной базы сравнение (¿(х) = х2 - п = 0 (тос! р) имело решение, а значит просеивать по р имело смысл.
23десь описана самая простая техника просеивания. На практике, для ускорения алгоритма, процедура выглядит несколько иначе: во-первых, переходя х логарифмам значений <3(х), деление можно заменить на вычитание, во-вторых просеивание можно производить «в обратную сторону», то есть инициализировать массив нулями, затем прибавлять 1:1 р л те места, которые делимы на р для каждого простого р из факторной базы, и на последнем этане — сравнивать значения элементов массива со средним приближенным значением \aQix). Подробнее об этом см. [12], стр. 123
Задача выбора оптимальных параметров для алгоритмов факторизации (в частности, параметра В) является нетривиальной. Благодаря удачному подбору параметров удается найти достаточное количество гладких чисел за относительно небольшое время от 1пп.
Сложность факторизации с помощью алгоритма квадратичного решета при оптимально выбранных параметрах основывается на важной теореме, сформулированной Карлом Померанцем в 1996 г.
Теорема, (см. [12], стр. 286 и [22], стр. 703-711) Пусть т\,т2,... — последовательность целых, равномерно распределенных независимых случайных величин на отрезке [1..-Х], N — наименьшее целое, такое что в тп1,т2,...тх существует подпоследовательность, произведение элементов которой является квадратом. Тогда ожидаемое значение N выражается формулой: где Ь(Х) = ехр(у/1п Х1п1пХ). Кроме того, ожидаемое значение N не изменится, если потребовать, чтобы каждое из чисел т] в произведении обладало В-гладкостъю, где В = Ь(Х)1^.
Поэтому сложность алгоритма факторизации КР оценивается выражением Ь„( 1/2,1) = ехр((1 + о(1))\/1пп1п1птг) и такая оценка является лучшей для входных чисел, примерно, от 50 до 100 десятичных знаков3 (см. [23] для подробного вывода). Из теоремы хорошо видно, почему такая оценка не является абсолютно строгой — предполагается, что числа порождаемые полиномом просеивания в алгоритме будут обладать требуемой степенью гладкости с той же вероятностью, что и независимые равномерно распределенны случайные величины.
Алгоритм решета числового поля, имеет таким же образом полученную теоретическую оценку сложности
¿,„(1/3,с) = ехр((с + о(1))(1пп)1/3(1п1пп)2/3 (2)
где с ~ 1,92, которая, конечно же, асимптотически значительно лучше, чем оценка полученная для алгоритма квадратичного решета. Однако в остальном алгоритм РЧП лишь развивает описанные выше идеи, используя более общее понятие гладкости и позволяя, кроме того, более гибко выбирать параметры, но не вносит существенных изменений в основные этапы процедуры факторизации.
Далее, с помощью описанного в тексте диссертации численного эксперимента показано, что асимптотическая оценка времени работы алгоритма решета числового поля действительно отражает фактическую сложность факторизации даже для небольших п, однако при этом значительную роль
З0бщий вид функции ¿»[а, с] =ехр ((с + о(1))(1пп)"(1п1пп)1_0), причем о(1) -+ 0, только если п -+ 00.
10
Рис. 1: Сравнение оценок сложности алгоритмов КР и РЧП для небольших чисел 35000 ---
-Т(п) -S(n) ~S*(n) -S"(n)
n 29737 44431 57949 70349 82Б61 94097
играет оптимальный выбор всех параметров. Более того, на практике уменьшение или увеличение значения константы с и даже слагаемого о(1) в выражении (2) также будет вносить существенный вклад в сложность алгоритма.
Пусть Ln(rj) = ехр ^(1 + 77)л/1пп1п1пп^ — оценка сложности факторизации методом КР с учетом константы г]. На рис. 1 отображены S(ri) = Ln{0), S"(n) = Lra(0,55) и S*(n) = ¿„(0,94). Видно, что, хоть S(n) в этом случае выглядит значительно предпочтительнее всех прочих оценок, уже S**(n) = Ln(0,55) сравнима по величине с асимптотически оптимальной функцией сложности РЧП — Г*(га) = ехр (1,92 • (lnn)1/3(lnlnn)2/3), а S*(n) = Ln(0,94) практически совпадает с эмпирически выведенной функцией сложности РЧП для малых п и оптимальных начальных параметрах — Пп).
Во второй главе теоретически выводится, анализируется, получает теоретическую и экспериментальную оценки методика просеивания по подин-тервалам.
Рассмотрим ситуацию, когда процедура просеивания завершила свою работу. Результат ее работы — множество пар
5 = {(А, В) : A = x + m, B = q(x)}, (3)
удовлетворяющих условию А2 = В mod п, где В обладает свойством гладко-
сти. Далее это множество должно быть отфильтровано так, чтобы остались
лишь пары [А, В), для которых НОД(А, В) = 1.
Часто бывает, что размер множества S после фильтрации становится значительно меньше размера факторной базы. Итак, нужно совершить допол-
нительную работу для поиска новых гладких чисел. Это тем более вероятно,
11
что потенциально отфильтровано может быть также большое количество пар, для которых В хоть и является гладким, но не может быть использовано для получения искомого соотношения конгруэнтности двух квадратов по модулю п (это такие В, которые содержат в качестве произведения простое число р, не содержащееся ни в одном другом В из S).
Предлагается теперь вместо увеличения радиуса просеивания L или изменения границы В наибольшего простого в FB произвести дополнительный поиск гладких среди значений полиномов qv{k) = q(x + рк)/р, где q(x) = 0 (mod р).
Определение 5. 1-гладтм называют число z, если оно является произведением гладкого числа г и простого р, меньшего чем В\ = В2.
После завершения первого этапа просеивания находится также большое количество 1-гладких чисел. Если для некоторого х значение q{х) будет 1-гладким, то есть q{x) = г • р, где В < р < Ви то каждое последующее значение q{x +р • к) также делимо на р для всех к € Z. Запишем многочлен q(x + р- к) в виде:
q{x + р ■ к) = (х + р ■ kf + 2т(х + р-к)-а = q(x) + р2к2 + 2рк(х + т). Обозначим через qp(k) последнее выражение, поделенное на р:
qp{k) — q{x + р • к)/р = pfc2 + 2к(х + т) + г, (4)
так как q(x) =р-г.
Несложно показать, что скорости роста функций q(x) и qp(k) приблизительно совпадают, если р невелико. Таким образом, мы получаем новый объект для просеивания. Так как просеивание полинома (4) эквивалентно просеиванию исходного полинома q(x) по аргументам Хк = х+р • к, методика получила название просеиванием по подинтервалам.
Заметим, что на возможность такого просеивания указывается в одной из ранних статей Померанца о методе квадратичного решета ([23], с.6-7), однако без детального анализа алгоритма, его ограничений и приемуществ. Просеивание по подинтервалам перекликается также со стратегией решеточного просеивания в методе решета числового поля, которая была предложена Дж.Поллардом в [16], с.43-49, и, частично, с идеей поиска полугладких чисел (Боендер, [8]), однако полностью не повторяет ни одну из них. В работе осуществляется вывод теоретических оценок, подтверждающих эффективность методики просеивания по подинтервалам, а также приводятся результаты численного эксперимента на большом объеме данных.
Сформулирована и доказана следующая теорема.
12
Теорема 1. Если на некотором интервале Ь, полином просеивания д(х) ограничен сверху некоторой константой М, то эффективность просеивания по одному дополнительному подинтервалу для р ~ В относительно просеивания по двукратному расширению исходного интервала можно оценить формулой:
где р(и) - функция Дикмана де-Брюина. Причем наибольший выигрыш в выходе гладких на подынтервале будет достигаться при условии 2В — Ь.
Следствие. Для того, чтобы просеивание по подинтервалам было эффективно, достаточно чтобы выполнялось условие 1? 4-16Ь2 < 2М.
Вследствие проведенного численного эксперимента удалось показать, что выигрыш в среднем от использования методики просеивания по подинтервалам в алгоритме КР, при условии достаточно хорошо подобранных исходных параметров4 достигает от 20% до 50%. Следующие графики отражают этот выигрыш как относительный прирост в выходе гладких при использовании гладких найденных на исходном интервале и подинтервалах, относительно прироста гладких, получаемого вследствие увеличения исходного интервала просеивания в два, три и четыре раза.
Также в работе рассматривается применение методики просеивания по подинтервалам к специальному виду алгоритма КР, который называется вариацией Занга ([26], стр. 3-4). Анализ показывает низкую эффективность методики для полиномов просеивания, степень которых г > 2.
Итак, методика просеивания по подинтервалам может очень эффективно использоваться как в алгоритме квадратичного решета, так и в его модификациях, для получения выигрыша при поиске гладких чисел, причем численный эксперимент показывает стабильность этого выигрыша при росте п. Однако эффективность методики быстро падает с ростом степени полинома просеивания. В методе решета числового поля похожий подход носит название решеточного просеивания, однако они не идентичны. Приведенные теоретические и экспериментальные оценки уточняют на какой именно выигрыш можно рассчитывать, применяя данную методику и очерчивают границы ее эффективного применения в том или ином алгоритме факторизации.
'Параметрами в данном случае была полином 13(1) = (т+х)2-п, граница поиска гладких В и радиус просеивания
180.00« 190.00% 140,00% 120,00% 100,00* 80.00% 60,00% 40,00% "20,00% 0,00%
-nnxi -XTSX2
200,00% 160,00% 100,00% 50,00% 0,00%
-ге-іхз
-ХПхЗ
200
-хп*«
Рис. 2: Относительный выигрыш от методики просеивания по подинтервалам в алгоритме квадратичного решета для равномощных классов "хороших"исходных полиномов (ХП) и "плохих"исходных полиномов (ПП) для чисел длины от 60 до 150 бит.
В третьей главе рассматривается общая методика, позволяющая сделать алгоритмы факторизации более эффективными за счет просеивания значений порождающего полинома по области особого вида. Сначала строится и анализируется гибридный метод факторизации, совмещающий в себе идеи алгоритмов KP и РЧП, доказывается утверждение об эффективности просеивания в таком алгоритме вдоль оптимальной прямой. Затем осуществляются теоретические построения, связывающие методику просеивания по особой области с процедурой выбора оптимального полинома для алгоритма решета числового поля. В конце приводятся результаты численного эксперимента, эмпирически доказывающего эффективность описываемой методики для кубических полиномов просеивания в РЧП и чисел п длины порядка 120-бит.
В гибридном методе факторизации предлагается сначала, так же как и в методе РЧП сначала выбирать неприводимый в поле рациональных чисел Q многочлен Р(х) степени г > 2 с целыми коэффициентами. На следующем этапе РЧП предполагает просеивание многочленов вида о + Ьх по алгебраической факторной базе, состоящей из простых идеалов вида а + Ьв в кольце Х[в], где 9 — комплексный корень многочлена Р(х) с одновременным просеиванием чисел а + Ьт по рациональной базе.
В гибридном методе предлагается отказаться от просеивания по алгебраической факторной базе,' рассматривая в качестве множества для просеивания по рациональной базе числа специального вида а + Ьт, где о и & подобраны так, что многочлен а + Ьх является квадратичным вычетом по модулю многочлена Р(х).
При таком подходе алгебраическая факторная база не нужна вообще, и двучлены а + Ьх, рассматриваемые здесь, автоматически будут полными квадратами по модулю Р(х) в силу выбора (а,Ь). Просеивание будет проводиться только по рациональной базе, которая выбирается обычным образом.
Пусть Р(х) = х2 + сх + d — квадратичный полином5, а + Ьх = Q2(x) mod Р{х), тогда Qa,b(x) = (а + bx)2 mod р(х) = (°2 ~ + (2ab ~ b2c)x = ai+bix. Теперь обозначим F(a,b) = Qa,b{m) mod Р{т), тогда F(a, b) всегда будет квадратом в Z/NZ.
F(a,b) = Qa,b{m) = aj +hm mod N. (6)
SB случае кубического полинома P(x) данный метод преобразуется в не очень эффективный метод квадратичного решета в вариации Занга [26]. Кале показано в [19] эффективно использовать подобную же методику для степеней Р(х) г > 3 скорее всего невозможно. Опять же, литература по данным методикам крайне малодоступна н не отражает весь спектр их возможных применений
100 90 80 70 60 b 50 40 30 20 10
О
О 500 1000 1500 2000 2500 3000 3500 4000 4500 а
Рис. 3: Распределение гладких пар вдоль оптимальной прямой
Для оценки роста значений функционала F(a, b, то) заметим, что наименьшее значение он достигает в начале координат а = 0, Ь = 0 и на прямых
а = ib
где t — корень многочлена W{t) —t2 + 2mt — cm — d.
Поскольку, коэффициенты a ab принимают только целые значения, а значения корня t иррациональны (иначе, мы бы имели нетривиальное разложение числа N), то точного значения достичь невозможно. Пусть і — один из корней полинома W{t). Будем называть прямую а = tb оптимальной.
Утверждение 1. Значение функционала F(a,b) в точках (ао>&о)> примыкающих к оптимальной прямой a = tb прямо пропорционально аргументу Ьо с коэффициентом пропорциональности, равным примерно 1,2т.
Другими словами, функционал F(a, b) изменяется линейно вдоль линии а = tb.
Рис.1 демонстрирует распределение гладких значений F(a, b, т) = b2W(t) на примере N = 1439 • 1747 = 2513933,т = 1531, Р{х) = х1 + lllx + 3, W(t) = t2 + 30621 - 169972, i0 » 54,54. Размер факторной базы - 30 элементов. Кружочками обведены пары, найденные в результате просеивания по области (а, 6) Є [(54Ь - 10...54Ы-10) х (1...100)].
Этот метод очень близко смыкается с методом квадратичного решета. Действительно, просеивание в методе квадратичного решета выполняется по последовательности Q(a) = ([v^J + й)2 — N яа а2 + 2a\/N для а Є {±1, ±2, ±3, ...}. Поскольку, параметр то при г — 2 равен примерно
[л/Л/], то можно считать просеивание по методу квадратичного решета частным случаем формул (6) при 01 = а2, 61 = 2а.
Отличие заключается в том, что теперь мы можем просеивать по области особого вида, минимизирующей рост полинома <2(а). Это позволяет, просеивая равное количество элементов, найти до 6 раз большее количество гладких пар по сравнению с обычным КР.
Ту же идею можно применить для алгоритма решета числового поля.
В статье Кляйгаонга [18] предложен метод построения пары полиномов с целыми коэффициентами ^(х) = р^аах1* + а^-гх^1 + ... + а\х + ао) и 1*2 =рх — т, имеющих общий корень тп/р по модулю п, где п — это число, которое требуется факторизовать, р — целое число. То есть выполняется:
(7)
Яф-О.
Р
В указанной статье на выбор числа р не накладывается никаких условий, кроме:
1. р < т;
2. р представляет собой произведение нескольких небольших простых чисел.
Выбор пары полиномов в методе Кляйюонга выполняется неоднозначно, а критерием оценки качества полинома является некоторая мера, представляющую собой функционал, значение которого определяется коэффициентами полинома и действительным числом к, называемым вкевдгекз. В результате выбор полиноминальной пары сводится к перебору всевозможных полиномов ^(х), удовлетворяющих условию (7), и выбору среди них полинома с наименьшей мерой. Второй полином определяется однозначно параметрами р и т. Такой подход не оптимален и обладает тем недостатком, что время его работы для больших п слишком велико (полгода для подбора подходящего полинома в рекордном разложении 768-битового числа га, см [17]).
В диссертации предлагается другой подход к выбору полинома ¿^(х). Наша идея заключается в том, чтобы выбирать полином Fl(x) так, чтобы его производная Р[{х) имела два действительных корня о^ и 02, расположенных недалеко друг от друга, причем полином ^(х) в точках ах и аг имел противоположные значения, тогда ^(х) имеет действительный корень между а! и
Рис. 4: График полинома Fi(x) с корнями производной ai и аг
Пусть М — max(|Fi(ai)|, |Fi(q2)|)- Рассмотрим наибольший непрерывный интервал [с, е], содержащий точки ai и ai на котором выполнено неравенство |Fi(x)| < М (см. рис. 4). Обозначим через х0 корень Fi(x), находящийся между точками ai и а?. По теореме Лагранжа для некоторого в окрестности точки хо выполняется Fi(x) < F(((i) • (х - Хо) < L-ii(fi), где L — длина интервала [с, е]. Поскольку точка также находится в окрестности нулей производной F[(ж), то опять, по теореме Лагранжа, Fi(£i) < F"(£2) ■ L, и следовательно Fi(x) < Ff(&) • Ьг.
Предположим теперь, что полиномиальная пара F\(x), ^г(х) выбрана. Для эффективности работы метода РЧП необходимо обеспечить сравнительно небольшие значения нормы линейных полиномов а — Ьв в числовом поле ЪЩ 6 при изменении параметров а и b в некоторой области SR (от англ. sieve region). Норма полинома Nr(a — Ьв) может быть вычислена по формуле Nr(a-be)=l^F1(f).
Предположим теперь, что полином Fi(x) имеет свойства, сформулированные выше, и оценим значения нормы Nr(a — b9) в специальной области SR, описываемой неравенствами:
1 <b<Q, с<%<е, о
в0 здесь — комплексный корень Fl(x)
где <Э — некоторое целое число, а интервал [с, е] выбран как на рис. 4. Эта область представляет собой некоторый сектор ширины Ь и высоты
Ыг{а - Ьв) < Ь^ф <Я*-Ь- <0?-Ь-Ми (8)
где М1 обозначает максимум второй производной на интервале [с, е], Ь - длина интервала [с, е]. Подсчитаем размер XV области 5Я (количество пар (а, Ъ) € <57?):
V/ = Ь + 2Ь +... + <Э • Ь ~ | • Ь • <52. Найдем из последнего равенства (5 и подставим в (8):
д = \ мг{а= (9)
Оценка (9) показывает, что при увеличении площади 1У сектора 5Я рост нормы происходит пропорционально 2. При изменении ширины Ь сектора БП без изменения И7 рост нормы Л^г(а — ¿5) будет пропорционален росту полинома ■РЦЬ), т.е. пропорционален Ьл.
Значит, в первичном приближении рост нормы будем наименьшим в направлении увеличения высоты <5 сектора в Я, а не его ширины Ь. Значит просеивание по сектору с основанием у корней кубического полинома, подобранного таким образом, как это описано выше, должно давать преимущество по сравнению с просеиванием по прямоугольной области того же размера.
Действительно, в результате численного эксперимента на большом наборе полиномов-кандидатов для факторизации 34-значного числа п = 3159302165809317095910228615234377 показано, что просеивание по особой области дает преимущество перед просеиванием по прямоугольной области. Как характерный результат здесь приведены данные эксперимента, полученные для трех различных т при фиксированном р среднего размера, представляющие собой результаты просеивания массива из 1000 полиномов по особой и прямоугольной областям. Так как использовались полиномы 3-й степени, то выбиралось порядка ^п/р, по рекомендации Кляйнюнга параметр р состоял из произведения нескольких небольших простых чисел сравнимых с единицей по модулю й, граница факторной базы В и 20000.
Уточним, как в этом эксперименте определялась высота особой области. Чтобы рост нормы полинома в секторе не превышал роста нормы в прямоугольной области, границу Ьв для высоты сектора можно выбрать как Ь$ — А/С, где А - радиус просеивания по прямоугольной области, а = тах(с, е), и где и е — упоминавшиеся ранее границы основания сектора.
NN с е ь. Размер области Найдено гладких Плотность г.
0 -10 4 100 70800 512 0,0072
1 -8 3 125 86750 762 0,0088
2 -6 1 167 98363 583 0,0059
Таблица 1: Результаты просеивания по особой области
NN с е ь Размер области Найдено гладких Плотность Гр
0 -1000 1000 35 70035 409 0,0058
1 -1000 1000 43 86043 596 0,0069
2 -1000 1000 49 98049 400 0,0041
Таблица 2: Результаты просеивания по прямоугольной области
Очевидно, такое условие является достаточным для того, чтобы норма полинома в секторе, оцениваемая как ЬаМ, не превысила нормы Ьа}(а/Ь), для о 6 [-А;А]. Затем, для прямоугольной области граница Ь выбирается таким образом, чтобы площади обеих областей были примерно одинаковыми.
В результате плотность гладких (см. таб. 1 и 2) в особой области оказалась в среднем на 23% выше, чем в прямоугольной. Следующий график наглядно показывает соотношение плотности гладких в секторе (г3) и прямоугольной области (гр) для части полиномов из эксперимента с параметрами тп = 276147977, р = 13 • 19 • 61 = 15067.
Рис. 5: Отношение доли гладких найденной при просеивании по сектору к доле гладких найденной при просеивании по прямоугольной области того же размера для различных порождающих полиномов в модификации метода Кляйнюнга
Из рис. 5 хорошо видно, что почти все полиномы эффективнее просеивать по сектору, и выигрыш при этом может достигать 50% по сравнению с обычным просеиванием.
В четвертой главе описывается структура и состав программного комплекса, использованного для практической апробации методик и получения статистически достоверных оценок, кратко обосновывается необходимость его создания, даются ссылки на программные средства, которые были
20
использованы помимо специально разработанных для целей диссертационной работы, описывается методика проведенных экспериментов.
Основные проблемы, которые были решены для создания программной системы:
1. Выделение в отдельные логические блоки функций 1) для генерации исходных полиномов просеивания, 2) генерации большого числа их вариаций и детальной теоретической оценки свойств, 3) фактического просеивания по большому набору полиномов и 4) последующего сбора статистики для построения графиков и обоснования теоретических оценок;
2. Реализация в качестве модуля Delphi системы для работы с арифметикой длинных чисел, включая операции в конечных полях Z,;
3. Реализация обобщенной процедуры просеивания, позволяющей использовать максимально возможное количество памяти компьютера, а также просеивать по особым областям;
4. Оптимизация процедуры просеивания: просеивание "в обратную сторону приближенное вычисление логарифма значений полинома (значительное ускорение по сравнению с тривиальными методами);
5. Оптимизация процедуры поиска факторной базы: реализация алгоритмов ШенксагТоннели (для KP) и Нидеррайтера (РЧП) для поиска корней полинома просеивания по модулю р е FB (значительное ускорение по сравнению с алгоритмами полного перебора);
6. Организация внешних вызовов в систему компьютерной алгебры PARI/GP для тестирования корректности работы программы, а также для сравнения скорости работы реализованных алгоритмов.
Отметим, что, хоть их и не много, существуют свободно доступные готовые реализации таких популярных алгоритмов как квадратичное решето и решето числового поля. Наиболее известные и зарекомендовавшие себя это проекты Msieve7, GGNFS8, а также система компьютерной алгебры PARI/GP9. Также некоторые из нужных нам алгоритмов реализованы в коммерческом пакете Wolfram Mathematica. Однако для целей, заявленных в диссертационной работе, было необходимо произвести достаточно тонкую настройку и модификацию общего алгоритма, которую невозможно сделать
7http://www.boo.net/ jasonp/qa-html
ahttp://www.math.ttu.edu/ cmonico/software/ggnfe/, активная разработка прекращена в 2005
'http: //pari.math.u-bordeaux.£r/
в существующих готовых программных продуктах. Вместе с тем, полная реализация, например, эффективного алгоритма решета числового поля стояла за рамками данного диссертационного исследования, поскольку сама по себе является неоправданно трудоемкой задачей. В результате был создан программный комплекс, реализующий отдельные этапы алгоритмов квадратичного решета и решета числового поля, который позволяет оценить эффективность предложенных в работе методик, а также эффективность целочисленной факторизации в целом. Акцент в данном случай был сделан на генерацию полиномов, просеивание и подсчет оценок.
Программный комплекс реализован в среде Delphi и состоит из 4-х отдельных, но логические связанных друг с другом программ: для генерации исходного полинома, подходящего для процедуры факторизации; генерация набора его вариаций, вычисление их свойств и подсчет критериев; просеивание, включая просеивание по особой области и по подинтервалам; подсчета статистики для построения графиков и получения обобщенных численных оценок.
Общий объем исходных текстов составляет примерно 5000 строчек кода, из которых около 20% занимает реализация на языке Object Pascal библиотеки для быстрой работы с большими целыми числами. Также были реализованы следующие необходимые для работы алгоритмы теории чисел: алгоритм решения квадратичного уравнения по модуля простого числа Шенксаг Тоннели, алгоритм "поднятия"решения по модулю pfc+1 при известном решении под модулю рк (поднятие Гензеля), алгоритм Бернштейна приближенного значения функции Дикмана-де Брюина, алгоритм быстрого поиска корней полинома произвольной степени по модулю произвольного большого простого числа (алгоритм Нидеррайтера). Для оценки корректности реализованных алгоритмов использовалась система компьютерной алгебры PARI/GP.
Были проведены следующие численные эксперименты:
1. эксперимент по оценки сложности метода решета числового поля, ограниченного входными числами п < 105 и квадратичными полиномами факторизации;
2. эксперимент, оценивающий эффективность просеивания по подинтервалам для п различной длины и различных простых чисел р;
3. эксперимент, оценивающий эффективность просеивания по подинтервалам в модификации КР Занга;
4. эксперимент, оценивающий эффективность просеивания в гибридном методе по особой области — вдоль оптимальной прямой;
22
5. эксперимент для сравнения просеивания по прямоугольной области с предложенным в диссертации просеиванием по сектору.
В заключении приведены основные выводы по диссертации, сформулированы полученные научные и практические результаты, состоящие в следующем:
1. Описана, реализована и проанализирована методика просеивания по по-динтервалам в методе факторизации квадратичного решета (КР), которую также можно использовать в методе факторизации числового поля (РЧП), а также в модификации КР Занга. На примере КР видно, что эта стратегия может давать существенный выигрыш, уменьшая величины верхней границы простых чисел в факторной базе и радиуса интервала просеивания, предоставляя дополнительные возможности для параметризации алгоритма, а также допуская его распараллеливание.
2. Описана методика выбора и просеивания по особой области полиномов для алгоритма факторизации числового поля, позволяющая в среднем получать до 20% больший выход гладких по сравнению с обычным просеиванием, а значит быстрее находить лучший полином на первом шаге алгоритма и быстрее находить достаточное количество гладких чисел для факторизации п, чем это возможно в обычном методе РЧП.
3. Разработан программный комплекс, реализующий процедуру просеивания для алгоритмов квадратичного решета и решета числового поля, позволяющий оценивать скорость решения задачи факторизации этими алгоритмами при различных параметрах. Получена численная оценка, подтверждающая эффективность предложенных методик.
Поскольку рассматриваемые алгоритмы квадратичного решета и решета числового поля являются лучшими на сегодняшний день для разложения произвольных больших составных целых на простые множители, это позволяет говорить о том, что с помощью результатов, изложенных в диссертации, можно сделать процедуру факторизации более эффективной.
Список публикаций по теме диссертации
1. В изданиях из списка ВАК:
[1] Зиятдинов Д.Б. Об одном подходе к проблеме факторизации натуральных чисел [Текст] / A.A. Бойко , Д.Б. Зиятдинов ,Ш.Т. Ишмухаметов // Известия вузов. Математика. — 2011. — N»4. — С. 15-22.
[2] Зиятдинов Д.Б. Об одной стратегии в процедуре просеивания для факторизации больших натуральных чисел [Текст] / Д.Б. Зиятдинов, Р.Г. Рубцова // Ученые записки Казанского университета. — 2011. — вып. 153. — т. 1. - С. 231-239.
2. Прочие публикации:
[3] Зиятдинов Д.Б. Об одной оценке метода решета числового поля / Д.Б. Зиятдинов // Труды VII международной научно-практической конференции «Инфо-коммуникационные технологии глобального информационного общества». — 2009. — Казань. — http://iktgio.mcrt.ru/rusiktgio/tezisy
[4] Зиятдинов Д.Б Методы защиты информации с открытым ключом и математические проблемы / Зиятдинов Д.Б., Ишмухаметов Ш.Т. // Материалы ежегодной научно-практическая конференция «Инновации РАН-2010».
— 2010. — Казань: Изд-во «Слово». — С. 303.
[5| Зиятдинов Д.Б. О проблеме выбора полинома в методе решета числового поля / Д.Б.Зиятдинов, Ш.Т. Ишмухаметов, Р.Г.Рубцова // Труды III Всероссийской конференции "Информационные технологии в системе социально-экономической безопасности России и ее регионов". — 2010. — Казань: Изд-во ТГГПУ. - С. 177-183.
3. Использованные источники
[6] Agrawal М., Kayal N., Saxena N. PRIMES is in P // Annais of Mathematics.
- 2004. - Т. 160. - № 2. — Р. 781-793
[7] Bernstein D.J. Introduction to post-quantum cryptography. Springer-Verlag Berlin Heidelberg, 2009
[8] Boender H., Riele H. Factoring Integers vnth Large-Prime Variations of the Quadratic Sieve, Centrum voor Wiskunde en Informática, No. NM-R9513,1995.
24
9] Briggs M. An Introduction to the General Number Field Sieve // Master's Thesis, Virginia Polytechnic Institute and State University, Blacksburg, Virginia -1998. — P. 1-84.
10] Buhler J.P., Lenstra Jr H.W., Pomerance C. Factoring Integers vnth the Number Field Sieve // The Development of the Number Field Sieve, LNM 1554 (1993) P. 50-94.
11] Buhler J., editor. Algorithmic Number Theory: Proc. ANTS-III, Portland, OR, volume 1423 of Lecture Notes in Computer Science. Springer-Verlag, 1998.
12] Crandall R.E., Pomerance C. Prime numbers: A Computational Perspective. Springer, 2002.
13] Granville A. Smooth numbers: computational number theory and beyond // Algorithmic Number Theory MSRI Publications Volume 44, 2008.
14] Lenstra A.K., Lenstra H.W. Jr., Manasse M.S., Pollard J.M., Factoring integers with the number field sieve / in [16] P. 11—42.
16] Lenstra A., Lenstra H. (Eds) The Development of the Number Field Sieve // LNM v.1554, Springer-Verlag, Berlin, 1993.
17] Kleinjung Th., Aoki K., Franke J., Lenstra A., Thomd E., Bos J., Gaudry P., Kruppa A., Montgomery P., Osvik D. A., te Riele H., Timofeev A., Zimmermann P. Factorization of a 768-bit RSA modulus. Online report, 18 Feb 2010.
18] Kleinjung T. On Polynomial Selection for the General Number Field Sieve/ Math. Comp. 75 (2006), P. 2037-2047.
19] Landquist E. Possible Ways to Extend Zhang's Special Quadratic Sieve, 2003.
20] Murphy B. A. Polynomial Selection for the Number Field Sieve integer Factorisation Algorithm //A thesis submitted for the degree of Doctor of Philosophy of The Australian National University, 1999.
21] Pomerance C. A Tale of Two Sieves // Notices of the AMS 43 (12): P. 14731485, Dec 1996.
22] Pomerance C. Multiplicative independence for random integers // Analytic Number Theory, vol. 2: Proceedings of a Conference in Honor of Heini Halberstam, Birkhauser, Boston, 1996.
23] Pomerance C. The quadratic sieve factoring algorithm // Advances in Ciyptology, Proceedings of Eurocrypt 84, Paris, 1984.
25
[24) Rothe J. Complexity theory and cryptology: an introduction to cryptocomplexity, Springer Berlin Heidelberg New York, 1998.
[25[ Williams C.P., Clearwater S.H. Ultimate zero and one: computing at the quantum frontier. Springer-Verlag New York, Oct 1999.
[26J Zhang M. Factorization of the Numbers of the Formic? + сгт2 + Cim + Cq. // in [11], P. 131-136.
[28] Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. — Казань: Казан ун-т., 2011.
Подписано в печать 22.02.2012 г. Бумага офсетная. Гарнитура «Тайме».
Формат 60x84 i/I6. Усл. печл. 1,5. У ч.-изд.л.1,75. Печать ризографическая. Тираж 100 экз. Заказ 004.
Отпечатано с готового оригинал-макета в типографии ООО «Олитех». 420021, г. Казань, ул. Ахтямова, 1.
61 12-1/684
КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
На правах рукописи
ЗИЯТДИНОВ ДМИТРИЙ БУЛАТОВИЧ
РАЗРАБОТКА И ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ПРОСЕИВАНИЯ ДЛЯ ФАКТОРИЗАЦИИ НАТУРАЛЬНЫХ ЧИСЕЛ
Специальность 01.01.06 — «Математическая логика, алгебра и теория чисел»
Диссертация на соискание учёной степени кандидата физико-математических наук
Казань - 2012
ОГЛАВЛЕНИЕ
Введение......................................................................5
ГЛАВА 1. Основные алгоритмические этапы методов факторизации
модулей RSA и оценка их сложности..................................15
1.1 Квадратичное решето..............................................15
1.2 Алгоритм решета числового поля................................24
1.3 Экспериментальная оценка сложности алгоритма РЧП .... 29 ГЛАВА 2. Методика просеивания по подинтервалам и ее оценка ... 37
2.1 Просеивание по подинтевалам в КР..............................37
2.1.1 Пример просеивания по подинтервалам в КР......39
2.1.2 Оценка эффективности просеивания по подинтервалам. 41
2.1.3 Экспериментальная оценка эффективности АПП ... 44
2.2 Просеивание по подинтервалам в модификации Занга.....49
2.2.1 Оценка эффективности просеивания по подинтервалам
в модификации Занга........................................52
ГЛАВА 3. Методика просеивания по особой области и ее оценка .... 56
3.1 Просеивание по особой области в гибридном методе............56
3.1.1 Оценка сложности гибридного метода....................61
3.2 Эффективный выбор полинома и просеивание по особой области в РЧП..........................................................64
3.2.1 Экспериментальная оценка эффективности просеивания
по особой области в РЧП..................................67
ГЛАВА 4. Состав программного комплекса и методика численных экспериментов ..............................................................70
4.1 Общие проблемы программной реализации......................70
4.1.1 Генерация полиномов просеивания........................74
4.1.2 Статистическая обработка данных........................75
4.1.3 Некоторые алгоритмы................... 75
4.2 Метода Гаусса для систем линейных уравнений большой размерности .............................. 78
4.2.1 Оценки производительности............... 80
4.2.2 Пример........................... 83
4.3 Методика экспериментов..................... 85
Заключение.................................. 87
Публикации автора............................. 88
Использованная литература........................ 88
ПРИЛОЖЕНИЕ А. Дополнительные таблицы и графики....... 95
А.1 Просеивание по подинтервалам для КР............. 95
ПРИЛОЖЕНИЕ Б. Некоторые исходные тексты программ ......101
Б.1 Генерация сильных чисел RSA..................101
Б.2 Программа для быстрого поиска корней полинома по модулю
простых чисел...........................103
Б.З Программа для просеивания по подинтервалам для модификации КР Занга ...........................109
Список обозначений
В работе используются следующие обозначения:
7г(п) — Количество простых чисел, не превосходящих п
(р(п) — Количество натуральных чисел, взаимнопростых с п
Z/nZ — Кольцо вычетов, изоморфное целым числам по модулю п
р (и) — Функция Дикмана-Де Брюина (см. [28], стр. 49 и [32])
p\f(x + кр) — То же, что f(x + кр) = 0 mod р\ р делит f{x) в точках х + кр
КР — Алгоритм целочисленной факторизации «квадратичное решето»
РЧП — Алгоритм целочисленной факторизации «решето числового поля»
ВВЕДЕНИЕ
Задача целочисленной факторизации состоит в разложении произвольного натурального числа п на простые множители. Общеизвестно, что эта задача относится к классу трудных, однако на сегодняшний день не доказана принадлежность факторизации к формальным классам сложности Р или NP1. Напомним, что в недавней работе [7] показано, что более простая задача определения простоты числа лежит в Р, а значит существует детерминированный алгоритм, за полиномиальное время от длины поданного на его вход целого числа определяющий, является ли оно простым или нет. В то же время на практической трудоемкости решения задачи факторизации с помощью современных вычислительных средств в настоящее время основывается чрезвычайно широко распространенный метод шифрования с открытым ключом RSA, а также алгоритмы цифровой подписи.
Напомним кратко, что в протоколе RSA сначала происходит выбор открытого ключа, представляющего собой пару целых чисел (е, п), где число п = pq называется модулем RSA и является произведением двух хранящихся в тайне больших простых чисел р и q, а также вычисляется секретный ключ d = е-1 mod f(n). Затем передаваемое по открытому каналу вместе с открытым ключом сообщение m шифруется как с = те mod п, и потом, согласно теореме Эйлера, расшифровывается с помощью секретного ключа: cd = m mod п. Если злоумышленнику станет известна факторизация п, то он легко сможет вычислить секретный ключ d и расшифровать сообщение. Подробнее о проблеме RSA см. [31], с. 14, а также книги [68] с. 101, [70], § 33.7, [73], с. 87 и работу [46].
Можно утверждать, что обнаружение классического алгоритма, решающего задачу факторизации за полиномиальное время, заставило бы полностью отказаться от RSA в будущем, и скомпрометировало бы большое
1Подробнее см. [55], стр 336, citeNosov, § 14, а также книги [72] и [64]
количество уже существующих систем. Однако, самый быстрый алгоритм факторизации произвольных натуральных чисел, известный на сегодняшний день, имеет субэкспоненциальную оценку времени работы (опять же, от длины числа п). Это значит, что теоретически оцениваемое количество шагов до завершения его работы хоть и уступает значениям полинома от п = ехр[1пп], все-таки значительно превышает значение полинома от Inn. Функция сложности работы такого алгоритма, как правило, выражается формулой (см. [50]):
Ln[a, с] = ехр [(с + о(1)) (lnnHlnlnn)1"0] , а > 1/3.
Благодаря этому, приемлемый уровень безопасности в протоколе шифрования RS А достигается при использовании ключа (е, п) относительно небольшого размера, что очень важно для практического использования. Прогресс в области компьютерных технологий и алгоритмов факторизации увеличивает нижнюю границу размера ключа, в частности размер модуля RSA, шифрование по которому считалось бы на текущий момент безопасным.
Согласно отчету о последнем достигнутом рекорде факторизации (см. [35]), который был установлен 12 декабря 2009 г., с помощью алгоритма решета числового поля на простые множители было разложено 768-битное 232-значное число RSA-768. Общее потраченное на выполнение этой работы время составило два с половиной года. При этом распределенные вычисления на сотнях компьютеров потребовали более 1020 операций, что эквивалентно 2000 годам вычислений на компьютере класса 2.2GHz AMD Opteron. Тем не менее, авторы исследования справедливо оценивают затраченные усилия по факторизации 768-битного модуля как достаточно малые, чтобы рекомендовать не использовать в дальнейшем модули такого размера даже для кратковременной защиты данных. Кроме того, выдвигается предположение (см. также [22] и [23]), что факторизация 1024-битного RS А модуля хоть и будет примерно в тысячу раз более сложной задачей, но ее реше-
ние в рамках схожего академического проекта может быть получено уже в течение следующего десятилетия.
Рассмотрим кратко основные исторические вехи в поиске более быстрых алгоритмов факторизации произвольных больших натуральных чисел, связанные естественным образом с атакой на протокол RSA. Согласно обзору, проделанному в книге [10], можно выделить:
• 1978 г. выходит статья Р. Ривеста, А. Шамира и Л. Адлемана, впервые описывающая новый алгоритм шифрования RSA. В этом же году алгоритм факторизации «Линейное решето» Ричарда Шроппеля, позднее преобразованный в метод квадратичного решета, раскладывает произвольный RSA-модуль п на простые множители, а значит взламывает RSA, используя порядка Ln[ 1/2,1] простых операций. Размер надежного ключа RSA начинает оцениваться из того соображения, что для экспоненциального времени работы линейного решета (2Ь операций) необходимо, чтобы размер модуля п составлял по меньшей мере (0,5 + o(l))b2/log2 Ъ бит. 2
• 1988 г. Дж. Поллард объявляет о новом алгоритме факторизации «Решето числового поля» для чисел специального вида. Этот алгоритм, впоследствии обобщенный Дж. Булером, X. Ленстрой и К. Померанцем, факторизует любой RSA-модуль п, используя уже только около L[ 1/3,1.9] простых операций. Для экспоненциального времени работы решета числового поля необходимо, чтобы размер п составлял по крайней мере (0, 016... + o(l))63/(log2 b)2 бит.
• 1994 г. Питер Шор описывает алгоритм, который факторизует любой RSA-модуль п, используя порядка Ln[0,2] простых операций на квантовом компьютере размера Ln[0,1]. Для экспоненциального времени
2Параметр b определяет уровень безопасности шифра. Значение о(1) при этом стремится к нулю,
только когда b —> оо. Для конкретных значений b необходим более детальный анализ алгоритма.
работы этого алгоритма необходимо, чтобы размер модуля п составлял по крайней мере бит. То есть, при создании достаточно большого действующего квантового компьютера, шифры RSA однозначно перестанут быть актуальным средством шифрования информации, так как размер безопасного RSА-модуля окажется неприемлемо велик.
Отметим, что на текущий момент квантовые компьютеры, на практике способные факторизовать сколько-нибудь большие целые числа, так и не созданы (см., например, книгу [58]). Кроме того, полный переход на алгоритмы шифрования, не поддающиеся взлому на пока еще не существующем квантовом компьютере, связан со многими не до конца еще разрешенными трудностями. Можно привести следующие аргументы в пользу дальнейшего использования и изучения алгоритмов RSA, а значит и решения задачи факторизации на классическом компьютере:
1. Высокая эффективность RSA на текущий момент, и низкая эффективность альтернативных алгоритмов. Например, устойчивому к взлому с помощью квантового компьютера алгоритму шифрования с открытым ключом Мак-Элис (см. [74], гл. 19) требуется размер ключа порядка n2/4 « b2(log2b)2 бит. Поскольку мы допускаем, что на момент взлома не существует лучшего алгоритма факторизации, чем алгоритм решета числового поля, и реальный уровень безопасности имеет выглядящий разумным на сегодняшний день порядок b = 128, размеры ключей RSA будут исчисляться тысячами бит, в то время как размеры ключей Мак-Элис — миллионами. Также имеет значение скорость работы алгоритма. Алгоритмы цифровой подписи, широко распространенные на текущий момент, допускают подпись и верификацию информации за полиномиальное время. Алгоритмы, устойчивые к возможности взлома на большом квантовом компьютере, работают более медленно. Использование их в настоящее время в сети Ин-
тернет повлекло бы за собой существенное снижение производительности сети.
2. Более 20 лет поисков алгоритмов полиномиальной факторизации и безуспешных попыток значительно улучшить асимптотическое время факторизации решета числового поля (см. [28], [33], [34]) позволяют надеяться, что этот алгоритм действительно представляет собой быстрейшую схему факторизации произвольного составного числа на классическом компьютере. Однако, поскольку невыгодно без необходимости увеличивать размер ключа шифрования до бесконечности, а также поскольку алгоритм решета числового поля обладает сложной структурой, мы полагаем, что все еще возможно локально улучшить его производительность для некоторого класса практически разрешимых задач.
Таким образом, задача исследования классических алгоритмов факторизации является по-прежнему актуальной. Рассматриваемые в диссертации алгоритмы квадратичного решета (КР) и решета числового поля (РЧП) — сложные, состоящие из нескольких этапов-, современные алгоритмы, наиболее эффективные для факторизации целых чисел размером от 50 десятичных знаков и более. Одним из важнейших этапов обоих алгоритмов является просеивание — процедура поиска достаточного количества так называемых гладких чисел для получения нетривиальной факторизации на последнем этапе. Как показано в [28] (с. 268-277, 294-300) эффективность алгоритма факторизации в целом разумно оценивать исходя из того, насколько эффективно возможно выполнить именно этап просеивания. Однако, особенно для алгоритма РЧП, очень важен еще и этап выбора полинома (см. докторскую диссертацию Б.Мерфи, 1999 г. [48] и статью 2004 г. Т.Кляйнунга [37]).
Отметим особо, что на сегодняшний день не существует строгого математического обоснования для оценки эффективности работы КР и РЧП в общем случае, все имеющиеся оценки получены при условии ряда эври-
стических предпосылок. Тем не менее, алгоритмы КР и РЧП достаточно хорошо исследованы. Уже в публикации [51] 1984 г. предлагаются ряд значительных модификаций базового алгоритма КР, без которых эффективное его применение на практике становится уже почти невозможным. Прежде всего это так называемое мультиполиномиальное квадратичное решето (МПКР), позволяющее решать задачу факторизации в параллельных процессах. Подробная публикация [12] 1995 г. описывает важную стратегию просеивания, в результате которой для факторизации могут быть использованы не только найденные гладкие числа (которых в результате однократной работы базового алгоритма может быть найдено недостаточное количество) , но и так называемые полугладкие. Такая же стратегия применима для алгоритма РЧП. Но еще большее значение имеет сформулированная для РЧП методика решеточного просеивания (см. [34], с.43-49), позволяющая, с помощью особым образом подобранных параметров р, просеивать только выборочные значения полиномов, и при этом получать лишь незначительно меньший выход гладких чисел относительно простого просеивания по всем элементам факторной базы.
В данной работе осуществляется теоретический вывод, обоснование и оценка эффективности одного из возможных алгоритмов просеивания, делающих процедуру факторизации более эффективной — алгоритма просеивания по подынтервалам для КР, а также исследуется процедура выбора эффективного полинома для алгоритма РЧП, связанного с особой областью просеивания. Кроме того исследуется гибридный алгоритм факторизации, полученный с помощью объединения идей КР и РЧП, обнаруживающий при ближайшем рассмотрении большое сходство с алгоритмом, известным как модификация КР Занга3. Подобные теоретические обоснования вместе с некоторыми подтверждающими их экспериментальными оценками позволяют получить лучшее представление о границах эффективности процедуры
3См. [59].
просеивания в алгоритмах КР и РЧП, а значит, в определенном смысле, и об эффективности процедуры факторизации в целом.
Основной целью работы является исследование алгоритмов просеивания в методе квадратичного решета и решета числового поля и оценка их эффективности, построение оценок для сходимости алгоритма просеивания по подинтервалам.
Для достижения поставленной цели были решены следующие основные задачи:
1. Исследованы современные алгоритмы целочисленной факторизации квадратичного решета и числового поля;
2. Построены оценки для частот появления гладких чисел для алгоритма просеивания по подинтервалам, оценена его эффективность относительно стратегии расширения интервала просеивания;
3. Исследованы процедуры выбора эффективных полиномов просеивания для алгоритма решета числового поля;
Основные положения, выносимые на защиту:
1. Разработка алгоритма просеивания по подинтервалам (АПП);
2. Получение оценки выигрыша для выхода гладких при использовании АПП;
3. Разработка программного комплекса для численной проверки полученных оценок;
4. Исследование метода Занга и оценка его эффективности;
5. Разработка алгоритма выбора эффективного полинома для алгоритма решета числового поля и проверка его эффективности;
1. Разработка и оценка эффективности алгоритма просеивания по подин-тервалам, обеспечивающего более эффективный поиск гладких пар в методах целочисленной факторизации квадратичного решета и решета числового поля;
2. Анализ и развитие специального метода Занга целочисленной факторизации;
3. Разработка алгоритма выбора оптимального полинома просеивания в методе решета числового поля;
Практическая значимость: Разработка и анализ алгоритмов просеивания, которые могут быть использованы для построения более эффективных алгоритмов факторизации.
Достоверность изложенных в работе результатов обеспечивается строгостью постановки задач и математических методов их решения, а также системным подходом к разработке и тестированию программного комплекса, экспериментально подтверждающего теоретические оценки.
Апробация работы. Основные результаты работы докладывались на конференциях:
1. Конференция аспирантов и молодых преподавателей КГУ, 2009, Казань
2. 7-я международная научно-практическая конференция «Инфокомму-никационные технологии глобального информационного общества» Казань, 2009;
3. Международная школа-конференция молодых ученых - Турку, Финляндия, июнь 2009;
4. Научно-практическая конференции и выставка «Инновации РАН -2010»;
5. III Всероссийской научно-практической конференции «Информационные технологии в системе экономической безопасности России и ее регионов», Казань, 2010.
Личн�
