Задачи по информационной безопасности
Задания на контрольную работу 2
Примеры выполнения заданий 3
Приложение А. Алгоритм шифрования ГОСТ 28147-89 10
Приложение Б. Символы кириллицы
(альтернативная кодовая таблица ASCII) 13
Приложение В. Блок подстановки в алгоритме шифрования
ГОСТ 28147-89 14
Приложение Г. Алгоритм шифрования RSA 15
Приложение Д. Таблица простых чисел 17
Приложение Е. Функция хеширования 18
Приложение Ж. Электронная цифровая подпись 19
Вопросы к зачету 21
Литература 22
Задача №1. Шифр Цезаря .
Используя шифр Цезаря, зашифруйте свои данные: Фамилию Имя Отчество.
Задача №2. Алгоритм шифрования гост 28147-89.
Выполните первый цикл алгоритма шифрования ГОСТ 28147 89 в режиме простой замены. Для получения 64 бит исходного текста используйте 8 первых букв из своих данных: Фамилии Имени Отчества. Для получения ключа (256 бит) используют текст, состоящий из 32 букв. Первый подключ содержит первые 4 буквы.
Задача №3. Алгоритм шифрования rsa.
Сгенерируйте открытый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.
Задача №4. Функция хеширования.
Найти хеш–образ своей Фамилии, используя хеш–функцию , гдеn = pq.
Задача №5. Электронная цифровая подпись.
Примеры выполнения заданий
Задача №1. Шифр Цезаря . Используя шифр Цезаря, зашифруйте свои данные: Фамилию Имя Отчество.
Исходный текст:
« КОЗИНА ГАЛИНА ЛЕОНИДОВНА»
Используем алфавит, содержащий 33 буквы и пробел, стоящий после буквы Я:
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯпробел
Ключом в шифре Цезаря является число 3. Каждая буква в исходном тексте сдвигается по алфавиту на 3 позиции. Таким образом, получаем:
Исходный текст |
ЛЕОНИДОВНА |
||||
Зашифрованный текст |
ОЗСРЛЖСЕРГ |
Задача №2. Алгоритм шифрования ГОСТ 28147-89. Выполните первый цикл алгоритма шифрования ГОСТ 28147-89 в режиме простой замены. Для получения 64 бит исходного текста используйте 8 первых букв из своих данных: Фамилии Имени Отчества. Для получения ключа (256 бит) используют текст, состоящий из 32 букв. Первый подключ содержит первые 4 буквы.
Исходные данные для зашифрования: КОЗИНА Г
Для ключа возьмем последовательность состоящую из 32 букв:
АЛИНа пошла в лес собирать грибы
Для первого подключа Х используем первые 4 буквы ключа: АЛИН.
Переводим исходный текст и первый подключ в двоичную последовательность (см. Приложение Б):
исходный текст
первый подключ X0
Таким образом, первые 64 бита определяют входную последовательность
L0: 11001010 11001110 11000111 11001000
R0: 11001101 11000000 00100000 11000011
следующие 32 бита определяют первый подключ
Х0: 11000000 11001011 11001000 11001101
I. Найдем значение функции преобразования f(R0,X0) (см. Приложение А)
1). Вычисление суммы R0 и X0 по mod 2 32
R0: 1100 1101 1100 0000 0010 0000 1100 0011
Х0: 1100 0000 1100 1011 1100 1000 1100 1101
1000 1110 1000 1011 1110 1001 1001 0000
2). Преобразование в блоке подстановки
Результат суммирования R0+X0 по mod 2 32
1000 1110 1000 1011 1110 1001 1001 0000
преобразуем в блоке подстановки (см. Приложение В). Для каждого 4-битного блока вычислим его адрес в таблице подстановки. Номер блока соответствует номеру столбца, десятичное значение блока соответствует номеру строки в таблице. Таким образом, 5-тый блок (1011) заменяется заполнением 11-ой строки и пятого столбца в таблице подстановки (1110).
номера блоков
1000 1110 1000 1011 1110 1001 1001 0000
соответствующие номера строк в таблице подстановки
8 14 8 11 14 9 9 0
заполнение
9 2 3 14 5 15 3 4
результат
1001 0010 0011 1110 0101 1111 0011 0100
3). Циклический сдвиг результата п.2 на 11 бит влево
Таким образом, нашли значение функции f (R0,X0):
1111 0010 1111 1001 1010 0100 1001 0001
II. Вычисляем R1= f(R0,X0) L0.
Результат преобразования функции f(R0,X0) складываем с L0 по mod2:
L0: 1100 1010 1100 1110 1100 0111 1100 1000
f(R0,X0): 1111 0010 1111 1001 1010 0100 1001 0001
R1: 0011 1000 0011 0111 0110 0011 0101 1001
Задача №3. Алгоритм шифрования RSA . Сгенерируйте откры-тый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.
I.Генерация ключей (см. Приложение Г).
Выберем два простых числа р = 13 и q = 19 (см. Приложение Д).
Тогда модуль
n = pq =13*19 = 247
и функция Эйлера
(n ) = (p -1)(q -1) = 12*18 = 216.
Закрытый ключ d выбираем из условий d < (n ) и d взаимно просто с (n ) , т.е. d и (n ) не имеют общих делителей.
Пусть d = 25.
Открытый ключ e выбираем из условий e < (n ) и de =1(mod (n )): e <216,
25e =1(mod 216).
Последнее условие означает, что число 25e -1 должно делиться на 216 без остатка.
Таким образом, для определения e нужно подобрать такое число k , что
25e -1 = 216 k .
При k =14 получаем 25e =3024+1 или
В нашем примере
(121, 247) – открытый ключ,
(25, 247) – секретный ключ.
II. Шифрование.
Представим шифруемое сообщение «КГЛ» как последова-тельность целых чисел. Пусть буква «К» соответствует числу 12, буква «Г» - числу 4 и буква «Л» - числу 13.
Зашифруем сообщение, используя открытый ключ (121, 247):
С 1
= (
)
mod
247= 12
С 2
= (
)
mod
247=199
С 3
= (
)
mod
247= 91
Таким образом, исходному сообщению (12, 4, 13) соответствует криптограмма (12, 199, 91).
III. Расшифрование
Расшифруем сообщение (12, 199, 91), пользуясь секретным ключом (25,247):
М 1
= (
)
mod 247=12
М 2
= (
)
mod 247= 4
М З
= (
)
mod 247=13
В результате расшифрования было получено исходное сообщение (12, 4, 13), то есть "КГЛ".
Замечания.
Например,
Для рассматриваемого примера получим
Задача №4. Функция
хеширования.
Найти
хеш–образ своей Фамилии, используя
хеш–функцию
,
гдеn
= pq,
p,
q
взять из Задания №3.
Хешируемое сообщение «КОЗИНА». Возьмем два простых числа p =13, q =19 (см. Приложение Е). Определим n =pq =13*19=247. Вектор инициализации выберем равным 8 (выбираем случайным образом). Слово«КОЗИНА» можно представить последователь-ностью чисел (12, 16, 9, 10, 15, 1) по номерам букв в алфавите. Таким образом,
n=247, H 0 =8, M 1 =12, M 2 =16, M 3 =9, M 4 =10, M 5 =15, M 6 =1.
Используя формулу
,
получим хеш-образ сообщения «КОЗИНА»:
H 1 =(H 0 +M 1) 2 mod n = (8 + 12) 2 mod 247 = 400 mod 247=153
H 2 =(H 1 +M 2) 2 mod n = (153 + 16) 2 mod 247 = 28561 mod 247= 156
H 3 =(H 2 +M 3) 2 mod n = (156 + 9) 2 mod 247 = 27225 mod 247= 55
H 4 =(H 3 +M 4) 2 mod n = (55 + 10) 2 mod 247 = 4225 mod 247= 26
H 5 =(H 4 +M 5) 2 mod n = (26 + 15) 2 mod 247 = 1681 mod 247= 199
H 6 =(H 5 +M 6) 2 mod n = (199 + 1) 2 mod 247 = 40000 mod 247= 233
В итоге получаем хеш-образ сообщения «КОЗИНА», равный 233.
Задача №5. Электронная цифровая подпись. Используя хеш-образ своей Фамилии, вычислите электронную цифровую подпись по схеме RSA.
Пусть хеш-образ Фамилии равен 233, а закрытый ключ алгоритма RSA равен (25, 247). Тогда электронная цифровая подпись сообщения, состоящего из Фамилии, вычисляется по правилу (см. Приложение Ж)
s = 233 25 mod 247 = 168.
Для проверки ЭЦП, используя открытый ключ (121, 247), найдем
H = 168 121 mod 247 = 233.
Поскольку хеш-образ сообщения совпадает с найденным значением H, то подпись признается подлинной.
Этот алгоритм является обязательным для применения в качестве алгоритма шифрования в государственных организациях РФ и ряде коммерческих .
Описание алгоритма
Схема алгоритма показана на рис. 3.1 . Как видно, схема этого алгоритма достаточно проста, что однозначно упрощает его программную или аппаратную реализацию.
Алгоритм ГОСТ 28147-89 шифрует информацию блоками по 64 бита, которые разбиваются на два субблока по 32 бита (N1 и N2). Субблок N1 определенным образом обрабатывается, после чего его значение складывается
со значением субблока N2 (сложение выполняется по модулю 2), затем субблоки меняются местами. Такое преобразование выполняется определенное количество раундов: 16 или 32 в зависимости от режима работы алгоритма (описаны далее). В каждом раунде выполняются следующие операции:
1. Наложение ключа. Содержимое субблока /VI складывается по модулю 2 32 с частью ключа Кх.
Ключ шифрования алгоритма ГОСТ 28147-89 имеет размерность 256 битов, а Кх— это его 32-битная часть, т. е. 256-битный ключ шифрования представляется в виде конкатенации 32-битных подключей (рис. 3.2):
Щ ATI, АГ2, Ю, АГ4, К5, Кб, К7.
В процессе шифрования используется один из этих подключей — в зависимости от номера раунда и режима работы алгоритма.
Рис. 3.1. Схема алгоритма ГОСТ 28147-
Рис. 3.2. Ключ шифрования алгоритма ГОСТ 28147-89
2. Табличная замена. После наложения ключа субблок /VI разбивается на 8 частей по 4 бита, значение каждой из которых по отдельности заменяется в соответствии с таблицей замены для данной части субблока. Табличные замены (Substitution box, S-box) часто используются в современных алгоритмах шифрования, поэтому стоит рассмотреть их подробнее.
Табличная замена используется таким образом: на вход подается блок данных определенной размерности (в этом случае — 4-битный), числовое представление которого определяет номер выходного значения. Например, имеем S-box следующего вида:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Пусть на вход пришел 4-битный блок «0100», т. е. значение 4. Согласно таблице, выходное значение будет равно 15, т.е. «1111» (0 заменяется на 4, 1 — на 11, значение 2 не изменяется и т. д.).
Как видно, схема алгоритма весьма проста, что означает, что наибольшая нагрузка по шифрованию данных ложится на таблицы замен. К сожалению, алгоритм обладает тем свойством, что существуют «слабые» таблицы замен, при использовании которых алгоритм может быть раскрыт криптоаналитическими методами. К числу слабых относится, например, таблица, в которой выход равен входу :
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Побитовый циклический сдвиг влево на 11 битов.
Режимы работы алгоритма
Алгоритм ГОСТ 28147-89 имеет 4 режима работы:
□ режим простой замены;
□ режим гаммирования;
П режим гаммирования с обратной связью;
□ режим выработки имитоприставок.
Эти режимы несколько отличаются от общепринятых (описанных в разд. 1.4), поэтому стоит рассмотреть их подробнее.
Данные режимы имеют различное назначение, но используют одно и то же описанное выше шифрующее преобразование.
Режим простой замены
В режиме простой замены для зашифровывания каждого 64-битного блока информации просто выполняются 32 описанных выше раунда. 32-битные подключи используются в следующей последовательности:
□ КО, Kl, К2, КЗ, К4, К5, Кб, АГ7, КО, ATI и т. д. — в раундах с 1-го по 24-й;
□ К1, Кб, К5, К4, КЗ, К2, К\, КО —в раундах с 25-го по 32-й.
Расшифровывание в режиме простой замены производится совершенно так же, но с несколько другой последовательностью применения подключей:
□ КО, К\, К2, КЗ, К4, К5, Кб, КП — в раундах с 1-го по 8-й;
□ КП, Кб, К5, К4, КЗ, К2, К\, КО, К1, Кб и т. д. — в раундах с 9-го по 32-й.
Аналогично стандартному режиму ЕСВ, по причине раздельного шифрования блоков режим простой замены категорически не рекомендуется использовать для шифрования собственно данных; он должен использоваться только для шифрования других ключей шифрования в многоключевых схемах.
Режим гаммирования
В режиме гаммирования (рис. 3.3) каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бита. Гамма шифра — это специальная последовательность, которая вырабатывается с помощью описанных выше преобразований следующим образом:
1. В регистры N1 и N2 записывается их начальное заполнение— 64-битная величина, называемая «синхропосылкой» (синхропосылка, практически, является аналогом вектора инициализации в режимах СВС, CFB и OFB).
2. Выполняется зашифровывание содержимого регистров /VI и N2 (в данном случае — синхропосылки) в режиме простой замены.
3. Содержимое N1 складывается по модулю (2 32 – 1) с константой CI = 2 24 + 2 16 + 2 8 + 4 , результат сложения записывается в регистр /VI.
4. Содержимое N2 складывается по модулю 2 с константой С2 = 2 24 + 2 16 + 2 8 +1, результат сложения записывается в регистр N2.
5. Содержимое регистров /VI и N2 подается на выход в качестве 64-битного блока гаммы шифра (т. е. в данном случае /VI и N2 образуют первый блок гаммы).
6. Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифровывание или расшифровывание), выполняется возврат к шагу 2.
Для расшифровывания аналогичным образом выполняется выработка гаммы, затем снова применяется операция XOR к битам зашифрованного текста и гаммы.
Для выработки той же самой гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же самый ключ и то же значение синхропосылки, которые применялись при зашифровывании информации. В противном случае получить исходный текст из зашифрованного не удастся.
В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не является секретным элементом, однако синхропосылка может быть так же секретна, как и ключ шифрования. В этом случае можно считать, что эффективная длина ключа алгоритма (256 битов) увеличивается еще на 64 бита синхропосылки, которую можно рассматривать как дополнительный ключевой элемент.
Режим гаммирования с обратной связью
В режиме гаммирования с обратной связью в качестве заполнения регистров /VI и Л/2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифровывания предыдущего блока открытого текста (рис. 3.4). Первый же блок в данном режиме генерируется полностью аналогично предыдущему.
Рис. 3.4. Выработка гаммы шифра в режиме гаммирования с обратной связью
Режим выработки имитоприставки
Имитоприставка — это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. Для ее вычисления существует специальный режим алгоритма ГОСТ 28147-89.
Генерация имитоприставки выполняется следующим образом:
1. Первый 64-битный блок информации, для которой вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены, в котором выполняются первые 16 раундов из 32.
2. Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
3. М и N2 снова зашифровываются в сокращенном режиме простой замены и т. д. до последнего блока информации.
Имитоприставкой считается 64-битное результирующее содержимое регистров N1 и N2 или его часть. Чаще всего используется 32-битная имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как и любая контрольная сумма, имитоприставка предназначена, прежде всего, для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы — в первую очередь электронная цифровая подпись {см. разд. 1.1).
Имитоприставка используется следующим образом:
1. При зашифровывании какой-либо информации вычисляется имитоприставка открытого текста и посылается вместе с шифртекстом.
2. После расшифровывания имитоприставка снова вычисляется и сравнивается с присланной.
3. Если вычисленная и присланная имитоприставки не совпадают— шифр-текст был искажен при передаче или использовались неверные ключи при расшифровывании.
Имитоприставка особенно полезна для проверки правильности расшифровывания ключевой информации при использовании многоключевых схем.
Имитоприставка— это некоторый аналог кода аутентификации сообщений MAC, вычисляемого в режиме СВС; отличие состоит в том, что при вычислении имитоприставки не используется синхропосылка, тогда как при вычислении MAC используется вектор инициализации.
Криптостойкость алгоритма
В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на английский язык и опубликовано ; именно после этого стали появляться результаты его анализа, выполненного зарубежными специалистами; однако в течение значительного времени не было найдено каких-либо атак, приближающихся к практически осуществимым .
□ большой длины ключа — 256 битов; вместе с секретной синхропосылкой эффективная длина ключа увеличивается до 320 битов;
□ 32 раундов преобразований; уже после 8 раундов достигается полный эффект рассеивания входных данных: изменение одного бита блока открытого текста повлияет на все биты блока шифртекста, и наоборот, т. е. существует многократный запас стойкости.
Рассмотрим результаты криптоанализа алгоритма ГОСТ 28147-89.
Анализ таблиц замен
Поскольку таблицы замен в стандарте не приведены, в ряде работ (например, в ) высказывается предположение, что «компетентная организация» может выдать как «хорошие», так и «плохие» таблицы замен. Однако в известнейший эксперт Брюс Шнайер называет такие предположения «слухами». Ясно, что криптостойкость алгоритма во многом зависит от свойств используемых таблиц замен, соответственно, существуют слабые таблицы замен (пример см. выше), применение которых может упростить вскрытие алгоритма. Тем не менее, возможность использования различных таблиц замен кажется весьма достойной идеей, в пользу которой можно привести два следующих факта из истории стандарта шифрования DES (подробности см. в разд. 3.15):
□ атаки с помощью как линейного, так и дифференциального криптоанализа алгоритма DES используют конкретные особенности таблиц замен; при использовании других таблиц криптоанализ придется начинать сначала;
□ были предприняты попытки усилить DES против линейного и дифференциального криптоанализа путем использования более стойких таблиц замен; такие таблицы, действительно более стойкие, были предложены, например, в алгоритме s 5 DES ; но, увы, заменить DES на s 5 DES было невозможно, поскольку таблицы замен жестко определены в стандарте , соответственно, реализации алгоритма наверняка не поддерживают возможность смены таблиц на другие.
В ряде работ (например, , и ) ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом). Однако в работе доказано, что секретные таблицы замен могут быть вычислены с помощью следующей атаки, которая может быть применена практически:
1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т. е. значения z = /(0), где /() — функция раунда алгоритма. Этот этап занимает порядка 2 операций шифрования.
2. С помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 2 11 операций.
Модификации алгоритма и их анализ
В работе проведен криптоанализ модификаций алгоритма ГОСТ 28147-89:
□ алгоритма GOST-H, в котором, относительно оригинального алгоритма, изменен порядок использования подключей, а именно в раундах с 25-го по 32-й подключи используются в прямом порядке, т. е. точно так же, как и в предыдущих раундах алгоритма;
□ 20-раундового алгоритма GOST®, в раунде которого для наложения ключа используется операция XOR вместо сложения по модулю 2 32 .
По результатам анализа сделан вывод о том, что GOST-H и GOST© слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей. Стоит отметить, что в части криптоанализа GOST© работа слово в слово повторяет раздел, посвященный криптоанализу алгоритма ГОСТ 28147-89, вышедшей в 2000 г. известной работы (без каких-либо ссылок на оригинал). Это ставит под сомнение профессионализм авторов работы и остальные ее результаты.
Весьма интересная модификация алгоритма предложена в работе : таблицы S\…Ss обязательно должны быть различными; в каждом раунде алгоритма должна выполняться их перестановка по определенному закону. Данная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т. е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.
И еще одна модификация, связанная с таблицами замен, приведена в работе , в которой анализируется один из возможных методов вычисления таблиц замен на основе ключа шифрования. Авторы работы сделали вывод, что подобная зависимость ослабляет алгоритм, поскольку приводит к наличию слабых ключей и к некоторым потенциальным уязвимостям алгоритма.
Анализ полнораундового алгоритма
Существуют атаки и на полнораундовый ГОСТ 28147-89 без каких-либо модификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма,— широко известная работа — посвящена атакам, использующим слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако сильные таблицы замен (например, приведенная в ) делают такую атаку абсолютно непрактичной.
Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. в работе предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифртекстов с достаточно низкой сложностью. Криптоанализ алгоритма продолжен в работе .
В 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 битов секретного ключа . Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрования. Как видно, данная атака, практически, бесполезна для реального вскрытия алгоритма.
Алгоритм, определяемый ГОСТ 28147-89, имеет длину ключа шифрования 256 бит. Он шифрует информацию блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2) (рисунок 1). Субблок N1 обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - «исключающее или»), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз («раундов»): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции.
Рисунок 1. Схема алгоритма ГОСТ 28147-89.
Первая - наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-бит частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-бит подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.
Вторая операция - табличная замена. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.
Табличные замены (Substitution box - S-box) часто используются в современных алгоритмах шифрования, поэтому стоит пояснить, как организуется подобная операция. В таблицу записываются выходные значения блоков. Блок данных определенной размерности (в нашем случае - 4-бит) имеет свое числовое представление, которое определяет номер выходного значения. Например, если S-box имеет вид 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 и на вход пришел 4-бит блок «0100» (значение 4), то, согласно таблице, выходное значение будет равно 15, т. е. «1111» (0 а 4, 1 а 11, 2 а 2 ...).
Алгоритм, определяемый ГОСТ 28147-89, предусматривает четыре режима работы: простой замены, гаммирования, гаммирования с обратной связью и генерации имитоприставок. В них используется одно и то же описанное выше шифрующее преобразование, но, поскольку назначение режимов различно, осуществляется это преобразование в каждом из них по-разному.
В режиме простой замены для зашифрования каждого 64-бит блока информации выполняются 32 описанных выше раунда. При этом 32-бит подключи используются в следующей последовательности:
K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;
K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.
Расшифрование в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:
K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;
K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.
Все блоки шифруются независимо друг от друга, т. е. результат зашифрования каждого блока зависит только от его содержимого (соответствующего блока исходного текста). При наличии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающегося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифрования (очень часто реализуются многоключевые схемы, в которых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы - гаммирования и гаммирования с обратной связью.
В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2.
- 1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.
- 2. Выполняется зашифрование содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.
- 3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.
- 4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.
- 5. Содержимое регистров N1 и N2 подается на выход в качестве 64-бит блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).
Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифрование или расшифрование), выполняется возврат к операции 2.
Для расшифрования гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR. Поскольку эта операция обратима, в случае правильно выработанной гаммы получается исходный текст (таблица 1).
Таблица 1. Зашифрование и расшифрование в режиме гаммирования
Для выработки нужной для расшифровки гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же ключ и то же значение синхропосылки, которые применялись при зашифровании информации. В противном случае получить исходный текст из зашифрованного не удастся.
В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не секретна, однако есть системы, где синхропосылка - такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бит секретной синхропосылки, которую также можно рассматривать как ключевой элемент.
В режиме гаммирования с обратной связью для заполнения регистров N1 и N2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифрования предыдущего блока открытого текста (рисунок 2). Первый же блок в данном режиме генерируется полностью аналогично предыдущему.
Рисунок 2. Выработка гаммы шифра в режиме гаммирования с обратной связью.
Рассматривая режим генерации имитоприставок, следует определить понятие предмета генерации. Имитоприставка - это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-бит блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-бит содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-бит имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.
При обмене информацией имитоприставка служит своего рода дополнительным средством контроля. Она вычисляется для открытого текста при зашифровании какой-либо информации и посылается вместе с шифртекстом. После расшифрования вычисляется новое значение имитоприставки, которое сравнивается с присланной. Если значения не совпадают - значит, шифртекст был искажен при передаче или при расшифровании использовались неверные ключи. Особенно полезна имитоприставка для проверки правильности расшифрования ключевой информации при использовании многоключевых схем.
Алгоритм ГОСТ 28147-89 считается очень сильным алгоритмом - в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод «грубой силы». Его высокая стойкость достигается в первую очередь за счет большой длины ключа - 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).
Достоинствами ГОСТ 28147-89 являются наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТ.
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 .
Раунд | 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 . При расшифровании подключи должны быть использованы в обратном порядке, а именно, как указано на