Криптографические методы защиты информации

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра безопасности информационных систем (БИС)

Отчёт по практической работе №4

По дисциплине

“Криптографические методы защиты информации”

Студент гр. 744 П. И. Култаев

Руководитель К.т.н, доцент

каф. БИС О. О. Евсютин

Томск 2016

Цель

Целью данной работы является реализация программы, выполняющей шифрование входной строки алгоритмом RSA, а также проведение криптоанализа.

Ход работы

Краткая теория

Криптосистемы с открытым ключом, также называемые асимметричными криптосистемами, используют два разных ключа: открытый ключ зашифрования и закрытый ключ расшифрования. Открытый ключ в общем случае доступен всем желающим, а закрытый ключ известен только законному владельцу. Оба ключа связаны между собой некоторой зависимостью. При этом данная зависимость такова, что, зная один ключ, вычислить другой практически невозможно.

RSA - Криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

Шифрование происходит в несколько этапов:

1. Генерация ключей

Человек А придумывает два больших простых числа q и p, при этом p должно быть не равно q, а также |q-p| тоже должен быть большим числом. Человек А держит p и q в секрете, но вычисляет так называемый модуль алгоритма n = p*q, который станет частью открытого ключа. Далее вычисляется функция Эйлера по формуле ц=(q-1)*(p-1). После, человек А выбирает целое число e, взаимно простое со значением функции ц(n). Это число называется экспонентой зашифрования. Как правило, e берут равным 3, 17 или 65537. Далее применяется расширенный алгоритм Евклида для пары чисел e и ц(n), в результате чего вычисляется число d удовлетворяющее соотношению e·d ? 1 (mod ц(n)), называемое экспонентой расшифрования. Теперь у человека А есть две пары ключей (открытый и закрытый). Открытый ключ (e, n) человек А отправляет всем желающим для того, чтобы для него могли зашифровать сообщение, а закрытый ключ (d, n) держит у себя для расшифрования.

2. Зашифрование

Человек В получил от человека А открытый ключ (e, n) и хочет зашифровать для него сообщение. Человек В представляет сообщение в виде числа m, меньшего модуля алгоритма. Если необходимое сообщение больше модуля алгоритма, то сообщение разбивается на блоки. Само зашифрование производится по следующей формуле:

Где C - Зашифрованное сообщение

m - Исходное сообщение

e - Экспонента зашифрования

n - Модуль алгоритма

Зашифрованное сообщение отправляется обратно человеку А.

3. Расшифрование

Человек А получил шифртекст от человека В и расшифровывает его по следующей формуле:

Где d - Экспонента расшифрования

Пример шифрования с помощью алгоритма RSA

Для шифрования был использован латинский алфавит, состоящий из 26 букв. Попробуем зашифровать и расшифровать последовательность «KPI», используя при этом алгоритм RSA. Каждый символ заменим соответствующим элементом кольца классов вычетов по модулю 26. Получим последовательность 10 15 8. Представим полученные числа в двоичном виде, при этом, так как латинский алфавит содержит 26 знаков, каждый элемент алфавита можно закодировать 5-ю битами. Таким образом, мы получим битовую строку вида 010100111101000. Дальше необходимо сгенерировать ключи: в качестве p и q возьмем 13 и 17 соответственно. е возьмем равной 5. Вычислим d. (d*5)%192=1. d получается равным 77. Теперь вычислим длину блока: n = 221 размер блока равен 7 бит (). Делим наше сообщение на семизначные блоки. Получилось три блока: 1101000 1010011 0. Теперь каждый блок переведем в десятичную систему и применим алгоритм шифрования:

Теперь применим алгоритм шифрования к каждому блоку:

= 117

= 70

= 0

После этого, блоки зашифрованного текста передаем обратно владельцу ключей, и он производит расшифрование:

= 104

= 83

= 0

Применив расшифрование, владелец текста переведет блоки открытого текста в бите и запишет это в виде строки 010100111101111, которую разобьет на буквы по 5 бит: 01010 01111 01111, переведя которые в десятичную систему получит номера букв и исходное сообщение «KPI»

Реализация шифра

Был реализован алгоритм шифрования на языке программирования C#. Программа представляет собой форму с кнопками и полями для заполнения:

алгоритм шифрование программа программирование

Рисунок 2.3.1 Главная форма программы

Форма содержит в себе поля для ввода ключей, кнопку проверки ключей, кнопку генерации экспоненты d, поле для ввода открытого текста, поля для вывода шифртекста и расшифрованного текста, а также кнопки «Зашифровать» и «Расшифровать».

Рисунок 2.3.2 Пример работы программы

Описание алгоритма работы программы

На вход программе подаются p, q, e. После этого программа проверит проверку корректности ключей. Если ключи корректны, программа генерирует экспоненту расшифрования d, после чего открытый текст разбивает на буквы, представляя каждую букву как 5 бит. Далее идет вычисление длины блока, и вся последовательность бит делится на блоки. После этого происходит процесс зашифрования. При нажатии на кнопки «Расшифровать» происходит функция расшифрования, после чего обратные переводы в биты, потом в десятичные числа и в буквы.

Криптоанализ

Разумеется, что при большой длине n атака грубой силы невозможна. В 2009 году группа ученых дешифровывала текст, зашифрованный алгоритмом RSA с ключом 768 бит. Только на поиск пары полиномов ушло полгода. Можно с уверенностью сказать, что при длине ключа 1024, а тем более 2048 бит, атака грубой силы невозможна за сколько угодно приемлимое время.

