Базовая идея блочного шифра

Отправной точкой в реализации рассматриваемого подхода является идея вырабатывать гамму для зашифрования сообщения … из самого сообщения! Однако сделать это непосредственно невозможно, так как при этом возникают трудности с расшифрованием: пусть гамма вырабатывается из шифруемого блока согласно уравнению G = f(T), где f – некоторая функция. При этом уравнение зашифрования будет иметь следующий вид: С = E_K(T) = T ° G = T ° f(T). Для расшифрования сообщения его получатель должен решить это уравнение относительно T: T ° f(T) = С. Если функция f сложна и нелинейна, что требуется для достаточной стойкости шифра, данная задача может оказаться практически неразрешимой.

Тем не менее, при разработке новой криптографической схемы нам не хотелось бы отказываться от ранее использованных и хорошо зарекомендовавших себя решений, к числу которых относится наложение гаммы на данные для их шифрования. Как же выйти из того затруднительного положения, в котором мы оказались? Попытаемся решить хотя бы часть проблемы, для чего представим шифруемый массив данных T размера ïTï = N в виде пары блоков меньшего размера: T = (T₀,T₁), ïT₀ï = N₀, ïT₁ï = N₁, N₀ + N₁ = N, где T₀будет обозначать младшую, а T₁– старшую часть массива T. Выполним зашифрование старшего блока с помощью младшего, используя при этом некоторую функцию f, отображающую N₁-битовый блок данных на N₀-битовый, и обратимую бинарную операцию °над N₀-битовыми блоками данных. Полученное шифрующее преобразование обозначим через . Уравнение этого преобразования будет следующим:

Для легко построить обратное, или расшифровывающее преобразование :

Действительно, если бинарные операции °и •взаимно обратные, каков бы ни был N-битовый блок данных T = (T₀, T₁), всегда справедливо следующее равенство:

Ясно, что назначение функции f заключается в том, чтобы маскировать зависимость между блоком T₀ и гаммой для шифрования блока T₁, которая из него вырабатывается. Для этого функция f должна быть секретным элементом нашего шифра – мы пока закроем глаза на это нарушение принципа Кирхгофа. Отметим очень важный факт: наша схема работоспособна при любой функции f, после расшифрования мы всегда получим те же самые данные, которые были перед зашифрованием.

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

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

1. Назовем композицией преобразований A и B такое преобразование C = AB, что каков бы ни был блок данных T, всегда выполняется равенство C(T) = B(A(T)). Таким образом, по определению композиции AB(T) = B(A(T)).

2. Для композиции преобразований справедлив ассоциативный закон, то есть для любых преобразований A, B, C справедливо тождество: A(BC) = (AB)C. Действительно, каким бы ни был блок данных T, справедливо следующее равенство: (A(BC))(T) = BC(A(T)) = C(B(A(T))) = C(AB(T)) = ((AB)C)(T). Поэтому в выражении для композиции трех и более преобразований скобки излишни: A(BC) = (AB)C = ABC.

3. Среди всех преобразований существует одно особое, называемое тождественным и обозначаемое нами через I. Отличительной особенностью данного преобразования является то, что оно оставляет свой аргумент неизменным: каков бы ни был блок данных T , всегда справедливо I(T) = T. Очевидно, что композиция любого преобразования A с тождественным дает в результате это же преобразование A: IA = AI = A. Действительно, для любого блока данных T справедливы следующие равенства: AI(T) = I(A(T)) = A(T) и IA(T) = A(I(T)) = A(T).

4. Преобразование B называется обратным к преобразованию A, если их композиция является тождественным преобразованием, то есть если выполняется условие AB = I или для произвольного блока данных T справедливо равенство B(A(T)) = T. Преобразование A называется обратимым, если существует обратное к нему преобразование, обозначаемое A^–1: A A^–1 = I.

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

Теперь вспомним про то, что предложенная нами схема решила лишь половину проблемы, так как младшая часть T₀ блока T осталась незашифрованной. Но эта проблема имеет очевидное решение: на следующем шаге необходимо зашифровать часть T₀ массива T, используя элемент гаммы, выработанный из части блока T с использованием некоторой другой функции g, отображающей N₀-битовые блоки данных на N₁-битовые. Теперь обе части исходного блока окажутся зашифрованными. По ряду причин, однако, принято, что шифруемая на каждом таком шаге и используемая для выработки гаммы части находятся на фиксированных позициях внутри блока – традиция предписывает вырабатывать гамму из младшей части и накладывать ее на старшую. По крайней мере, дело обстоит именно так в ГОСТе, DESе, и всех других шифрах, построенных по их образу и подобию. Для того, чтобы обеспечить указанное свойство, между шагами шифрования необходимо выполнить перестановку частей блока, помещающую соответствующие части на надлежащие места.

По соображениям обеспечения максимальной криптостойкости и эффективности реализации шифра целесообразно взять размеры старшей и младшей частей шифруемого блока одинаковыми: N₀ = N₁ = . Именно такое условие выбрали разработчики большинства шифров рассматриваемой архитектуры. В этом случае между шагами алгоритма части шифруемого блока просто меняются местами. Однако существуют шифры, не подчиняющиеся этому правилу, о них будет сказано несколько слов ниже в настоящей статье.

Обозначим через S операцию перестановки старшей и младшей частей массива информации: S(T) = S(T₀, T₁) = (T₁, T₀). Очевидно, что операция S является обратной для самой себя: S² = S · S = I. Действительно, для произвольного блока данных T = (T₀, T₁) справедливо равенство:

S²(T) = S²(T₀, T₁) = S(S(T₀, T₁)) = S(T₁, T₀) = (T₀, T₁) = T.

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

При этом обратное, или расшифровывающее преобразование может быть представлено следующим соотношением:

Действительно, справедливо следующее равенство:

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

Как уже отмечалось выше, существуют шифры, в которых шифруемый блок данных делится на две не одинаковые по размеру части. Если элемент гаммы вырабатывается из младшей части блока, имеющей размер N₀ и накладывается на старшую часть, имеющую размер N₁, то схема более устойчива к криптоанализу когда выполняется условие N₁ < N₀. При этом просто менять местами части блока между шагами шифрования уже не годится, необходимо после каждой такой перестановки заново разбивать блок на части. Обычно в такой ситуации используют циклический сдвиг (вращение) блока на N₁ бит влево или вправо, а при расшифровании между шагами необходимо будет повернуть блок на такое же число битов в обратную сторону. В указанном случае выражения для преобразований зашифрования и расшифрования блока будут следующими:

, ,

где через и обозначены операторы вращения блока данных на m бит влево и вправо соответственно. Поскольку за один шаг алгоритма шифруется N₁ < битов блока, то для зашифрования всего блока потребуется более двух шагов. Точное значение числа минимально требуемых шагов в таком алгоритме равно , где через éxù обозначен результат округления числа x до ближайшего целого в сторону увеличения. Из соображения простоты реализации шифра обычно выбирают N₁ так, чтобы размер блока N делился на него без остатка. Как правило, если N = 64, то берут N₁ = 16 или N₁ = 8.

Следует отметить, что шифров, построенных по такому принципу, намного меньше чем шифров, в которых блок делится на две одинаковые по размеру части. Обусловлено это тем, что в них за один шаг шифруется меньшее количество битов, и, соответственно, требуется больше шагов. По такому принципу, например, построен шифр под кодовым названием «албер», созданный в недрах одного из многочисленных НИИ, и, поговаривают, даже претендовавший на место Российского стандарта шифрования, для него N₁ = 8.