Алгоритмы шифрования. Алгоритм DES.

Как я уже говорил на прошлом уроке, алгоритм шифрования DES -  это стандарт шифрования данных, который был разработан еще в 1974 году компанией IBM. Шифрование происходит на основе ключа длиной 64 бита, из которых 56 приходятся непосредственно на шифрование, а 8 бит - это системные  разряды.

Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

• режим электронной кодовой книги (ECB — Electronic Code Book),
• режим сцепления блоков (СВС — Cipher Block Chaining),
• режим обратной связи по шифротексту (CFB — Cipher Feed Back),
• режим обратной связи по выходу (OFB — Output Feed Back).

Разберем эти режимы более подробно.

Режим электронной кодовой книги заключается в том, что каждый блок открытого текста заменяется блоком шифротекста. Еще этот метод называется методом простой замены. Недостаток ECB, в сравнении c другими режимами шифрования — сохранение статистических особенностей открытого текста. Например, если зашифровать таким методом картинку, то даже в зашифрованном виде сохраниться контру этой картинки.

Рассмотрим это на примере. Исходная картинка (Источник: http://commons.wikimedia.org/wiki/File:Tux.jpg?uselang=ru):

Картинка в зашифрованном виде (Источник http://commons.wikimedia.org/wiki/File:Tux_ecb.jpg?uselang=ru):

Картинка, зашифрованная другим методом шифрования (Источник http://commons.wikimedia.org/wiki/File:Tux_secure.jpg?uselang=ru):

Режим сцепления блоков. Это более надежный метод, чем режим электронной кодовой книги.  Его суть в том, что каждый блок открытого текста (кроме первого) побитово складывается по модулю 2 (операция XOR) с предыдущим результатом шифрования. Это усовершенствованный режим шифрования по сравнению с ECB: каждый блок открытого текста маскируется соответственно блоком шифротекста, полученном на предыдущем этапе. Однако и у него есть недостатки:

• возможность определения начала изменения данных при изменении шифротекста

• возможность переделать открытый текст при перемещении блоков

• подмена шифротекста с следующим за ней изменением открытого текста

Режим обратной связи по шифротексту. Для шифрования следующего блока открытого текста он складывается по модулю 2 с перешифрованным (блочным шифром) результатом шифрования предыдущего блока. Криптостойкость этого метода  определяется криптостойкостью используемого шифра. Фиксированные блоки открытого текста маскируются блоками шифротекста. Если в режиме СFВ с полноблочной обратной связью имеется два идентичных блока шифротекста, результат шифрования на следующем шаге будет тем же.

Режим обратной связи по выходу. Режим (OFB)[5] обратной связи вывода превращает блочный шифр в синхронный шифрпоток: это генерирует ключевые блоки, которые являются результатом сложения с блоками открытого текста, чтобы получить зашифрованный текст. Так же, как с другими шифрами потока, зеркальное отражение в зашифрованном тексте производит зеркально отраженный бит в открытом тексте в том же самом местоположении. Это свойство позволяет многим кодам с исправлением ошибок функционировать как обычно, даже когда исправление ошибок применено перед кодированием.

Шифр DES является блочным шифром. Входными данными для него служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований.

Шифрование начинается с начальных перестановок, затем идет 16 циклов шифрование, после чего конечные перестановки.

Начальные перестановки определяются следующей таблицей:

Иными словами, первые три бита после перестановок - это биты 58,50 и 42, а последние 23,15 и 7.

Полученные таким образом данные участвую в 16-ти итерационных преобразованиях  Фейстеля. Суть этих преобразований состоит в том, что мы разбиваем  блок данных на две части по 32 бита: L(0) и R(0). Где L(0) - старшие биты, R0 - младшие. Весь блок мы обозначим T(0).

Пусть T(i-1)=L(i-1)R(i-1) - это результат i-1 итерации, тогда результат i-ой итерации T(i)=L(i)R(i) определяется следующим образом:

L(i)=R(i-1)

R(i)=L(i) исключающее ИЛИ f((R(i-1),(k(i))

Где функция f - это функция шифрования. Ее аргументами являются 32-битный вектор R(i-1) и 48-битный ключ k(i), который является результатом преобразования 56- битного ключа k.

Считается функция f по следующему алгоритму:

1. Вычисляется функция расширения E.

2. Производиться функция XOR (исключающее или) с ключом k.

3. Производиться преобразование S, состоящее из 8 преобразований S1, S2,  S3, ... S8.

4. Перестановка P.

И сейчас мы эти шаги рассмотрим более подробно. Функция расширения E является перестановкой согласно следующей таблице:

Таким образом, первые три бита вектора E(Ri-1) являются битами 32,1 и 2 вектора Ri-1. Стоит заметить, что некоторые биты дублируются.

Полученный после перестановок вектор E(Ri-1) складывается по модулю 2 (применяется функция XOR) с ключами ki. Затем результат представляется в виде восьми последовательных блоков B1, B2, B3, ... B8. Каждый такой B блок является 6-битным блоком.  

Далее, каждый блок B трансформируется в блок B' с помощью преобразования S. Такое преобразование определяется следующей таблицей:

Предположим, что B3=101111 и мы ходим найти B'3. Первые и последние разряды являются двоичной записью числа  a, лежит в диапазоне от 0 до 3. Средние 4 разряда представляют число b, лежащее в диапазоне от 0 до 15. Строки таблицы S3 нумеруются от 0 до 3, столбцы от 0 до 15. Пара чисел (а, b) определяет число, находящееся в пересечении строки а и столбца b. Двоичное представление этого числа дает B'3. В нашем случае двоичное значение числа a = 11. Десятичное 3. Для числа b двоичное значение 0111, десятичное 7. Таким образом, нам надо взять число на пересечении строки 3 и столбца 7. Это число 7.

Далее идет перестановка P. Она задана следующей таблицей:

Согласно этой таблицы, первые четыре бита результатирующей функции P-преобразования - это 16,17,20,21.

Ключи тоже получаются хитромудрым способом. Они делаются из исходного ключа k, путем разбиения его на 8 ключей ki. Восемь бит, находящихся в позициях 8, 16, 24, 32, 40, 48, 56, 64 убираются из ключа k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Далее делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64), согласно следующей таблице:

Эта перестановка определяется двумя блоками C0 и D0 по 28 бит в каждом. Первые три бита C0 это биты 59, 49 и 41 расширенного ключа. А первые три бита блока D0 - это биты 63,55,47 расширенного ключа. Ci, Di получаються из C(i-1), D(i-1) одним или двумя левыми циклическими сдвигами согласно таблице:

Ключи ki, i=1,...16 состоит из 48 бит, выбранных из битов 56-битного вектора CiDi согласно таблице ниже:

И завершает шифрование конечная перестановка IP-1. Она действует на T16 согласно следующей таблице

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

R(i-1)=Li

L(i-1)=Ri исключающее ИЛИ f(Li,ki)

Ключи ki, функция f, перестановки IP и IP-1 точно такие же, как и в процессе шифрования.