Схема des шифрования. Начальные и конечные перестановки

Аннотация: Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard. Эта система первой получила статус государственного стандарта в области шифрования данных. И хотя старый американский стандарт DES в настоящее время утратил свой официальный статус, этот алгоритм все же заслуживает внимания при изучении криптографии. Кроме того в этой лекции объясняется, что такое "двухкратный DES", атака "встреча посередине" и способы ее устранения. В этой же лекции кратко рассматривается новый стандарт США на блочный шифр – алгоритм Rijndael.

Цель лекции : познакомить студента с основными сведениями об алгоритме шифрования DES .

Основные сведения

Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard . Эта система первой получила статус государственного стандарта в области шифрования данных. Она разработана специалистами фирмы IBM и вступила в действие в США 1977 году. Алгоритм DES широко использовался при хранении и передаче данных между различными вычислительными системами; в почтовых системах, в электронных системах чертежей и при электронном обмене коммерческой информацией . Стандарт DES реализовывался как программно, так и аппаратно. Предприятиями разных стран был налажен массовый выпуск цифровых устройств, использующих DES для шифрования данных. Все устройства проходили обязательную сертификацию на соответствие стандарту.

Несмотря на то, что уже некоторое время эта система не имеет статуса государственного стандарта, она по-прежнему широко применяется и заслуживает внимания при изучении блочных шифров с закрытым ключом.

Длина ключа в алгоритме DES составляет 56 бит . Именно с этим фактом связана основная полемика относительно способности DES противостоять различным атакам. Как известно, любой блочный шифр с закрытым ключом можно взломать, перебрав все возможные комбинации ключей. При длине ключа 56 бит возможны 2 56 разных ключей. Если компьютер перебирает за одну секунду 1 000 000 ключей (что примерно равно 2 20), то на перебор всех 2 56 ключей потребуется 2 36 секунд или чуть более двух тысяч лет, что, конечно, является неприемлемым для злоумышленников.

Однако возможны более дорогие и быстрые вычислительные системы, чем персональный компьютер . Например, если иметь возможность объединить для проведения параллельных вычислений миллион процессоров, то максимальное время подбора ключа сокращается примерно до 18 часов. Это время не слишком велико, и криптоаналитик, оснащенный подобной дорогой техникой, вполне может выполнить вскрытие данных, зашифрованных DES за приемлемое для себя время.

Вместе с этим можно отметить, что систему DES вполне можно использовать в небольших и средних приложениях для шифрования данных, имеющих небольшую ценность. Для шифрования данных государственной важности или имеющих значительную коммерческую стоимость система DES в настоящее время, конечно, не должна использоваться. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блочный шифр , названный AES (Advanced Encryption Standard) , в основу которого был положен шифр Rijndael , разработанный бельгийскими специалистами. Этот шифр рассматривается в конце лекции.

Основные параметры DES : размер блока 64 бита, длина ключа 56 бит , количество раундов – 16. DES является классической сетью Фейштеля с двумя ветвями. Алгоритм преобразует за несколько раундов 64-битный входной блок данных в 64-битный выходной блок. Стандарт DES построен на комбинированном использовании перестановки, замены и гаммирования. Шифруемые данные должны быть представлены в двоичном виде.

Шифрование

Общая структура DES представлена на рис. 4.1 . Процесс шифрования каждого 64-битового блока исходных данных можно разделить на три этапа:

начальная подготовка блока данных;
16 раундов "основного цикла";
конечная обработка блока данных.

На первом этапе выполняется начальная перестановка 64-битного исходного блока текста, во время которой биты определенным образом переупорядочиваются.

На следующем (основном) этапе блок делится на две части (ветви) по 32 бита каждая. Правая ветвь преобразуется с использованием некоторой функции F и соответствующего частичного ключа , получаемого из основного ключа шифрования по специальному алгоритму преобразования ключей. Затем производится обмен данными между левой и правой ветвями блока. Это повторяется в цикле 16 раз.

Наконец, на третьем этапе выполняется перестановка результата, полученного после шестнадцати шагов основного цикла . Эта перестановка обратна начальной перестановке.

Рис. 4.1.

Рассмотрим более подробно все этапы криптографического преобразования по стандарту DES .

На первом этапе 64-разрядный блок исходных данных подвергается начальной перестановке. В литературе эта операция иногда называется "забеливание" – whitening . При начальной перестановке биты блока данных определенным образом переупорядочиваются. Эта операция придает некоторую "хаотичность" исходному сообщению, снижая возможность использования криптоанализа статистическими методами.

