2.1. Теория шифров с секретным ключом

Блочные и поточные системы шифрования

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

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

Естественно, что точное значение мощности алфавита, начиная с которого шифр следует считать уже не поточным, а блочным, назвать нельзя. Более того, с развитием техники эта характеристика меняется в сторону увеличения. Например, в настоящее время используются 16- и 32-разрядные процессоры, а перспективная шифровальная техника проектируется уже на 64-разрядных процессорах. Поэтому при построении поточных шифров могут быть использованы алфавиты мощности 232 и 264.

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

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

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

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

117

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

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

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

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

Li–1 Ri–1

f ki

Li	Ri

Рис. 2.1. Сеть Фейстеля

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

Li Ri 1 ,	(5)
Ri Li 1 fi Ri 1 , ki ,

где Li-1 и R i-1 – левая и правая части входного блокаLi и R i – левая и правая части блока,

являющегося результатом зашифрования входного блока на ключе ki с помощью функции fi. 118

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

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

Li 1 Ri			f i Li , k i ,
R	i 1	L .
		i

Примеры блочных шифров Стандарт шифрования данных ГОСТ 28147-89

ВРоссии установлен единый алгоритм криптографического преобразования данных – ГОСТ 28147-89. Этот алгоритм предназначен для аппаратной и программной реализации, удовлетворяет необходимым криптографическим требованиям и не накладывает ограничений на степень секретности защищаемой информации. Алгоритм реализует шифрование 64-битовых блоков данных с помощью 256-битового ключа.

ГОСТ 28147-89 содержит описание алгоритмов нескольких уровней. На самом верхнем находятся практические алгоритмы, предназначенные для шифрования массивов данных и выработки для них имитовставки. Все они опираются на три алгоритма низшего уровня, называемые в тексте ГОСТа циклами. Будем называть эти фундаментальные алгоритмы базовыми циклами, чтобы отличать их от всех прочих циклов. Они имеют следующие названия и обозначения, последние приведены в скобках и смысл их будет объяснен позже:

цикл зашифрования (32-З);

цикл расшифрования (32-Р);

цикл выработки имитовставки (16-З).

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

основным шагом криптопреобразования.

Таким образом, чтобы разобраться в ГОСТе, надо понять три следующие вещи:

1.что такое основной шаг криптопреобразования;

2.как из основных шагов складываются базовые циклы;

3.как из трех базовых циклов складываются все практические алгоритмы

ГОСТа.

119

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

1.Ключ является массивом из восьми 32-битных элементов кода и обозначается символом K: K = {Ki}0 i 7. В ГОСТе элементы ключа используются как 32-разрядные целые числа без знака: 0 Ki < 232. Таким образом, размер ключа составляет 32 8=256 бит или 32 байта.

2.Таблица замен является матрицей 8 16, содержащей 4-битовые элементы, которые можно представить в виде целых чисел от 0 до 15. Строки таблицы замен называются узлами замен, они должны содержать различные значения, то есть каждый узел замен должен содержать 16 различных чисел от 0 до 15 в произвольном порядке. Таблица замен обозначается символом H: H = {Hi,j}

0 ij 7 , 0 Hi,j 15. Таким образом, общий объем таблицы замен равен: 8 узлов

0 15

16 элементов/узел 4 бита/элемент = 512 бит или 64 байта.

Основной шаг криптопреобразования.

Основной шаг криптопреобразования по своей сути является оператором, определяющим преобразование 64-битового блока данных. Дополнительным параметром этого оператора является 32-битовый блок, в качестве которого используется какой-либо элемент ключа. Схема алгоритма основного шага приведена на рисунке 2.2.

120

0

Начало (N, X)

1

S =(N1+X)mod 232

m = 0 .. 7

2

Sm = Hm,Sm

3

S = 11(S)

4

S = S N2

5

N2=N1, N1=S

6

Конец (N)

Рис. 2.2. Схема основного шага криптопреобразования алгоритма ГОСТ 28147-89

Ниже даны пояснения к алгоритму основного шага:

0.Определяет исходные данные для основного шага криптопреобразования:

N – преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая (N1) и старшая (N2) части обрабатываются как отдельные 32битовые целые числа без знака. Таким образом, можно записать N=(N1,N2).

X – 32-битовый элемент ключа;

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

2.Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода:

S = (S0, S1, S2, S3, S4, S5, S6, S7).

Далее значение каждого из восьми блоков заменяется на новое, которое

выбирается по таблице замен следующим образом: значение блока Si заменяется на Si -тый по порядку элемент (нумерация с нуля) i-того узла замен (т.е. i-той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным

номеру заменяемого блока, и номером столбца, равным значению заменяемого 121