Задачи по информационной безопасности

Задания на контрольную работу 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, то подпись признается подлинной.

Алгоритм шифрования ГОСТ 28147-89. Метод простой замены. — Архив WASM.RU

«Пока ты жив, не умирай, на этот мир взгляни.
У многих здесь душа мертва – они мертвы внутри.
Но ходят и смеются, не зная, что их нет,
Не торопи свой смертный час» – она сказала мне.

Ария, «Там высоко»

2.1 Сети Файстеля.
2.2 Блочный шифр ГОСТ 28147-89

3.1 Ключевая информация
3.2 Основной шаг криптопреобразования

3.3 Базовые циклы: “ 32-З ” , “ 32-Р ” .

4.1 Реализация основного шага криптопреобразования
4.2 Увеличение быстродействия алгоритма
5. Требования к ключевой информации
6. Список использованной литературы
7. Благодарности.

Введение.

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

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

Предварительные сведения о блочных шифрах.

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

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

Группу исследователей – разработчиков фирмы IBM, приступившей к исследованию систем шифрования с симметричной схемой использования ключей, возглавил доктор Хорст Файстель .

2.1 Сети Файстеля

Предложенная Файстелем архитектура нового метода шифрования в классической литературе получила название «Архитектура Файстеля», но на данный момент в русской и зарубежной литературе используется более устоявшийся термин – "сеть Файстеля" или Feistel`s NetWork. В последствии по данной архитектуре был построен шифр «Люцифер» - который позднее был опубликован и вызвал новую волну интереса к криптографии в целом.

Идея архитектуры "сети Файстеля" заключается в следующем: входной поток информации разбивается на блоки размером в n битов, где n четное число. Каждый блок делится на две части – L и R, далее эти части подаются в итеративный блочный шифр, в котором результат j-го этапа определяется результатом предыдущего этапа j-1! Сказанное можно проиллюстрировать на примере:

Рис. 1

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

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

Для того чтобы идея сетей Файстеля была окончательна ясна, рассмотрим простейший случай изображенный на рис. 1 , где в функции А – выступит операции “mod 2” (“xor”), но это простейший случай, в более серьезной ситуации, например сокрытие информации государственной важности функция А может быть более сложной (сколько я видел функция А действительно бывает очень сложной):

Исходные данные:

L = 1110b, R = 0101, K = 1111b

Получить шифрограмму

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Поясним наши действия:

1. Эта операция сложение по mod 2 4 . На практике такая операция сводится к простому сложению, где мы должны сложить два числа и проигнорировать перенос в 5й разряд. Так как, если проставить над разрядами двоичного представления числа проставить показатели степени, над пятым разрядом как раз будет показатель четыре, взглянем на рисунок ниже, где изображены действия нашей операции:

Рис. 2

Здесь я стрелкой указал на показатели степени, как видно, результат должен был получиться 10100, но так как при операции mod 2 4 игнорируется перенос, мы получаем 0100.

2. Эта операция в литературе называется mod 2, на языке ассемблера реализуется командой XOR . Но ее более правильное название mod 2 1 . Без этой уникальной операции вряд ли можно построить быстрый, легко реализуемый алгоритм шифрования и при этом, чтобы он был еще довольно криптостойким. Уникальность этой операции заключается в том, что она сама себе обратная! К примеру, если число А поXORить с числом Б, в результате получим В, в дальнейшем достаточно переXORить числа Б и В между собой, чтобы получить прежнее значение А!

В этой операции мы получили 1010 имея числа 1110 и 0100, чтобы получить обратно 1110, достаточно переXORрить между собой числа 0100 и 1010! Более подробно об этой операции можно почитать в статье, которая вложена на сайте www.wasm.ru , «Элементарное руководство по CRC_алгоритмам обнаружения ошибок » автор, которой Ross N. Williams . В этом труде есть пункт - «5. Двоичная арифметика без учета переносов ». Вот именно в этой статье и описана операция xor! Я восклицаю потому что в этой статье эта операция так расписана, что читатель не просто понимает как работает эта операция, он даже начинает ее видеть, слышать и чувствовать!

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

2.2 Блочный шифр ГОСТ 28147-89

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

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

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

Теоретический минимум.

3.1 Ключевая информация

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

3.1.1. Ключ – это последовательность восьми элементов размером в 32 бита каждый. Далее будем обозначать символом К, а элементы из которых он состоит – k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 Таблица замен – матрица из восьми строк и шестнадцати столбцов, в дальнейшем – Hij. Каждый элемент на пересечении строки i и столбца j занимает 4 бита.

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

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

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

1. Сложение часть блока R суммируется с элементом ключа K по mod 2 32 . О подобной операции я описал выше, здесь тоже самое только показатель степени не «4», а «32» - результат этой операции в дальнейшем буду обозначать Smod.
2. Полученный ранее результат Smod делим на четырех битные элементы s7,s6,s5,s4,s3,s2,s1,s0 и подаем в функцию замены. Замена происходит следующим образом: выбирается элемент Smod - s i , с начала начинаем с младшего элемента, и заменяем значением из таблицы замен по i - той строке и столбцу, на который указывает значение элемента s i . Переходим к s i +1 элементу и поступаем аналогичным образом и продолжаем так, пока не заменим значение последнего элемента Smod – результат этой операции будем обозначать как, Ssimple.
3. В этой операции значение Ssimple сдвигаем циклически влево на 11 бит и получаем Srol.
4. Выбираем вторую часть блока L и складываем по mod 2 с Srol, в итоге имеем Sxor.
5. На этой стадии часть блока L становится равным значению части R, а часть R в свою очередь инициализируется результатом Sxor и на этом функция основного шага завершена!

3.3 Базовые циклы: “32-З”, “32-Р”.

Для того чтобы зашифровать информацию надо разбить ее на блоки размером в 64 бита, естественно последний блок может быть меньше 64 битов. Этот факт является ахиллесовой пятой данного метода «простая замена». Так как его дополнение до 64 бит является очень важной задачей по увеличению криптостойкости шифрограммы и к этому чувствительному месту, если оно присутствует в массиве информации, а его может и не быть (к примеру, файл размером в 512 байт!), следует отнестись с большой ответственностью!

После того как вы разбили информацию на блоки, следует разбить ключ на элементы:

K = k1,k2,k3,k4,k5,k6,k7,k8

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

Базовые циклы имеют, как бы это сказать, маркировку: n – m. Где n – количество основных шагов криптопреобразования в базовом цикле, а m – это «тип» базового цикла, т.е. о чем идет речь, о «З» ашифровывании или «Р» асшифровывании данных.

Базовый цикл шифрования 32–З состоит из 32-х основных шагов криптопреобразования. В функцию реализующую действия шага подают блок N и элемент ключа К причем, первый шаг происходит с к1, второй над полученным результатом с элементом к2 и т.д. по следующей схеме:

k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7,k6,k5,k4,k3,k2,k1

Процесс расшифровывания 32–Р происходит аналогичным образом, но элементы ключа подаются в обратной последовательности:

k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1

Практика.

4.1 Реализация основного шага криптопреобразования

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

Исходные данные:

Возьмем блок информации N = 0102030405060708h, здесь части L и R равны:

L = 01020304h, R =05060708h, возьмем ключ:

K = ‘as28 zw37q839 7342ui23 8e2twqm2 ewp1’ (это ASCII – коды, для того, чтобы посмотреть шестнадцатеричное представление, можно открыть этот файл в режим просмотра в Total Commander нажав на клавишу «F3 » и далее клавишу «3 »). В этом ключе значения элементов будут:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Также возьмем следующую таблицу замен:

Рис. 3

Здесь строки нумеруются от 0 до 7, столбцы от 0 до F.

Предупреждение: Вся информация, в том числе и ключ с таблицей замен взята в качестве примера для рассмотрения алгоритма!

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

1. Выбираем часть R = 05060708h и элемент ключа k1 = ‘as28’, в шестнадцатеричном виде элемент ключа будет выглядеть так: 61733238h. Теперь же делаем операцию суммирования по mod 2 32:

Рис. 4

Как видно на рисунке у нас не произошло переноса в 33 бит помеченный красным цветом и с показателем степени «32 ». А если бы у нас были бы другие значения R и элемента ключа – это вполне могло бы произойти, и тогда бы мы его проигнорировали, и в дальнейшем использовали только биты, помеченные желтым цветом.

Такую операцию я выполняю командой ассемблера add :

; eax = R, ebx = ‘as28’

Результат этой операции Smod = 66793940h

2. Теперь самая заковыристая операция, но если присмотреться по внимательней, то она уже не такая страшная, как кажется в первое время. Представим Smod в следующем виде:

Рис. 5

Я постарался наглядно представить элементы Smod на рисунке, но все равно поясню:

s0 = 0, s1 = 4, s2 = 9 и т.д.

Теперь начиная с младшего элемента s0, производим замену. Вспоминая пункт «3.2 Основной шаг криптопреобразования » i ­– строка, s i – столбец, ищем в нулевой строке и нулевом столбце значение:

Рис.6

Таким образом, текущее значение Smod, не 66793940 h, а 66793945 h.

Приступаем заменять s1, т.е. четверку. Используя первую строку и четвертый столбец (s1= 4!). Глядим на рисунок:

Рис. 7

Теперь уже значение Smod, не 6679394 5h, 6679392 5h. Я предполагаю, что теперь алгоритм замены читателю понятен, и я могу сказать, что после конечный результат Ssimple будет иметь следующее значение – 11e10325h.

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

1. Полученное значение Ssimple мы должны сдвинуть на 11 бит влево.

Рис. 8

Как видно это действие довольно простое, и реализуется одной командой языка ассемблера – rol и результат этой операции Srol равен 0819288Fh.

4. Теперь же остается часть L нашего блока информации поXORить со значением Srol. Я беру калькулятор от w2k sp4 и получаю Sxor = 091b2b8bh.

5. Это действие итоговое и мы просто присваиваем, чисти R значение части L, а часть L инициализируем значением Sxor.

Конечный результат:

L = 091b2b8bh, R = 01020304h

4.2 Увеличения быстродействия алгоритма

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

Когда я реализовывал алгоритм шифрования в своей программе, я поступил следующим образом:

1. Выбрал часть блока L в регистр eax, а R в edx.

2. В регистр esi инициализировал адресом расширенного ключа, об этом ниже.

3. В регистр ebx присваивал значение адреса расширенной таблицы замен, об этом тоже ниже

4. Передавал информацию пунктов 1,2, 3 в функцию базового цикла 32 – З или 32 – Р, в зависимости от ситуации.

Если посмотреть на схему подачи элементов ключа в пункте «Базовые циклы: “32-З”, “32-Р” », то наш ключ для базового цикла 32 – З можно представить в следующем:

К 32-З =

‘as28’,‘zw37’,‘q839’,‘7342’,‘ui23’,‘8e2t’,‘wqm2’,‘ewp1’,

‘as28’,‘zw37’,‘q839’,‘7342’,‘ui23’,‘8e2t’,‘wqm2’,‘ewp1’,

‘ewp1’,‘wqm2’,‘8e2t’,‘ui23’,‘7342’,‘q839’,‘zw37’,‘as28’

Т.е. с начала идут k1,k2,k3,k4,k5,k6,k7,k8 - ‘ as28’, ‘ zw37’, ‘ q839’, ‘7342’, ‘ ui23’, ‘8 e2 t’, ‘ wqm2’, ‘ ewp1’ три раза эта последовательность повторяется. Затем элементы идут в обратном порядке, т.е.: k8,k7,k6,k5,k4,k3,k2,k1 - ‘ewp1’, ‘wqm2’, ‘8e2t’,‘ui23’,‘7342’,‘q839’,‘zw37’,‘as28’ .

Я заранее расположил в массиве элементы в том порядке, как они должны подаваться в 32 – З. Тем самым я увеличил память, требуемую под ключ, но избавил себя от некоторых процессов мышления, которые мне были не нужны, и увеличил скорость работы алгоритма, за счет уменьшения времени обращения к памяти! Здесь я описал только ключ для 32 – З, для цикла 32 – Р я поступил аналогично, но используя другую схему подачи элементов, которую я тоже описывал в пункте «Базовые циклы: “32-З”, “32-Р ».

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

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

К примеру, нам потребовалось заменить, число 66793940h. Представлю его в следующем виде:

Рис. 9

Теперь если взять элементы s1,s0, т.е. младший байт, то результат функции замены будет равен 25h! Почитав статью Андрея Винокурова, которую я привел в пункте «Список используемой литературу », вы действительно обнаружите, что если взять две строки можно получить массив, позволяющий быстро находить элементы замены с помощью команды ассемблера xlat. Говорят можно и другим способом более быстрым, но Андрей Винокуров потратил на исследование быстрых алгоритмов для реализации ГОСТа около четырех лет! Думаю, не стоит изобретать велосипед, когда он уже есть.

Итак, о массиве:

Возьмем две первые строки нулевую и первую, создадим массив на 256 байт. Теперь наблюдаем одну особенность, что если надо преобразовать 00h, то результат будет 75h (опираемся на рис.3) – кладем это значение в массив на смещение 00h. Берем значение 01h, результат функции замен 79h, кладем его в массив на смещение 01 и так далее до 0FFh, которое нам даст 0FCh, которое мы положим в массив по смещение 0FFh. Вот мы и получили расширенную таблицу замен для первой группы строк: первой и нулевой. Но еще есть три группы: вторая стр.2, стр.3, третья стр.4, стр. 5, четвертая стр.6, стр.7. С этим тремя группами поступаем тем же способом, что и с первой. Результат – расширенная таблица замен!

Теперь можно реализовать алгоритм, который будет производить замену. Для этого берем исходные коды, которые выложил Андрей Винокуров на своей страничке, смотри «Список используемой литературы ».

lea ebx,extented_table_simple

mov eax,[положить число которое нужно заменить]

add ebx,100h ;переход к двум следующим узлам

sub ebx,300h ; чтобы в дальнейшем ebx показывал на таблицу

Теперь еще одна особенность, предыдущими действиями мы не только заменили, но и сдвинули число на 8 бит влево! Нам остается только сдвинуть число еще на 3 бита влево:

и мы получаем результат операции rol eax,11!

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

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

Как сказано в статье Андрея Винокурова ключ выбирают по двум критериям:

Критерий равновероятного распределения битов между значениями 1 и 0. Обычно в качестве критерия равновероятного распределения битов – выступает критерий Пирсона («хи-квадрат»).

Это значит ключом, в принципе может любое число. То есть при формировании очередного бита ключа вероятность его инициализации единицей или нулем 50/50!

Прошу заметить, что ключ из восьми элементов, каждый по 32 бита, таким образом всего в ключе 32*8 = 256 битов и количество возможных ключей 2 256 ! Тебя это не поражает?

Критерий серий.

Если мы посмотрим на наш ключ, который я привел в пункте «4.1 Реализация основного шага криптопреобразования », то вы заметите, что справедлива следующая запись:

Рис. 10

Одной фразой значение k 1 не должно повториться не в k 2 , не в каком либо другом элементе ключа.

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

Теперь про выбор таблицы замен:

Теперь же поговорим о том, как правильно выбрать таблицу замен. Основное требование к выбору таблиц замен – это явление «неповторяемости» элементов, каждый из которых размером в 4 бита. Как вы уже видели выше, каждая строка таблицы замен состоит из значений 0h, 1h, 2h, 3h, …, 0fh. Так вот основное требование гласит о том, что в каждой строке есть значения 0h, 1h, 2h, … , 0fh и каждое такое значение в одном экземпляре. К примеру, последовательность:

1 2 3 4 5 6 7 8 9 A B C D E F

Вполне соответствует этому требованию, но все же! Такую последовательность в качестве строки выбирать не рекомендуется. Так как если вы подадите значение на вход функции, которая опирается на такую строку, то на выходе вы получите такое же значение! Не верите? Тогда возьмите число 332DA43Fh и восемь таких строк, в качестве таблицы замен. Проведите операцию замены, и уверяю вас, на выходе вы получите число 332DA43Fh! То есть такое же, что вы подали на вход операции! А это не является признаком хорошего тона при шифровании, да и являлось ли?

Это было одно требование, следующий критерий говорит о том, что – каждый бит выходного блока должен быть статистически независим от каждого бита входного блока!

Как это выглядит проще? А вот как, к примеру, мы выбрали из приведенного выше числа элемент s0 = 0Fh, 01111b. Вероятность того, что мы сейчас заменим первый бит единицей или нулем равна 0,5! Вероятность замены второго, третьего и четвертого бита, каждый бит, рассматриваем по отдельности, единицами или нулями тоже равна 0, 5. При выборе s1 = 0Eh, вероятность того, что мы нулевой бит, а это «0», заменим нулем или единицей тоже равна – 0,5! Таким образом, согласно этому критерию между заменой нулевых битов элементов s0, s1 нет никакой закономерности! Да, вы могли заменить единицами, но вы также могли поставить и нули.

Для оценки таблицы по этому критерию можно построить таблицу коэффициентов корреляции, рассчитанные по формуле:

Если p = 1, то значение бита j на выходе равно значению бита i на входе при любых комбинациях бит на входе;

Если p = -1, то значение бита j на выходе всегда является инверсией входного бита i;

Если p = 0, то выходной бит j с равной вероятностью принимает значения 0 и 1 при любом фиксированном значении входного бита i.

Возьмем пример одной строки:

Разложим на «составляющие»:

Рассчитаем один коэффициент по формуле приведенной выше. Чтобы проще было понять, как это делается, поясню более подробно:

Берем 0-й бит 0-ого числа (0) на входе и 0-й бит 0-ого числа на выходе (1) проводим операцию 0 XOR 1 = 1.

Берем 0-й бит 1-ого числа (1) на входе и 0-й бит 1-ого числа на выходе (1) проводим операцию 1 XOR 1 = 0.

Берем 0-й бит 2-ого числа (0) на входе и 0-й бит 2-ого числа на выходе (0) проводим операцию 0 XOR 0 = 0.

Берем 0-й бит 3-ого числа (1) на входе и 0-й бит 3-ого числа на выходе (1) проводим операцию 1 XOR 1 = 0.

Проведя последовательно операции XOR в такой последовательности, подсчитываем количество всех ненулевых значений, получаем значение 6. Отсюда P 00 = 1-(6/2 4-1) = 0,25. Итак, выяснилось, что значение бита 0 на выходе равно значению бита 0 на входе в 4-х случаях из 16-ти;

Итоговая таблица коэффициентов:

Как видно из таблицы корреляционных коэффициентов бит 3 на входе инвертирован относительно бита 0 на выходе в 14 случаях из 16, что составляет 87.5 % Вот это уже не допустимо для нормальных систем шифрования. Для разнообразия возьмем еще примерчик:

Таблица коэффициентов будет следующая (кому не лениво может пересчитать)

Ну, в этой таблице дела обстоят еще хуже – биты 1 и 2 группы остаются неизменными! Криптоаналитику есть, где развернуться С учетом всех этих требований простым перебором («в лоб») были найдены таблицы перестановки соответствующие указанной теории (на сегодняшний день – 1276 сочетаний) Вот некоторые из них:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Список использованной литературы.

1. Статья Андрея Винокурова:

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

для компьютеров платформы Intel x86.

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

1. Статья Хорста Файстеля:

Криптография и Компьютерная безопасность.

(можно найти по тому же адресу что и предыдущую статью)

1. Ross N. Williams:

Элементарное руководство по CRC алгоритмам обнаружения ошибок

Выложена на сайте www. wasm. ru .

Благодарности.

Хотелось бы высказать благодарность всем посетителям форума www.wasm.ru . Но особо бы хотелось бы поблагодарить ChS, который в настоящий момент известен, как SteelRat, он помог мне понять такие вещи, чего я бы, наверное, никогда бы не понял, а так же помощь при написании пункта: «Требования к ключевой информации », основной часть данного пункта была написана им. Также глубоко признателен сотруднику КГТУ им. А.Н. Туполева Аникину Игорю Вячеславовичу и грех было бы не отметить Криса Касперски, за то, что он есть и Volodya / wasm.ru за его наставления. Ох, и достается мне от него . Так же хочу отметить Sega-Zero / Callipso зато, что донес до моего разума некоторые математические дебри.

Это, пожалуй, все, что я хотел бы сказать вам.

Буду, признателен за критику или вопросы, связанные с этой статьей или просто советы. Мои контактные данные: [email protected] , ICQ – 337310594.

С уважением Evil`s Interrupt.

