Цель работы - закрепление теоретических знаний и практическое освоение метода дифференциального (разностного) криптоанализа блочных симметричных криптосистем на примере криптосистемы S-DES.
Время - 4 часа.
Основные теоретические сведения
Криптосистема S-DES подробно рассмотрена в практической работе №3.
Метод дифференциального (разностного) криптоанализа предложен Э. Байхэмом и А. Шамиром, и, по мнению ряда специалистов компании IBM, является общим методом криптоанализа блочно-итерационных криптосистем. Идея заключается в анализе процесса изменения несходства для пары открытых текстов АХ = X © X ', имеющих определенные исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом.
Пусть задана пара входов X и Х ', с несходством А Х = Х © Х '. Известны перестановка IP и перестановка с расширением Е, а следовательно, известны и несходства АА на входе блоков замены S q и Si. Выходы Y и Y ' известны,
следовательно, известно и несходство A Y = Y © 7', а значит, при известных
перестановках IP и Р известны несходства ΔС на выходе блоков замены S q
и Si.
Доказано, что для любого заданного Δ A не все значения ΔС равновероятны. Комбинация ΔА и ΔС позволяет предположить значения битов для Е(Х) © k { и Е(Х') © k {. То, что Е (Х ) и Е(Х') известны, дает информацию о
ki.
Несходство различных пар открытых текстов приводит к несходству получаемых шифр-текстов с определенной вероятностью. Эти вероятности можно определить, построив таблицы для каждого из блоков замены. Таблицы сроятся по следующему принципу: по вертикали располагаются все возможные комбинации АА, по горизонтали - все возможные комбинации ΔС, а на пересечении - число соответствий данного ΔС данному АА.
Число наибольших совпадений указывает нам пару ΔA и ΔС, с помощью которой можно определить секретный ключ. Пара открытых текстов, соответствующих данным ΔА и ΔС называется правильной парой, а пара открытых текстов, не соответствующих данным ΔA и ΔС - неправильной парой. Правильная пара подскажет правильный ключ цикла, а неправильная пара -случайный. Чтобы найти правильный ключ, необходимо просто собрать достаточное число предположений. Один из подключей будет встречаться чаще, чем все остальные. Фактически правильный подключ появляется из всех возможных случайных подключей.
Порядок выполнения работы
Практическаяработа выполняется с использование программы «Cryptoanaliz».
2.1. При подготовке к практической работе
На этапе подготовки к практической работе студенты должны, используя литературу [1-4], материалы лекций углубить свои знания по следующим вопросам: блочные симметричные криптосистемы (определение, основные характеристики, достоинства и недостатки), блочная криптосистема S-DES, метод дифференциального (разностного) криптоанализа блочных криптосистем, а также изучить инструкцию по использованию программы «Cryptoanaliz».
2.2. Во время проведения занятия
Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к практической работе.
Преподаватель разбивает группу студентов на 5 подгрупп, для каждой подгруппы определяется номер индивидуального задания на предстоящую лабораторную работу. Варианты индивидуальных заданий заложены в программе «Cryptoanaliz».
В процессе выполнения работы студенты должны:
1. Запустить на исполнение программу «Cryptoanaliz» и пройти
предлагаемый контрольный тест.
2. В соответствии с заданием определенным преподавателем студенты выбирают номер варианта и количество известных текстов.
3. Используя таблицы анализа несходств (АЛ, АС) для блоков замены S0
и S1 студенты определяют оптимальный дифференциал (A *, C *) и осуществляют зашифрование случайным образом сгенерированных открытых текстов. Программа выбирает из множества пар текстов пары
удовлетворяющие оптимальному дифференциалу (АА, АС) и представляет их в виде в табл. 1.
Таблица 1 – Пары текстов удовлетворяющие оптимальному
дифференциалу
| № | X | Е (Х) | S (Е (Х)) | Y |
| … | ||||
| № | X' | Е(Х') | S(Е(Х') | Г |
| … |
4. Студенты анализируют пары открытых текстов и определяют
множество раундовых ключей шифра и, соответственно, множество основных
ключей шифра. Ключ, получаемый чаще остальных и будет наиболее
вероятным ключом шифра.
5. Используя модуль «Проверка» студенты проверяют правильность определенного анализом ключей шифра.
6. При совпадении результатов анализа с истинным ключом шифра студенты оформляют, в соответствии с требованиями настоящего пособия отчет и представляют его преподавателю для защиты.
Содержание отчета
Отчет должен включать в себя следующие пункты:
1. Структуру алгоритма S-DES и таблицы перестановок и замен,
соответствующие заданному варианту.
2. Результаты анализа таблиц замен S 0 и S 1.
3. Результаты анализа пар открытых текстов.
4. Множество возможных раундовых ключей.
5. Результаты проверки, подтверждающие правильность определенного в работе ключа.
Контрольные вопросы
1. Основные понятия криптографии и криптоанализа.
2. Понятие блочной симметричной криптосистемы.
3. Основные характеристики блочных симметричных криптосистем.
4. Метод дифференциального (разностного) криптоанализа.
Литература
1. Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.
2. Харин Ю.С., Беник В.И, Матвеев Г.В., Агиевич СВ. Математические и компьютерные основы криптологии: Учеб. пособие. -Минск: Новое знание, 2003.
3. Бабенко Л.К., Мишустина Е.А. Лабораторный практикум по изучению современных методов криптоанализа по курсу «Криптографические методы и средства обеспечения защиты информации». - Таганрог: Изд-во ТРТУ, 2003.
4. Бабенко Л.К., Мишустина Е.А. Изучение современных методов криптоанализа. Методическое пособие. - Таганрог: Изд-во ТРТУ, 2003