Зная разложение модуля n на произведение двух простых чисел, противник может легко найти секретную экспоненту d и тем самым взломать RSA. Однако на сегодняшний день самый быстрый алгоритм факторизации -- решето обобщённого числового поля не позволяет разложить большое целое за приемлемое время.

Основные виды атак связаны с неправильным использованием алгоритмов RSA. Рассмотрим пример: Злоумышленник знает шифртекст, который выглядит следующим образом: 11 9 7 42 9 7, а также знает открытый ключ (7, 55). Зная эти данные, злоумышленник с легкостью определит длину блока (5 бит), а также p и q, так как 55 в произведении могут давать только два простых числа: 5 и 11. Таким образом, злоумышленник в легкостью определяет d, (d*7)%40=1которое в нашем случае равно 23. Теперь у злоумышленника есть все для того, чтобы расшифровать текст. Каждый символ шифртекста расшифровывается:

= 11

= 14

= 13

= 3

= 14

= 13

и получается последовательность: 11, 14, 13, 3, 14, 13. Переведя эти номера в буквы, он получит «London», что и было исходным сообщением. Конечно, такой способ не является эффективным для ключей размера хотя бы 1024 бит, так как на факторизацию числа уйдет слишком много времени.

Рассмотрим следующий тип атаки, который относится к атакам исходного текста (атака короткого сообщения). Заключается в следующем: если исходный текст имеет малый размер, и Ева знает множество возможных исходных текстов, то ей известна еще одна информация и дополнительный факт, что зашифрованный текст -- перестановка исходного текста. Ева может зашифровать все возможные сообщения, пока результат не будет совпадать с перехваченным зашифрованным текстом. Например, если известно, что Алиса посылает число с четырьмя цифрами Бобу, Ева может легко испытать числа исходного текста от 0000 до 9999 и найти исходный текст. Но и этот метод легко сводится на нет добавлением «лишних» бит в начало и конец сообщения.

Рассмотрим пример: Предположим, что Ева перехватила шифртекст, который выглядит следующим образом: «1». Также, Ева знает, что исходный текст - это возраст человека. Ева понимает, что исходный текст расположен где-то в интервале от 1 до 100. Также, Ева знает открытый ключ (7, 55). Для того, чтобы узнать открытый текст, Ева начинает зашифровывать каждый из возможных вариантов открытым ключом. На числе 56 Ева получит шифртекст «1» и тогда она будет знать, что исходным сообщением было число «56», и для этого ей не потребовалось узнавать экспоненту расшифрования.

Еще одна атака такого же типа заключается в многократном шифровании шифртекста, пока мы не получим шифртекст снова. После этого нам нужно вернуться на одну итерацию назад, это и будет исходным текстом. Однако это не может являться серьезном атакой на RSA, так как время, затраченное на такое шифрование, является недопустимо большим.

Атака на алгоритм RSA может быть эффективной, если экспонента расшифрования мала. В 1990 году Михаэль Винер показал, что в случае малого значения d возможен взлом системы RSA, а именно: Пусть n=p*q, причем q<p<2q, при этом d <. В таком случае, d можно вычислить за относительно небольшое время, что является уязвимостью. Эта атака полностью сходит на нет, если при длине ключа 1024 бит, длина d при это не менее 256 бит.

Следующая рассмотренная атака: атака Хастада. Начальные условия: Сторона B отсылает зашифрованное сообщение M пользователям P_1,P_2,...P_k. Каждый пользователь имеет свой открытый ключ n_e, причём M<n для каждого i. Сторона B зашифровывает сообщение, используя поочерёдно открытый ключ каждого пользователя, и отсылает его соответствующему адресату. Противник прослушивает канал передачи и собирает k переданных шифротекстов. В таком случае, злоумышленник может восстановить сообщение, если k>=e. Атака решается большим значением открытой экспоненты.

В заключение нужно отметить, что при выполнении следующих рекомендаций, RSA является практически полностью криптостойкой.

Список рекомендаций:

1. Число битов для n должно быть, по крайней мере, 1024. Это означает, что n должно быть приблизительно, или 309 десятичных цифр.

2. Два простых числа p и q должны каждый быть по крайней мере 512 битов. Это означает, что p и q должны быть приблизительно или 154 десятичными цифрами.

3. Значения p и q не должен быть очень близки друг к другу.

4. p - 1 и q - 1 должны иметь по крайней мере один большой простой сомножитель.

5. Отношение p/q не должно быть близко к рациональному числу с маленьким числителем или знаменателем.

6. Модуль n не должен использоваться совместно.

7. Значение e должно быть + 1 или целым числом, близким к этому значению.

8. Если произошла утечка частного ключа d, Боб должен немедленно изменить n так же, как e и d. Было доказано, что знание n и одной пары (e, d) может привести к открытию других пар того же самого модуля.

9. Сообщения должны быть дополнены, используя OAEP

Вывод

В результате выполнения работы был реализован алгоритм RSA на языке С#, а также было произведено ознакомлении с криптоанализом и получены навыки работы с данным шифром.

Список использованных источников

1. RSA [Электронный ресурс] // URL: ru.wikipedia.org/wiki/RSA(Дата обращения 11.12.2016).

2. Криптоанализ RSA [Электронный ресурс] // URL: https://ru.wikipedia.org/wiki/Криптоанализ RSA (Дата обращения 11.12.2016).

3. Криптоанализ RSA [Электронный ресурс] // URL: http://www.intuit.ru/studies/courses/552/408/lecture/9371?page=4 (Дата обращения 11.12.2016).

Размещено на Allbest.ru