P.S.: Этой статьей я не старался кого-то перещеголять. Она была написана с умыслом, облегчить изучение ГОСТа и если у вас получились трудности, то это не значит, что я повинен в этом. Будь разумны, и наберитесь терпения, всего вам доброго!

Этот алгоритм является обязательным для применения в качестве алгорит­ма шифрования в государственных организациях РФ и ряде коммерческих .

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

Схема алгоритма показана на рис. 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 .

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

При описании алгоритма используются следующие обозначения:

L и R - последовательности битов;
LR - конкатенация последовательностей L и R, в которой биты последовательности R следуют за битами последовательности L;
(+) - поразрядное сложение по модулю 2 (операция "исключающее ИЛИ");
[+] - сложение 32-разрядных чисел по модулю 2 32 ;
{+} - сложение 32-разрядных чисел по модулю 2 32 -1.

Числа суммируются по следующему правилу:

A [+] B = A + B, если A + B < 2 32 ,
A [+] B = A + B - 2 32 , если A + B >= 2 32 . A {+} B = A + B , если A + B < 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Алгоритм предусматривает четыре режима работы:

В любом случае для шифрования данных используется 256-битовый ключ K, который представляется в виде восьми 32-битовых подключей K i:

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

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

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

Первый и самый простой режим - замена . Данные, подлежащие шифрованию, разбивают на 64-битовые блоки. Процедура шифрования блока открытых данных T 0 включает 32 цикла (j=1...32).

