ВВЕДЕНИЕ 3
Глава 1. Теоретические основы разработки тестов на простоту 5
1.1 Основные понятия и классификация тестов на простоту 5
1.2 Теоретические основы разработки теста на простоту Миллера-
Рабина 6
1.3 Теоретические основы разработки тестов на простоту Соловея-
Штрассена 9
1.4 Теоретические основы разработки теста на простоту
Гольдвассера-Киллиана 10
Глава 2. Практическая реализация тестов на простоту 14
2.1 Выбор языка программирования 14
2.2 Практическая реализация теста на простоту Гольдвассера-
Киллиана 15
2.3 Практическая реализация теста на простоту Миллера-Рабина.... 18
2.4 Практическая реализация теста на простоту Соловея-Штрассена
23
Глава 3. Анализ эффективности тестов на простоту 28
3.1 Методика анализа эффективности тестов на простоту 28
3.2 Анализ эффективности теста на простоту Миллера-Рабина 31
3.3 Анализ эффективности теста на простоту Соловея-Штрассена .. 38
3.4 Анализ эффективности теста на простоту Гольдвассера-Киллиана 46
СПИСОК ЛИТЕРАТУРЫ 56
ПРИЛОЖЕНИЕ 60
В современном мире большинство государственных и коммерческих услуг можно получить в электронном виде. Для доступа к данным услугам в большинстве случаев используется электронная цифровая подпись, которая полностью идентифицирует человека в мире электронного документооборота.
Очевидно, что качество защиты электронной цифровой подписи, а также все аспекты, связанные с её выпуском и использованием, играют очень важную роль в обеспечении информационной безопасности современного человека.
С момента изобретения метода шифрования с открытым ключом, используемого при шифровании информации, а также в алгоритмах электронной цифровой подписи, в области информационной безопасности широко применяются простые числа. На сегодняшний день по стандартам размер простых чисел, которые используются при формировании цифровой подписи с помощью алгоритмов, использующих эллиптические кривые, в соответствии с ГОСТ Р 34.10-2012 составляет не менее 256 бит. Для чисел такого размера крайне важным является вопрос определения простоты, так как такому простому методу, как метод перебора, необходимо чрезвычайно много вычислительных ресурсов, время его работы слишком велико.
Простые числа используются в алгоритме шифрования RSA. В ходе работы алгоритма необходимо сформировать модуль, найти функцию Эйлера, сформировать открытый и закрытый ключ. Криптостойкость этого алгоритма основана на вычислительной сложности задачи факторизации, поэтому для большей криптостойкости необходимо наличие двух больших простых чисел.
Существуют детерминированные и вероятностные тесты. В рамках этой работы мы рассматриваем вероятностные тесты Миллера-Рабина и Соловея-Штрассена и детерминированный тест Г ольдвассера-Килиана. Есть много исследований тестов на простоту, данная тема пользуется большой популярностью.
Таким образом, использование эффективного теста простоты является одним из главных способов формирования ключей большого размера в алгоритме RSA и ему подобных, что влечет увеличение криптостойкости используемой схемы шифрования. Этим обусловлена актуальность темы.
Целью данной работы является реализация и исследование тестов на простоту: Гольдвассера-Киллиана, Миллера-Рабина, Соловея-Штрассена.
Для достижения данной цели необходимо решить следующие задачи:
1) провести обзор литературы по существующим алгоритмам и классификации тестов на простоту;
2) рассмотреть теоретические основы работы тестов на простоту, исследование которых является целью данной работы;
3) выбрать язык программирования для практический реализации данных тестов;
4) реализовать рассмотренные тесты на выбранном языке программирования;
5) разработать методику анализа эффективности работы тестов на простоту;
6) провести анализ эффективности работы реализованных тестов на простоту согласно разработанной методике;
7) сделать выводы о возможности применения реализованных тестов к задачам определения простоты чисел.
Проведенные исследования имеют теоретическую и практическую значимость.
Глава 1. Теоретические основы разработки тестов на простоту
1.1 Основные понятия и классификация тестов на простоту
По определению число P является простым в том случае, если оно не имеет нетривиальных делителей, то есть, делится только на само себя и на единицу [1].
Задача определения, является ли число N - простым числом, одна из важнейших в области криптографии и информационной безопасности, так как многие криптографические алгоритмы используют простые числа в ходе работы. Алгоритмы, целью которых является решение данной задачи, называются тестами на простоту.
Большинство алгоритмов, предназначенных для тестирования чисел на простоту, можно разделить на две больших группы, у каждой из которых есть свои достоинства и недостатки [2-3]:
- вероятностные алгоритмы - алгоритмы, которые определяют является число простым или нет с некоторой вероятностью, которая зависит от числа итераций;
- детерминированные алгоритмы - такие алгоритмы, для которых при прохождении числом N теста простота числа определяется достоверно.
Исходя из приведенной выше классификации, может показаться, что детерминированные алгоритмы являются наилучшими. Тем не менее, их использование в практических приложениях сильно ограничено [4].
В связи с тем, что криптостойкость многих алгоритмов шифрования увеличивается с размером простого числа, то достаточно быстрая проверка больших чисел на простоту является одной из ключевых проблем в данной области. Вероятностные тесты на простоту при использовании в данных приложениях показывают по сравнению с детерминированными тестами большую простоту выражения и эффективность использования.
В качестве примеров вероятностных алгоритмов будут рассмотрены следующие три алгоритма:
- тест Миллера - Рабина;
- тест Соловея - Штрассена;
- тест Гольдвассера - Килиана.
В работе рассмотрены основы работы тестов на простоту Миллера- Рабина, Соловея-Штрассена и Г ольдвассера-Киллиана, а также разработаны их реализации на языке программирования С++.
Для оценки эффективности работы разработанного программного обеспечения создана методика анализа эффективности работы программного обеспечения, на основе которой проведен анализ эффективности работы программного обеспечения, реализующего рассматриваемые тесты на простоту. В результате анализа сделаны следующие выводы:
- наибольшая точность достигается при использовании алгоритма Гольдвассера-Киллиана, так как с помощью данного теста на простоту простые и составные числа определяются без ошибок;
- наибольшая скорость достигается при применении тестов на простоту Миллера-Рабина и Соловея-Штрассена, при этом тест Миллера-Рабина уже при малых значения параметра к практически не допускает ошибок, а тест Соловея-Штрассена безошибочно работает только при больших значениях данного параметра.
Таким образом, в процессе выполнения работы решены следующие задачи:
- проведен обзор литературы по существующим алгоритмам и классификации тестов на простоту;
- рассмотрены теоретические основы работы наиболее часто встречающихся алгоритмов работы тестов на простоту;
- выбран язык программирования С++ для практический реализации данных тестов;
- рассмотренные тесты реализованы на выбранном языке программирования;
- разработана методика анализа эффективности работы тестов на простоту;
- проведен анализ эффективности работы реализованных тестов на простоту согласно разработанной методике;
- сделаны выводы о возможности применения реализованных тестов к задачам определения простоты чисел.
Таким образом, в результате выполнения работы достигнута её основная цель - реализованы и исследованы тесты на простоту: Гольдвассера-Киллиана, Миллера-Рабина, Соловея-Штрассена.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
