Алгоритм DES и его варианты. Прошло уже белее 3.
DES в качестве стандарта шифрования США. DES — алгоритм шифрования с наиболее богатой и интересной историей. История создания алгоритма. Один из наиболее известных в мире криптологов Брюс Шнайер в своей знаменитой книге «Прикладная криптография» . XX века (естественно, речь идет о пользователях по ту сторону «железного занавеса»): П не было как общепринятого стандарта шифрования данных, так и просто достаточно широко используемых алгоритмов защиты информации, поэтому о совместимости между различными программными или аппаратными средствами шифрования не могло быть и речи; ? В результате в 1. Генерация ключей в S-DES. Шифрование в S-DES. Алгоритм шифрования включает последовательное выполнение пяти операций: . Рис.4 Подробная схема шифрования алгоритма DES. Схема шифрования алгоритма DES .NBS было готово исследовать с целью выбора стандарта алгоритмы- претенденты, удовлетворяющие следующим критериям: ? Предполагалось также, что алгоритм будет сертифицирован NBS для всеобщего использования, с него будут сняты все патентные и экспортные ограничения, в результате чего такой стандарт должен будет решить все проблемы совместимости средств шифрования. Кроме того, NBS брало на себя функции сертификации средств шифрования — т. В течение двух лет проводилась доработка алгоритма: ? DES был опубликован как стандарт США (последняя версия этого стандарта — в документе . Алгоритм DES был запатентован фирмой ЮМ, однако NBS получило, фактически, бесплатную и неограниченную лицензию на использование данного алгоритма . Альтернативное, но реже используемое название алгоритма — DEA (Data Encryption Algorithm). Основные характеристики и структура алгоритма. Алгоритм DES шифрует информацию блоками по 6. Шифрование информации выполняется следующим образом (рис. Над 6. 4- битным блоком данных производится начальная перестановка согласно табл. Таблица 3. 1. 65. Таблица трактуется следующим образом: значение входного бита 5. Результат предыдущей операции делится на 2 субблока по 3. А0 и В0), над которыми производятся 1. Как было сказано выше, из 6. DES использует только 5. Каждый 8- й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся битов ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом . Процедура извлечения 5. Е. Помимо извлечения, данная процедура выполняет еще и перестановку битов ключа согласно табл. Таблица 3. 1. 95. Таблица 3. 2. 06. В результате перестановки формируются два 2. С и D. Таблица 3. С, табл. 3. 2. 0 — для D. Затем выполняются 1. Kt. В каждом раунде процедуры расширения ключа производятся следующие действия: 1. Для раундов 1, 2, 9 и 1. Сжимающая перестановка выполняется согласно табл. Таблица 3. 2. 11. При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раундов в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на п битов, где гс’ = 0 для первого раунда, и’=1 для раундов 2, 9, 1. Такая процедура расширения ключа сразу даст нужные для расшифровывания ключи раундов . Стоит сказать, что возможность выполнения расширения ключа «на лету» (особенно если эта возможность существует как при зашифровывании, так и при расшифровывании) считается достоинством алгоритмов шифрования, поскольку в этом случае расширение ключа можно выполнять параллельно шифрованию и не тратить память на хранение ключей других раундов, кроме текущего. Линейный криптоанализ для чайников / Хабрахабр. Привет, %username%! Первая успешная атака на этот неубиваемый алгоритм была опубликована в 1. Метод, который автор назвал линейным криптоанализом, при наличии 2. DES за 2. 43 операций. В общем случае атака на основе линейного криптоанализа сводится к следующим условиям. Злоумышленник обладает большим количеством пар открытый/зашифрованный текст, полученных с использованием одного и того же ключа шифрования K. Цель атакующего восстановить частично или полностью ключ K. В первую очередь злоумышленник производит исследование шифра и находит т. Чем больше вероятность P равенства (1) отличается от 1/2, тем меньше количество открытых текстов N необходимо для атаки. Возникают две проблемы, которые необходимо решить для успешной реализации атаки: Как найти эффективное уравнение вида (1). Как с помощью такого уравнения получить больше одного бита информации о ключе. О DES сказано уже достаточно. Полное описание шифра можно найти на Википедии. Однако для дальнейшего объяснения атаки нам потребуется ряд определений которые лучше ввести заранее. Итак, DES это блочный шифр, основанный на сети Фейстеля. Шифр имеет размер блока 6. Рассмотрим схему шифрования алгоритма DES. Как видно из рисунка, при шифровании над текстом производятся следующие операции: Начальная перестановка бит. На этом этапе биты входного блока перемешиваются в определенном порядке. После этого перемешанные биты разбиваются на две половины, которые поступают на вход функции Фейстеля. Для стандартного DES сеть Фейстеля включает 1. Два блока, полученных на последнем раунде преобразования объединяются и над полученным блоком производится еще одна перестановка. На каждом раунде сети Фейстеля 3. Рассмотрим операции, выполняющиеся на этом этапе: Входной блок проходит через функцию расширения E, которая преобразует 3. Полученный блок складывается с раундовым ключом Ki. Результат предыдущего шага разбивается на 8 блоков по 6 бит каждый. Каждый из полученных блоков Bi проходит через функцию подстановки S- Boxi, которая заменяет 6- битную последовательность, 4- битным блоком. Полученный в результате 3. P и возвращается в качестве результата функции f. Наибольший интерес, с точки зрения криптоанализа шифра, для нас представляют S блоки, предназначенные для скрытия связи между входными и выходными данными функции f. Для успешной атаки на DES мы сперва построим статистические аналоги для каждого из S- блоков, а затем распространим их на весь шифр. Анализ S блоков. Каждый S- блок принимает на вход 6- битную последовательность, и для каждой такой последовательности возвращается фиксированное 4- битное значение. Наша задача показать взаимосвязь между входными и выходными данными S блоков. К примеру, для третьего S- блока шифра DES, 3- й бит входной последовательности равен 3- му биту выходной последовательности в 3. Следовательно, мы нашли следующий статистический аналог для третьего S- блока. S3(x). Поэтому в случае если бы левая и правая части были независимы друг от друга, уравнение должно было бы выполняться с вероятностью равной 1/2. Таким образом, мы только что продемонстрировали связь между входными и выходными данными 3- го S- блока алгоритма DES. Рассмотрим как можно найти статистический аналог S- блока в общем случае. Для S- блока Sa, 1 . Это значит, что справедливо следующее уравнение: Z. Или с учетом того, что в алгоритме DES перед входом в S- блок данные складываются по модулю 2 с раундовым ключом, т. Анализируя функцию расширения можно установить что на месте 2. X(1). Исследовав перестановку P, получаем что биты Y. На этот раз мы имеем уравнение. X(3). Покажем как с помощью данного статистического аналога можно вскрыть не 1, а 1. K. Атака на DES с известным открытым текстом. Приведем способ с помощью которого можно расширить атаку и получить сразу 6 бит подключа первого раунда. Поэтому мы использовали его статистический аналог K1. Вероятность изменилась так как мы оставили только статистический аналог из третьего раунда, все остальные значения фиксированы. Выше мы уже определили, что на значение F1(PR, K1). Покажем каким образом обладая только набором открытых/закрытых текстов можно восстановить значение K1. Для этого воспользуемся алгоритмом 2. Алгоритм 2. Пусть N — количество известных перед атакой пар открытый/закрытый текст. Тогда для вскрытия ключа необходимо проделать следующие шаги. For (i=0; i< 6. Объясняется это тем, что в случае если переменная i не равна K1. В случае же если подключ угадан верно, левая часть будет с вероятностью 1. K3. Все что для этого нужно, это заменить в уравнении (6) C на P и K1 на K3: PL. Так на первом раунде расшифрования используется ключ K3, а на последнем ключ K1. Получив по 6 бит подключей K1 и K3 злоумышленник восстанавливает 1. K, т. к. Количество открытых текстов необходимых для успешной атаки зависит от вероятности статистического аналога. Для вскрытия 1. 2 бит ключа 3- раундового DES достаточно 1. Для вскрытия 1. 2 бит ключа 1. DES потребуется порядка 2. Остальные 4. 4 бита ключа вскрываются обычным перебором.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
November 2017
Categories |