Диференційні характеристики шифру DES

 

 

 

 

 

 

 

 

 

  

 

 

 

 

 

 

 

 

 

 

Рис. 2.2 Один этап DES

Если Bi - это результат i-ой итерации, Li и Ri - левая и правая половины Bi, Ki - 48-битовый ключ для этапа i, а f - это функция, выполняющие все  подстановки, перестановки и XOR с ключом, то этап можно представить как:

Li = Ri-1                                            (2.17) 

                                       (2.18)

 

          Начальная перестановка выполняется  еще до этапа 1, при этом входной  блок переставляется, как показано  в Табл. 2.1. Эту и все другие  таблицы этой главы надо читать  слева направо и сверху вниз. Например, начальная перестановка  перемещает бит 58 в битовую  позицию 1, бит 50 - в битовую  позицию 2, бит 42 - в битовую  позицию 3, и так далее.

Таблица 2.1

 

           Начальная перестановка и соответствующая  заключительная перестановка не  влияют на безопасность DES. (Как  можно легко заметить, эта перестановка  в первую очередь служит для  облегчения побайтной загрузки  данных открытого текста и  шифротекста в микросхему DES. Не  забывайте, что DES появился раньше 16- и 32-битовых микропроцессорных  шин.) Так как программная реализация  этой многобитовой перестановки  нелегка (в отличие от тривиальной  аппаратной), во многих программных  реализациях DES начальная и заключитель-ные  перестановки не используются. Хотя  такой новый алгоритм не менее  безопасен, чем DES, он не соответст-вует  стандарту DES и, поэтому, не  может называться DES.

 

2.3.1 Преобразования ключа

 

Сначала 64-битовый ключ DES уменьшается до 56-битового ключа  отбрасыванием каждого восьмого бита, как показано в Табл. 2.2. Эти  биты используются только для контроля четности, позволяя проверять правиль-ность  ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый подключ. Эти подключи, Ki, определяются следующим  образом.

 

Таблица 2.2

Во первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвига-ются налево на один или два бита в  зависимости от этапа. Этот сдвиг  показан в Табл. 2.3

 

 

 

 

Таблица 2.3

После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и  изменяется их порядок, эта операция называется перестановка со сжатием. Ее результатом является набор из 48 битов. Перестановка со сжатием (также  называемая переставленным выбором) определена в Табл. 2.4 На-пример, бит сдвинутого ключа в позиции 33 перемещается в  позицию 35 результата, а 18-й бит сдвинутого ключа отбрасывается.

Таблица 2.4

Из-за сдвига для каждого подключа используется отличное подмножество битов  ключа. Каждый бит используется приблизительно в 14 из 16 подключей, хотя не все биты используются в точности одинаковое число раз.

 

2. Перестановка с расширением

 

            Эта операция расширяет правую  половину данных, Ri, от 32 до 48 битов.  Так как при этом не просто  повто-ряются определенные биты, но и изменяется их порядок,  эта операция называется перестановкой  с расшире-нием. У нее две задачи: привести размер правой половины  в соответствие с ключом для  операции XOR и полу-чить более  длинный результат, который можно  будет сжать в ходе операции  подстановки. Однако главный криптографический  смысл совсем в другом. За счет  влияния одного бита на две  подстановки быстрее возраста-ет  зависимость битов результата  от битов исходных данных. Это  называется лавинным эффектом. DES спро-ектирован так, чтобы как  можно быстрее добиться зависимости  каждого бита шифротекста от  каждого бита открытого текста  и каждого бита ключа.

         Перестановка с расширением показана  на Рис. 2.3. Иногда она называется E-блоком (от expansion). Для каждого 4-битового  входного блока первый и четвертый  бит представляют собой два  бита выходного блока, а второй  и третий биты - один бит выходного  блока. В Табл. 2.5 показано, какие  позиции результата соответст-вуют  каким позициям исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока.

Рис. 2.3 Перестановка с расширением.

Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.

 

3. Подстановка с помощью S-блоков

 

После объединения сжатого  блока с расширенным блоком с  помощью XOR над 48-битовым результатом  выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках (от substitution). У каждого S-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков.  48 битов  делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, второй - S-блоком 2, и так далее. См. Рис. 2.4

 

Рис. 2.4 Подстановка - S-блоки.

Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4-битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное

Входные биты особым образом  определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: b1, b2, b3, b4, b5 и b6. Биты b1 и b6 объединяются, образуя 2-битовое  число от 0 до 3, соответствующее строке таблицы. Средние 4 бита, с b2 по b5, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу табли-цы.

Например, пусть на вход шестого S-блока (т.е., биты функции XOR с 31 по 36) попадает 110011. Первый и последний бит, объединяясь, образуют 11, что соответствует строке 3 шестого S-блока. Средние 4 бита образу-ют 1001, что соответствует столбцу 9 того же S-блока. Элемент S-блока 6, находящийся  на пересечении строки 3 и столбца 9, - это 14. (Не забывайте, что строки и  столбцы нумеруются с 0, а не с 1.) Вместо 110011 подстав-ляется 1110.

