Автор: Пользователь скрыл имя, 20 Мая 2013 в 01:01, курсовая работа
Криптоанализ традиционно используется для решения таких задач, как восстановление исходной информации по ее криптограмме, вычисление закрытого ключа по известному открытому, формирование электронной цифровой подписи сообщения без знания закрытого ключа, а также создание фальшивого электронного документа, соответствующего известной подписи.
В данной работе рассмотрим алгоритмы шифрования и дешифрования системы RSA и проведём её криптоанализ.
Введение 3
1 Техническое задание 5
2 Алгоритм шифрования RSA 6
2.1 Описание RSA 6
2.2 Нахождение простых чисел 6
2.3 Нахождение взаимно простых чисел 7
2.4 Решение уравнения Диофанта 8
2.5 Большие числа и работа с ними 8
2.5.1 Хранение больших чисел, алгебраическое сложение, умножение 9
2.5.2 Алгоритм быстрого возведения в степень 9
2.5.3 BigInteger 10
3 Средства взлома 11
3.1 Алгоритм взлома основанный на факторинге 12
4 Руководство пользователя 13
Выводы 16
Список использованной литературы 17
Приложение А (листинг основных модулей) 18
Приложение Б (диск с программой и документацией) 31
УДК 51
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Дешифрування системи RSA
Пояснювальна записка до курсової роботи (проекту)
з дисципліни «Дискретна математика»
назва дисципліни
Виконав студент гр._________________
______________ (№ групи) (П.І.Б.)
(підпис, дата)
Керівник ___________________________
(науковий ступінь, вчене
______________________________
(підпис, дата)
Нормоконтролер _______________
(науковий ступінь, вчене
______________________________
(підпис, дата)
2007
Содержание
Содержание 2
Введение 3
1 Техническое задание 5
2 Алгоритм шифрования RSA 6
2.1 Описание RSA 6
2.2 Нахождение простых чисел 6
2.3 Нахождение взаимно простых чисел 7
2.4 Решение уравнения Диофанта 8
2.5 Большие числа и работа с ними 8
2.5.1 Хранение больших чисел, алгебраическое сложение, умножение 9
2.5.2 Алгоритм быстрого возведения в степень 9
2.5.3 BigInteger 10
3 Средства взлома 11
3.1 Алгоритм взлома основанный на факторинге 12
4 Руководство пользователя 13
Выводы 16
Список использованной литературы 17
Приложение А (листинг основных модулей) 18
Приложение Б (диск с программой и документацией) 31
Введение
Быстрое развитие процессов
автоматизации, проникновение компьютеров
во все сферы жизни повлекли за
собой, помимо несомненных преимуществ,
ряд специфических проблем. Одной
из таких проблем стала
В настоящее время проблемами шифрования и дешифрования занимается наука криптология, состоящая из двух ветвей: криптографии и криптоанализа. Соответственно, криптография – это наука о способах преобразования (шифрования) информации с целью ее защиты от незаконных пользователей, а криптоанализ – наука о методах и способах вскрытия шифров (и ее практическое применение).
Фактически, криптоанализ представляет собой набор математических методов вскрытия алгоритмов шифрования. Здесь явно прослеживается то же эволюционное противодействие, что и в случае брони и снаряда: появляются все более стойкие (без потери в других важных характеристиках – например, в быстродействии) алгоритмы шифрования, в ответ на которые изобретаются все более совершенные методы их взлома.
Современная криптография исходит
из принципа, что стойкость
В данной работе рассмотрим алгоритмы шифрования и дешифрования системы RSA и проведём её криптоанализ.
Реализовать алгоритм восстановления секретной части ключа и дешифровать текст. Исходными данными является открытая часть ключа (число не более ) и текст, закодированный с помощью алгоритма RSA.
RSA относится к так называемым
асимметричным алгоритмам, у которых
ключ шифрования не совпадает
с ключом дешифровки. Один из
ключей доступен всем (так делается
специально) и называется открытым
ключом, другой хранится только
у его хозяина. С помощью
одного ключа можно
Алгоритм RSA состоит из следующих пунктов:
Числа и являются ключами. Шифруемые данные необходимо разбить на блоки – числа от до . Шифрование и дешифровка данных производятся следующим образом:
Следует также отметить, что ключи и равноправны, т. е. сообщение можно шифровать как ключом , так и ключом , при этом расшифровка должна быть произведена с помощью другого ключа.
В первом пункте алгоритма RSA сказано, что необходимо выбрать два простых числа и . Как это сделать, если числа имеют большую разрядность? Простой способ – деление предполагаемого простого числа на все числа меньшие его не работоспособен уже с 32-битными числами (требуется очень много времени на выполнение).
Для нахождения всех простых чисел не больше заданного числа , рассмотрим метод Эратосфена, который реализуется следующим образом:
На практике, алгоритм можно немного улучшить следующим образом. На шаге 3, числа можно вычеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем .
Так же для выработки простых чисел используют вероятностные методы, один из которых будет здесь представлен. Вероятностные методы не дают полной гарантии, что найденное число простое, но при достаточно небольшом количестве операций позволяют получить очень высокую вероятность этого.
Алгоритм поиска простых чисел:
Если для какого-либо числа проверено чисел , то математически доказанная вероятность того, что число является составным, будет приблизительно равна . Следовательно, для числа , состоящего из бит, целесообразно проверить различных значений . Если во время этого не обнаружится, что – число составное, то вероятно число является простым.
Число не может превышать количества бит в числе. Числа и находятся при помощи двоичного сдвига числа , пока младший разряд не станет . В результате – количество сдвигов, – число после сдвига.
На шаге 4 алгоритма RSA необходимо найти число взаимно простое с . Число должно быть меньше , т. о. разрядность числа равна сумме бит в числах и . Для нахождения взаимно простых чисел используется алгоритм Евклида, который находит наибольший общий делитель двух чисел. Если найденный делитель больше единицы, то необходимо выбрать другое число и повторить проверку.
Алгоритм Евклида:
При вычислении наибольшего общего делителя с помощью алгоритма Евклида будет выполнено не более операций деления с остатком, где есть количество цифр в десятичной записи меньшего из чисел и . На практике алгоритм работает очень быстро.
В 5-м пункте алгоритма RSA предполагается нахождение такого числа , чтобы . Для этого нужно использовать модифицированный алгоритм Евклида, который работает только в том случае, если числа и взаимно просты. Вычисление числа сводится к решению уравнения в натуральных числах. Число не существенно.
Алгоритм решения уравнения :
В данном алгоритме все вычисления можно производить по модулю большего из чисел и . Отрицательное число заменяется положительным, полученным путем вычитания числа из числа, взятого в качестве модуля. Например, если из чисел и большим является число , то все вычисления можно производить по модулю числа , при этом будет представлено как . Скорость работы алгоритма и количество производимых им операций примерно равно соответствующим параметрам алгоритма Евклида, описанного выше.
На данный момент времени рекомендуется в качестве чисел и брать числа, длиной не менее бит. Чтобы подобрать ключ такой длины потребуется $1000000 и примерно год времени. Ключ в бит является достаточно надежным для обычных целей шифрования. Для повышенной безопасности рекомендуется брать ключи размером бит. Т. о. числа и должны иметь разрядность вдвое ниже чисел , , и ( и рекомендуется брать примерно одного порядка, но не слишком близко друг к другу).
Действия со столь большими числами требуют специальных алгоритмов и структур данных. Основные вопросы этой области: как хранить эти числа, как их складывать, умножать, делить, брать остаток от деления, возводить в большую степень по модулю целого числа.
Числа лучше всего хранить в массиве 2-х байтовых переменных. Об отрицательных числах можно забыть: использоваться не будут, т. к. их всегда можно заменить на обратные. Переменные в 2 байта удобны при умножении при работе с языками высокого уровня: результат будет 4-х байтовым и потом его можно разделить на две части для дальнейшей обработки.
Умножение производится с помощью обычного алгоритма умножения "в столбик". Есть также и более эффективные алгоритмы умножения, но у них существует понятие "обменной точки" – необходимой длины числа для того, чтобы алгоритм начал выигрывать по скорости в сравнении с простым алгоритмом. Обычный алгоритм работает вполне нормально. Для ускорения работы лучше использовать более быстрый алгоритм, но и более сложный в реализации.
Сложение и вычитание также производятся "в столбик".
В алгоритме RSA много возведений в степень по модулю натурального числа. Остаток от деления берется после каждого умножения. Таким образом, при перемножении двух чисел, состоящих из бит, потребуется -битное число, которое затем делится на модуль и получается остаток, опять же состоящий из бит (если модульное число состоит из бит).
Сложность этого алгоритма может быть оценена как , где – модуль, по которому производится умножение. Запись означает, что для реализации алгоритма потребуется порядка операций. Например, если число имеет разрядность бит (при этом длина не менее бит), то умножение по модулю необходимо будет провести порядка раз, что относительно немного.
Алгоритм вычисления :