3. Симметричные блоковые шифры

Еще в работе Шеннона «Теория связи секретных систем» были сформулированы следующие основные принципы преобразования сообщений, которые могут обеспечить высокую стойкость блокового шифрования (рис. 9):

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

2) перестановка выполняет перепутывание, перемешивание символов, скрывает частоту появления устойчивых сочетаний символов;

3) итерирование (повторение двух предыдущих пунктов многократно) распространяет (рассредоточивает, рассеивает) влияние отдельных символов открытого текста и отдельных символов ключа на значительное число символов шифртекста.

Рис. 9. Принцип построения блоковых шифров

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

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

000 0, 0011, 0102,..., 1117,

а таблица подстановок задается ключом следующим образом:

{0, 1, 2, 3, 4, 5, 6, 7}{4, 2, 6, 7, 0, 5, 1, 3} .

Это означает, что, например, входной блок 011 будет преобразован в выходной блок 111. Сложность такого преобразования равна 2ⁿ , т.е. равна числу возможных двоичных слов длиноюn, гдеn – длина блока.

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

4. Структура Файстеля

Многие современные блоковые шифры реализуются на основе так называемой структуры Файстеля. Для этого предварительно из секретного ключа=₀при помощи заданного детерминированного преобразования, входящего в описание алгоритма шифрования, формируется последовательность текущих ключей_i ,i = 1, 2,...,d, гдеd –число итераций.

Сама структура Файстеля предполагает следующий способ преобразования блоков. Сначала каждый блок сообщения, образованный последовательностью двоичных символов. длиною n , разбивается пополам на подблоки длиноюn₀ =n/2 (рис. 10). Для этогоnдолжно быть четным

Шифрование каждого блока выполняется отдельно с использованием рекуррентного соотношения

Рис. 10. Подготовка блока для шифрования на основе структуры Файстеля

,i = 1, 2,...,d. Здесь f ( , ) – открытая нелинейная детерминированная функция,i – текущие ключевые элементы, сформированные детерминированным образом из основного секретного ключаданной криптосистемы. Криптограмма образуется на заключительной итерации (i =d) и имеет вид блока

= (_d ,_d +1)

длиною n. Этот блок также составлен из последовательно записанных друг за другом подблоков, но теперь уже_dи_d +1 .Отметим, что примененное объединение подблоков в единый блок называетсяконкатенация.

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

Имеется много различных блоковых шифров, основанных на структуре Файстеля, которые отличаются выбором функции f и способом формирования текущих ключевых элементов_i ,i = 1, 2,…,d, из секретного ключа.