Блок T 0 разделяется на две последовательности по 32 бита: В(0)A(0), где В(0) - левые или старшие биты, A(0) - правые или младшие биты.

Эти последовательности вводят в накопители N 1 и N 2 перед началом первого цикла шифрования.

Первый цикл (j=1) процедуры шифрования 64-битового блока данных описывается следующими формулами:

Здесь i обозначает номер итерации (i = 1, 2,..., 32).

Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 2 32 числа A(i), полученного на предыдущем шаге итерации, и числа X(j) ключа (размерность каждого из этих чисел равна 32 знакам).

Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой К. Блок подстановки К состоит из 8 узлов замены К(1) ... К(8) с памятью 64 бит каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-х разрядных векторов, каждый из которых преобразуется в 4-х разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0...15.

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

Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т ш представляется в виде Т ш =A(32)B(32).

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

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

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

Открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m, где m определяется обьемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит, то есть Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Уравнение зашифрования данных в режиме гаммирования может быть представлено в следующем виде:

Ш(i) = A (Y(i-1) [+] C2, Z(i-1) {+} C1) (+) T(i) = Г(i) (+) T(i) .
Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа),
С1 и С2 - константы, заданные в ГОСТ 28147-89,
Y(i) и Z(i) - величины, которые определяются итерационно по мере формирования гаммы следующим образом:
(Y(0), Z(0)) = A(S), где S - 64-разрядная двоичная последовательность (синхропосылка);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) {+} C1) для i = 1, 2,...,m.

Расшифрование данных возможно только при наличии синхропосылки, которая не является секретным элементом шифра и может храниться в памяти ЭВМ или передаваться по каналам связи вместе с зашированными данными.

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

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как в и режиме гаммирования открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m , где m определяется обьемом шифруемых данных), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит:

Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.

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

Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены. Аргументом функции на первом шаге итеративного алгоритма является 64-разрядная синхропосылка, а на всех последующих - предыдущий блок зашифрованных данных Ш(i-1).

Bыработки имитовставки

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

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

Для получения имитовставки открытые данные представляются в виде 64-разрядных блоков Т(i) (i = 1, 2,..., m , где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.

Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком открытых данных Т(2). Результат суммирования снова подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Полученное 64-разрядное число суммируется по модулю 2 с третьим блоком открытых данных Т(3) и т.д. Последний блок Т(m) при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.

Имитовставка Ир передается по каналу связи или в память ЭВМ после зашифрованных данных. Поступившие зашифрованные данные расшифровываются, и из полученных блоков открытых данных T(i) вырабатывается имитовставка Ир", которая затем сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все расшифрованные данные считают ложными.