DES отечественный стандарт шифрования более удобен для программной реализации.

В отличие от американского DES в отечественном стандарте применяется более длинный ключ – 256 бит . Кроме того, российский стандарт предлагает использовать 32 раунда шифрования, тогда как DES – только 16.

Таким образом, основные параметры алгоритма криптографического преобразования данных ГОСТ 28147-89 следующие: размер блока составляет 64 бита, размер ключа – 256 бит , количество раундов – 32.

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

В алгоритме шифрования используются следующие операции :

• сложение слов по модулю 2 32 ;
• циклический сдвиг слова влево на указанное число бит;
• побитовое сложение по модулю 2;
• замена по таблице.

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

Структура раунда ГОСТ 28147-89

Структура одного раунда ГОСТ 28147-89 приведена на рис. 5.1 .

Шифруемый блок данных разбивается на две части, которые затем обрабатываются как отдельные 32-битовые целые числа без знака. Сначала правая половина блока и подключ раунда складываются по модулю 2 32 . Затем производится поблочная подстановка . 32-битовое значение , полученное на предыдущем шаге (обозначим его S ), интерпретируется как массив из восьми 4-битовых блоков кода: S=(S 0 ,S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 ,S 7) . Далее значение каждого из восьми блоков заменяется на новое, которое выбирается по таблице замен следующим образом: значение блока S i заменяется на S i -тый по порядку элемент ( нумерация с нуля) i-го узла замен (т.е. i-той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент c номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. В каждой строке таблицы замен записаны числа от 0 до 15 в произвольном порядке без повторений. Значения элементов таблицы замен взяты от 0 до 15 , так как в четырех битах, которые подвергаются подстановке, может быть записано целое число без знака в диапазоне от 0 до 15 . Например, первая строка S-блока может содержать такие значения: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . В этом случае значение блока S 0 (четыре младших бита 32-разрядного числа S) заменится на число, стоящее на позиции, номер которой равен значению заменяемого блока. Если S 0 = 0 , то оно заменится на 5 , если S 0 = 1 , то оно заменится на 8 и т.д.

Рис. 5.1.

После выполнения подстановки все 4-битовые блоки снова объединяются в единое 32-битное слово , которое затем циклически сдвигается на 11 битов влево. Наконец, с помощью побитовой операции "сумма по модулю 2" результат объединяется с левой половиной, вследствие чего получается новая правая половина R i . Новая левая часть L i берется равной младшей части преобразуемого блока: L i = R i-1 .

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

Процедуры шифрования и расшифрования

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

Рассмотрим процесс создания подключей раундов. В ГОСТ эта процедура очень проста, особенно по сравнению с DES . 256-битный ключ K разбивается на восемь 32-битных подключей, обозначаемых K 0 , K 1 , K 2 ,K 3 , K 4 , K 5 , K 6 , K 7 . Алгоритм включает 32 раунда, поэтому каждый подключ при шифровании используется в четырех раундах в последовательности, представленной на таблица 5.1 .

Таблица 5.1. Последовательность использования подключей при шифровании

Раунд	1	2	3	4	5	6	7	8
Подключ	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
Раунд	9	10	11	12	13	14	15	16
Подключ	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
Раунд	17	18	19	20	21	22	23	24
Подключ	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
Раунд	25	26	27	28	29	30	31	32
Подключ	K 7	K 6	K 5	K 4	K 3	K 2	K 1	K 0

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

1 Структурная схема алгоритма криптографического преобразования 1

2 Режим простой замены 4

3 Режим гаммирования 8

4 Режим гаммирования с обратной связью 11

5 Режим выработки имитовставки 14

Приложение 1 Термины, применяемые в настоящем стандарте, и их определения 16

Приложение 2 Значения констант С1, С2 18

Приложение 3 Схемы программной реализации алгоритма криптографического

преобразования. 19

Приложение 4 Правила суммирования по модулю 2 32 и по модулю (2 32 -I) 25

ГОСУДАРСТВЕННЫЙ СТАНДАРТ

СОЮЗА ССР

СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ. ЗАШИТА КРИПТОГРАФИЧЕСКАЯ

Алгоритм криптографического преобразования

Дата введения 01.07.90

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

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

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

Термины, применяемые в настоящем стандарте, и их определения приведены в приложении 1.

I. СТРУКТУРНАЯ СХЕМА АЛГОРИТМА КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ

1.1. Структурная схема алгоритма криптографического преобразования (криптосхема) содержит (см.черт. 1):

Издание официальное ★

ключевое запоминающее устройство (КЗУ) на 256 бит, состоящее из восьми 32-разрядных накопителей (Х 0 , X t . Х 2 , A3 Л4, Х$, Х 6 , Ху); четыре 32-разрядных накопителя (/V (, N 2 , Nj, /V 4);

Перепечатка воспрещена

© Издательство стандартов, 1989 © ИПК Издательство стандартов, 1996

два 32-разрядных накопителя Л/$,) с записанными в них постоянными заполнениями С 2 , С\\

два 32-разрядных сумматора по модулю 2 32 (СМ|, СЛ/3);

32-разрядный сумматор поразрядного суммирования по модулю 2 (СЛ/ 2);

32-разрядный сумматор по модулю (2 32 - 1) (СЛ/ 4);

сумматор по модулю 2(СЛ/ 5), ограничение на разрядность сумматора СЛ/$ не накладывается;

блок подстановки (А);

регистр циклического сдвига на одиннадцать шагов в сторону старшего разряда (R).

1.2. Блок подстановки А" состоит из восьми узлов замены A’j,

А 2 , А“з, К 4 , А5, А7, А 8 с памятью на 64 бита каждый. Посту

пающий на блок подстановки 32-разрядный вектор разбивается на восемь последовательно идущих 4-разрядных векторов, каждый из которых преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющим собой таблицу из шестнадцати строк, содержащих по четыре бита заполнения в строке. Входной вектор определяет адрес строки в таблице, заполнение данной строки является выходным вектором. Затем 4-разрядные выходные векторы последовательно объединяются в 32-разрядный вектор.

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

1.4. При записи ключа (И", W 2 ..., W q e{0,1), д= N256, в

КЗУ значение W\ вводится в i-й разряд накопителя Xq, значение W 2 вводится во 2-й разряд накопителя Л#, ... , значение W^ 2 вводится в 32-й разряд накопителя Xq; значение W33 вводится в 1-й разряд накопителя Х\ у значение вводится во 2-й разряд накопителя Х\ у... , значение W M вводится в 32-й разряд накопителя Х\\ значение W 6 5 вводится в 1-й разряд накопителя Х 2 и т.д., значение 1У 2 5Ь вводится в 32-й разряд накопителя Ху.

1.5. При перезаписи информации содержимое р-го разряда одного накопителя (сумматора) переписывается в р-й разряд другого накопителя (сумматора).

1.6. Значения постоянных заполнений Cj, С 2 (констант) накопителей /V 6 , /V5 приведены в приложении 2.

1.7. Ключи, определяющие заполнения КЗУ и таблиц блока подстановки К, являются секретными элементами и поставляются в установленном порядке.

Заполнение таблиц блока подстановки К является долговременным ключевым элементом, общим для сети ЭВМ.

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

1.8. В криптосхеме предусмотрены четыре вида работы: зашифрование (расшифрование) данных в режиме простой замены; зашифрование (расшифрование) данных в режиме гаммирования;

зашифрование (расшифрование) данных в режиме гаммирования с обратной связью;

режим выработки имитовставки.

Схемы программной реализации алгоритма криптографического преобразования приведены в приложении 3.

2. РЕЖИМ ПРОСТОЙ ЗАМЕНЫ

2.1. Зашифрование открытых данных в режиме простой замены

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

Открытые данные, подлежащие зашифрованию, разбивают на блоки по 64 бита в каждом. Ввод любого блока Т {) = (Д|(0), ^(О), ..., д 3 1(0), я 32 (0), £|(0), Ь 2 (0) у... , Z> 32 (0)) двоичной информации в накопители N\ и N 2 производится так, что значение Д|(0) вводится в 1-й разряд N|, значение а 2 (0) вводится во 2-й разряд /Vj и т.д, значение я 32 (0) вводится в 32-й разряд iVj; значение />|(0) вводится в

1- й разряд Л/ 2 , значение Ь 2 (0) вводится во 2-й разряд N 2 и т.д., значение /> 32 (0) вводится в 32-й разряд N 2 . В результате получают состояние (я 32 (0), я 3 |(0), ... , а 2 (0) у <7|(0)) накопителя yVj и состояние (/> 32 (0), Ь 2 1(0), ... , />|(0)) накопителя N 2 .

2.1.2. В КЗУ вводятся 256 бит ключа. Содержимое восьми 32-раз-рядных накопителей Aq, X\ t ... , Xj имеет вид:

^0 = (^32^3.....

*1 =(^64^63, . ^34^33)

*7 = (^56> ^255. ... , И/ 226 , ^ 225)

2.1.3. Алгоритм зашифрования 64-разрядного блока открытых данных в режиме простой замены состоит из 32 циклов.

В первом цикле начальное заполнение накопителя суммируется по модулю 2 32 в сумматоре СМ\ с заполнением накопителя Xq при этом заполнение накопителя Nj сохраняется.

Результат суммирования преобразуется в блоке подстановки К и полученный вектор поступает на вход регистра /?, где циклически сдвигается на одиннадцать шагов в сторону старших разрядов. Результат сдвига суммируется поразрядно по модулю 2 в сумматоре СМ 2 с 32-разрядным заполнением накопителя yV 2 . Полученный в СМ 2 результат записывается в N\ % при этом старое заполнение N| переписывается в N 2 . Первый цикл заканчивается.

Последующие циклы осуществляются аналогично, при этом во

2- м цикле из КЗУ считывается заполнение Х\, в 3-м цикле из КЗУ

считывается заполнение Х 2 и т.д., в 8-м цикле из КЗУ считывается заполнение Xj. В циклах с 9-го по 16-й, а также в циклах с 17-го по 24-й заполнения из КЗУ считываются в том же порядке:

В последних восьми циклах с 25-го по 32-й порядок считывания заполнений КЗУ обратный:

ад,ад,ад,ад.

Таким образом, при зашифровании в 32 циклах осуществляется следующий порядок выбора заполнений накопителей:

ад, ^2,^},^4>^5,^6»^7, ад, ^2,^3»^4,^5,-^6,^7, ад, ад,ад,ад, ад,ад,ад,ад.

В 32 цикле результат из сумматора СЛ/ 2 вводится в накопитель УУ 2 , а в накопителе N\ сохраняется старое заполнение.

Полученные после 32-го никла зашифрования заполнения накопителей N| и N2 являются блоком зашифрованных данных, соответствующим блоку открытых данных.

2.1 4 Уравнения зашифрования в режиме простой замены имеют вид:

J*Cr> »(

I Ь(/) = а(/~ I)

при у = I -24;

Г«

\bO) - а О - О при / 8* 25 -г 31; а(32) = а (31)

А (32) = (д (31) ffl X 0)KRG> Ь (31)

где д(0) = (а 32 (0), «з|(0), ... , Д|(0)) - начальное заполнение N\ перед первым циклом зашифрования;

6(0) = (632(0), 63j(0), ... , 6j(0)) - начальное заполнение /У 2 перед первым циклом зашифрования;

a(j) = (032(7), 0з|(/) э... , 0|(/)) - заполнение УУ, после у-го цикла зашифрования;

b(j) = (6з 2 (/), 63j(/"), ... , 6|(/)) - заполнение /V 2 после у-го цикла зашифрования, у = 032.

Знак ф означает поразрядное суммирование 32-разрядных векторов по модулю 2.

Знак Ш означает суммирование 32-разрядных векторов по модулю 2 32 . Правила суммирования по модулю 2 32 приведены в приложении 4;

/?- операция циклического сдвига на одиннадцать шагов в сторону старших разрядов, т.е.

^(г 32»О|> г 30> г 29> г 28> г 27> г 26» г 25> г 24> г 23’ Г 22» Г 2Ь Г 20> » г 2* г |)~

= (г 21» г 20> - » г 2* г 1 * Г 32>Г31 *ГзО» г 29* г 28* , 27э"26э/"25> , 24>Г23» , 22)*

2.1.5. 64-разрядный блок зашифрованных данных Т ш выводится из накопителей Л^, УУ 2 в следующем порядке: из 1-го, 2-го, ... , 32-го разрядов накопителя Л7|, затем из 1-го, 2-го, ... , 32-го разрядов накопителя W 2 , т.е.

т ш - (а,<32),0 2 (32),0 32 (32), 6,(32), 6 2 <32),6 32 <32».

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

2.2. Расшифрование зашифрованных данных в режиме простой замены

2.2.1. Криптосхема, реализующая алгоритм расшифрования в режиме простой замены, имеет тот же вид (см.чсрт.2), что и при зашифровании. В КЗУ вводятся 256 бит того же ключа, на котором осуществлялось зашифрование. Зашифрованные данные, подлежащие расшифрованию, разбиты на блоки по 64 бита в каждом Ввод любого блока

Т ш - (0,(32),о 2 (32), ..., 0 32 (32), 6,(32), 6 2 (32), ..., 6 32 (32))

в накопители Л’, и N 2 производятся так, что значение дj(32) вводится в 1-й разряд /V, значение о 2 (32) вводится во 2-й разряд /V, и т.д., значение a 32 (32) вводится в 32-й разряд /V,; значение 6,(32) вводится в 1-й разряд N 2 и т.д., значение 6 32 (32) вводится в 32-й разряд N 2 .

2.2.2. Расшифрование осуществляется по тому же алгоритму, что и зашифрование открытых данных, с тем изменением, что заполнения накопителей Xq, Х\ у... , Xj считываются из КЗУ в циклах расшифрования в следующем порядке:

ад, ад 3 ,ад,ад, ад,ад,ад,ад 0 ,

ад 6 ,ад 4 ,ад 2 ,ад, ад,ад,ад 2 ,ад.

2.2.3. Уравнения расшифрования имеют вид:

Г д (32 -/) = (д (32 - / + 1) ШЛГ,.,) *ЛФ6(32-/ + 1) b (32 - /) = д (32 - / + 1) при,/=1+8;

I о(32- /) = (а(32-/М)ШДГ (32 _ /)(тод8))КЛФЬ(32./М) |6(32-/) = д (32 - / + 1)

при /= 9 + 31;

Ь(0) = (а (1) ШДГо) ОФй(1)

2.2.4. Полученные после 32 циклов работы заполнения накопителей W, и N 2 составляют блок открытых данных.

То = (fli(O), а 2 (0), ... , Аз 2 (0)» 6,(0), 6 2 (0), ... , 6 32 (0)), соответствующий блоку зашифрованных данных, при этом значение о,(0) блока 7о соответствует содержимому 1-го разряда yV, значение 02(0) соот-

С. 8 ГОСТ 28147-89

ветствует содержимому 2-го разряда N\ и т.д., значение Дз2(0) соответствует содержимому 32-го разряда N\; значение 6j(0) соответствует содержимому 1-го разряда значение ^(0) соответствует содержимому 2-го разряда N2 и т.д., значение £зг(0) соответствует содержимому 32-го разряда N2-

Аналогично расшифровываются остальные блоки зашифрованных данных.

2.3. Алгоритм зашифрования в режиме простой замены 64-битового блока Г 0 обозначается через А у т.е.

А (Т 0) = А (а (0), Ь (0)) = (а (32), Ь (32)) = Т ш.

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

3. РЕЖИМ ГАММИРОВАНИЯ

3.1. Зашифрование открытых данных в режиме гаммирования

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

Открытые данные, разбитые на 64-раэрядиые блоки Т\}\ 7}, 2) ..., 7}) м “ , 1 7[) М) , зашифровываются в режиме гаммирования путем поразрядного суммирования по модулю 2 в сумматоре СЛ/5 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бита, т е.

