Общие сведения о блочных шифрах

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

Z=EnCrypt(X,Key) и X=DeCrypt(Z,Key)

Z=E(X, K) и X=D(Z, K) (сокращенно)

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

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

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

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

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

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

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

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

1. Функция EnCrypt должна быть обратимой.

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

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

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

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

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

Биективные математические функции
	Сложение	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 для любого из этих преобразований может использоваться:

1. фиксированное число (например, X'=X+125)

2. число, получаемое из ключа (например, X'=X+F(Key))

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

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

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

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

Рассмотрим сеть Фейштеля и блочный криптоалгоритм DES более подробно.

Сеть Фейштеля имеет следующую структуру. Входной блок делится на несколько равной длины подблоков, называемых ветвями. В случае, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Каждая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется несколько циклов или раундов. В случае двух ветвей каждый раунд имеет структуру, показанную на рисунке:

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

Сеть Фейштеля является обратимой даже в том случае, если функция F не является таковой, так как для дешифрования не требуется вычислять F^-1.

Поиск по сайту: