Блочные шифры

Блочные шифры оперируют с блоками открытого текста. К ним предъявляются следующие требования:

• достаточная криптостойкость;
• простота процедур зашифрования и расшифрования;
• приемлемая надежность.

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

Каким условиям должен удовлетворять стойкий блочный шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории шифрования: такой шифр должен обладать свойствами перемешивания и рассеивания:

• Рассеивание - это свойство шифра, при котором один символ (бит) исходного текста влияет на несколько символов (битов) шифротекста, оптимально - на все символы в пределах одного блока.

Если данное условие выполняется, то при шифровании двух блоков данных с минимальными отличиями между ними должны получаться совершенно непохожие друг на друга блоки шифротекста. Точно такая же картина должна иметь место и для зависимости шифротекста от ключа - один символ (бит) ключа должен влиять на несколько символов (битов) шифротекста;

• Перемешивание - это свойство шифра скрывать зависимости между символами исходного текста и шифротекста.

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

Характерной особенностью блочных алгоритмов шифрования является тот факт, что в ходе своей работы они производят преобразование блока входной информации фиксированной длины и получают результирующий блок того же объема, но недоступный для прочтения сторонним лицам, не владеющим ключом. Таким образом, схему работы блочного шифра можно описать функциями Z=EnCrypt(X,Key) и X=DeCrypt(Z,Key).

Ключ Key является параметром блочного криптоалгоритма и представляет собой некоторый блок двоичной информации фиксированного размера. Исходный (X) и зашифрованный (Z) блоки данных также имеют фиксированную разрядность, равную между собой, но необязательно равную длине ключа.

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

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

Таблица 6.2.1.1

Криптоалгоритм именуется идеально стойким, если прочесть зашифрованный блок данных можно только перебрав все возможные ключи, до тех пор, пока сообщение не окажется осмысленным. Так как по теории вероятности искомый ключ будет найден с вероятностью 1/2 после перебора половины всех ключей, то на взлом идеально стойкого криптоалгоритма с ключом длины N потребуется в среднем 2^N-1 проверок. Таким образом, в общем случае стойкость блочного шифра зависит только от длины ключа и возрастает экспоненциально с ее ростом. Даже предположив, что перебор ключей производится на специально созданной многопроцессорной системе, в которой благодаря диагональному параллелизму на проверку 1 ключа уходит только 1 такт, то на взлом 128 битного ключа современной технике потребуется не менее 10²¹ лет. Естественно, все сказанное относится только к идеально стойким шифрам.

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

Таким образом, на функцию стойкого блочного шифра Z=EnCrypt(X,Key) накладываются следующие условия:

1. Функция EnCrypt должна быть обратимой.
2. Не должно существовать иных методов прочтения сообщения X по известному блоку Z, кроме как полным перебором ключей Key.
3. Не должно существовать иных методов определения, каким ключом Key было произведено преобразование известного сообщения X в сообщение Z, кроме как полным перебором ключей.

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

Все действия, производимые над данным блочным криптоалгоритмом, основаны на том факте, что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности. Так, например, 32-битный блок данных можно интерпретировать как число из диапазона 0..4'294'967'295. Кроме того, блок, разрядность которого обычно является "степенью двойки", можно трактовать как несколько независимых неотрицательных чисел из меньшего диапазона (рассмотренный выше 32-битный блок можно также представить в виде 2 независимых чисел из диапазона 0..65535 или в виде 4 независимых чисел из диапазона 0..255).

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

Таблица 6.2.1.2

Биективные математические функции
	Сложение	X'=X+V
	Исключающее ИЛИ	X'=X XOR V
-	Умножение по модулю 2N+1	X'=(X*V) mod (2N+1)
	Умножение по модулю 2N	X'=(X*V) mod (2N)
Битовые сдвиги
	Арифметический сдвиг влево	X'=X SHL V
	Арифметический сдвиг вправо	X'=X SHR V
	Циклический сдвиг влево	X'=X ROL V
	Циклический сдвиг вправо	X'=X ROR V
Табличные подстановки
	S-box (англ. substitute)	X'=Table[X,V]

В качестве параметра V для любого из этих преобразований может использоваться:

• фиксированное число (например, X'=X+125);
• число, получаемое из ключа (например, X'=X+F(Key));
• число, получаемое из независимой части блока (например, X₂'=X₂+F(X₁)) .

Последний вариант используется в схеме, названной по имени ее создателя сетью Фейстеля (нем. Feistel).

Классическая сеть Фейстеля имеет структуру, представленную на рисунке 6.2.1.1.

Рисунок 6.2.1.1 - Классическая сеть Фейстеля

При этом правая часть блока будет называтья R (right), а левая - L (left). Ключ называется К (key), а элементарная функция шифра - F. Поскольку данный шифр итеративный, то на каждом цикле будет индекс i, показывающий номер этой итерации. Каждый следующий цикл (i) определяется значением, полученным на предыдущем цикле. С точки же зрения алгебры это выглядит примерно так:

L_i = R_i-1

R_i = L_{i -1} XOR F(R_{i -1}, K_i)

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

L_{i -1} XOR F(R_{i -1}, K_i) XOR F(_{Ri -1}, K_i) = L_{i -1}

Шифр, использующий эту методику, гарантированно обратим, если можно восстановить данные для функции F на каждом раунде (а это подключ цикла и данные предыдущего цикла). При этом тип самой функции совершенно не важен! Использование сколь угодно сложной функции не требует использования двух алгоритмов для зашифрования и расшифрования - алгоритм автоматически работает за счет самой методики сети Фейстеля.

Сеть Фейстеля надежно зарекомендовала себя как криптостойкая схема произведения преобразований, и ее можно найти практически в любом современном блочном шифре. Незначительные модификации касаются обычно дополнительных начальных и оконечных преобразований над шифруемым блоком. Подобные преобразования, выполняемые обычно также либо "исключающим ИЛИ" или сложением, имеют целью повысить начальную рандомизацию входного текста. Таким образом, криптостойкость блочного шифра, использующего сеть Фейстеля, определяется на 95% функцией F.

The Data Encryption Standard (DES)

Система шифрования DES была разработана IBM под именем Lucifer в 1976 году. В ней применялся ключ длиной 56 бит. В стандарте DES применены перестановки специального вида, что и наводило на мысль об известных АНБ (Агентство национальной безопасности США) слабых местах системы. Однако принцип этого шифрования прошел самую широкую апробацию. Нарекания вызывали лишь выбранные короткими длины блока в 64 бита и ключа в 56 бит, что недостаточно для задач национальной безопасности. Свое развитие DES получил в ГОСТ 28147-89, который увеличил длину ключа до 256 бит и допустил произвольные перестановки.

Шифр DES принят федеральным стандартом США. Он хорош для многих коммерческих приложений, но недостаточно стоек от атак аналитиков. Например, 16‑кратный DES был взломан Шамиром с помощью дифференциального криптоанализа и Матсуи с помощью линейного криптоанализа. Серьезную практическую атаку на DES осуществил Мишель Винер. Все вышесказанное означает, что DES нельзя использовать для серьезных приложений. Для исправления этого положения некоторые коммерсанты используют так называемый "тройной DES", шифруя сообщение трижды двумя различными ключами. Это увеличивает реальную длину ключа до 112 бит, но такой метод медленнее обычного DES в три раза.

Общая схема алгоритма представлена на рисунке 6.2.1.2.

Рисунок 6.2.1.2 – Общая схема алгоритма DES

Cхема шифрования (расшифрования) DES представлена на рисунке 6.2.1.3.

Рисунок 6.2.1.3 - Схема шифрования (расшифрования) DES

Схема функции F представлена на рисунке 6.2.1.4.

Рисунок 6.2.1.4 - Схема функции F

Описание алгоритма:

Шаг 1.На i-м цикле входной блок xⁱ длиной 64 символа xⁱ = (x_i,0, x_i,1 ..., x_i,63) делится на два блока по 32 символа X =(x_i,0, x_i,1 ..., x_i,31) и X' = (x'_i,0, x'_i,1 ..., x'_i,31).

Правый блок X'разбивается на восемь блоков по четыре символа:

Эти восемь блоков путем копирования крайних элементов преобразуются в восемь блоков из шести символов:

Формирование ключей показано на рисунке 6.2.1.5.

Рисунок 6.2.1.5 - Формирование ключей

Шаг 2.На i-й циклической итерации 48 разрядов ключа(k_i,0, k_i,1, ... , k_i,47) поразрядно суммируются (по модулю 2) с полученными выше 48 разрядами данных.

Шаг 3. j-й блок из шести символов (0Ј j <8) подается на вход блока подстановки (S‑бокс), S[j] имеет шестиразрядный вход и четырехразрядный выход и представляет собой четыре преобразования из Z_2,4 в Z_2,4; два крайних разряда входного блока служат для выборки одного из этих преобразований. Каждая из восьми подстановок S[0], S[1],..., S[7] осуществляется с использованием четырех строк и 16 столбцов матрицы с элементами {0,1,...,15}. Каждый из массивов размерностью 4ґ16 определяет подстановку на множестве Z_2,4 следующим образом. Если входом является блок из шести символов (z₀, z₁, z₂, z₃, z₄, z₅), то две крайние позиции (z₀, z₅) интерпретируются как двоичное представление целых чисел из набора {0,1,2,3}.

Эти целые определяют номер строки (от 0 до 3). Оставшиеся четыре символа (z₁, z₂, z₃, z₄) интерпретируются как двоичное представление целых чисел из набора {0,1,...,15} и служат для определения столбца в массиве (от 0 до 15). Таким образом, входной блок (0,0,1,0,1,1) соответствует строке 1 и столбцу 5.

Шаг 4. 32 разряда, составляющие выход S-бокса, подаются на вход блока проволочной коммутации (P-бокс).

Шаг 5. Компоненты правого входного 32-разрядного блока X', преобразованного в T(X'), поразрядно суммируются по модулю 2 с компонентами левого входного 32‑разрядного блока X.

На каждой итерации используется 48-разрядный ключ (k_i,0, k_i,1 ..., k_i,47). Поскольку входным ключом DES является 56-разрядный блок k = (k_i,0, k_i,1 ..., k_i,55), то каждый его разряд используется многократно. Какой именно из ключей используется на i-й циклической итерации, определяется списком ключей. Для описания списка ключей введены дополнительные элементы.

Ключ определяется по следующему алгоритму:

§ производится начальная перестановка PC-1 ключа 56-разрядного ключа пользователя k = (k_i,0, k_i,1 ..., k_i,55). Получаемый в результате 56-разрядный блок рассматривается как два 28-разрядных блока: левый – C₀ и правый – D₀;

§ производится левый циклический сдвиг блоков C₀ и D₀ s[1] раз для получения блоков C₁ и D₁;

§ из сцепления блоков (C₁, D₁) выбираются 48 разрядов с помощью перестановки PC-2. Эти разряды используются на первой итерации;

§ используемые на i-й циклической итерации разряды ключа определяются методом индукции. Для получения блоков C_i и D_i производим левый циклический сдвиг s[i] раз блоков C_i–1 и D_i–1.

Инверсией DES (обеспечивающей расшифрование зашифрованных посредством DES данных) является DES^-1 = IP^-1ґp_T1ґp*ґ...ґp*ґ p_T16 ґIP.

Расшифрование зашифрованного посредством DES текста осуществляется с использованием тех же блоков благодаря обратимости преобразования. Таков общий алгоритм DES.

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

Однако данный алгоритм, являясь первым опытом стандарта шифрования, имеет ряд недостатков. За время, прошедшее после создания DES, компьютерная техника развилась настолько быстро, что оказалось возможным осуществлять исчерпывающий перебор ключей и тем самым раскрывать шифр. Стоимость этой атаки постоянно снижается. В 1998г. была построена машина стоимостью около 100000 долларов, способная по данной паре <исходный текст, шифрованный текст> восстановить ключ за среднее время в 3 суток. Таким образом, DES, при его использовании стандартным образом, уже стал далеко не оптимальным выбором для удовлетворения требованиям скрытности данных.