Алгоритм шифрования ГОСТ 28147-89. Метод простой замены
«Пока ты жив, не умирай, на этот мир взгляни.
У многих здесь душа мертва – они мертвы внутри.
Но ходят и смеются, не зная, что их нет,
Не торопи свой смертный час» – она сказала мне.
Ария, «Там высоко»
Содержание:
- Введение
- Предварительные сведения о блочных шифрах
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
Цель:
Получить шифрограмму
Решение:
- (R + K) mod 24 = Smod, Smod = 0100b
- (Smod + L) mod 2 = Sxor, Sxor = 1010b
- L = R, R = Sxor
Итог:
L = 0101b, R = 1010b
Поясним наши действия:
- Эта операция сложение по mod 24. На практике такая операция сводится к простому сложению, где мы должны сложить два числа и проигнорировать перенос в 5й разряд. Так как, если проставить над разрядами двоичного представления числа проставить показатели степени, над пятым разрядом как раз будет показатель четыре, взглянем на рисунок ниже, где изображены действия нашей операции:
Рис. 2
Здесь я стрелкой указал на показатели степени, как видно, результат должен был получиться 10100, но так как при операции mod 24 игнорируется перенос, мы получаем 0100.
- Эта операция в литературе называется mod 2, на языке ассемблера реализуется командой XOR. Но ее более правильное название mod 21. Без этой уникальной операции вряд ли можно построить быстрый, легко реализуемый алгоритм шифрования и при этом, чтобы он был еще довольно криптостойким. Уникальность этой операции заключается в том, что она сама себе обратная! К примеру, если число А поXORить с числом Б, в результате получим В, в дальнейшем достаточно переXORить числа Б и В между собой, чтобы получить прежнее значение А!
В этой операции мы получили 1010 имея числа 1110 и 0100, чтобы получить обратно 1110, достаточно переXORрить между собой числа 0100 и 1010! Более подробно об этой операции можно почитать в статье, которая вложена на сайте www.wasm.ru, «Элементарное руководство по CRC_алгоритмам обнаружения ошибок» автор, которой Ross N. Williams. В этом труде есть пункт — «5. Двоичная арифметика без учета переносов». Вот именно в этой статье и описана операция xor! Я восклицаю потому что в этой статье эта операция так расписана, что читатель не просто понимает как работает эта операция, он даже начинает ее видеть, слышать и чувствовать!
- Это действие необходимо, чтобы при расшифровывании из шифрограммы можно было получить исходные значения.
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 бита каждая. Выбирают элемент ключа и только потом подают эти две части блока, элемент ключа таблицу замен в функцию основного шага, результат основного шага это одна итерация базового цикла, о котором речь пойдет в следующем пункте. Основной шаг состоит из следующих действий:
- Сложение часть блока R суммируется с элементом ключа K по mod 232. О подобной операции я описал выше, здесь тоже самое только показатель степени не «4», а «32» — результат этой операции в дальнейшем буду обозначать Smod.
- Полученный ранее результат Smod делим на четырех битные элементы s7,s6,s5,s4,s3,s2,s1,s0 и подаем в функцию замены. Замена происходит следующим образом: выбирается элемент Smod — si, с начала начинаем с младшего элемента, и заменяем значением из таблицы замен по i — той строке и столбцу, на который указывает значение элемента si. Переходим к si+1 элементу и поступаем аналогичным образом и продолжаем так, пока не заменим значение последнего элемента Smod – результат этой операции будем обозначать как, Ssimple.
- В этой операции значение Ssimple сдвигаем циклически влево на 11 бит и получаем Srol.
- Выбираем вторую часть блока L и складываем по mod 2 с Srol, в итоге имеем Sxor.
- На этой стадии часть блока 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 = ‘as28zw37q8397342ui238e2twqm2ewp1’ (это 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.
Предупреждение: Вся информация, в том числе и ключ с таблицей замен взята в качестве примера для рассмотрения алгоритма!
Задача:
Используя «Исходные данные», необходимо получить результат действия основного шага криптопреобразования.
Решение:
- Выбираем часть R = 05060708h и элемент ключа k1 = ‘as28’, в шестнадцатеричном виде элемент ключа будет выглядеть так: 61733238h. Теперь же делаем операцию суммирования по mod 232:
Рис. 4
Как видно на рисунке у нас не произошло переноса в 33 бит помеченный красным цветом и с показателем степени «32». А если бы у нас были бы другие значения R и элемента ключа – это вполне могло бы произойти, и тогда бы мы его проигнорировали, и в дальнейшем использовали только биты, помеченные желтым цветом.
Такую операцию я выполняю командой ассемблера add:
; eax = R, ebx = ‘as28’
add eax,ebx
; eax = Smod
Результат этой операции Smod = 66793940h
- Теперь самая заковыристая операция, но если присмотреться по внимательней, то она уже не такая страшная, как кажется в первое время. Представим Smod в следующем виде:
РИСУНОК НЕ СОХРАНЕН
Рис. 5
Я постарался наглядно представить элементы Smod на рисунке, но все равно поясню:
s0 = 0, s1 = 4, s2 = 9 и т.д.
Теперь начиная с младшего элемента s0, производим замену. Вспоминая пункт «3.2 Основной шаг криптопреобразования» i – строка, si – столбец, ищем в нулевой строке и нулевом столбце значение:
Рис.6
Таким образом, текущее значение Smod, не 66793940h, а 66793945h.
Приступаем заменять s1, т.е. четверку. Используя первую строку и четвертый столбец (s1= 4!). Глядим на рисунок:
Рис. 7
Теперь уже значение Smod, не 66793945h, 66793925h. Я предполагаю, что теперь алгоритм замены читателю понятен, и я могу сказать, что после конечный результат Ssimple будет иметь следующее значение – 11e10325h.
О том, как это проще всего реализовать в виде команд ассемблера я расскажу позже в следующем пункте, после того, как расскажу о расширенной таблице.
- Полученное значение Ssimple мы должны сдвинуть на 11 бит влево.
Рис. 8
Как видно это действие довольно простое, и реализуется одной командой языка ассемблера – rol и результат этой операции Srol равен 0819288Fh.
- Теперь же остается часть L нашего блока информации поXORить со значением Srol. Я беру калькулятор от w2k sp4 и получаю Sxor = 091b2b8bh.
- Это действие итоговое и мы просто присваиваем, чисти R значение части L, а часть L инициализируем значением Sxor.
Конечный результат:
L = 091b2b8bh, R = 01020304h
4.2 Увеличения быстродействия алгоритма
Теперь же поговорим об оптимизации алгоритма по скорости. При процессе реализации, какого либо проекта, приходится учитывать, что программа, которая работает с регистрами чаще, чем с памятью работает наиболее быстрее и здесь это суждение тоже очень важно, т.к. над одним блоком информации целых 32 действия шифрации!
Когда я реализовывал алгоритм шифрования в своей программе, я поступил следующим образом:
- Выбрал часть блока L в регистр eax, а R в edx.
- В регистр esi инициализировал адресом расширенного ключа, об этом ниже.
- В регистр ebx присваивал значение адреса расширенной таблицы замен, об этом тоже ниже
- Передавал информацию пунктов 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’,
‘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’, ‘8e2t’, ‘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,[положить число которое нужно заменить]
REPT 3
xlat
ror eax,8d
add ebx,100h ;переход к двум следующим узлам
ENDM
xlat
sub ebx,300h ; чтобы в дальнейшем ebx показывал на таблицу
Теперь еще одна особенность, предыдущими действиями мы не только заменили, но и сдвинули число на 8 бит влево! Нам остается только сдвинуть число еще на 3 бита влево:
rol eax,3h
и мы получаем результат операции rol eax,11!
Больше я ничего не могу добавить по оптимизации, единственное, что могу подчеркнуть то, что я говорил выше – используйте регистры чаще, чем обращение к памяти. Думаю эти слова только для новичков, опытные и без моих слов это прекрасно понимают :).
Требования к ключевой информации.
Как сказано в статье Андрея Винокурова ключ выбирают по двум критериям:
— критерий равновероятного распределения битов между значениями 1 и 0. Обычно в качестве критерия равновероятного распределения битов – выступает критерий Пирсона («хи-квадрат»).
Это значит ключом, в принципе может любое число. То есть при формировании очередного бита ключа вероятность его инициализации единицей или нулем 50/50!
Прошу заметить, что ключ из восьми элементов, каждый по 32 бита, таким образом всего в ключе 32*8 = 256 битов и количество возможных ключей 2256! Тебя это не поражает? 🙂
— критерий серий.
Если мы посмотрим на наш ключ, который я привел в пункте «4.1 Реализация основного шага криптопреобразования», то вы заметите, что справедлива следующая запись:
Рис. 10
Одной фразой значение k1 не должно повториться не в k2, не в каком либо другом элементе ключа.
То есть ключ, который мы выбрали в качестве рассмотрения алгоритма шифрования, вполне соответствует двум приведенным выше критериям.
Теперь про выбор таблицы замен:
Теперь же поговорим о том, как правильно выбрать таблицу замен. Основное требование к выбору таблиц замен – это явление «неповторяемости» элементов, каждый из которых размером в 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 нет никакой закономерности! Да, вы могли заменить единицами, но вы также могли поставить и нули. 🙂
Для оценки таблицы по этому критерию можно построить таблицу коэффициентов корреляции, рассчитанные по формуле:
где
0≤i≤3
0≤j≤3
N=4
— если p = 1, то значение бита j на выходе равно значению бита i на входе при любых комбинациях бит на входе;
— если p = -1, то значение бита j на выходе всегда является инверсией входного бита i;
— если p = 0, то выходной бит j с равной вероятностью принимает значения 0 и 1 при любом фиксированном значении входного бита i.
Возьмем пример одной строки:
D | B | 4 | 1 | 3 | F | 5 | 9 | 0 | A | E | 7 | 6 | 8 | 2 | C | |
Разложим на «составляющие»:
Вход
Выход
Рассчитаем один коэффициент по формуле приведенной выше. Чтобы проще было понять, как это делается, поясню более подробно:
— берем 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. Отсюда P00 = 1-(6/24-1) = 0,25. Итак, выяснилось, что значение бита 0 на выходе равно значению бита 0 на входе в 4-х случаях из 16-ти;
Итоговая таблица коэффициентов:
Вход | |||||
Выход | 0 | 1 | 2 | 3 | |
0 | 0,25 | 0,00 | 0,00 | -0,75 | |
1 | 0,00 | -0,25 | 0,00 | 0,25 | |
2 | -0,25 | 0,25 | 0,00 | 0,00 | |
3 | 0,50 | -0,25 | 0,00 | 0,00 |
Как видно из таблицы корреляционных коэффициентов бит 3 на входе инвертирован относительно бита 0 на выходе в 14 случаях из 16, что составляет 87.5 % Вот это уже не допустимо для нормальных систем шифрования. Для разнообразия возьмем еще примерчик:
9 | 8 | 3 | A | C | D | 7 | E | 0 | 1 | B | 2 | 4 | 5 | F | 6 |
Таблица коэффициентов будет следующая (кому не лениво может пересчитать)
Вход | |||||
Выход | 0 | 1 | 2 | 3 | |
0 | -0,25 | 0,00 | 0,00 | 0,00 | |
1 | 0,00 | 1,00 | 0,00 | 0,00 | |
2 | 0,00 | 0,00 | 1,00 | 0,00 | |
3 | 0,00 | 0,00 | 0,00 | -0,50 |
Ну, в этой таблице дела обстоят еще хуже – биты 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 |
Список использованной литературы.
- Статья Андрея Винокурова:
Алгоритм шифрования ГОСТ 28147-89, его использование и реализация
для компьютеров платформы Intel x86.
(можно найти по адресу: http://www.enlight.ru/crypto/frame.htm).
Тут же и исходные коды, по реализации алгоритма шифрования.
- Статья Хорста Файстеля:
Криптография и Компьютерная безопасность.
(можно найти по тому же адресу что и предыдущую статью)
- Ross N. Williams:
Элементарное руководство по CRC алгоритмам обнаружения ошибок
Выложена на сайте www.wasm.ru.
Благодарности.
Хотелось бы высказать благодарность всем посетителям форума www.wasm.ru. Но особо бы хотелось бы поблагодарить ChS, который в настоящий момент известен, как SteelRat, он помог мне понять такие вещи, чего я бы, наверное, никогда бы не понял, а так же помощь при написании пункта: «Требования к ключевой информации», основной часть данного пункта была написана им. Также глубоко признателен сотруднику КГТУ им. А.Н. Туполева Аникину Игорю Вячеславовичу и грех было бы не отметить Криса Касперски, за то, что он есть и Volodya / wasm.ru за его наставления. Ох, и достается мне от него :). Так же хочу отметить Sega-Zero / Callipso зато, что донес до моего разума некоторые математические дебри.
Это, пожалуй, все, что я хотел бы сказать вам.
Буду, признателен за критику или вопросы, связанные с этой статьей или просто советы. Мои контактные данные: int20h@yandex.ru, ICQ – 337310594.
С уважением Evil`s Interrupt.
+ P.S.: Этой статьей я не старался кого-то перещеголять. Она была написана с умыслом, облегчить изучение ГОСТа и если у вас получились трудности, то это не значит, что я повинен в этом. Будь разумны, и наберитесь терпения, всего вам доброго!
[C] Evil`s Interrupt.
Источник: WASM.RU /17.10.2004/