Современные симметричные криптосистемы

СОВРЕМЕННЫЕ СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ

По мнению К. Шеннона [83J, в практических шифрах необходимо использовать два общих принципа: рассеивание и перемешивание.

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

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

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

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

При многократном чередовании простых перестановок и подстановок, управляемых достаточно длинным секретным ключом, можно получить очень стойкий шифр с хорошим рассеиванием и перемешиванием. Рассмотренные ниже криптоалгоритмы DES, IDEA и отечественный стандарт шифрования данных построены в полном соответствии с указанной методологией.
1. Американский стандарт шифрования данных DES

Стандарт шифрования данных DES (Data Encryption Standard) опубликован в 1977 г. Национальным бюро стандартов США.

Стандарт DES предназначен для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 г. был одобрен Национальным институтом стандартов и технологий США (НИСТ). С этого момента DES превращается в стандарт не только по названию (Data Encryption- Standard), но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования и расшифрования информации в сетях передачи данных.

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

Основные достоинства алгоритма DES:

• используется только один ключ длиной 56 бит;

• зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой пакет программ, соответствующий стандарту DES;

• относительная простота алгоритма обеспечивает высокую скорость обработки;

• достаточно высокая стойкость алгоритма.

Первоначально метод, лежащий в основе стандарта DES, был разработан фирмой IBM для своих целей и реализован в виде системы "Люцифер". Система "Люцифер" основана на комбинировании методов подстановки и перестановки и состоит из чередующейся последовательности блоков перестановки и подстановки. В ней использовался ключ длиной 128 бит, управлявший состояниями блоков перестановки и подстановки. Систем Люцифер" оказалась весьма сложной для практической реализации из-за отно83сительно малой скорости шифрования (2190 байт/с- программная реализация, 96970 байт/с - аппаратная реализация).

Алгоритм DES также использует комбинацию подстановок и перестановок. DES осуществляет шифрование 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 бит - проверочные биты для контроля на четность). Дешифрование в DES является операцией, обратной шифрованию, и выполняется путем повторения операций шифрования в обратной последовательности. Обобщенная схема процесса шифрования в алгоритме DES показана на рисунке 1. Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, в конечной перестановке битов.

Рисунок 3.1  Обобщенная схема шифрования в алгоритме DES

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

Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. При описании алгоритма DES (рисунке 2) применены следующие обозначения:

L и R - последовательности битов (левая (left) и правая (right));

Рисунок 2  Структура алгоритма DES

LR - конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

Ф - операция побитового сложения по модулю 2.

Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помощью матрицы начальной перестановки IP (таблица 1).

Таблица 1  Матрица начальной перестановки IP

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

Биты входного блока Т (64 бита) переставляются в соответствии с матрицей IP: бит 58 входного блока Т становится битом 1, бит 50 - битом 2 и т.д. Эту перестановку можно описать выражением То = IP(T). Полученная последо-вательность битов То разделяется на две последовательности: Lo - левые или старшие биты, Ro-правые или младшие биты, каждая из которых содержит 32 бита.

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Т, - результат i-й итерации:

Т_i = L_i R_i,

где L_i = t₁ t₂ ... t₃₂ (первые 32 бита); R_i = t₃₃ t₃₄... t₆₄ (последние 32 бита). Тогда результат i-й итерации описывается следующими формулами:

L_i = R _{i -1}, i = 1,2.....16;

R_i =L_i-1  f (R_i-1, K_i ), i = 1,2.....16.
Функция f называется функцией шифрования. Ее аргументами являются последовательность R_i_-1, получаемая на предыдущем шаге итерации, и 48-битовый ключ К_i, который является результатом преобразования 64-битового ключа шифра К. (Подробнее функция шифрования f и алгоритм получения ключа К_i, описаны ниже.)

На последнем шаге итерации получают последовательности R₁₆ и L₁₆ (без перестановки местами), которые конкатенируются в 64-битовую последовательность R₁₆L₁₆.

По окончании шифрования осуществляется восстановление позиций битов с помощью матрицы обратной перестановки IP^-1 (таблица 2).

