Анализ алгоритмов шифрования в сетях передачи данных
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
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 Временной криптоанализ
Суть данного метода заключается в измерении времени, которое затрачивает устройство на шифрование того или иного текста. Существует некоторое математическое обоснование, доказывающее, что данным способом можно получить некоторую информацию о ключе. [13]
Общая схема атаки описана в [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, ..., z