Одновременно с начальной перестановкой блока данных выполняется начальная перестановка 56 бит ключа. Из рис. 4.1 . видно, что в каждом из раундов используется соответствующий 48-битный частичный ключ K i . Ключи K i получаются по определенному алгоритму, используя каждый из битов начального ключа по нескольку раз. В каждом раунде 56-битный ключ делится на две 28-битовые половинки. Затем половинки сдвигаются влево на один или два бита в зависимости от номера раунда. После сдвига определенным образом выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, то эта операция называется " перестановка со сжатием". Ее результатом является набор из 48 битов. В среднем каждый бит исходного 56-битного ключа используется в 14 из 16 подключей, хотя не все биты используются одинаковое количество раз.

Далее выполняется основной цикл преобразования, организованный по сети Фейштеля и состоящий из 16 одинаковых раундов. При этом в каждом раунде ( рис. 4.2) получается промежуточное 64-битное значение , которое затем обрабатывается в следующем раунде.

Рис. 4.2.

Левая и правая ветви каждого промежуточного значения обрабатываются как отдельные 32-битные значения, обозначенные L и R .

Вначале правая часть блока R i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Эта операция приводит размер правой половины в соответствие с размером ключа для выполнения операции XOR . Кроме того, за счет выполнения этой операции быстрее возрастает зависимость всех битов результата от битов исходных данных и ключа (это называется "лавинным эффектом"). Чем сильнее проявляется лавинный эффект при использовании того или иного алгоритма шифрования, тем лучше.

После выполнения перестановки с расширением для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K i . Затем полученное 48-битное значение подается на вход блока подстановки S (от англ. Substitution - подстановка), результатом которой является 32-битное значение . Подстановка выполняется в восьми блоках подстановки или восьми S-блоках (S-boxes). При выполнении этой DES на бумаге выглядит достаточно сложным, что уж говорить про его программную реализацию! Разработать правильно и оптимально функционирующую программу полностью в соответствии с DES , наверно, под силу только опытным программистам. Некоторые трудности возникают при программной реализации, например, начальной перестановки или перестановки с расширением. Эти сложности связаны с тем, что первоначально планировалось реализовывать DES только аппаратно. Все используемые в стандарте операции легко выполняются аппаратными блоками, и никаких трудностей с реализацией не возникает. Однако через некоторое время после публикации стандарта разработчики программного обеспечения решили не стоять в стороне и тоже взяться за создание систем шифрования. В дальнейшем DES реализовывался и аппаратно, и программно.

симметричными ключами .

Предложенная IBM модификация проекта, названная Lucifer, была принята как DES . DES были изданы в эскизном виде в Федеральном Регистре в марте 1975 года как Федеральный Стандарт Обработки Информации (FIPS – Federal Information Processing Standard) .

После публикации эскиз строго критиковался по двум причинам. Первая: критиковалась сомнительно маленькая длина ключа (только 56 битов), что могло сделать шифр уязвимым к атаке "грубой силой". Вторая причина: критики были обеспокоены некоторым скрытым построением внутренней структуры DES .

Они подозревали, что некоторая часть структуры (S -блоки) может иметь скрытую лазейку, которая позволит расшифровывать сообщения без ключа. Впоследствии проектировщики IBM сообщили, что внутренняя структура была доработана, чтобы предотвратить криптоанализ .

DES был наконец издан как FIPS 46 в Федеральном Регистре в январе 1977 года. Однако FIPS объявил DES как стандарт для использования в неофициальных приложениях. DES был наиболее широко используемым блочным шифром с симметричными ключами , начиная с его публикации. Позже NIST предложил новый стандарт ( FIPS 46-3), который рекомендует использование тройного DES (трехкратно повторенный шифр DES ) для будущих приложений. Как мы увидим далее, в лекциях 9-10, предполагается, что более новый стандарт AES заменит DES .

Общие положения

Как показано на рис. 8.1. , DES - блочный шифр .

Рис. 8.1.

На стороне шифрования DES принимает 64 -битовый исходный текст и порождает 64 -битовый зашифрованный текст; на стороне дешифрования DES принимает 64 -битовый зашифрованный текст и порождает 64 -битовый исходный текст. На обеих сторонах для шифрования и дешифрования применяется один и тот же 56 -битовый ключ.

8.2. Структура DES

