📄Работа №45591
Тема: ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ ТЕСТОВ ПРОСТОТЫ С ИСПОЛЬЗОВАНИЕМ ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Тип работы
Дипломные работы, ВКР
Предмет
информационная безопасность
Объем:
81 листов
Год:
2018
Просмотров:
710
4370
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 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
ПРИЛОЖЕНИЕ
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. Чем оно больше, тем сложнее взломать систему, которая использует его в качестве шифрования.
Существующие алгоритмы нахождения простого числа используют либо вероятностные тесты, либо детерминированные. Первые работают гораздо быстрее, чем вторые, но могут ошибаться, выдавая составное число простым. Последние совершенно точно срабатывают верно. К ним относится полный перебор всевозможных делителей числа.
Алгоритмы, основанные на эллиптических кривых, точно определяют простое число и конкурируют с вероятностными тестами по скорости выполнения. Они представляют собой математические вычисления, производящиеся над уравнениями третьего порядка, которые и называются эллиптическими. Построение кривой производится в поле предполагаемого простого числа. Происходит подсчет точек на заданной кривой и по некоторому списку критериев делают определенные выводы. Примерами такого теста являются тесты на простоту Гольдвассера-Килиана и Аткина- Морейна(ЕСРР), реализация и анализ последнего как раз и описывает данная работа.
Практически на всех уровнях сетевой модели 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, тогда начинается сложная математика, которая
включается в себя операции над многочленами такие, например, как деление полинома большой степени на полином в малой степени и пр.
Проверка сертификата, сгенерированного при помощи метода доказательства простоты, сразу проверяет условия теоремы Гольдвассера- Килиана, таким образом, затрачивает основное время выполнения на несложные операции над кривыми. В таком случае естественно, что проверка числа занимает очень малое время.
Метод Аткина-Морейна хорошо работает на практике и однозначно определяет простоту числа - казалось, что эти два пункта не могут употребляться как характеристики одного. Существует много вариантов реализации теста и скорость его работы может совершенствоваться в будущем благодаря применению новых быстрых алгоритмов факторизации, операций над многочленами и прочее. Выполнение программы на компьютерах больших мощностей позволяет генерировать сертификаты чисел. Таким образом, проверка очень большого числа на простоту может быть выполнена обычным пользователем за реальное время.
Самой емкой частью алгоритма является этап факторизации порядка. В реализации сначала поиск тривиальных делителей, а после, если факторизовать все-таки не получилось, начинает работать po-метод Полларда. Для повышения эффективности на этом этапе было введено распараллеливание, так как алгоритм может генерировать до 6 разных порядков, и в ситуации, когда в их последовательном разложении удастся разложить только последний элемент, время работы заметно увеличивается.
Факторизация может производиться любым известным способом, главный критерий - эффективность метода, но это уже другая область исследования, вопросы которой решаются отдельно. Следующим емким шагом алгоритма является поиск параметров кривой. Дело в том, что в случае, когда дискриминант Э -3, -4, тогда начинается сложная математика, которая
включается в себя операции над многочленами такие, например, как деление полинома большой степени на полином в малой степени и пр.
Проверка сертификата, сгенерированного при помощи метода доказательства простоты, сразу проверяет условия теоремы Гольдвассера- Килиана, таким образом, затрачивает основное время выполнения на несложные операции над кривыми. В таком случае естественно, что проверка числа занимает очень малое время.
Метод Аткина-Морейна хорошо работает на практике и однозначно определяет простоту числа - казалось, что эти два пункта не могут употребляться как характеристики одного. Существует много вариантов реализации теста и скорость его работы может совершенствоваться в будущем благодаря применению новых быстрых алгоритмов факторизации, операций над многочленами и прочее. Выполнение программы на компьютерах больших мощностей позволяет генерировать сертификаты чисел. Таким образом, проверка очень большого числа на простоту может быть выполнена обычным пользователем за реальное время.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.