Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Ρ-алгоритм Полларда).pdf

Решая линейную систему уравнений, получаем, что . Тогда

Следовательно,

.

Получилось разложение

2.1.7 Факторизация с помощью эллиптических кривых

Допустим, нам нужно факторизовать число n = 455839.

Возьмем эллиптическую кривую и точку, лежащую на этой кривой

Попробуем вычислить 10!P:

• Для начала вычислим координаты точки . Тангенс угла наклона касательной в точке P равен:
• Находим координаты точки :

.

• Проверяем, что точка 2P действительно лежит на кривой:

2. Теперь вычислим .

• Тангенс угла наклона касательной в точке 2P составляет

.

Для вычисления 593 / 106 по модулю n можно воспользоваться расширенным алгоритмом Евклида: 455839 = 4300·106 + 39, далее 106 = 2·39 + 28, далее 39 = 28 + 11, далее 28 = 2·11 + 6, далее 11 = 6 + 5, далее 6 = 5 + 1. Откуда получаем, что НОД(455839, 106) = 1, и в обратную сторону: 1 = 6 - 5 = 2·6 - 11 = 2·28 - 5·11 = 7·28 - 5·39 = 7·106 - 19·39 = 81707·106 - 19·455839. Откуда 1/106 = 81707 (mod 455839), таким образом, -593 / 106 = 322522 (mod 455839).

• Учитывая вычисленное s, мы можем вычислить координаты точки 2(2P), так же, как это было сделано выше: 4P = (259851, 116255). Проверяем, что точка действительно лежит на нашей эллиптической кривой.
• Суммируя 4P и 2P, находим .
• Аналогичным образом можно вычислить , , и так далее. Когда дойдем до 8!P заметим, что требуется вычисление обратного элемента к 599 (mod 455839). Так как 455839 делится на 599, то мы нашли искомое разложение: 455839 = 599·761.

2.2 Факторизация в криптографии

Разложение (разложение) натуральных чисел на множители является сложной вычислительной задачей. Сложность решения этой проблемы лежит в основе одного из самых известных методов криптографии - метода RSA. Существует большое количество алгоритмов факторизации, среди которых наиболее быстрыми сегодня являются метод квадратичного сита и метод численного сита.

• RSA (сокращение от имен Rivest, Shamir и Adleman) - это криптографический алгоритм с открытым ключом, основанный на вычислительной сложности задачи факторизации больших целых чисел.
• Криптографические системы с открытым ключом используют так называемые односторонние функции, которые имеют следующее свойство:
• Если известно , то вычислить относительно просто
• Если известно , то для вычисления нет простого (эффективного) пути.

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

Криптографическая система с открытым ключом RSA основана на сложности проблемы факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Чтобы расшифровать за разумное время (обратная операция), необходимо уметь вычислять функцию Эйлера для данного большого числа, для которого необходимо знать разложение числа в простые множители.

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

сообщения , где — множество допустимых сообщений

допустимых открытого и закрытого ключей и

соответствующие функции шифрования и расшифрования , такие что

Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом:

1. Выбираются два различных случайных простых числа и заданного размера.
2. Вычисляется их произведение , которое называется модулем.
3. Вычисляется значение функции Эйлера от числа :

1. Выбирается целое число , взаимно простое со значением функции . Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
   • Число называется открытой экспонентой.
   • Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в .
   • Слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA.
2. Вычисляется число , мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее условию:

• • Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

1. Пара публикуется в качестве открытого ключа RSA.
2. Пара играет роль закрытого ключа RSA секрете.

2.3 Примеры применения алгоритмов факторизации натуральных чисел в программной среде Maple

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

Ниже приведены списки методов, которые включены в различные версии Maple.

В Maple 6:

'squfof' - метод Квадратичных форм Шенкса;

'pollard' – алгоритм Полларда;

'lenstra' - метод эллиптических кривых Ленстры;

'easy' - без дальнейшей обработки.

В последних версиях Maple:

'mpqs' – множественный полиномиальный метод квадратичного решета;

'morrbril' – алгоритм Брилхарта-Моррисона;

'squfof' – метод квадратичных форм Шенкса;