Конечно же, намного легче  реализовать S-блоки программно в  виде массивов с 64 элементами. Для этого  потребуется переупорядочить элементы, что не является трудной задачей. (Изменить индексы, не изменяя по-рядок  элементов, недостаточно. S-блоки спроектированы  очень тщательно.) Однако такой способ описания S-блоков помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4-битового элемента: b2 по b5являются входом, а некоторое 4-битовое число - результатом. Биты b1 и b6 опреде-ляются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном S-блоке.

Подстановка с помощью S-блоков является ключевым этапом DES. Другие действия алгоритма линейны и легко  поддаются анализу. S-блоки нелинейны, и именно они в большей степени, чем все остальное, обеспечи-вают безопасность DES.

В результате этого этапа  подстановки получаются восемь 4-битовых  блоков, которые вновь объединяются в единый 32-битовый блок. Этот блок поступает на вход следующего этапа - перестановки с помощью P-блоков.

 

2.3.4 Перестановка с помощью  P-блоков

 

32-битовый выход подстановки  с помощью S-блоков, перетасовываются  в соответствии с P-блоком. Эта  пе-рестановка перемещает каждый  входной бит в другую позицию,  ни один бит не используется  дважды, и ни один бит не  игнорируется. Этот процесс называется  прямой перестановкой или просто  перестановкой. Пози-ции, в которые  перемещаются биты, показаны в  Табл. 12-7. Например, бит 21 перемещается  в позицию 4, а бит 4 - в позицию  31.

Таблица 2.7  Перестановка с помощью P-блоков

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

 

5. Заключительная перестановка

 

Заключительная перестановка является обратной по отношению к  начальной перестановки и описана  в Табл. 2-8. Обратите внимание, что  левая и правая половины не меняются местами после последнего этапа DES, вместо этого объединенный блок R16L16 используется как вход заключительной перестановки. В этом нет ничего особенного, перестановка половинок  с последующим циклическим сдвигом  привела бы к точно такому же результату. Это сделано для того, чтобы  алгоритм можно было использовать как  для шифрования, так и для дешифрирования.

Таблица 2.8

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

DES позволяет использовать  для шифрования или дешифрирования  блока одну и ту же функцию.  Единственное отличие состоит  в том, что ключи должны использоваться  в обратном порядке. То есть, если на этапах шифрования  использовались ключи K1, K2, K3, ..., K16, то ключами дешифрирования будут  K16, K15, K14, ..., K1. Алгоритм, который создает  ключ для каждого этапа, также  цикличен. Ключ сдвигается направо,  а число пози-ций сдвига равно  0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.

FIPS PUB 81 определяет четыре  режима работы: ECB, CBC, OFB и CFB . Банковские  стандарты ANSI определяют для шифрования ECB и CBC, а для проверки подлинности  - CBC и n- битовый CFB .

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

 

3 ПОСТРОЕНИЕ ПРОГРАММНОГО  КОМПЛЕКСА ДЛЯ ИССЛЕДОВАНИЯ СВОЙСТВ  БСШ DES

 

1. Построение таблиц дифференциальных разностей

 

Исследования, проведенные  в работах [5,6,7], показали, что среднее  значение максимумов таблиц XOR разностей  является специфическим показателем  для шифрующих преобразований, выполняемых  современными БСШ, в то время как  многие из подходов к оценке дифференциальных свойств шифров строятся на основе изучения свойств входящих в шифр подстановочных преобразований (S-блоков), а не шифров в целом как подстановок.

Учитывая жесткую связь  дифференциальных свойств шифрующих  преобразований с показателями их стойкости  к атакам дифференциального криптоанализа, будет полезным определить какими дифференциальными  свойствами (распределением переходов  таблицы XOR-разностей и средними значениями максимумов переходов) должен обладать БСШ, чтобы он был максимально  близок к случайной подстановке.

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

Дифференциальный криптоанализ, таким образом, основан на установлении разностей , которые переходят при  шифровании в выходные разности   с некоторой высокой вероятностью p [8].

Под "высокой" подразумевается  вероятность значительно более  высокая, чем 1/2n  средняя вероятность  того, что некоторый дифференциал (,) поддерживается для случайной  подстановки.

Такой дифференциал обнаруживается сначала путем оценки вероятностей всех возможных дифференциалов для  каждого S-блока, а затем предпринимается  попытка соединить эти дифференциалы  вместе для того, чтобы, в конце  концов, получить дифференциал (,) для  целого шифра [8]. Таблица, содержащая вероятности, связывающие пары входов и выходов  различных S-блоков называется таблицей распределении XOR разностей. С использованием этих таблиц можно определить параметр, измеряющий сопротивляемость S-блоков дифференциальному криптоанализу, как это было сделано для линейного  криптоанализа: -параметр для q ´ r  S-блока S есть вероятность наилучшего дифференциала (разности) через этот S-блок :

 

  (3.1)

 

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

 Сам алгоритм различения  состоит в следующем :