Г _/Л1) Я2) Лм-1) ЛМ)\

"ill V 1 ш э * ш * » " Ш » " * * * " 111 /»

где М - определяется объемом шифруемых данных.

Tjj) - У-й 64-разрядный блок, /« число двоичных разрядов в блоке 7J) M) может быть меньше 64, при этом неиспользованная для зашифрования часть гаммы шифра из блока Г\^ ] отбрасывастся.

3.1.2. В КЗУ вводятся 256 бит ключа. В накопители iVj, N 2 вводится 64-разрядная двоичная последовательность (синхропосылка) S = (5*1, S 2 , ... , 5^4), являющаяся исходным заполнением этих накопителей для последующей выработки Мблоков гаммы шифра. Синхропосылка вводится в jV| и Л^так, что значение 5[ вводится в 1-й разряд УУ}, значение S 2 вводится во 2-й разряд N\ и т.д., значение ^вводится в 32-й разряд 7V|; значение S33 вводится в 1-й разряд N 2 , значение 4S34 вводится во 2-й разряд N 2 и т.д., значение вводится в 32-й разряд N 2 .

3.1.3. Исходное заполнение накопителей /Vj и N 2 (синхропосылка.5) зашифровывается в режиме простой замены в соответствии с

История этого шифра гораздо более давняя. Алгоритм, положенный впоследствии в основу стандарта, родился, предположительно, в недрах Восьмого Главного управления КГБ СССР (ныне в структуре ФСБ), скорее всего, в одном из подведомственных ему закрытых НИИ , вероятно, ещё в 1970-х годах в рамках проектов создания программных и аппаратных реализаций шифра для различных компьютерных платформ.

