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

6.1. Принципы построения блочных шифров

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

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

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

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

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

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

Получили распространение алгоритмы, в которых осуще­ствляются преобразования над векторами, представляющими собой левую и правую половины содержимого регистра сдвига. Для построения таких алгоритмов часто используется сеть Фейстеля (Feistel Network).

Преобразование, реализуемое сетью Фейстеля в i-м цикле шифрования, имеет вид

(6.1)

где Х – входной блок, разделенный на две половины Х₁ и Х₂, а (Y₁, Y₂) – результат зашифрования блока Х на ключе k_i с помощью функции f_i.

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

Ценность преобразований подобного вида заключается в том, что даже если f_i не является обратимой функцией, преобразование сети Фейстеля обратимо. В самом деле, из (6.1) следует, что