Рассмотрим сначала шифрование , а потом дешифрование . Процесс шифрования состоит из двух перестановок (P -блоки) - они называются начальные и конечные перестановки, - и шестнадцати раундов Файстеля. Каждый раунд использует различные сгенерированные 48 -битовые ключи. Алгоритм генерации будет рассмотрен в этой лекции позднее. Рисунок 8.2 показывает элементы шифра DES на стороне шифрования.

Начальные и конечные перестановки

Рисунок 8.3 показывает начальные и конечные перестановки (P -блоки). Каждая из перестановок принимает 64 -битовый вход и переставляет его элементы по заданному правилу. Мы показали только небольшое число входных портов и соответствующих выходных портов. Эти перестановки - прямые перестановки без ключей, которые инверсны друг другу. Например, в начальной перестановке 58 -й бит на входе переходит в первый бит на выходе. Аналогично, в конечной перестановке первый входной бит переходит в 58 -й бит на выходе. Другими словами, если между этими двумя перестановками не существует раунда, 58 -й бит, поступивший на вход устройства начальной перестановки, будет доставлен на 58 -й выход финальной перестановкой.

Рис. 8.2.

Рис. 8.3.

Правила перестановки для этого P -блока показаны в таблице 8.1 . Таблицу можно представить как 64 -элементный массив. Заметим, что работу с таблицей мы обсуждали, значение каждого элемента определяет номер входного порта, а порядковый номер (индекс) элемента определяет номер выходного порта.

Таблица 8.1. Таблица начальных и конечных перестановок

Начальные перестановки								Конечные перестановки
58	50	42	34	26	18	10	02	40	08	48	16	56	24	64	32
60	52	44	36	28	20	12	04	39	07	47	15	55	23	63	31
62	54	46	38	30	22	14	06	38	06	46	14	54	22	62	30
64	56	48	40	32	24	16	08	37	05	45	13	53	21	61	29
57	49	41	33	25	17	09	01	36	04	44	12	52	20	60	28
59	51	43	35	27	19	11	03	35	03	43	11	51	19	59	27
61	53	45	37	29	21	13	05	34	02	42	10	50	18	58	26
63	55	47	39	31	23	15	07	33	01	41	09	49	17	57	25

Эти две перестановки не имеют никакого значения для криптографии в

Прошло уже белее 30 лет с даты принятия алгоритма DES в качестве стандарта шифрования США. DES - алгоритм шифрования с наиболее богатой и интересной историей.

История создания алгоритма

Один из наиболее известных в мире криптологов Брюс Шнайер в своей знаменитой книге «Прикладная криптография» так описал проблемы пользователей средств защиты информации в начале 70-х гг. XX века (естественно, речь идет о пользователях по ту сторону «железного занавеса»):

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

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

Данной проблемой озаботилось Национальное Бюро Стандартов (National Bureau of Standards, NBS) США. В результате в 1973 г. был объявлен первый в истории открытый конкурс на стандарт шифрования. NBS было готово исследовать с целью выбора стандарта алгоритмы-претенденты, удовлетворяющие следующим критериям:

Алгоритм должен быть криптографически стойким;

Алгоритм должен быть быстрым;

П структура алгоритма должна быть четкой и ясной;

Стойкость шифрования должна зависеть только от ключа, сам алгоритм не должен быть секретным;

Алгоритм должен быть легко применим для различных целей;

Алгоритм должен легко реализовываться аппаратно на существующей элементной базе.

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

Фактически алгоритм-претендент оказался всего один: это был разработанный фирмой ШМ алгоритм шифрования Lucifer {см. разд. 3.31). В течение двух лет проводилась доработка алгоритма:

Во-первых, NBS совместно с Агентством Национальной Безопасности (АНБ, NSA - National Security Agency) США был проведен тщательный анализ алгоритма, результатом которого явилась его достаточно существенная переработка;

Во-вторых, принимались к рассмотрению комментарии и критические замечания от всех заинтересованных организаций и частных лиц.

В результате совместной деятельности IBM, NBS и АНБ в январе 1977 г. DES был опубликован как стандарт США (последняя версия этого стандарта - в документе ) на алгоритм шифрования данных (кроме информации повышенной степени секретности). Алгоритм DES был запатентован фирмой ЮМ, однако NBS получило, фактически, бесплатную и неограниченную лицензию на использование данного алгоритма . Альтернативное, но реже используемое название алгоритма - DEA (Data Encryption Algorithm).

Основные характеристики и структура алгоритма