Таблица 2 Матрица обратной перестановки IP^-1

40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62/	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	57	25

Пример того, как соотносятся элементы первой строки матрицы IP^-1 с элементами матрицы IP приведен в таблице 3.

Таблица 3  Связь элементов матриц

Элемент матрицы IP^-1	Элемекг матрицы IP
40	01
8	02
48	03
16	04
56	05
…	…

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP"1, а затем над последовательностью битов R16Li6 выполняются те же действия, что и в процессе шифрования, но в обратном порядке.

Итеративный процесс расшифрования может быть описан следующими формулами:
R _{i -1} = L_i, i = 1,2.....16;
L_i-1 R_i = R_i  f (R_i-1, K_i ), i = 1,2.....16.
Таким образом, для процесса расшифрования с переставленным входным блоком R₁₆L₁₆ на первой итерации используется ключ К₁₆, на второй итерации - К₁₅ и т.д. На 16-й итерации используется ключ K₁. На последнем шаге итерации будут получены последовательности Lo и Ro, которые конкатенируются в 64-битовую последовательность LoRo. Затем в этой последовательности 64 бита переставляются в соответствии с матрицей IP. Peзультат такого преобразования - исходная последовательность битов (расшифрованное 64-битовое значение).

Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f (R_i_-1, K_i ) показана на рисунке 3.

Рисунок 3  Схема вычисления функции шифрования f

Для вычисления значения функции f используются:

• функция Е (расширение 32 бит до 48);

• функция S_l , S₂, ..., S₈ (преобразование 6-битового числа в 4-битовое);

• функция Р (перестановка битов в 32-битовой последовательности).

Приведем определения этих функций.

Аргументами функции шифрования f являются R_i_-1 (32 бита) и К_i, (48 бит). Результат функции Е(R_i_-1) есть 48-битовое число. Функция расширения Е, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), определяется таблицей 4.

В соответствии с таблицей 4 первые три бита Е(R_i_-1) - это биты 32, 1 и 2, а последние - 31, 32, 1. Полученный результат (обозначим его Е(R_i_-1)) складывается по модулю 2 (операция XOR)

Таблица 4  Функция расширения Е

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	'1	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

с текущим значением ключа К_i и затем разбивается на восемь 6-битовых блоков В₁, В2,.....,В8:

Е (К_i_-1 )  К_i = В₁, В₂,.....,В₈.

Далее каждый из этих блоков используется как номер элемента в функциях-матрицах S₁, S₂, ..., S₈, содержащих 4-битовые значения (таблица 5).

Следует отметить, что выбор элемента в матрице S_j осуществляется достаточно оригинальным образом. Пусть на вход матрицы S_j поступает 6-битовый блок В_j, = b₁ b₂ b₃ b₄ b₅ b₆, тогда двухбитовое число b₁ b₆ указывает номер строки матрицы, а четырехбитовое число b₂ b₃ b₄ b₅ - номер столбца. Например, если на вход матрицы S₁ поступает 6-битовый блок b₁ b₂ b₃ b₄ b₅ b₆ = 100110, то 2-битовое число b₁ b₆ = 10₍₂₎ = 2₍₁₀₎ указывает строку с номером 2 матрицы S₁ а 4-битовое число b₂ b₃ b₄ b₅=0011₍₂₎=3_(1О) указывает столбец с номером 3 матрицы S_1. Это означает, что в матрице S₁ блок В₁ = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8₍₁₀₎ = =1000₍₂₎. Совокупность 6-битовых блоков B₁, B ₂, …,B ₈ обеспечивает выбор четы-рехбитового элемента в каждой из матриц S₁, S ₂, …, S ₈.

В результате получаем S₁(B₁), S ₂(B₂), …, S ₈(B₈), т.е. 32-битовый блок (поскольку матрицы S_j, содержат 4-битовые элементы). Этот 32-битовый блок преобразуется с помощью функции перестановки битов Р (таблица 6).

Таким образом, функция шифрования