С момента опубликования ГОСТа на нём стоял ограничительный гриф «Для служебного пользования», и формально шифр был объявлен «полностью открытым» только в мае 1994 года . История создания шифра и критерии разработчиков по состоянию на 2010 год не опубликованы.

Описание

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

• режим имитовставки .

Режим простой замены

Для зашифрования в этом режиме открытый текст сначала разбивается на две половины (младшие биты - A, старшие биты - B ). На i-ом цикле используется подключ K i:

( = двоичное «исключающее или»)

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K 1 …K 8 .

Ключи K 9 …K 24 являются циклическим повторением ключей K 1 …K 8 (нумеруются от младших битов к старшим). Ключи K 25 …K 32 являются ключами K 8 …K 1 .

После выполнения всех 32 раундов алгоритма, блоки A 33 и B 33 склеиваются (обратите внимание, что старшим битом становится A 33 , а младшим - B 33) - результат есть результат работы алгоритма.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей K i .

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

A i и K i складываются по модулю 2 32 .

Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком . Общее количество S-блоков ГОСТа - восемь, то есть столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая - на вход второго и т. д.

Если S-блок выглядит так:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12

и на входе S-блока 0, то на выходе будет 1, если 4, то на выходе будет 5, если на входе 12, то на выходе 6 и т. д.

Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

Режим простой замены имеет следующие недостатки:

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

В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, то есть разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовало используемые в Интернет узлы замены, см. RFC 4357 .

Достоинства ГОСТа

• бесперспективность силовой атаки (XSL-атаки в учёт не берутся, так как их эффективность на данный момент полностью не доказана);
• эффективность реализации и соответственно высокое быстродействие на современных компьютерах .
• наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТа.

Криптоанализ

Считается (см. например Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST), что ГОСТ устойчив к таким широко применяемым методам, как линейный и дифференциальный криптоанализ. Обратный порядок использования ключей в последних восьми раундах обеспечивает защиту от атак скольжения(slide attack) и отражения(reflection attack).

В мае 2011 года известный криптоаналитик Николя Куртуа доказал существование атаки на данный шифр, имеющей сложность в 2 8 (256) раз меньше сложности прямого перебора ключей при условии наличия 2 64 пар открытый текст/закрытый текст. Данная атака не может быть осуществлена на практике ввиду слишком высокой вычислительной сложности. Более того, знание 2 64 пар открытый текст/закрытый текст, очевидно, позволяет читать зашифрованные тексты, даже не вычисляя ключа. В большинстве других работ также описываются атаки, применимые только при некоторых предположениях, таких как определенный вид ключей или таблиц замен, некоторая модификация исходного алгоритма, или же требующие все еще недостижимых объемов памяти или вычислений. Вопрос о наличии применимых на практике атак без использования слабости отдельных ключей или таблиц замены остается открытым.

Критика ГОСТа

Основные проблемы ГОСТа связаны с неполнотой стандарта в части генерации ключей и таблиц замен. Считается, что у ГОСТа существуют «слабые» ключи и таблицы замен, но в стандарте не описываются критерии выбора и отсева «слабых». Также стандарт не специфицирует алгоритм генерации таблицы замен (S-блоков). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой, поднимает ряд проблем:

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

В октябре 2010 года на заседании 1-го объединенного технического комитета Международной организации по стандартизации (ISO/IEC JTC 1/SC 27) ГОСТ был выдвинут на включение в международный стандарт блочного шифрования ISO/IEC 18033-3. В связи с этим в январе 2011 года были сформированы фиксированные наборы узлов замены и проанализированы их криптографические свойства. Однако ГОСТ не был принят в качестве стандарта, и соответствующие таблицы замен не были опубликованы

Возможные применения

Примечания

См. также

Ссылки

• ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования»
• Сергей Панасенко Стандарт шифрования ГОСТ 28147-89 (рус.) (15 августа 2007). Проверено 3 августа 2012.

• . - криптографический проект компании ООО «Криптоком» по добавлению российских криптографических алгоритмов в библиотеку OpenSSL. Архивировано из первоисточника 24 августа 2011. Проверено 16 ноября 2008.

Литература

• Мельников В. В. Защита информации в компьютерных системах. - М .: Финансы и статистика, 1997.
• Романец Ю. В.. Тимофеев П. А., Шаньгин В. Ф. Защита информации в компьютерных системах и сетях. - М .: Радио и связь, 1999.
• Харин Ю. С., Берник В. И., Матвеев Г. В. Математические основы криптологии. - Мн. : БГУ, 1999.
• Герасименко В. А., Малюк А. А. Основы защиты информации. - М .: МГИФИ, 1997.
• Леонов А. П., Леонов К. П., Фролов Г. В. Безопасность автоматизированных банковских и офисных технологий. - Мн. : Нац. кн. палата Беларуси, 1996.
• Зима В. М.. Молдовян А. А., Молдовян Н. А. Компьютерные сети и защита передаваемой информации. - СПб. : СПбГУ, 1998.
• Шнайер Б. 14.1 Алгоритм ГОСТ 28147-89 // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. - М .: Триумф, 2002. - С. 373-377. - 816 с. - 3000 экз. - ISBN 5-89392-055-4
• Popov, V., Kurepkin, I., and S. Leontiev Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms (англ.) // RFC 4357 . - IETF, January 2006.

Wikimedia Foundation . 2010 .

Алгоритм ГОСТ 28147-89

ГОСТ 28147-89 -- советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название -- «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».

Рис. 4.

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

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

Недостатки алгоритма: Основные проблемы ГОСТа связаны с неполнотой стандарта в части генерации ключей и таблиц замен. Считается, что у ГОСТа существуют «слабые» ключи и таблицы замен, но в стандарте не описываются критерии выбора и отсева «слабых». Также стандарт не специфицирует алгоритм генерации таблицы замен (S-блоков). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой, поднимает ряд проблем: нельзя определить криптостойкость алгоритма, не зная заранее таблицы замен; реализации алгоритма от различных производителей могут использовать разные таблицы замен и могут быть несовместимы между собой; возможность преднамеренного предоставления слабых таблиц замен лицензирующими органами РФ.