Алгоритм DES шифрует информацию блоками по 64 бита с помощью 64- битного ключа шифрования, в котором используется только 56 битов (процедура расширения ключа подробно описана далее).

Шифрование информации выполняется следующим образом (рис. 3.56):

1. Над 64-битным блоком данных производится начальная перестановка согласно табл. 3.16.

Таблица 3.16

Таблица трактуется следующим образом: значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита - в бит 2 и т. д.

2. Результат предыдущей операции делится на 2 субблока по 32 бита (на

рис. 3.56 обозначены А 0 и В 0), над которыми производятся 16 раундов

следующих преобразований:

Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 битов. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся битов ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом . Процедура извлечения 56 значащих битов 64-битного ключа на рис. 3.59 обозначена как Е. Помимо извлечения, данная процедура выполняет еще и перестановку битов ключа согласно табл. 3.19 и 3.20.

Таблица 3.19

Таблица 3.20

В результате перестановки формируются два 28-битных значения С и D. Таблица 3.19 определяет выборку битов ключа для С, табл. 3.20 - для D.

Затем выполняются 16 раундов преобразований, каждый из которых дает один из ключей раундов K t . В каждом раунде процедуры расширения ключа производятся следующие действия:

1. Текущие значения С и D циклически сдвигаются влево на переменное число битов п. Для раундов 1, 2, 9 и 16 п = 1, в остальных раундах выполняется циклический сдвиг на 2 бита.

2. С и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда К (. Сжимающая перестановка выполняется согласно табл. 3.21.

Таблица 3.21

При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раундов в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на п битов, где гс’ = 0 для первого раунда, и’=1 для раундов 2, 9, 16 и п= 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифровывания ключи раундов.

Стоит сказать, что возможность выполнения расширения ключа «на лету» (особенно если эта возможность существует как при зашифровывании, так и при расшифровывании) считается достоинством алгоритмов шифрования, поскольку в этом случае расширение ключа можно выполнять параллельно шифрованию и не тратить память на хранение ключей других раундов, кроме текущего.

Tutorial

Привет, %username%!
Многим известно, что стандартом по умолчанию в области симметричного шифрования долгое время считался алгоритм DES. Первая успешная атака на этот неубиваемый алгоритм была опубликована в 1993 году, спустя 16 лет после принятия его в качестве стандарта. Метод, который автор назвал линейным криптоанализом, при наличии 2 47 пар открытых/зашифрованных текстов, позволяет вскрыть секретный ключ шифра DES за 2 43 операций.
Под катом я попытаюсь кратко изложить основные моменты этой атаки.

Линейный криптоанализ

Линейный криптоанализ - особый род атаки на симметричные шифры, направленный на восстановление неизвестного ключа шифрования, по известным открытым сообщениям и соответствующим им шифртекстам.

В общем случае атака на основе линейного криптоанализа сводится к следующим условиям. Злоумышленник обладает большим количеством пар открытый/зашифрованный текст, полученных с использованием одного и того же ключа шифрования K. Цель атакующего восстановить частично или полностью ключ K.

В первую очередь злоумышленник производит исследование шифра и находит т.н. статистический аналог, т.е. уравнение следующего вида, выполняющееся с вероятностью P ≠ 1/2 для произвольной пары открытый/закрытый текст и фиксированного ключа:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
где P n , C n , K n - n-ые биты текста, шифртекста и ключа.
После того как подобное уравнение будет найдено атакующий может восстановить 1 бит информации о ключе, используя следующий алгоритм

Алгоритм 1
Пусть T - количество текстов, для которых левая часть уравнения (1) равняется 0, тогда
Если T>N/2, где N - число известных открытых текстов.
Предположить, что K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (когда P>1/2) или 1 (когда P<1/2).
Иначе
Предположить, что K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (когда P>1/2) или 0 (когда P<1/2).
Очевидно, что успех алгоритма напрямую зависит от значения |P-1/2| и от количества доступных пар открытый/закрытый текст N. Чем больше вероятность P равенства (1) отличается от 1/2, тем меньше количество открытых текстов N необходимо для атаки.

Возникают две проблемы, которые необходимо решить для успешной реализации атаки:

Как найти эффективное уравнение вида (1).
Как с помощью такого уравнения получить больше одного бита информации о ключе.

Рассмотрим решение этих вопросов на примере шифра DES.

Описание DES

Но для начала кратко опишем работу алгоритма. О DES сказано уже достаточно. Полное описание шифра можно найти на Википедии . Однако для дальнейшего объяснения атаки нам потребуется ряд определений которые лучше ввести заранее.

Итак, DES это блочный шифр, основанный на сети Фейстеля . Шифр имеет размер блока 64 бита и размер ключа 56 бит. Рассмотрим схему шифрования алгоритма DES.

Как видно из рисунка, при шифровании над текстом производятся следующие операции:

Начальная перестановка бит. На этом этапе биты входного блока перемешиваются в определенном порядке.
После этого перемешанные биты разбиваются на две половины, которые поступают на вход функции Фейстеля. Для стандартного DES сеть Фейстеля включает 16 раундов, но существуют и другие варианты алгоритма.
Два блока, полученных на последнем раунде преобразования объединяются и над полученным блоком производится еще одна перестановка.

На каждом раунде сети Фейстеля 32 младших бита сообщения проходят через функцию f:

Рассмотрим операции, выполняющиеся на этом этапе:

Входной блок проходит через функцию расширения E, которая преобразует 32-битный блок в блок длиной 48 бит.
Полученный блок складывается с раундовым ключом K i .
Результат предыдущего шага разбивается на 8 блоков по 6 бит каждый.
Каждый из полученных блоков B i проходит через функцию подстановки S-Box i , которая заменяет 6-битную последовательность, 4-битным блоком.
Полученный в результате 32-битный блок проходит через перестановку P и возвращается в качестве результата функции f.

Наибольший интерес, с точки зрения криптоанализа шифра, для нас представляют S блоки, предназначенные для скрытия связи между входными и выходными данными функции f. Для успешной атаки на DES мы сперва построим статистические аналоги для каждого из S-блоков, а затем распространим их на весь шифр.

Анализ S блоков

Каждый S-блок принимает на вход 6-битную последовательность, и для каждой такой последовательности возвращается фиксированное 4-битное значение. Т.е. имеется всего 64 варианта входных и выходных данных. Наша задача показать взаимосвязь между входными и выходными данными S блоков. К примеру, для третьего S-блока шифра DES, 3-й бит входной последовательности равен 3-му биту выходной последовательности в 38 случаях из 64. Следовательно, мы нашли следующий статистический аналог для третьего S-блока:
S 3 (x) = x, который выполняется с вероятность P=38/64.
Обе части уравнения представляют 1 бит информации. Поэтому в случае если бы левая и правая части были независимы друг от друга, уравнение должно было бы выполняться с вероятностью равной 1/2. Таким образом, мы только что продемонстрировали связь между входными и выходными данными 3-го S-блока алгоритма DES.

Рассмотрим как можно найти статистический аналог S-блока в общем случае.

Для S-блока S a , 1 ≤ α ≤ 63 и 1 ≤ β ≤ 15, значение NS a (α, β) описывает сколько раз из 64 возможных XOR входных бит S a наложенных на биты α равны XOR выходных бит, наложенных на биты β, т.е.:
где символ - логическое И.
Значения α и β, для которых NS a (α, β) сильнее всего отличается от 32, описывают самый эффективный статистический аналог S-блока S a .

Наиболее эффективный аналог был найден в 5-ом S-блоке шифра DES для α = 16 и β = 15 NS 5 (16, 15)=12. Это значит, что справедливо следующее уравнение: Z=Y ⊕ Y ⊕ Y ⊕ Y, где Z - входная последовательность S-блока, а Y - выходная последовательность.
Или с учетом того, что в алгоритме DES перед входом в S-блок данные складываются по модулю 2 с раундовым ключом, т.е. Z = X ⊕ K получаем
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, где X и Y - входные и выходные данные функции f без учета перестановок.
Полученное уравнение выполняется на всех раундах алгоритма DES с одинаковой вероятностью P=12/64.
На следующей таблице приведен список эффективных, т.е. имеющих наибольшее отклонение от P=1/2, статистических аналогов для каждого s-блока алгоритма DES.

Построение статистических аналогов для нескольких раундов DES

Покажем теперь каким образом можно объединить статистические аналоги нескольких раундов DES и в итоге получить статистический аналог для всего шифра.
Для этого рассмотрим трехраундовую версию алгоритма:

Применим эффективный статистический аналог 5-го s-блока для вычисления определенных бит значения X(2).
Мы знаем что с вероятностью 12/64 в f-функции выполняется равенство X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, где X - второй входной бит 5-го S-блока, он по сути является 26-м битом последовательности, полученной после расширения входных бит. Анализируя функцию расширения можно установить что на месте 26 бита оказывается 17-й бит последовательности X(1).
Аналогичным образом, Y,…, Y по сути являются 17-м, 18-м, 19-м и 20-м битом последовательности полученной до перестановки P. Исследовав перестановку P, получаем что биты Y,…, Y на самом деле являются битами Y(1), Y(1), Y(1), Y(1).
Бит ключа K вовлеченный в уравнения является 26 битом подключа первого раунда K1 и тогда статистический аналог приобретает следующую форму:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1 .
Следовательно, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) (2) с вероятностью P=12/64.
Зная 3, 8, 14, 25 биты последовательности Y(1) можно найти 3, 8, 14, 25 биты последовательности X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) или с учетом уравнения (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) с вероятностью 12/64.

