Разработка алгоритма и программы генерации Больших простых чисел. Повышение эффективности работы криптосистем с открытыми

  • 14 нояб. 2010 г.
  • 2237 Слова
Пояснительная записка к курсовому проекту по дисциплине «Криптографические методы защиты информации».

Санкт-Петербург
2009

Задание

Разработка алгоритма и программы генерации больших простых чисел. Повышение эффективности работы криптосистем с открытыми ключами

Исходные данные

Для создания программногокомплекса была использована интегрированная среда разработки программного обеспечения MS Visual Studio 2005.
Для написания программы, реализующий алгоритм генерации больших простых чисел, был использован язык объектно-ориентированный язык программирования C#.
Разрядность генерируемого большого простого числа составляет 512 бит.
Для проверки числа на простоту среди многихсуществующих тестов, таких, как:
• Перебор делителей
• Теорема Вильсона
• Тест Ферма
• Тест Миллера-Рабина
• Тест Соловея-Штрассена
• Тест Люка-Лемера
• Тест Пепина
• Тест Агравала-Каяла-Саксены

был выбран тест Ферма, основанный на следствие из малой теоремы Ферма.

Аннотация

В курсовом проекте осуществляется разработкаалгоритма генерации больших простых чисел, основанного на следствие из малой теоремы Ферма.
Реализация данного алгоритма, по средствам написания программы генерации больших простых чисел на языке C#.
Целью данного курсового проекта является – изучения существующих алгоритмов генерации больших простых чисел и принципов их построения; также реализация разработанного алгоритма в видекомпьютерной программы.

Содержание

Задание 2
Исходные данные 3
Аннотация 4
Содержание 5
Введение 6
1. Теоретические сведения 7
1.1. Способы генерации больших простых чисел 7
1.2. Тесты чисел на простоту 8
1.2.1 Перебор делителей 8
1.2.2 Теорема Вильсона 8
1.2.3. Тест Миллера — Рабина 8
1.2.4. Тест Соловея — Штрассена 9
1.2.5. Тест Люка́ — Ле́мера 9
1.2.6.Тест Пепина 10
1.2.7. Тест Ферма 10
2. Разработка алгоритма генерации больших простых чисел 11
2.1. Схема алгоритма 11
2.2. Описание алгоритма генерации больших простых чисел 12
3. Проект программного комплекса 13
3.1. Состав и структура 13
3.2. Требования к системе 13
3.3. Интерфейс программы 13
Заключение 16
Список использованных источников 17

Введение

Тематикагенерации больших простых чисел является ключевой для изучения криптографических методов защиты информации. Почти каждый криптографический алгоритм с открытым ключом требует генерации простого числа размером не менее 512 бит. В процессе использования таких алгоритмов приходится многократно создавать такие числа, причем некоторые алгоритмы требуют простые числа специального вида. Например, алгоритмцифровой подписи (ЦП) стандарта ГОСТ Р 34.11-94 требует генерации двух простых чисел p и q таких, что q является делителем числа (p-1).
В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов k, на алгоритм генерации которого накладываются определенные ограничения. Получение случайных простых чисел является неотъемлемой частьюпроцедур выработки ключей во многих криптографических алгоритмах, включая RSA и ElGamal.
Ввиду того, что тестирование простоты больших чисел требует существенных временных затрат, требование простоты получаемого числа часто ослабляют до сильной псевдо простоты по нескольким различным случайным основаниям. Существующие алгоритмы тестирования сильной псевдо простоты на порядки быстрее лучшихизвестных алгоритмов тестирования простоты. В то же время, числа, успешно прошедшие тестирования сильной псевдо простоты по нескольким случайным основаниям, с большой вероятностью являются простыми, причем эта вероятность растет с ростом количества оснований, по которым проводится тестирование. В данном курсовом проекте для проверки числа на простоту используется...
tracking img