Анализ алгоритмов шифрования в сетях передачи данных
МИНОБРНАУКИ
РОССИИ
ФЕДЕРАЛЬНОЕ
ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ -
УЧЕБНО-НАУЧНО-ПРОИЗВОДСТВЕННЫЙ
КОМПЛЕКС»
Кафедра
«Электроника, вычислительная техника
и
информационная безопасность»
КУРСОВАЯ
РАБОТА
по
дисциплине «Информационная безопасность и защита информации»
на
тему: «Анализ алгоритмов шифрования в сетях передачи данных»
Студент Богатырев П. Ю. Шифр 091122
Учебно-научно-исследовательский
институт информационных технологий
Специальность 230201 «Информационные системы и
технологии»
Группа 31-ИТ
Руководитель Фисун А.П.
Орел 2012
Содержание
Введение
Криптоанализ
в контексте криптологии
.1
Терминология криптологии
.2
Криптографическая защита, как элемент систем обеспечения безопасности
информации
.3
Исторические шифры и их взлом
.4
Особенности современной криптологии
.5
Современная криптография
.6
Современный криптоанализ
Основные
методы современного криптоанализа
.1
Метод грубой силы
.2
Атаки класса «встреча посередине»
.3
Дифференциальный криптоанализ
.4
Линейный криптоанализ
.5
Временной криптоанализ
.6
Решеточный криптоанализ
Заключение
Литература
Введение
В настоящее время большую роль в коммуникации
занимают электронные технические средства. Информация в больших объемах
передается по компьютерным сетям, обрабатывается в ЭВМ и хранится на цифровых
носителях. Более того, в связи с информатизацией общества, информация
приобретает все более и более значимую роль в жизни людей. В связи с этим,
актуальным является вопрос обеспечения безопасности информации при передаче,
обработке и хранении ее при помощи ЭВМ. Одним из способов осуществления данной
задачи является шифрование данных.
Объектом данного исследования являются алгоритмы
шифрования в сетях передачи данных. Предмет исследования - методы
криптографического анализа (взлома) шифров. Целью курсовой работы является
изучение основных принципов, на которых базируется современный криптоанализ.
Невозможно рассматривать анализ алгоритмов шифрования отдельно его объекта,
поэтому для реализации поставленной цели необходимо решить следующие задачи:
- Определиться с используемой в
криптологии терминологией;
- Рассмотреть место криптографических
методов защиты в общей системе обеспечения безопасности информации;
- Изучить простые (докомпьютерные)
шифры и методы их взлома;
- Выделить особенности современной
криптолографии
- Охарактеризовать современный
криптоанализ
- Рассмотреть современные методы
криптоанализа;
Основным методом выполнения поставленных задач
является анализ литературы и электронных ресурсов по данной тематике. Наиболее
полное собрание электронных ресурсов по теме собрано по адресу
#"564456.files/image001.gif">
Рисунок 2 - Иллюстрация метода
«встреча по середине» для Double DES
Крупные государства могут иметь
вычислительные средства, для взлома DES методом грубой силы (размер ключа в
DES 56 значащих бит). В таком случае взлом Double DES методом встречи
посередине всего в 2 раза сложнее, чем полный перебор ключей обычного DES, что
несравнимо меньше 2112 возможных вариантов «двойного» ключа [10].
.3 Дифференциальный криптоанализ
Как видно из названия, данный метод
связан с вычислением разности. Действительно, в данном случае берутся две пары
открытый]шифрованный текст, вводиться некоторая функция разности между двумя
текстами, и производиться наблюдение, как значение этой функции меняется после
шифрования. Операции перестановки и XOR (в том числе с ключом), практически не
влияют на разность (ее легко вычислить), поэтому изменение разности в основном
характеризует работу S-блоков. Проанализировав статистическими методами
возможные значения S-блоков,
можно сделать некоторые предположения о ключе. [11]
Данный метод подробно описан в
[16]. Основная процедура ДКА r- циклического шифра с использованием выбранных
открытых текстов может быть следующей:
. На этапе предвычислений ищем
множество (r-1)-цикловых дифференциалов (a 1,b 1)r-1 , (a 2,b 2)r-1 ,.... (a
s,b s)r-1 . Упорядочиваем это множество дифференциалов по величине их
вероятности.
. Выбираем открытый текст x
произвольным образом и вычисляем x* так, чтобы разность между x и x* была
равна a 1. Тексты x и x* шифруется на подлинном ключе и после r циклов
получаем пару шифртекстов y(r) , y*(r). Предполагаем, что на выходе
предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной:
D y(r-1)=b 1. Для тройки (D y(r-1), y(r) , y*(r)) находим каждое возможное
(если их несколько) значение подключа последнего цикла к(r). Добавляем его к
количеству появлений каждого такого значения подключа к(r).
. Повторяем п.2 до тех пор, пока
одно или несколько значений подключа к(r) не станет появляться чаще других.
Берем этот подключ или множество таких подключей в качестве криптографического
решения для подключа к(r).
. Повторяем пп.1-3 для
предпоследнего цикла, при этом значения y(r-1) вычисляются расшифрованием
шифртекстов на найденном подключе последнего цикла к(r). Далее действуем
аналогично, пока не будут раскрыты ключи всех циклов шифрования.
Предложенный впервые для анализа
конкретного шифра, ДКА оказался применимым для анализа широкого класса
марковских шифров. Марковским называется шифр, у которого уравнение шифрования
на одном цикле удовлетворяет условию: вероятность дифференциала не зависит от
выбора открытых текстов. Тогда, если подключи циклов независимы, то
последовательность разностей после каждого цикла образует марковскую цепь, где
последующее состояние определяется только предыдущим. Примерами марковских
шифров являются DES и FEAL.
Можно показать, что марковский
r-цикловый шифр с независимыми подключами является уязвимым для ДКА тогда и
только тогда, когда для одного цикла шифрования ключ по известной тройке
(y,y*,D x) может быть легко вычислен, и существует (r-1)-цикловый дифференциал
(a ,b )к-1 такой, что его вероятность удовлетворяет условию(D y(r-1)=b | D x=a
)>>2-n ,
где n-количество бит в блоке
шифруемого текста.
Сложность раскрытия ключа
r-циклического шифра Q(r) определяется как число используемых шифрований с
последующим вычислением ключа:
Q(r)і
2/ (Pmax - 1/(2n-1)),
где
Pmax=max(a )max(b )(P(D y(r-1)=b | D x=a )).
В частности, если Pmax » 1/(2n-1),
то атака не будет успешной. Поскольку вычисление подключа - более трудоемкая
операция, чем шифрование, то единицей измерения сложности является сложность
нахождения возможных подключей одного цикла по известным (D
y(r-1),y(r),y*(r)).
Отличительной чертой
дифференциального анализа является то, что он практически не использует
алгебраические свойства шифра (линейность, аффинность, транзитивность,
замкнутость и т.п.), а основан лишь на неравномерности распределения
вероятности дифференциалов.
.4 Линейный криптоанализ
Линейный криптоанализ изобрел
японский криптолог Мицуру Мацуи (Mitsuru Matsui). Предложенный им в 1993 г.
метод изначально был направлен на вскрытие алгоритма DES. Впоследствии
линейный криптоанализ был распространен и на другие алгоритмы. [12]
Смысл линейного криптоанализа
состоит в нахождении соотношений следующего вида: [12]
Pi1 Å Pi2 Å … Å Pia Å Cj1 Å Cj2 Å … Å Cjb = Kk1 Å Kk2 Å … Å Kkc
где Pn,
Cn и Kn
-
n-е биты открытого
текста, шифртекста и ключа соответственно.
Для произвольно выбранных бит
открытого текста, шифртекста и ключа вероятность P справедливости такого
соотношения составляет около ½. В
том случае, если криптоаналитику удается найти такие биты, при которых
вероятность P заметно отличается от ½, данным
соотношением можно воспользоваться для вскрытия алгоритма. [12]
Для раскрытия ключа шифра DES этим
методом необходимо 247 пар известных открытых и зашифрованных текстов. [16]
.5 Временной криптоанализ
Общая схема атаки описана в [17].
Атаку можно трактовать как проблему распознавания сигналов. "Сигнал"
состоит из вариаций измерения времени для известных бит, "шум" - из
погрешностей измерения времени и вариаций измерения времени для неизвестных
бит. Свойства "сигнала" и "шума" определяют количество
замеров времени, требуемых для атаки. Пусть получено j сообщений y0, y1, .,
yj-1 и им соответствующие измерения времени T0, T1, ., Tj-1. Вероятность, что
предположение xb для первых b бит правильно, пропорциональна,
где t(yi,xb) - время, требуемое для
первых b итераций цикла вычсиления yix mod n с использованием бит xb,-
ожидаемая фунция распределения вероятности T-t(y,xb) по всем значениям y и
правильному xb. Т.к. F определена как распределение вероятностиTi-t(yi,xb),
если xb правильно, то это - лучшая функция для предсказания Ti-t(yi,xb).
Обратите внимание, что измерения времени и промежуточные значения s могут
использоваться для улучшения оценки F.
При правильном предположении для
xb-1 имеются два возможных значения для xb. Вероятность того, что xb -
является правильным, а xb' - неправильным, может быть найдена как
2.6 Решеточный криптоанализ
В отличие от предыдущих методов
вскрытия, решеточный криптоанализ является не статистическим, а
алгебраическим. Вместо оценки вероятностей, в данном случае строиться
некоторая целевая функция, и ищется ее максимум. При этом алгоритм шифрования представляется
как композиция продолженных или решеточно определенных булевых функций. Их
отличие от обычных булевых функций в том, что они могут принимать все
рациональные значения от 0 до 1 (считая, что 0 - ложь, 1 - истина). [14, 15]
Целевая функция описывается
следующим образом [14]. Предположим, что нарушитель знает криптоалгоритм и
некоторое количество разрядов открытых и соответствующих зашифрованных
текстов. Пусть разряды открытого текста описываются уравнениями
xi
= Fi(y1,
..., yn, z1,
..., zN). (1)
где yi
разряды шифрограммы, zj
разряды ключа. Булевы функции
Fi
не имеют аналитической записи (она очень сложна), но значения их могут быть
вычислены для произвольного набора аргументов. Если открытые и зашифрованные
тексты известны в достаточном количестве, равном O(N),
то система уравнений (1) имеет единственное решение, которое и является
ключом. При этом достаточно знать только отдельные разряды некоторых блоков
открытого текста. Запишем для этого случая систему уравнений (1) в виде
fi(z1,
..., zN) = ai
(2)
Поскольку система (2) имеет
единственное решение, оно может быть записано в виде булевой формулы,
содержащей единственную конъюнкцию:
(3)
Символ z
c тильдой означает
вхождение переменной с инверсией или без инверсии.
С другой стороны, (2) может быть
записана в виде следующей конъюнкции булевых формул:
(4)
Если xi
= 1, то Fi входит без
инверсии, в противном случае Fi
входит с инверсией. Поскольку левые части выражений (3) и (4) равны 1 на одном
и том же наборе аргументов, они представляют одну и ту же булеву функцию,
которую назовем целевой, при этом (4) дает способ вычисления целевой функции
для произвольного ключа.
Подход подтвержден
экспериментально. Для ГОСТ 28147-89 найден обширный класс потенциально слабых
ключей, которые, возможно, допускают вскрытие c
низкой сложностью. При этом требуется всего четыре блока подобранных открытых
текстов. [15]
Заключение
Подводя итог, можно сказать, что
любой алгоритм шифрования, кроме одноразового блокнота и других доказано
стойких шифров, является потенциально нестойким. Многократное использование
одного и того же ключа оставляет некоторый «след» в шифруемых сообщениях. С
помощью статистики и алгебры можно выделить данный след, и на его основе
сделать предположение о самом ключе.
Тем не менее, при настоящем уровне
вычислительной техники, современные алгоритмы шифрования являются достаточно
стойкими. Чтобы избежать утечки информации, необходимо только правильно
использовать данные алгоритмы. Это подразумевает достаточно частую смену
ключей, использование достаточно длинных и случайных ключей, правильно
реализовывать сам алгоритм и тд. Отсюда следует, что вопросами обеспечения
безопасности должны заниматься квалифицированные специалисты в данной области.
Литература
1 М. А. Асосков и др. Поточные
шифры / Асосков А.В., Иванов М.А., Мирский А.А., Рузин А.В., Сланин А.В.,
Тютвин А.Н. - М.: Кудиц-образ, 1983.
Ю.Е. Пудовченко, Пределы роста
[Электронный ресурс]/Ю. Е. Пудовченко, режим доступа:
http://ssl.stu.neva.ru/psw/crypto.html
П. Семьянов Почему криптосистемы
ненадежны? [Электронный ресурс]/П. Семьянов, - режим доступа:
http://ssl.stu.neva.ru/psw/publications/crypto.html
А. Винокуров, Задачи решаемые
криптографическими методами [Электронный ресурс] / А. Винокуров, - режим
доступа: http://www.enlight.ru/ib/tech/crypto/part2.htm
5 А.В. Лунин, А.А. Сальников,
Перспективы развития и использования асимметричных алгоритмов в криптографии
[Электронный ресурс]/А.В. Лунин, А.А. Сальников, - режим доступа:
http://ssl.stu.neva.ru/psw/crypto/Lunin24.html
Клод Шеннон, Работы по теории
информации и кибернетике / К. Шенон, - М., ИЛ, 1963, с. 333-369 (Перевод
В.Ф.Писаренко).
Брюс Шнайер, Ханаанский бальзам
[Электронный ресурс] / Б. Шнайер, - режим доступа:
http://www.password-crackers.ru/articles/30/#_ftn1.
С.П. Панасенко, Современные методы
вскрытия алгоритмов шифрования, часть 1 [Электронный ресурс] / С.П. Панасенко
- режим доступа: http://old.cio-world.ru/it-market/community/291719/page2.html
Брюс Шнайер, Прикладная
криптография: Протоколы, алгоритмы, исходные тексты на языке Си [ Б. Шнайер, -
Триумф, 2002 - 816 с.
10
С.П. Панасенко, Современные методы вскрытия алгоритмов шифрования, часть 2
[Электронный ресурс] / С.П. Панасенко - режим доступа: <http://old.cio-world.ru/weekly/293694>/
С.П.
Панасенко, Современные методы вскрытия алгоритмов шифрования, часть 3
[Электронный ресурс] / С.П. Панасенко - режим доступа:
http://old.cio-world.ru/weekly/295841/page2.html
С.П.
Панасенко, Современные методы вскрытия алгоритмов шифрования, часть 4
[Электронный ресурс] / С.П. Панасенко - режим доступа:
http://old.cio-world.ru/weekly/298888/page2.html
Пауль
Кочер, Временной анализ реализаций Диффи-Хеллмана, RSA, DSS и других систем
[Электронный ресурс] / П. Кочер, - режим доступа:
http://ssl.stu.neva.ru/psw/crypto/timing.html
А.
Г. Ростовцев, Решеточный криптоанализ [Электронный ресурс] / А. Г. Ростовцев,
- режим доступа:
http://ssl.stu.neva.ru/psw/crypto/rostovtsev/resh_analysis.pdf
Ростовцев
А. Г., Маховенко Е. Б., Два подхода к анализу блочных шифров [Электронный
ресурс] / Ростовцев А. Г., Маховенко Е. Б., - режим доступа:
http://ssl.stu.neva.ru/psw/crypto/rostovtsev/dva_podhoda.pdf
А.Г.
Ростовцев, Н.В. Михайлова Методы криптоанализа классических шифров
[Электронный ресурс] / А.Г. Ростовцев, Н.В. Михайлова, - режим доступа:
http://ssl.stu.neva.ru/psw/crypto/rostovtsev/cryptoanalysis.html
П.
Кочер, Временной анализ реализаций Диффи-Хеллмана, RSA, DSS и других систем
[Электронный ресурс] / П. Кочер, - режим доступа: http://ssl.stu.neva.ru/psw/crypto/timing.html