ВВЕДЕНИЕ 3
ГЛАВА 1 6
1.1. Асимметричные системы шифрования 6
1.1.1. Алгоритм Диффи-Хеллмана 9
1.1.2. Алгоритм RSA 11
1.1.3. Алгоритм Эль-Гамаля 13
1.2. Вероятностные и детерминированные алгоритмы 14
1.3. Псевдопростые и строго псевдопростые числа 15
ГЛАВА 2. АЛГОРИТМЫ ПОИСКА ПСЕВДОПРОСТЫХ ЧИСЕЛ 19
2.1. Алгоритм Померанса
2.2. Тест Бейли — Померанца — Селфриджа — Уогстаффа
2.3. Алгоритм Джаешке
2.4. Алгоритм нахождения ир
2.5. Особенности реализации
ГЛАВА 3. АНАЛИЗ ИССЛЕДОВАНИЯ РЕЗУЛЬТАТОВ //34
3.1. Анализ результатов поиска
3.2. Заключение 38
Литература 39
Купить

Сейчас сложно представить мир без Интернета. С каждым днём он завоёвывает новые области. Сегодня уже невозможно найти человека, не сталкивавшегося в той или иной степени с компьютерными технологиями, а, следовательно, и с цифровыми данными. С одной стороны, Интернет - мощнейший инструмент, помогающий экономить время. С другой, это и возможности выполнения с информацией каких-либо действий для разного рода злоумышленников. Естественно, все это приводит нас к тому, что задача защиты информации как никогда более актуальна. Ведь никто не хочет раскрывать свою переписку, важные данные третьим лицам.
Достичь защиты информации помогает, пожалуй, самый часто применяемый инструмент информационной безопасности - шифрование. Сейчас, например, популярен алгоритм шифрования RSA-1024. В данной системе открытого ключа нужно найти большое "случайное" простое число. Проблема определения по заданному натуральному числу п, является ли оно простым или составным является одной из наиболее важных проблем в криптографии и теории чисел. Процедура, решающая такую задачу, называется тестом простоты [10]. Тест на простоту представляет собой критерий того, что число п не является простым. Если число п "проходит" этот тест, то оно, возможно, простое число. Если оно "проходит" целый набор тестов на простоту, то весьма вероятно, что оно действительно является простым. С другой стороны, если п не проходит хотя бы одного теста на простоту, то оно совершенно определенно является составным. Однако при этом остается нерешенной трудная задача нахождения простых делителей числа п (задача факторизации). В общем случае для разложения на множители большого числа, о котором известно, что оно составное (поскольку оно не прошло теста на простоту), требуется порядка величины. Надежность криптосистемы RSA основывается на том предположении, что значительно легче найти два чрезвычайно больших простых числа п и q, чем, зная n=p*q, но не p или q, найти делители числа п.
Известно множество различных тестов простоты, среди которых наиболее распространенным является тест простоты Миллера- Рабина[1,5,12]. Проблема изучения строго псевдопростых чисел имеет также важные приложения в теории чисел [11].
Алгоритм Миллера-Рабина является вероятностным полиномиальным тестом простоты. Определяя точно результат в случае составного числа на входе, он не позволяет строго доказать простоту числа. Это обосновано существованием псевдопростых чисел - т.е. таких составных чисел, которые обладают некоторыми свойствами простого числа. Получив подобное число на вход, алгоритм Миллера-Рабина может “ошибиться”, вернув результат о том, что предложенное число является простым. Избавиться от такого поведения можно увеличив число проверок в тесте, уменьшая тем самым вероятность ошибки.
Таким образом, проблема изучения строго псевдопростых чисел, их распределения и свойств имеет серьёзный прикладной аспект, а не только теоретический интерес. Результаты подобных исследований способствуют развитию тестов простоты, например, различного рода рекомендаций по выбору свидетелей простоты для теста Миллера-Рабина.
С каждым годом появляется все больше публикаций на данную тематику. В первую очередь, хочется отметить статью [13], в которой авторы дают оценку границы натуральных чисел, тест простоты для которых выполняется безошибочно при выбранных свидетелях простоты как множество из первых 9, 10 и 11 простых чисел. Однако, авторы [11]
показали, что требование простоты для выбираемых свидетелей простоты не является существенным, и не влияет на корректность работы теста.
Стоит отметить работу [8], в которой предлагается несколько теоретических соображений, позволяющих отбросить некоторую часть рассматриваемых кандидатов на псевдопростое число, ускорив таким образом время работы алгоритма.
Целью данной работы является оценка количества таких псевдопростых чисел на интервале от 1 до 1016 и исследование их распределения. Также мы попробуем выявить некоторые свойства, позволяющие выявлять псевдопростые числа.
В первой главе будут освещены теоретические вопросы этой тематики. Будет подробно рассмотрены алгоритмы ассиметричного шифрования, в которых используются большие простые числа, алгоритмы поиска простых чисел и взаимосвязь с псевдопростыми числами. Даются определения псевдопростому и сильно псевдопростому числу, перечисляются их свойства.
Во второй главе рассматриваются прикладные аспекты работы. Приводится описание программной платформы и используемых средств. Затем рассматриваются шаги по разработке и реализации алгоритмов нахождения и генерации псевдопростых чисел.
В последней главе проводится анализ полученных результатов, делаются выводы, а также осуществляется постановка некоторых важных вопросов для дальнейшего исследования.
Очевидно, что полученные результаты будут непосредственным образом влиять на оценку эффективности работы теста Миллера-Рабина, помогут выработать рекомендации по выбору свидетелей простоты и заложить предпосылки для его возможного улучшения алгоритма в целом.

Купить