Достоинства IDEA перед аналогами

В программной реализации на Intel486SX по сравнению с DES IDEA в два раза быстрее, что является существенным повышением скорости, длина ключа у IDEA имеет размер 128 бит, против 56 бит у DES, что является хорошим улучшением против полного перебора ключей. Вероятность использования слабых ключей очень мала и составляет 1/2 64 . IDEA быстрее алгоритма ГОСТ 28147-89 (в программной реализации на Intel486SX). Использование IDEA в параллельных режимах шифрования на процессорах Pentium III и Pentium MMX позволяет получать высокие скорости. По сравнению с финалистами AES, 4-way IDEA лишь слегка медленнее, чем RC6 и Rijndael на Pentium II, но быстрее, чем Twofish и MARS. На Pentium III 4-way IDEA даже быстрее RC6 и Rijndael. Преимуществом также является хорошая изученность и устойчивость к общеизвестным средствам криптоанализа.

Алгоритм шифрования ГОСТ 28147-89, его использование и программная реализация для компьютеров платформы Intel x86.

Андрей Винокуров

Описание алгоритма.

Термины и обозначения.

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

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

Элементы данных в данной статье обозначаются заглавными латинскими буквами с наклонным начертанием (например, X ). Через |X | обозначается размер элемента данных X в битах. Таким образом, если интерпретировать элемент данных X как целое неотрицательное число, можно записать следующее неравенство:.