R_i  f (R_i-1, K_i )=Р(S₁(B₁), S ₂(B₂), …, S ₈(B₈))

Как нетрудно заметить, на каждой итерации используется новое значение ключа К_j (длиной 48 бит). Новое значение ключа К_j вычисляется из начального ключа К (рисунок 4). Ключ К представляет собой 64-битовый блок с 8 битами контроля по четности, расположенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (таблица 7).

Таблица 5

Рисунок 4  Схема алгоритма вычисления ключей К_j
Таблица 7 разделена на две части. Результат преобразования G(K) разбивается на две половины Со и Do по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбирают-

Таблица 3.6 Таблица 3.7

ся биты последовательности Со (первым битом Со будет бит 57 ключа шифра, затем бит 49 и т д., а последними битами - биты 44 и 36 ключа).

Следующие четыре строки матрицы G определяют, как выбираются биты последовательности Do (т.е. последовательность Do будет состоять из битов 63, 55, 47, ...,12, 4 ключа шифра).

Как видно из таблицы 7, для генерации последовательностей Со и Do не используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для других целей (например, для контроля по четности). Таким образом, в действительности ключ шифра является 56-битовым.

После определения Со и Do рекурсивно определяются С_i и D_i, i = 1, 2, ..., 16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в таблице 8.

Операции сдвига выполняются для последовательностей С_i и D_i независимо. Например, последовательность С₃ получается посредством циклического сдвига влево на две позиции последовательности С₂, а последовательность D₃ - посредством сдвига влево на две позиции последовательности D₂, C₁₆ и D₁₆ получаются из С₁₅ и D₁₅ посредством сдвига влево на одну позицию.

Таблица 3 8  Количество сдвигов s_i для вычисления ключа

Номер итерации	Количество s_i сдвигов влево бит	Номер итерации	Количество s_i сдвигов влево бит
1	1	9	1
2	1	10	2
3	2	11	2
4	2	12	2
5	2	13	2
6	2	14	2
7	2	15	2
8	2	16	1

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

Таблица 9  Функция Н завершающей обработки ключа

(переставленная выборка 2)

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

Как следует из таблицы 9, первым битом ключа К_i будет 14-й бит последовательности С_i D_i, вторым - 17-й бит, 47-м битом ключа К_i будет 29-й бит С_i D_i, а 48-м битом - 32-й бит С_i D_i.

2 Основные режимы работы алгоритма DES

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

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

• электронная кодовая книга ЕСВ (Electronic Code Book);

• сцепление блоков шифра СВС (Cipher Block Chaining);

• обратная связь по шифртексту CFB (Cipher Feed Back);

• обратная связь по выходу OFB (Output Feed Back).

Режим "Электронная кодовая книга"

Длинный файл разбивают на 64-битовые отрезки (блоки) по 8 байтов. Каждый из этих блоков шифруют независимо с использованием одного и того же ключа шифрования (рисунок 5).

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

Рисунок 5  Схема алгоритма DES в режиме электронной кодовой книги

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

Режим "Сцепление блоков шифра"

В этом режиме исходный файл М разбивается на 64-битовые блоки: М = M₁M₂...Mn. Первый блок M₁ складывается по модулю 2 с 64-битовым начальным вектором IV, который меняется ежедневно и держится в секрете (рисунок 6). Полученная сумма затем шифруется с использованием ключа DES, известного и отправителю, и получателю информации. Полученный 64-битовый шифр C₁ складывается по модулю 2 со вторым блоком текста, результат шифруется и получается второй 64-битовый шифр С₂, и т.д. Процедура повторяется до тех пор, пока не будут обработаны все блоки текста.

Таким образом, для всех i = 1...n (n  число блоков) результат шифрования С_i определяется следующим образом: С_i = =DES (M_i  С_i), где Со = IV - начальное значение шифра, равное начальному вектору (вектору инициализации).

Очевидно, что последний 64-битовый блок шифртекста является функцией секретного ключа, начального вектора и каж-

Рисунок 6  Схема алгоритма DES в режиме сцепления блоков шифра