'pollard' – алгоритм Полларда;

'lenstra' - метод эллиптических кривых Ленстры;

‘mpqsmixed' – ‘mpqs', ‘morrbril' и ‘pollard';

‘mixed' – 'morrbril' и 'pollard' (по умолчанию в версиях Maple 11 и более ранних)

‘easy' - без дальнейшей обработки;

‘Easy' – если данный вариант разложения будет выбран, результатом ifactor будет произведение чисел, которые легко было отделить, а также «_c.m._.n», которое обозначает m-значное составное число, которое не было разложено, где n – уникальный номер данного составного числа.

‘Pollard’ – метод Полларда, опционально требующий дополнительное целое k (ifactor(n,pollard,k)), которое повышает эффективность метода в том случае, если один из сомножителей имеет форму k*m+1.

• В процессе написания этой работы я использовал платформу Maple 6 для более детального рассмотрения различных алгоритмов факторизации натуральных чисел. Так как моей целью было проанализировать и сравнить некоторые алгоритмы, реализованные в среде Maple, и время их выполнения, я сделал следующее (см. Приложение, стр. 35)

n:=1225992214214988495889178222383575197953889910663283660941397211195293307578078718078619789346251171394591299026682300363349450174814676994019289743170166203329177516492641629553799863550875253574485611528087163760246308842411883285814684377331873414394475363668140223797216205606498904469268054423713940637910055764209685035

1. Проверить время выполнения алгоритмов для неструктурированного числа.

- сгенерировал два больших простых числа с использованием функций nextprime и prevprime;

- Умножил их и запустил процедуру ifactor для полученного числа без дополнительных параметров, с параметрами squifof, pollard и lenstra. Так как мне нужно время выполнения, я использовал функцию времени из ifactor;

• Получил значения для разных алгоритмов. Для алгоритма по умолчанию (алгоритм Моррисона-Брилхарта вместе с алгоритмом Полларда), получил значение 632,795 секунды.

- Для squifof это значение было «0», то есть малейшие доли секунды. Алгоритм Полларда пришлось остановить на 308ой тысяче секунд(3,56 суток), алгоритм Ленстры дал результат через 20311,795 секунды.

1. Далее я применил алгоритмы для структурированного числа вида k*(2^t+1).

• Взял k равным простому числу 331, а t (степень двойки в выражении) равным 190. Нашёл значение выражения с этими данными;
• Применил ifactor и нашёл время выполнения ifactor от нашего числа. Время выполнения составило 47193,554 секунды;
• Далее я применил алгоритм squifof для числа той же структуры, но с большим показателем степени двойки, t = 9290. Данным алгоритмом число разложилось за 77.5 секунды;

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

• Я положил t равным 1221 и получил очень крупное число в 2800 знаков;
• Воспользовавшись алгоритмом Ленстры, я получил время выполнения – всего 0,63 секунды.

Отсюда мы видим, что при изменении числовой структуры алгоритмы ведут себя по-разному. Используя тот же алгоритм, для разложения числа с 2800 символами требуется примерно в 32000 раз меньше времени, чем для разложения числа с 48 символами. Структура номера отличается. В первом случае в числе много маленьких делителей, а во втором случае их всего два, и оба являются большими простыми числами.

2.4 Оценка эффективности алгоритмов факторизации натуральных чисел

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

На практике алгоритм Ленстры часто используется для идентификации (отбрасывания) небольших простых чисел. И мы увидели это, расширив 32000-значное число 1221! за 0,63 секунды. Как среди 1221! содержит все первые 1221 чисел, тогда не составит труда идентифицировать и отбросить все тривиальные делители.

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

Среди алгоритмов факторинга с экспоненциальной сложностью метод квадратичных форм Шенкса считается одним из наиболее эффективных. Этот алгоритм работает с целыми числами, не превышающими. Мы знаем, что для 32-битных компьютеров алгоритмы, основанные на этом методе, являются бесспорными лидерами алгоритмов факторизации для чисел между ранее и, вероятно, так и останутся. Этот алгоритм может разделить почти любое составное 18-значное число менее чем за миллисекунду.