Если элемент данных состоит из нескольких элементов меньшего размера, то этот факт обозначается следующим образом: X =(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n –1 . Процедура объединения нескольких элементов данных в один называется конкатенацией данных и обозначается символом «||». Естественно, для размеров элементов данных должно выполняться следующее соотношение: |X |=|X 0 |+|X 1 |+…+|X n -1 |. При задании сложных элементов данных и операции конкатенации составляющие элементы данных перечисляются в порядке возрастания старшинства. Иными словами, если интерпретировать составной элемент и все входящие в него элементы данных как целые числа без знака, то можно записать следующее равенство:

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

X =(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 ·x 1 +…+2 n –1 ·x n –1 .

Таким образом, если вы обратили внимание, для ГОСТа принята т.н. «little-endian» нумерация разрядов, т.е. внутри многоразрядных слов данных отдельные двоичные разряды и их группы с меньшими номерами являются менее значимыми. Об этом прямо говорится в пункте 1.3 стандарта: «При сложении и циклическом сдвиге двоичных векторов старшими разрядами считаются разряды накопителей с большими номерами». Далее, пункты стандарта 1.4, 2.1.1 и другие предписывают начинать заполнение данными регистров-накопителей виртуального шифрующего устройства с младших, т.е. менее значимых разрядов. Точно такой же порядок нумерации принят в микропроцессорной архитектуре Intel x86, именно поэтому при программной реализации шифра на данной архитектуре никаких дополнительных перестановок разрядов внутри слов данных не требуется.

Если над элементами данных выполняется некоторая операция, имеющая логический смысл, то предполагается, что данная операция выполняется над соответствующими битами элементов. Иными словами A B =(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n –1), где n =|A |=|B |, а символом « » обозначается произвольная бинарная логическая операция; как правило, имеется в виду операция исключающего или , она же – операция суммирования по модулю 2:

Логика построения шифра и структура ключевой информации ГОСТа.

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

• цикл зашифрования (32-З);
• цикл расшифрования (32-Р);
• цикл выработки имитовставки (16-З).

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

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

• что такое основной шаг криптопреобразования;
• как из основных шагов складываются базовые циклы;
• как из трех базовых циклов складываются все практические алгоритмы ГОСТа.

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

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

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

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

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

Шаг 0

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

Шаг 1

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

Шаг 2

Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S= (S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), причем S 0 содержит 4 самых младших, а S 7 – 4 самых старших бита S .

Далее значение каждого из восьми блоков заменяется новым, которое выбирается по таблице замен следующим образом: значение блока S i меняется на S i -тый по порядку элемент (нумерация с нуля) i -того узла замены (т.е. i -той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Отсюда становится понятным размер таблицы замен: число строк в ней равно числу 4-битовых элементов в 32-битовом блоке данных, то есть восьми, а число столбцов равно числу различных значений 4-битового блока данных, равному как известно 2 4 , шестнадцати.

Шаг 3

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

Шаг 4

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

Шаг 5

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

Шаг 6

Полученное значение преобразуемого блока возвращается как результат выполнения алгоритма основного шага криптопреобразования.

Базовые циклы криптографических преобразований.

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

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

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

Цикл зашифрования 32-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Рисунок 2а. Схема цикла зашифрования 32-З

Цикл расшифрования 32-Р:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Рисунок 2б. Схема цикла расшифрования 32-Р

Цикл выработки имитовставки 16-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Рисунок 2в. Схема цикла выработки имитовставки 16-З.

Каждый из циклов имеет собственное буквенно-цифровое обозначение, соответствующее шаблону «n-X» , где первый элемент обозначения (n ), задает число повторений основного шага в цикле, а второй элемент обозначения (X ), буква, задает порядок зашифрования («З») или расшифрования («Р») в использовании ключевых элементов. Этот порядок нуждается в дополнительном пояснении:

Цикл расшифрования должен быть обратным циклу зашифрования, то есть последовательное применение этих двух циклов к произвольному блоку должно дать в итоге исходный блок, что отражается следующим соотношением: Ц 32-Р (Ц 32-З (T ))=T , где T – произвольный 64-битовый блок данных, Ц X (T ) – результат выполнения цикла X над блоком данных T . Для выполнения этого условия для алгоритмов, подобных ГОСТу, необходимо и достаточно, чтобы порядок использования ключевых элементов соответствующими циклами был взаимно обратным. В справедливости записанного условия для рассматриваемого случая легко убедиться, сравнив приведенные выше последовательности для циклов 32-З и 32-Р. Из сказанного вытекает одно интересное следствие: свойство цикла быть обратным другому циклу является взаимным, то есть цикл 32-З является обратным по отношению к циклу 32-Р. Другими словами, зашифрование блока данных теоретически может быть выполнено с помощью цикла расшифрования, в этом случае расшифрование блока данных должно быть выполнено циклом зашифрования. Из двух взаимно обратных циклов любой может быть использован для зашифрования, тогда второй должен быть использован для расшифрования данных, однако стандарт ГОСТ28147-89 закрепляет роли за циклами и не предоставляет пользователю права выбора в этом вопросе.

Цикл выработки имитовставки вдвое короче циклов шифрования, порядок использования ключевых элементов в нем такой же, как в первых 16 шагах цикла зашифрования, в чем нетрудно убедиться, рассмотрев приведенные выше последовательности, поэтому этот порядок в обозначении цикла кодируется той же самой буквой «З».

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

Основные режимы шифрования.

ГОСТ 28147-89 предусматривает три следующих режима шифрования данных:

• простая замена,
• гаммирование,
• гаммирование с обратной связью,

и один дополнительный режим выработки имитовставки.

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

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

T о,T ш – массивы соответственно открытых и зашифрованных данных;

, – i - тые по порядку 64-битовые блоки соответственно открытых и зашифрованных данных:, , последний блок может быть неполным: ;

n – число 64-битовых блоков в массиве данных;

Ц X – функция преобразования 64-битового блока данных по алгоритму базового цикла «X».

Теперь опишем основные режимы шифрования:

Простая замена.

Зашифрование в данном режиме заключается в применении цикла 32-З к блокам открытых данных, расшифрование – цикла 32-Р к блокам зашифрованных данных. Это наиболее простой из режимов, 64-битовые блоки данных обрабатываются в нем независимо друг от друга. Схемы алгоритмов зашифрования и расшифрования в режиме простой замены приведены на рисунках 3а и б соответственно, они тривиальны и не нуждаются в комментариях.

Рисунок. 3а. Алгоритм зашифрования данных в режиме простой замены

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

Размер массива открытых или зашифрованных данных, подвергающийся соответственно зашифрованию или расшифрованию, должен быть кратен 64 битам: | T о |=| T ш |=64· n , после выполнения операции размер полученного массива данных не изменяется.

Режим шифрования простой заменой имеет следующие особенности:

• Так как блоки данных шифруются независимо друг от друга и от их позиции в массиве данных, при зашифровании двух одинаковых блоков открытого текста получаются одинаковые блоки шифртекста и наоборот. Отмеченное свойство позволит криптоаналитику сделать заключение о тождественности блоков исходных данных, если в массиве зашифрованных данных ему встретились идентичные блоки, что является недопустимым для серьезного шифра.
• Если длина шифруемого массива данных не кратна 8 байтам или 64 битам, возникает проблема, чем и как дополнять последний неполный блок данных массива до полных 64 бит. Эта задача не так проста, как кажется на первый взгляд. Очевидные решения типа «дополнить неполный блок нулевыми битами» или, более обще, «дополнить неполный блок фиксированной комбинацией нулевых и единичных битов» могут при определенных условиях дать в руки криптоаналитика возможность методами перебора определить содержимое этого самого неполного блока, и этот факт означает снижение стойкости шифра. Кроме того, длина шифртекста при этом изменится, увеличившись до ближайшего целого, кратного 64 битам, что часто бывает нежелательным.

На первый взгляд, перечисленные выше особенности делают практически невозможным использование режима простой замены, ведь он может применяться только для шифрования массивов данных с размером кратным 64 битам, не содержащим повторяющихся 64-битовых блоков. Кажется, что для любых реальных данных гарантировать выполнение указанных условий невозможно. Это почти так, но есть одно очень важное исключение: вспомните, что размер ключа составляет 32 байта, а размер таблицы замен – 64 байта. Кроме того, наличие повторяющихся 8-байтовых блоков в ключе или таблице замен будет говорить об их весьма плохом качестве, поэтому в реальных ключевых элементах такого повторения быть не может. Таким образом, мы выяснили, что режим простой замены вполне подходит для шифрования ключевой информации, тем более, что прочие режимы для этой цели менее удобны, поскольку требуют наличия дополнительного синхронизирующего элемента данных – синхропосылки (см. следующий раздел). Наша догадка верна, ГОСТ предписывает использовать режим простой замены исключительно для шифрования ключевых данных.

Гаммирование.

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

Теперь перейдем непосредственно к описанию режима гаммирования. Гамма для этого режима получается следующим образом: с помощью некоторого алгоритмического рекуррентного генератора последовательности чисел (РГПЧ) вырабатываются 64-битовые блоки данных, которые далее подвергаются преобразованию по циклу 32-З, то есть зашифрованию в режиме простой замены, в результате получаются блоки гаммы. Благодаря тому, что наложение и снятие гаммы осуществляется при помощи одной и той же операции побитового исключающего или, алгоритмы зашифрования и расшифрования в режиме гаммирования идентичны, их общая схема приведена на рисунке 4.

РГПЧ, используемый для выработки гаммы, является рекуррентной функцией: – элементы рекуррентной последовательности, f – функция преобразования. Следовательно, неизбежно возникает вопрос о его инициализации, то есть об элементе В действительности, этот элемент данных является параметром алгоритма для режимов гаммирования, на схемах он обозначен как S , и называется в криптографии синхропосылкой , а в нашем ГОСТе – начальным заполнением одного из регистров шифрователя. По определенным соображениям разработчики ГОСТа решили использовать для инициализации РГПЧ не непосредственно синхропосылку, а результат ее преобразования по циклу 32-З: . Последовательность элементов, вырабатываемых РГПЧ, целиком зависит от его начального заполнения, то есть элементы этой последовательности являются функцией своего номера и начального заполнения РГПЧ: где f i (X )=f (f i –1 (X )), f 0 (X )=X . С учетом преобразования по алгоритму простой замены добавляется еще и зависимость от ключа:

где Г i – i -тый элемент гаммы, K – ключ.

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

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

• период повторения последовательности чисел, вырабатываемой РГПЧ, не должен сильно (в процентном отношении) отличаться от максимально возможного при заданном размере блока значения 2 64 ;
• соседние значения, вырабатываемые РГПЧ, должны отличаться друг от друга в каждом байте, иначе задача криптоаналитика будет упрощена;
• РГПЧ должен быть достаточно просто реализуем как аппаратно, так и программно на наиболее распространенных типах процессоров, большинство из которых, как известно, имеют разрядность 32 бита.

Исходя из перечисленных принципов, создатели ГОСТа спроектировали весьма удачный РГПЧ, имеющий следующие характеристики:

Где C 0 =1010101 16 ;

Где C 1 =1010104 16 ;

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

Второе выражение нуждается в комментариях, так как в тексте ГОСТа приведено нечто другое: , с тем же значением константы C 1 . Но далее в тексте стандарта дается комментарий, что, оказывается, под операцией взятия остатка по модулю 2 32 –1 там понимается не то же самое, что и в математике. Отличие заключается в том, что согласно ГОСТу (2 32 –1)mod (2 32 –1)=(2 32 –1), а не 0. На самом деле, это упрощает реализацию формулы, а математически корректное выражение для нее приведено выше.

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

Схема алгоритма шифрования в режиме гаммирования приведена на рисунке 4, ниже изложены пояснения к схеме:

Рисунок 4. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования.

Шаг 0

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

• T о(ш) – массив открытых (зашифрованных) данных произвольного размера, подвергаемый процедуре зашифрования (расшифрования), по ходу процедуры массив подвергается преобразованию порциями по 64 бита;
• S – синхропосылка , 64-битовый элемент данных, необходимый для инициализации генератора гаммы;

Шаг 1

Начальное преобразование синхропосылки, выполняемое для ее «рандомизации», то есть для устранения статистических закономерностей, присутствующих в ней, результат используется как начальное заполнение РГПЧ;

Шаг 2

Один шаг работы РГПЧ, реализующий его рекуррентный алгоритм. В ходе данного шага старшая (S 1) и младшая (S 0) части последовательности данных вырабатываются независимо друг от друга;

Шаг 3

Гаммирование. Очередной 64-битовый элемент, выработанный РГПЧ, подвергается процедуре зашифрования по циклу 32–З, результат используется как элемент гаммы для зашифрования (расшифрования) очередного блока открытых (зашифрованных) данных того же размера.

Шаг 4

Результат работы алгоритма – зашифрованный (расшифрованный) массив данных.

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

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

• хранить или передавать синхропосылку вместе с зашифрованным массивом данных, что приведет к увеличению размера массива данных при зашифровании на размер синхропосылки, то есть на 8 байт;
• использовать предопределенное значение синхропосылки или вырабатывать ее синхронно источником и приемником по определенному закону, в этом случае изменение размера передаваемого или хранимого массива данных отсутствует;

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

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

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

где обозначает инвертированное по отношению к t значение бита ().

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

Гаммирование с обратной связью.

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

Схема алгоритмов за- и расшифрования в режиме гаммирования с обратной связью приведена на рисунке 5 и ввиду своей простоты в комментариях не нуждается.

Рисунок 5. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования с обратной связью.

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

Гаммирование;

Гаммирование с обратной связью;

Если в режиме обычного гаммирования изменения в определенных битах шифртекста влияют только на соответствующие биты открытого текста, то в режиме гаммирования с обратной связью картина несколько сложнее. Как видно из соответствующего уравнения, при расшифровании блока данных в режиме гаммирования с обратной связью, блок открытых данных зависит от соответствующего и предыдущего блоков зашифрованных данных. Поэтому, если внести искажения в зашифрованный блок, то после расшифрования искаженными окажутся два блока открытых данных – соответствующий и следующий за ним, причем искажения в первом случае будут носить тот же характер, что и в режиме гаммирования, а во втором случае – как в режиме простой замены. Другими словами, в соответствующем блоке открытых данных искаженными окажутся те же самые биты, что и в блоке шифрованных данных, а в следующем блоке открытых данных все биты независимо друг от друга с вероятностью 1/ 2 изменят свои значения.

Выработка имитовставки к массиву данных.

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

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

• вычисление имитовставки для заданного открытого массива информации;
• подбор открытых данных под заданную имитовставку;

Схема алгоритма выработки имитовставки приведена на рисунке 6.

Рисунок 6. Алгоритм выработки имитовставки для массива данных.

В качестве имитовставки берется часть блока, полученного на выходе, обычно – 32 его младших бита. При выборе размера имитовставки надо принимать во внимание, что вероятность успешного навязывания ложных данных равна величине 2 –| I | на одну попытку подбора, если в распоряжении злоумышленника нет более эффективного метода подбора, чем простое угадывание. При использовании имитовставки размером 32 бита эта вероятность равна

Обсуждение криптографических алгоритмов ГОСТа.

Криптографическая стойкость ГОСТа.

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

• можно ли вообще раскрыть данный шифр;
• если да, то насколько это трудно сделать практически;

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

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

В ГОСТе используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одном из существующих в настоящее время или предполагаемых к реализации в недалеком будущем электронном устройстве нельзя подобрать ключ за время, меньшее многих сотен лет. Эта величина стала фактическим стандартом размера ключа для симметричных криптоалгоритмов в наши дни, – так, новый стандарт шифрования США также его поддерживает. Прежний же американский стандарт, DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 уже не является достаточно стойким в свете возможностей современных вычислительных средств. Это было продемонстрировано в конце 90-х годов несколькими успешными попытками взлома DES переборным путем. Кроме того, DES оказался подвержен специальным способам криптоанализа, таким как дифференциальный и линейный. В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес. В 1998 году его криптографическая слабость была признана официально, – национальный институт стандартов США рекомендовал использовать троекратное шифрование по DES. А в конце 2001 года был официально утвержден новый стандарт шифрования США, AES, построенный на иных принципах и свободный от недостатков своего предшественника .

Замечания по архитектуре ГОСТа.

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

Алгоритмы «основных шагов криптопреобразования» для шифров, подобных ГОСТу, построены идентичным образом, и эта архитектура называется сбалансированная сеть Файстеля (balanced Feistel network) по имени человека, впервые предложившего ее . Схема преобразования данных на одном цикле, или, как его принято называть, раунде , приведена на рисунке 7.

Рисунок 7. Содержание основного шага криптопреобразования для блочных шифров, подобных ГОСТу.

На вход основного шага подается блок четного размера, старшая и младшая половины которого обрабатываются отдельно друг от друга. В ходе преобразования младшая половина блока помещается на место старшей, а старшая, скомбинированная с помощью операции побитового « исключающего или » с результатом вычисления некоторой функции, на место младшей. Эта функция, принимающая в качестве аргумента младшую половину блока и элемент ключевой информации (X ), является содержательной частью шифра и называется его функцией шифрования . По разным соображениям оказалось выгодно разделить шифруемый блок на две одинаковые по размеру части: |N 1 |=|N 2 | – именно этот факт отражает слово «сбалансированная» в названии архитектуры. Впрочем, шифрующие несбалансированные сети также используются время от времени, хотя и не так часто, как сбалансированные. Кроме того, соображения стойкости шифра требуют, чтобы размер ключевого элемента не был меньше размера половины блока: в ГОСТе все три размера равны 32 битам.

Если применить сказанное к схеме основного шага алгоритма ГОСТ, станет очевидным, что блоки 1,2,3 алгоритма (см. рис. 1) определяют вычисление его функции шифрования, а блоки 4 и 5 задают формирование выходного блока основного шага исходя из содержимого входного блока и значения функции шифрования. Более подробно об архитектурах современных блочных шифров с секретным ключом можно прочитать в классических работах , или, в адаптированной форме, в моих работах .

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

Ни одна из рассмотренных автором реализаций DESа для платформы Intel x86 не достигает даже половины производительности предложенной вашему вниманию в настоящей статье реализации ГОСТа несмотря на вдвое более короткий цикл. Все сказанное выше свидетельствует о том, что разработчики ГОСТа учли как положительные, так и отрицательные стороны DESа, а также более реально оценили текущие и перспективные возможности криптоанализа. Впрочем, брать DES за основу при сравнении быстродействия реализаций шифров уже не актуально. У нового стандарта шифрования США дела с эффективностью обстоят гораздо лучше – при таком же как у ГОСТа размере ключа в 256 бит AES работает быстрее него примерно на 14% – это если сравнивать по числу «элементарных операций». Кроме того, ГОСТ практически не удается распараллелить, а у AES возможностей в этом плане намного больше. На некоторых архитектурах это преимущество AES может быть меньше, на других – больше. Так, на процессоре Intel Pentium оно достигает 28%. Подробности можно найти в .

Требования к качеству ключевой информации и источники ключей.

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

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

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

Ключ

Ключ должен являться массивом статистически независимых битов, принимающих с равной вероятностью значения 0 и 1. Нельзя полностью исключить при этом, что некоторые конкретные значения ключа могут оказаться «слабыми», то есть шифр может не обеспечивать заданный уровень стойкости в случае их использования. Однако, предположительно, доля таких значений в общей массе всех возможных ключей ничтожно мала. По крайней мере, интенсивные исследования шифра до сих пор не выявили ни одного такого ключа ни для одной из известных (т.е. предложенных ФАПСИ) таблиц замен. Поэтому ключи, выработанные с помощью некоторого датчика истинно случайных чисел, будут качественными с вероятностью, отличающейся от единицы на ничтожно малую величину. Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, – не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генератором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев, – для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий Пирсона («хи квадрат»), а для проверки независимости битов ключа – критерий серий. Об упомянутых критериях можно прочитать в учебниках или справочниках по математической статистике.

Наилучшим подходом для выработки ключей было бы использование аппаратных датчиков СЧ, однако это не всегда приемлемо по экономическим соображениям. При генерации небольшого по объему массива ключевой информации разумной альтернативой использованию такого датчика является и широко используется на практике метод «электронной рулетки», когда очередная вырабатываемая порция случайных битов зависит от момента времени нажатия оператором некоторой клавиши на клавиатуре компьютера. В этой схеме источником случайных данных является пользователь компьютера, точнее – временные характеристики его реакции. За одно нажатие клавиши при этом может быть выработано всего несколько битов случайных данных, поэтому общая скорость выработки ключевой информации при этом невелика – до нескольких бит в секунду. Очевидно, данный подход не годится для получения больших массивов ключей.

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

Таблица замен

Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования в рамках одной системы криптографической защиты. Даже при нарушении конфиденциальности таблицы замен стойкость шифра остается чрезвычайно высокой и не снижается ниже допустимого предела. Поэтому нет особой нужды держать таблицу в секрете, и в большинстве коммерческих применений ГОСТа так оно и делается. С другой стороны, таблица замен является критически важным элементом для обеспечения стойкости всего шифра. Выбор ненадлежащей таблицы может привести к тому, что шифр будет легко вскрываться известными методами криптоанализа. Критерии выработки узлов замен – тайна за семью печатями и ФАПСИ вряд ли ей поделится с общественностью в ближайшем обозримом будущем. В конечном итоге, для того, чтобы сказать, является ли данная конкретная таблица замен хорошей или плохой, необходимо провести огромный объем работ – многие тысячи человеко- и машино-часов. Единожды выбранная и используемая таблица подлежит замене в том и только в том случае, если шифр с ее использованием оказался уязвимым к тому или иному виду криптоанализа. Поэтому лучшим выбором для рядового пользователя шифра будет взять одну из нескольких таблиц, ставших достоянием гласности. Например, из стандарта на хеш-функцию , она же «центробанковская» ; сведения об этих таблицах можно найти в открытой печати и даже в интернете, если хорошо поискать.

Для тех же, кто не привык идти легкими путями, ниже приведена общая схема получения качественных таблиц:

1. С помощью той или иной методики вырабатываете комплект из восьми узлов замен с гарантированными характеристиками нелинейности. Таких методик существует несколько, одна из них – использование так называемых бент-функций.
2. Проверяете выполнение простейших «критериев качества» – например, тех, что опубликованы для узлов замены DES. Вот еще несколько общих соображений на этот счет: Каждый узел замен может быть описан четверкой логических функций от четырех логических аргументов. Если эти функции, записанные в минимальной форме (т.е. с минимально возможной длиной выражения) окажутся недостаточно сложными, такой узел замены отвергается. Кроме того, отдельные функции в пределах всей таблицы замен должны отличаться друг от друга в достаточной степени. На этом этапе отсеиваются многие заведомо некачественные таблицы.
3. Для шифра с выбранными вами таблицами строите различные модели раунда, соответствующие разным видам криптоанализа, и измеряете соответствующие «профильные» характеристики. Так, для линейного криптоанализа строите линейный статистический аналог раунда шифрования и вычисляете «профильную» характеристику – показатель нелинейности. Если она оказывается недостаточной, таблица замен отвергается.
4. Наконец, используя результаты предыдущего пункта, подвергаете шифр с выбранной вами таблицей интенсивным исследованиям – попытке криптоанализа всеми известными методами. Именно этот этап является наиболее сложным и трудоемким. Но если он сделан качественно, то с высокой степенью вероятности можно констатировать, что шифр с выбранными вами таблицами не будет вскрыт простыми смертными, и, – не исключено, – окажется не по зубам спецслужбам.

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

Относительно таблицы замен необходимо отметить еще один интересный факт. Для обратимости циклов шифрования «32-З» и «32-Р» не требуется, чтобы узлы замен были перестановками чисел от 0 до 15. Все работает даже в том случае, если в узле замен есть повторяющиеся элементы, и замена, определяемая таким узлом, необратима, – однако в этом случае снижается стойкость шифра. Почему это именно так, не рассматривается в настоящей статье, однако в самом факте убедиться несложно. Для этого достаточно попытаться сначала зашифровать, а затем расшифровать блок данных, используя такую «неполноценную» таблицу замен, узлы которой содержат повторяющиеся значения.

Вариации на тему ГОСТа

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

Как поступить в этом и аналогичном ему случаях, чтобы увеличить быстродействие шифрования? Ответ лежит на поверхности – использовать модификацию шифра с меньшим количеством основных шагов (раундов) в базовых циклах. Во сколько раз мы уменьшаем число раундов шифрования, во столько же раз возрастает быстродействие. Указанного изменения можно достигнуть двумя путями, – уменьшением длины ключа и уменьшением числа «циклов просмотра» ключа. Вспомните, что число основных шагов в базовых циклах шифрования равно N =n·m , где n – число 32-битовых элементов в ключе, m – число циклов использования ключевых элементов, в стандарте n =8, m =4. Можно уменьшить любое из этих чисел, но простейший вариант – уменьшать длину ключа, не трогая схемы его использования.

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

Что касается устойчивости шифра к взлому «экстенсивными» методами, то есть к «переборной» атаке, тот тут все более или менее ясно: ключ размером 64 бита находится где-то на грани доступности этому виду атаки, шифр с ключом 96 бит и выше (помните, что ключ должен содержать целое число 32-битовых элементов) вполне устойчив против него. Действительно, несколько лет назад прежний стандарт шифрования США, DES, был неоднократно взломан переборным путем, – сначала его взломала вычислительная сеть, организованная на базе глобальной сети Интернет, а затем – специализированная, т.е. сконструированная специально для этого вычислительная машина. Примем, что стандартный вариант ГОСТа при программной реализации на современных процессорах работает вчетверо быстрее DES. Тогда 8-раундовый «редуцированный ГОСТ» будет работать в 16 раз быстрее DES. Примем также, что за прошедшее с момента взлома DES время производительность вычислительной техники согласно закону Мура возросла вчетверо. Получаем в итоге, что сейчас проверка одного 64-битового ключа для «редуцированного ГОСТа» с восемью циклами осуществляется в 64 раза быстрее, чем в свое время выполнялась проверка одного ключа DES. Таким образом, преимущество такого варианта ГОСТа перед DES по трудоемкости переборной атаки сокращается с 2 64–56 = 2 8 = 256 до 256/ 64 = 4 раз. Согласитесь, это весьма иллюзорное различие, почти что ничего.

Гораздо сложнее оценить устойчивость ослабленных модификаций ГОСТа к «интенсивным» способам криптоанализа. Однако общую закономерность можно проследить и здесь. Дело в том, что «профильные» характеристики многих наиболее сильных на сегодняшний момент видов криптоанализа зависят экспоненциально от числа раундов шифрования. Так, для линейного криптоанализа (ЛКА) это будет характеристика линейности L :

где C и – константы, R – число раундов. Аналогичная зависимость существует и для дифференциального криптоанализа. По своему «физическому смыслу» все характеристики такого рода – вероятности. Обычно объем необходимых для криптоанализа исходных данных и его трудоемкость обратно пропорциональны подобным характеристикам. Отсюда следует, что эти показатели трудоемкости растут экспоненциально с ростом числа основных шагов шифрования. Поэтому при снижении числа раундов в несколько раз трудоемкость наиболее известных видов анализа изменится как, – очень приблизительно и грубо, – корень этой степени из первоначального количества. Это очень большое падение стойкости.

С другой стороны, ГОСТ проектировался с большим запасом прочности и на сегодняшний день устойчив ко всем известным видам криптоанализа, включая дифференциальный и линейный. Применительно к ЛКА это означает, что для его успешного проведения требуется больше пар «открытый блок – зашифрованный блок», чем «существует в природе», то есть более 2 64 . С учетом сказанного выше это означает, что для успешного ЛКА 16-раундового ГОСТа потребуется не менее блоков или 2 35 байтов или 32 Гбайта данных, а для 8-раундового – не менее блоков или 2 19 байтов или 0.5 Мбайт.

Выводы из всего, сказанного выше, приведены в следующей таблице, обобщающей характеристики редуцированных вариантов ГОСТа.

Число раундов	Размер ключа, бит	Индекс быстро-действия	Вероятные характеристики шифра(очень грубая оценка)
24	192	1,33	Устойчив к большинству известных видов КА, или находиться на грани устойчивости. Практическая реализация КА невозможна из-за высоких требований к исходным данным и трудоемкости.
16	128	2	Теоретически неустойчив к некоторым видам криптоанализа, однако их практическая реализация в большинстве случаев затруднена из-за высоких требований к исходным данным и трудоемкости.
12	95	2,67	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков-сотен Кбайт) на короткий срок.
8	64	4	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков Кбайт) на короткий срок.

Два последних варианта, с 12 и 8 раундами, способны обеспечить весьма и весьма ограниченную во времени защиту. Их использование оправдано лишь в задачах, где требуется лишь краткосрочная секретность закрываемых данных, порядка нескольких часов. Возможная область применения этих слабых вариантов шифра – закрытие UDP-трафика электронных биржевых торговых систем. В этом случае каждый пакет данных (datagram, средняя «D» из аббревиатуры UDP) шифруется на отдельном 64-битовом ключе, а сам ключ шифруется на сеансовом ключе (ключе, область действия которого – один сеанс связи между двумя компьютерами) и передается вместе с данными.

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

У рассматриваемого вопроса есть и обратная сторона. Что если скорость шифрования некритична, а требования к стойкости весьма жестки? Повысить стойкость ГОСТа можно двумя путями – условно назовем их «экстенсивный» и «интенсивный». Первый из них – это ни что иное, как простое увеличение числа раундов шифрования. Мне не совсем понятно, зачем это может реально понадобиться, ведь отечественный стандарт и без этого обеспечивает необходимую стойкость. Впрочем, если вы страдаете паранойей больше необходимого уровня (а все «защитники информации» просто обязаны ею страдать, это условие профпригодности такое, вопрос только в степени тяжеcти случая:), это поможет вам несколько успокоиться. Если вы не уверены в этом КГБ-шном шифре или используемой вами таблице замен, просто удвойте, учетверите, и т.д. число раундов – кратность выберите исходя из тяжести вашего случая. Указанный подход позволяет реально увеличить стойкость шифра, – если раньше криптоанализ был просто невозможным, то теперь он невозможен в квадрате!

Более хитрым и интересным является вопрос, а можно ли увеличить стойкость шифра, не меняя количества и структуры основных шагов шифрования. Как ни удивительно, ответ на этот него положительный, хотя мы опять ступаем на зыбкую почву спекуляций. Дело в том, что в ГОСТе на основном шаге преобразования предполагается выполнение замены 4 на 4 бит, а на практике (речь об этом еще впереди) все программные реализации выполняют замену побайтно, т.е. 8 на 8 бит – так делается по соображениям эффективности. Если сразу спроектировать такую замену как 8-битовую, то мы существенно улучшим характеристики одного раунда. Во-первых, увеличится «диффузионная» характеристика или показатель «лавинности» – один бит исходных данных и/или ключа будет влиять на большее число бит результата. Во вторых, для больших по размеру узлов замены можно получить более низкие дифференциальную и линейную характеристики, уменьшив тем самым подверженность шифра одноименным видам криптоанализа. Особенно актуально это для редуцированных циклов ГОСТа, а для 8 и 12-раундовых вариантов такой шаг просто необходим. Это несколько скомпенсирует потерю стойкости в них от уменьшения числа раундов. Что затрудняет использование этого приема – так это то, что конструировать подобные «увеличенные» узлы замены вам придется самостоятельно. А также то, что более крупные узлы вообще конструировать заметно труднее, чем меньшие по размеру.

Нестандартное использование стандарта.

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

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

• Как уже отмечалось выше, гамму можно использовать как «сырье» для выработки ключей. Для этого нужно лишь получить отрезок гаммы нужной длины – 32 байта. Таким способом ключи можно изготавливать по мере необходимости и их не надо будет хранить, – если такой ключ понадобится повторно, будет достаточно легко его выработать снова. Надо только будет вспомнить, на каком ключе он был выработан исходно, какая использовалась синхропосылка и с какого байта выработанной гаммы начинался ключ. Вся информация, кроме использованного ключа, несекретна. Данный подход позволит легко контролировать достаточно сложную и разветвленную систему ключей, используя всего лишь один «мастер-ключ».
• Аналогично предыдущему, гамму можно использовать в качестве исходного «сырья» для выработки паролей. Тут может возникнуть вопрос, зачем вообще нужно их генерировать, не проще ли по мере надобности их просто выдумывать. Несостоятельность такого подхода была наглядно продемонстрирована серией инцидентов в компьютерных сетях, самым крупным из которых был суточный паралич интернета в ноябре 1988 года, вызванный «червем Морриса». Одним из способов проникновения злоумышленной программы на компьютер был подбор паролей: программа пыталась войти в систему, последовательно перебирая пароли из своего внутреннего списка в несколько сотен, причем в значительной доле случаев ей это удавалось сделать. Фантазия человека по выдумыванию паролей оказалась весьма бедной. Именно поэтому в тех организациях, где безопасности уделяется должное внимание, пароли генерирует и раздает пользователям системный администратор по безопасности. Выработка паролей чуть сложнее, чем выработка ключей, так как при этом «сырую» двоичную гамму необходимо преобразовать к символьному виду, а не просто «нарезать» на куски. Кроме того, отдельные значения, возможно, придется отбросить, чтобы обеспечить равную вероятность появления всех символов алфавита в пароле.
• Еще один способ использования криптографической гаммы – гарантированное затирание данных на магнитных носителях. Дело в том, что даже при перезаписи информации на магнитном носителе остаются следы предыдущих данных, которые может восстановить соответствующая экспертиза. Для уничтожения этих следов такую перезапись надо выполнить многократно. Оказалось, что потребуется перезаписывать информацию на носитель меньшее количество раз, если при такой процедуре использовать случайные или псевдослучайные данные, которые останутся неизвестными экспертам, пытающимся восстановить затертую информацию. Гамма шифра здесь будет как нельзя кстати.

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

• Мы знаем, что один из таких вариантов использования ГОСТа – выработка имитовставки для массивов данных. Однако на базе любого блочного шифра, и ГОСТа в том числе, достаточно легко построить схему вычисления односторонней хэш-функции, называемой также в литературе MDC, что в разных источниках расшифровывается как код обнаружения изменений / манипуляций (M odification/M anipulation D etection C ode) или дайджест сообщения (M essage D igest C ode). Первая расшифровка появилась в литературе гораздо раньше, вторую, более короткую, я думаю, придумали те, кому оказалось не под силу запомнить первую:), – это была шутка. MDC может непосредственно использоваться в системах имитозащиты в качестве аналога имитовставки, не зависящего, однако, от секретного ключа. Кроме того, MDC широко используется в схемах электронно-цифровой подписи (ЭЦП), ведь большинство таких схем сконструированы таким способом, что подписывать удобно блок данных фиксированного размера. Как известно, на базе обсуждаемого стандарта ГОСТ 28147-89 построен стандарт Российской Федерации на вычисление односторонней хэш-функции ГОСТ Р34.11-94 .
• Менее известно, что на базе любого блочного шифра, и ГОСТа в том числе, может быть построена вполне функциональная схема ЭЦП, с секретным ключом подписи и открытой проверочной комбинацией. По ряду причин эта схема не получила широкого практического распространения, однако в отдельных случаях до сих пор может рассматриваться как весьма привлекательная альтернатива доминирующим ныне в мире «математическим» схемам ЭЦП.

