ВВЕДЕНИЕ 3
1. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ 5
1.1 Операции на эллиптической кривой 7
1.1.1 Аффинные координаты 7
1.1.2 Проективные координаты 9
1.2 Использование эллиптических кривых 10
1.3 Тесты простоты на эллиптических кривых 11
2. ПОСТАНОВКА ЗАДАЧИ 13
3. ТЕСТ ПРОСТОТЫ АТКИНА-МОРЕЙНА 14
4. РЕАЛИЗАЦИЯ АЛГОРИТМА 16
4.1. Тест Аткина-Морейна 16
4.2. Организация проверки сертификата 21
5. ПРИМЕР ИСПОЛЬЗОВАНИЯ ПРОГРАММЫ 21
6. ИССЛЕДОВАНИЕ РЕЗУЛЬТАТОВ РАБОТЫ ПРОГРАММЫ 23
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 35
ПРИЛОЖЕНИЕ
С развитием информационных технологий увеличивается значение криптографии. Если раньше достаточно было защищать лишь документы, то теперь в этом нуждается вся система, которая имеет доступ к информации.
Практически на всех уровнях сетевой модели OSI, благодаря которым происходит взаимодействие между пользователями, используются протоколы, включающие в себя шифрование передаваемых данных. Таким образом, обеспечивается защита при передаче информации между уровнями и при передаче информации в сети между пользователями. Большое внимание уделяется методам шифрования, что понятно. Их делят на симметричные и асимметричные. Первые используют один ключ, который необходимо держать в тайне между общающимися сторонами. Вторые используют два ключа, открытый, который находится в общем доступе, и закрытый, который хранится в тайне. Огромное количество разных подходов к тем или иным способам сокрытия информации, однако, у всех есть общие стороны, одной из которых является использование простых чисел в своей основе. Гарантированно, что, к примеру, системы, взлом которых требует решения задачи дискретного логарифмирования, более криптостойки, если используют большие простые числа в качестве модуля. То же самое касается и задач разложения на множители.
К сложным задачам современности относится задача о факторизации большого числа N. Она требует значительных вычислительных ресурсов и, как следствие, выполнение программы, которая находит простые делители числа N, может длиться годами. Однако обратная задача выполнима легко [28]. Это значит, что мы быстро генерируем два простых числа p, q и находим их произведение p*q =N, а оппонент, имея N, долго раскладывает его на множители p и q. [11]
Становится естественным, что ключи и алгоритмы программ, которые используют генерацию большого простого числа, одни из самых криптостойких на сегодняшнее время.
Переходя к элементарным определениям:
Основная теорема арифметики гласит, что каждое натуральное число n можно единственным образом представить в виде
n = рр-* р2 pk, где ру< р2<.< Рк - простые числа,
а±, а2 ,... , ак - некоторые натуральные числа [20]
Так, если условиться, что произведение пустого множества чисел равно 1, выходит, что:
• само число 1 не считается простым;
• для простого числа k= 1; [25]
Таким образом, основная теорема арифметики, идея которой упоминалась еще до н.э., возможно первая обозначила проблему разложения данного целого числа на простые множители.[16]
Итак, простое число - натуральное число больше единицы, которое делится на себя и на 1. Чем оно больше, тем сложнее взломать систему, которая использует его в качестве шифрования.
Существующие алгоритмы нахождения простого числа используют либо вероятностные тесты, либо детерминированные. Первые работают гораздо быстрее, чем вторые, но могут ошибаться, выдавая составное число простым. Последние совершенно точно срабатывают верно. К ним относится полный перебор всевозможных делителей числа.
Алгоритмы, основанные на эллиптических кривых, точно определяют простое число и конкурируют с вероятностными тестами по скорости выполнения. Они представляют собой математические вычисления, производящиеся над уравнениями третьего порядка, которые и называются эллиптическими. Построение кривой производится в поле предполагаемого простого числа. Происходит подсчет точек на заданной кривой и по некоторому списку критериев делают определенные выводы. Примерами такого теста являются тесты на простоту Гольдвассера-Килиана и Аткина- Морейна(ЕСРР), реализация и анализ последнего как раз и описывает данная работа.
Тест простоты Аткина-Морейна - теста простоты основанный на теореме Гольдвассера-Килиана. В нем при определенных условиях генерируется порядок и уже после идет поиск параметров кривой. Недостаток алгоритма в том, что подходящие порядки имеют неизвестное распределение, именно поэтому говорят, что алгоритм имеет вероятностную сложность. Так этот аспект можно наблюдать на графике максимумов времени выполнения теста. Таким образом, мы не можем угадать, где нам повезет и алгоритм закончит свое выполнение за приемлемое время. Однако график значений среднего времени выполнения не так безнадежен: рост уже можно предсказать и на наших значениях является экспоненциальным. Степень экспоненты 0.017x, а это говорит о том, что на проверенном интервале, до 400 бит, график достаточно пологий и проверки проходят быстро. Еще лучше обстоят дела с графиком минимумов: полученные значения можно примерно аппроксимировать логарифмической функцией. Последнее означает, что при помощи алгоритма Аткина-Морейна можно за малый промежуток времени сгенерировать большое простое число, просто игнорируя те случаи, когда мы предпринимаем больше усилий, чем задано. К примеру, 747-битное число алгоритм определил как простое за 1,5 минуты. К тому же генерируется сертификат, который еще за более короткий срок, путем подстановки ранее вычисленных параметров кривой и разложений, позволяет произвести проверку. Так именно этим тестом были проверены числа, имеющие более чем две тысячи разрядов.
Самой емкой частью алгоритма является этап факторизации порядка. В реализации сначала поиск тривиальных делителей, а после, если факторизовать все-таки не получилось, начинает работать po-метод Полларда. Для повышения эффективности на этом этапе было введено распараллеливание, так как алгоритм может генерировать до 6 разных порядков, и в ситуации, когда в их последовательном разложении удастся разложить только последний элемент, время работы заметно увеличивается.
Факторизация может производиться любым известным способом, главный критерий - эффективность метода, но это уже другая область исследования, вопросы которой решаются отдельно. Следующим емким шагом алгоритма является поиск параметров кривой. Дело в том, что в случае, когда дискриминант Э -3, -4, тогда начинается сложная математика, которая
включается в себя операции над многочленами такие, например, как деление полинома большой степени на полином в малой степени и пр.
Проверка сертификата, сгенерированного при помощи метода доказательства простоты, сразу проверяет условия теоремы Гольдвассера- Килиана, таким образом, затрачивает основное время выполнения на несложные операции над кривыми. В таком случае естественно, что проверка числа занимает очень малое время.
Метод Аткина-Морейна хорошо работает на практике и однозначно определяет простоту числа - казалось, что эти два пункта не могут употребляться как характеристики одного. Существует много вариантов реализации теста и скорость его работы может совершенствоваться в будущем благодаря применению новых быстрых алгоритмов факторизации, операций над многочленами и прочее. Выполнение программы на компьютерах больших мощностей позволяет генерировать сертификаты чисел. Таким образом, проверка очень большого числа на простоту может быть выполнена обычным пользователем за реальное время.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
