ВВЕДЕНИЕ 3
1. Постановка задачи 5
2. Классификация алгоритмов тестирования чисел на простоту 6
2.1. Вероятностные алгоритмы с односторонней ошибкой 6
2.2. Алгоритмы с вероятностным временем выполнения 8
2.3. Детерминированные алгоритмы 9
3. Теория эллиптических кривых 10
3.1. Число точек эллиптической кривой 10
3.2. Метод Шуфа для вычисления порядка эллиптической кривой 12
3.3. Доказательство простоты при помощи эллиптических кривых 15
4. Алгоритм Гольдвассер-Килиана 16
5. Практическая реализация алгоритма 19
5.1. Статистика при различной длине входных значений 19
5.2. Особенность алгоритма и возможные улучшения 21
ЗАКЛЮЧЕНИЕ 24
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 25
Приложения должны быть в работе, но в данный момент отсутствуют
Бурное развитие информационных и коммуникационных технологий повышает актуальность проблемы информационной безопасности. В связи с этим требуется разработать ряд новых методов и средств, направленных на обеспечение информационной безопасности. Следовательно, требуется комплексный подход для надежного обеспечения информационной безопасности. Другими словами, возникает необходимость эффективного использования правовых, организационных и инженерно-технических обеспечений защиты информации.
В частности, криптографические методы играют важную роль в защите информации. Сегодня широко используется криптографические системы защиты информации. Все эти криптографические системы работают на основе криптографического алгоритма. В настоящее время в качестве основы для многих криптографических стандартов берутся алгоритмы RSA и Эль-Гамаль. Эти алгоритмы основаны на задаче факторизации и дискретном логарифмировании в конечном поле. Для шифрования данных и создания электронной цифровой подписи в обоих алгоритмах используются 1024-битные и большие простые числа. Таким образом, генерирование и работа с большими простыми числами стали одним из главных вопросов в криптографии. В общем, причиной широкого использования простых чисел в криптографии является трудность обнаружения этих чисел.
Целью работы является реализация алгоритма Гольдвассера-Килиана для проверки чисел на простоту в среде Visual Studb 2015 на языке C++ и проведение сравнительного анализа на разных входных данных.
План работы:
1. Изучение литературы. Сбор информации о проблеме тестирования чисел на простоту. Изучение алгоритмов факторизации и теории эллиптических кривых над конечными полями.
2. Реализация вспомогательного класса - многочлен в конечном поле на языке C++.
3. Реализация класса - арифметические операции на эллиптических кривых для точек, представленных в виде многочленов в конечном поле.
4. Реализация алгоритма факторизации - метод квадратичного решета.
5. Реализация алгоритма Шуфа для нахождения порядка эллиптической кривой.
6. Реализация алгоритма Гольдвассера-Килиана.
7. Проведение исследований характеристик выполнения алгоритма (скорость работы в различных ситуациях, сложность реализации).
Объектом исследования является алгоритм тестирования чисел на простоту Гольдвассера-Килиана.
Предметом исследования является реализация, обоснование и сравнительный анализ этого алгоритма.
На основе проведенных качественных и численных оценок можем утверждать, что реализация алгоритма Гольдвассер-Килиана с немодифицированным алгоритмом Шуфа для подсчета количества точек на эллиптической кривой является не таким эффективным, так как в этом случае мы получаем просадки в скорости работы уже для чисел размерности больше 100 бит. Но можно на порядок продвинуть эту границу, реализовав модификацию алгоритма Шуфа - Шуфа-Элкиса-Аткина.
В общем итоге мы достигли поставленных целей реализации, попутно объяснив принципы, на которых построен алгоритм Гольдвассер-Килиана. Также пришли к значимым выводам, что данный алгоритм при реализации дополнительных модификаций является довольно эффективным тестом. При этом заметим, что, реализовав модификацию алгоритма Шуфа, его можно использовать для генерации параметров эллиптических кривых.