Литература

Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ 28147-89. Гос. Ком. СССР по стандартам, М., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Шеннон Клод. Математическая теория секретных систем. В сборнике «Работы по теории информации и кибернетике», М., ИЛ, 1963, с. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Announcing Approval of Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, No. 235 / Thursday, December 6, 2001 / Notices, pp 63369–63371. http://csrc.nist.gov/encryption/aes/
Файстель Хорст. Криптография и компьютерная безопасность. Перевод А.Винокурова по изданию Horst Feistel. Cryptography and Computer Privacy, Scientific American, May 1973, Vol. 228, No. 5, pp. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Шнайер Брюс. Прикладная криптография. 2-е изд. Протоколы, алгоритмы и исходные тексты на языке Си., М., «Триумф», 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Handbook of applied cryptography. ttp://www.cacr.math.uwaterloo.ca/hac/
Винокуров Андрей. Как устроен блочный шифр? Рукопись. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Винокуров Андрей. Выпуски по криптографии для электронного журнала iNFUSED BYTES online. http://www.enlight.ru/crypto/articles/ib/ib.htm
Винокуров Андрей, Применко Эдуард. Текст доклада «О программной реализация стандартов шифрования РФ и США», конференция по информатизации, Москва, МИФИ, 28-29 января 2001г. Опубликован в материалах конференции.
Информационная технология. Криптографическая защита информации. Функция хэширования ГОСТ Р34.11-94, Госстандарт РФ, М., 1994.