дого бита открытого текста независимо от его длины. Этот блок шифртекста называют кодом аутентификации сообщения (КАС).

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

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

Блок М_i является функцией только С_i и С_i. Поэтому ошибка при передаче приведет к потере только двух блоков исходного текста.

Режим "Обратная связь по шифру"

В этом режиме размер блока может отличаться от 64 бит (рисунок 7). Файл, подлежащий шифрованию (расшифрованию), считывается последовательными блоками длиной k битов (k =1 ...64).

Рисунок 7  Схема алгоритма DES в режиме

обратной связи по шифртексту

Входной блок (64-битовый регистр сдвига) вначале содержит вектор инициализации, выровненный по правому краю.

Предположим, что в результате разбиения на блоки мы получили n блоков длиной k битов каждый (остаток дописывается нулями или пробелами). Тогда для любого i=1...n блок шифртекста

С_i= М_iР_i_-1

где Р_i_-1 обозначает k старших битов предыдущего зашифрованного блока.

Обновление сдвигового регистра осуществляется путем удаления его старших k битов и записи С_i в регистр. Восстановление зашифрованных данных также выполняется относительно просто: Р_i_-1 и С_i вычисляются аналогичным образом и

М_i = С_i Р_i_-1

Режим "Обратная связь по выходу"

Этот режим тоже использует переменный размер блока и сдвиговый регистр, инициализируемый так же, как в режиме CFB, а именно - входной блок вначале содержит вектор инициализации IV, выровненный по правому краю (рисунок 8). При этом для каждого

Рисунок 8  Схема алгоритма DES в режиме обратной связи по выходу

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

qПоложим

М = М₁ М₂... М _n
Для всех i = 1... n

С_i= М_iР_i_-1,

где Р_i - старшие к битов операции DES (Р_i_-1).

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

Это осуществляется путем отбрасывания старших k битов и дописывания справа Р_i.
Области применения алгоритма DES

Каждому из рассмотренных режимов (ЕСВ, СВС, CFB, OFB) свойственны свои достоинства и недостатки, что обусловливает области их применения.

Режим ЕСВ хорошо подходит для шифрования ключей, режим CFB, как правило, предназначается для шифрования отдельных символов, а режим OFB нередко применяется для шифрования в спутниковых системах связи.

Режимы СВС и CFB пригодны для аутентификации данных. Эти режимы позволяют использовать алгоритм DES для:

• интерактивного шифрования при обмене данными между терминалом и главной ЭВМ;

• шифрования криптографического ключа в практике автоматизированного распространения ключей;

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

Первоначально стандарт DES предназначался для шифрования и расшифрования данных ЭВМ. Однако его применение было обобщено и на аутентификацию.

В системах автоматической обработки данных человек не в состоянии просмотреть данные, чтобы установить, не внесены ли в них какие-либо изменения. При огромных объемах данных, проходящих в современных системах обработки, просмотр занял бы слишком много времени. К тому же избыточность данных может оказаться недостаточной для обнаружения ошибок. Даже в тех случаях, когда просмотр человеком возможен, данные могут быть изменены таким образом, что обнаружить эти изменения человеку очень трудно. Например, "do" может быть заменено на "do not", "$1900" - на "$9100". Без дополнительной информации человек при просмотре может легко принять измененные данные за подлинные. Такие опасности могут существовать даже при использовании шифрования данных. Поэтому желательно иметь автоматическое средство обнаружения преднамеренных и непреднамеренных изменений данных.

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

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

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

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

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

С помощью алгоритма DES можно также зашифровать файлы ЭВМ для их хранения.

Одним из наиболее важных применений алгоритма DES является защита сообщений электронной системы платежей (ЭСП) при операциях с широкой клиентурой и между банками.

Алгоритм DES реализуется в банковских автоматах, терминалах в торговых точках, автоматизированных рабочих местах и главных ЭВМ. Диапазон защищаемых им данных весьма широк  от оплат $50 до переводов на многие миллионы долларов. Гибкость основного алгоритма DES позволяет использовать его в самых разнообразных областях применения электронной системы платежей.