Найдем подобное выражение используя последний раунд. На этот раз мы имеем уравнение
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) .
Так как
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
получаем, что
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3 (4) с вероятностью 12/64.

Приравняв правые части уравнений (3) и (4) получаем
СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 с вероятностью (12/64) 2 +(1-12/64) 2 .
С учетом того, что X(1) = PR и X(3) = CR получаем статистический аналог
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
который выполняется с вероятностью (12/64) 2 +(1-12/64) 2 =0.7.
Описанный выше статистический аналог можно представить графически следующим образом (биты на рисунке пронумерованы справа налево и начиная с нуля):

Все биты в левой части уравнения известны атакующему, следовательно он может применить алгоритм 1 и узнать значение K1 ⊕ K3. Покажем как с помощью данного статистического аналога можно вскрыть не 1, а 12 бит ключа шифрования K.

Атака на DES с известным открытым текстом

Приведем способ с помощью которого можно расширить атаку и получить сразу 6 бит подключа первого раунда.
Составляя уравнение (5) мы принимали во внимание тот факт, что нам неизвестно значение F1(PR, K1). Поэтому мы использовали его статистический аналог K1 ⊕ PR.
Вернем вместо выражения K1 ⊕ PR значение F1(PR, K1) и получим следующее уравнение:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , которое будет выполняться с вероятностью 12/64. Вероятность изменилась так как мы оставили только статистический аналог из третьего раунда, все остальные значения фиксированы.

Выше мы уже определили, что на значение F1(PR, K1) оказывают влияние входные биты 5-го S-блока, а именно биты ключа K1 и биты блока PR. Покажем каким образом обладая только набором открытых/закрытых текстов можно восстановить значение K1. Для этого воспользуемся алгоритмом 2.

Алгоритм 2
Пусть N - количество известных перед атакой пар открытый/закрытый текст. Тогда для вскрытия ключа необходимо проделать следующие шаги.
For (i=0; i<64; i++) do
{
For(j=0; j {
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) then
T i =T i +1
}
}
В качестве вероятной последовательности K1 принимается такое значение i, при котором выражение |T i -N/2| имеет максимальное значение.

При достаточном количестве известных открытых текстов алгоритм будет с большой вероятностью возвращать корректное значение шести бит подключа первого раунда K1. Объясняется это тем, что в случае если переменная i не равна K1, тогда значение функции F1(PR j , K) будет случайным и количество уравнений для такого значения i, при котором левая часть равна нулю будет стремиться к N/2. В случае же если подключ угадан верно, левая часть будет с вероятностью 12/64 равна фиксированному биту K3. Т.е. будет наблюдаться значительное отклонение от N/2.

Получив 6 бит подключа K1, можно аналогичным образом вскрыть 6 бит подключа K3. Все что для этого нужно, это заменить в уравнении (6) C на P и K1 на K3:
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1 .
Алгоритм 2 возвратит корректное значение K3 потому что процесс расшифровки алгоритма DES идентичен процессу шифрования, просто последовательность ключей меняется местами. Так на первом раунде расшифрования используется ключ K3, а на последнем ключ K1.

Получив по 6 бит подключей K1 и K3 злоумышленник восстанавливает 12 бит общего ключа шифра K, т.к. раундовые ключи являются обычной перестановкой ключа K. Количество открытых текстов необходимых для успешной атаки зависит от вероятности статистического аналога. Для вскрытия 12 бит ключа 3-раундового DES достаточно 100 пар открытых/закрытых текстов. Для вскрытия 12 бит ключа 16-раундового DES потребуется порядка 2 44 пар текстов. Остальные 44 бита ключа вскрываются обычным перебором.

Tutorial