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

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

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

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

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

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

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

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

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

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

Рис. 5.1.

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

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

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

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

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

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

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

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

Алгоритм ГОСТ 28147-89 и шифр «Магма» (ГОСТ Р 34.12-2015)

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

Алгоритм ГОСТ 28147-89 (рис. 2.21) базируется на схеме Фейстеля и шифрует информацию блоками по 64 бит, которые разбиваются на два подблока по 32 бита (I, и R). Подблок R, обрабатывается функцией раундового преобразования, после чего его значение складывается со значением подблока Lj, затем подблоки меняются местами. Алгоритм имеет 16 или 32 раунда в зависимости от режима шифрования (вычисление имитовставки или другие режимы шифрования).

Рис. 2.21.

В каждом раунде алгоритма выполняются следующие преобразования.

1. Наложение ключа. Содержание подблока R i складывается по модулю 2 32 с ключом раунда К. Kj - это 32-битовая часть исходного ключа, используемая в качестве раундового. Алгоритм ГОСТ 28147-89 нс использует процедуру расширения ключа, исходный 256-битный ключ шифрования представляется в виде конкатенации (сцепления) восьми 32-битовых подключей (рис. 2.22): К 0 , К { , К т К, К А, К 5 , К 6 , К 7 .

В процессе шифрования используется один из этих подключей К

С 1-го по 24-й раунд - в прямой последовательности:

С 25-го но 32-й раунд - в обратной последовательности:

Рис. 2.22. Строение ключа шифрования алгоритма ГОСТ 28147-89

2. Табличная замена. После наложения ключа подблок R i разбивается на восемь частей но 4 бита, значение каждой из которых по отдельности заменяется в соответствии со своей таблицей замены (S-блоком). Всего используется восемь S-блоков - S 0 , S, S 2 , S 3 , S 4 , S 5 , S 6 , S 7 . Каждый S-блок алгоритма ГОСТ 28147-89 представляет собой вектор (одномерный массив) с ^элементами, пронумерованными от 0 до 15. Значениями S-блока являются 4-битовые числа, т.е. целые числа от 0 до 15.

Из таблицы S-блока берется элемент, порядковый номер которого совпадает со значением, пришедшим на вход подстановки.

Пример 2.6.

Пусть имеется S-блок следующего вида:

Пусть на вход этого S-блока подано значение 0100 2 = 4. Выходом S-блока будет 4-й элемент таблицы замен, т.е. 15 = 1111 2 (нумерация элементов начинается с нуля).

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

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

Таблица 2.16

Пример слабого S-блока

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

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

• устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т.е. значения z = F(0), где F - функция раундового преобразования алгоритма. Это требует порядка 2 32 тестовых операций шифрования;
• с помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 2 11 операций.

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

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

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

В современных алгоритмах S-блоки обычно представляют собой вектор (одномерный массив), содержащий 2" т- битовых элементов. Вход блока определяет номер элемента, значение которого служит выходом S-блока.

Для проектирования S-блоков был выдвинут целый ряд критериев. Таблица замен должна удовлетворять:

• строгому лавинному критерию;
• критерию независимости битов;
• требованию нелинейности от входных значений.

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

В некоторых работах для S-блоков предлагается проверка выполнения гарантированного лавинного эффекта порядка у - при изменении одного входного бита меняется, по крайней мере, у выходных бит S-блока. Свойство гарантированного лавинного эффекта порядка у от 2 до 5 обеспечивает достаточно хорошие диффузионные характеристики S-блоков для любого алгоритма шифрования.

При проектировании достаточно больших таблиц замен могут быть использованы следующие подходы:

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

Можно предложить следующий порядок проектирования отдельных S- блоков алгоритма ГОСТ 28147-89:

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

В 2011 г. предложена новая атака «рефлексивная встреча посередине», незначительно снижающая стойкость ГОСТ 28147-89 (с 2256 до 2225) . Лучший результата криптоанализа алгоритма по состоянию на 2012 г. позволяет снизить его стойкость до 2 192 , требуя относительно большого размера шифротекста и объема предварительно сформированных данных . Несмотря на предложенные атаки, на современном уровне развития вычислительной техники ГОСТ 28147-89 сохраняет практическую стойкость.

Шифр «Магма» (ГОСТ Р 34.12-2015). Стандарт ГОСТ 28147-89 действовал в России более 25 лет. За это время он показал достаточную стойкость и хорошую эффективность программных и аппаратных реализаций, в том числе и на низкоресурсных устройствах. Хотя и были предложены криптоаналитические атаки, снижающие оценки его стойкости (лучшая - до 2 192), они далеки от возможности практической реализации. Поэтому было принято решение о включении алгоритма ГОСТ 28147-89 во вновь разрабатываемый стандарт симметричного шифрования.

В шопе 2015 г. приняты два новых национальных криптографических стандарта: ГОСТ Р 34.12-2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» и ГОСТ Р 34.13-2015 «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров», которые вступают в действие с 1 января 2016 г.

Стандарт ГОСТ Р 34.12-2015 содержит описание двух блочных шифров с длиной блока 128 и 64 бит. Шифр ГОСТ 28147-89 с зафиксированными блоками нелинейной подстановки включен в новый ГОСТ Р 34.12-2015 в качестве 64-битового шифра под названием «Магма» («Magma»).

Ниже приведены закрепленные в стандарте блоки замен:

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

По мнению технического комитета по стандартизации «Криптографическая защита информации» (ТК 26), фиксация блоков нелинейной подстановки сделает алгоритм ГОСТ 28147-89 более унифицированным и поможет исключить использование «слабых» блоков нелинейной подстановки. Кроме того, фиксация в стандарте всех долговременных параметров шифра отвечает принятой международной практике. Новый стандарт ГОСТ Р 34.12-2015 терминологически и концептуально связан с международными стандартами ИСО/МЭК 10116 «Информационные технологии. Методы обеспечения безопасности. Режимы работы для «-битовых блочных шифров» (ISO/IEC 10116:2006 Information technology - Security techniques - Modes of operation for an n-bit block cipher) и серии ИСО/МЭК 18033 «Информационные технологии. Методы и средства обеспечения безопасности. Алгоритмы шифрования»: ИСО/МЭК 18033-1:2005 «Часть 1. Общие положения» (ISO/IEC 18033-1:2005 Information technology - Security techniques - Encryption algorithms - Part 1: General) и ИСО/МЭК 18033-3:2010 «Часть 3. Блочные шифры» (ISO/IEC 18033-3:2010 (Information technology - Security techniques - Encryption algorithms - Part 3: Block ciphers)).

В стандарт ГОСТ P 34.12-2015 включен также новый блочный шифр («Кузнечик») с размером блока 128 бит. Ожидается, что этот шифр будет устойчив ко всем известным на сегодняшний день атакам на блочные шифры.

Режимы работы блочных шифров (простой замены, гаммирования, гам- мирования с обратной связью по выходу, гаммирования с обратной связью по шифротексту, простой замены с зацеплением и выработки имитовстав- ки) выведены в отдельный стандарт ГОСТ Р 34.13-2015, что соответствует принятой международной практике. Эти режимы применимы как к шифру «Магма», так и к новому шифру «Кузнечик».

• Осуществляется побитовый циклический сдвиг влево на 11 битов. Расшифрование осуществляется по этой же схеме, но с другим расписаниемиспользования ключей: с 1-го по 8-й раунд расшифровки - в прямом порядке: с 9-го по 32-й раунд расшифровки - в обратном порядке: По сравнению с шифром DES у ГОСТ 28147-89 есть следующие достоинства: существенно более длинный ключ (256 бит против 56 у шифра DES),атака на который путем полного перебора ключевого множества на данныймомент представляется невыполнимой; простое расписание использования ключа, что упрощает реализациюалгоритма и повышает скорость вычислений. Проектирование S-блоков ГОСТ 28147-89. Очевидно, что схема алгоритма ГОСТ 28147-89 весьма проста. Это означает, что наибольшая нагрузка по шифрованию ложится именно на таблицы замен. Значения таб-
• Панасепко С. П. Алгоритмы шифрования: специальный справочник. СПб.: БХВ-Петер-бург, 2009.
• Kara О. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf
• Российский стандарт шифрования: стойкость снижена. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47-27
• Ачексеев Е. К., Смышляев С. В. ГОСТ 28147-89: «Не спеши его хоронить».

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

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

1. Введение

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

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

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

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

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

1. Практика

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.

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

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

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

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 бита.

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

Прежде чем начать шифровать, блок разбивают на две части 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

Практика.

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

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

Возьмем блок информации 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

1. Теперь самая заковыристая операция, но если присмотреться по внимательней, то она уже не такая страшная, как кажется в первое время. Представим 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.

1. Теперь же остается часть L нашего блока информации поXORить со значением Srol. Я беру калькулятор от w2k sp4 и получаю Sxor = 091b2b8bh.
2. Это действие итоговое и мы просто присваиваем, чисти 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.

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

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. Отсюда P 00 = 1-(6/2 4-1) = 0,25. Итак, выяснилось, что значение бита 0 на выходе равно значению бита 0 на входе в 4-х случаях из 16-ти;

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

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

	Вход
Выход		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

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

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

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

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

(можно найти по адресу: http://www.enlight.ru/crypto/frame.htm).

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

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

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

Далее приведены краткие выдержки из этой работы, которую можно рассматривать как алармистский выпад в разгаре международной стандартизации (схожими преувеличениями автор был известен и в отношении AES, однако его работы тогда оказали большое теоретическое влияние на криптоанализ, но так и не привели на сегодняшний момент к практическим атакам на сам AES). Но, возможно, это и реальное предупреждение о начале этапа "пикирующего в штопор самолёта", которое может закончиться крахом национального стандарта шифрования, как это было с алгоритмом хэширования SHA-1 и алгоритмом хэширования "де-факто" MD5.

ГОСТ 28147-89 был стандартизирован в 1989 году и впервые стал официальным стандартом защиты конфиденциальной информации, но спецификация шифра оставалась закрытой. В 1994 году стандарт был рассекречен, опубликован и переведён на английский язык. По аналогии с AES (и в отличие от DES), ГОСТ допущен к защите секретной информации без ограничений, в соответствии с тем, как это указано в российском стандарте. Т.о. ГОСТ — это не аналог DES, а конкурент 3-DES с тремя независимыми ключами или AES-256. Очевидно, что ГОСТ — это достаточно серьёзный шифр, удовлетворяющий военным критериям, созданный с расчётом на самые серьёзные применения. По крайней мере два набора S-блоков ГОСТа были идентифицированы на основе приложений, используемых российскими банками. Эти банки нуждаются в проведении секретных коммуникаций с сотнями филиалов и защите миллиардов долларов от мошеннических хищений.

ГОСТ — это блочный шифр с простой структурой Файстеля, с размером блока 64 бита, 256-битным ключом и 32 раундами. Каждый раунд содержит сложение с ключом по модулю 2^32, набор из восьми 4-битных S-блоков и простой циклический сдвиг на 11 битов. Особенностью ГОСТа является возможность хранения S-блоков в секрете, что можно представить как второй ключ, увеличивающий эффективный ключевой материал до 610 битов. Один набор S-блоков был опубликован в 1994 году в рамках спецификации хэш-функции ГОСТ-Р 34.11-94 и, как писал Шнайер, использовался Центральным Банком Российской Федерации. Он также вошёл в стандарт RFC4357 в части "id-GostR3411-94-CryptoProParamSet". В исходных кодах в конце книги Шнайера была ошибка (в порядке S-блоков). Наиболее точную эталонную реализацию исконно российского происхождения сейчас можно встретить в библиотеке OpenSSL. Если где-то применяются секретные S-блоки, то они могут быть извлечены из программных реализаций и из микросхем, по факту чего были опубликованы соответствующие работы.

ГОСТ — серьёзный конкурент

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

Неудивительно, что ГОСТ стал интернет-стандартом, в частности, он включён во многие криптобиблиотеки, такие как OpenSSL и Crypto++, и становится всё популярнее за пределами страны своего происхождения. В 2010 году ГОСТ был заявлен на стандартизацию ISO как всемирный стандарт шифрования. Крайне малое количество алгоритмов смогли стать международными стандартами. ISO/IEC 18033-3:2010 описывает следующие алгоритмы: четыре 64-битных шифра — TDEA, MISTY1, CAST-128, HIGHT — и три 128-битных шифра — AES, Camellia, SEED. ГОСТ предлагается добавить в этот же самый стандарт ISO/IEC 18033-3.

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

Как стало недавно известно автору из приватной переписки, большинство стран высказались против ГОСТа на голосовании ISO в Сингапуре, однако результаты этого голосования будут ещё рассматриваться на пленарном заседании ISO SC27, так что ГОСТ всё ещё находится в процессе стандартизации на момент публикации этой работы.

Мнения экспертов по поводу ГОСТ

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

Все, кому знаком закон Мура, понимают, что, в теории, 256-битные ключи останутся безопасными по крайней мере 200 лет. ГОСТ был широко исследован ведущими экспертами в области криптографии, известными в области анализа блочных шифров, такими как Шнайер, Бирюков, Данкельман, Вагнер, множеством австралийских, японских и российских учёных, экспертами по криптографии от ISO, и все исследователи высказывались, что всё выглядит так, что он он может быть или должен быть безопасным. Хотя широкого понимания достигло мнение, что сама по себе структура ГОСТа крайне слаба, например, по сравнению с DES, в частности, диффузия не настолько хороша, однако это всегда обуславливалось тем, что это должно компенсироваться большим числом раундов (32), а также дополнительной нелинейностью и диффузией, обеспечиваемой сложением по модулю.

Бирюков и Вагнер писали: "Большое число раундов (32) и хорошо изученная конструкция Фейстеля, сочетаемая с последовательными Шенноновскими подстановками-перестановками, обеспечивают солидную основу безопасности ГОСТ". В той же самой работе мы читаем: "после значительных затрат времени и усилий, никакого прогресса в криптоанализе стандарта в открытой литературе достигнуто не было". Таким образом, не было никаких существенных атак, которые позволяли бы дешифрование или восстановление ключа в реалистичном сценарии, когда ГОСТ используется в шифровании со множеством разных случайных ключей. В противоположность этому, известно очень много работ по атакам на слабые ключи в ГОСТ, атаки со связанными ключами, атаки на восстановление секретных S-блоков. На Crypto-2008 был представлен взлом хэш-функции, основанной на этом шифре. Во всех атаках атакующий имеет значительно больший уровень свободы, чем ему обычно допускается. В традиционных применениях шифрования с использованием случайно выбираемых ключей до настоящего момента никаких серьёзных криптографических атак на ГОСТ найдено не было, что в 2010 году выражалось итоговой фразой: "несмотря на существенные усилия криптоаналитиков за прошедшие 20 лет, ГОСТ всё ещё не взломан" (Axel Poschmann, San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).

Линейный и дифференциальный анализ ГОСТ

В широкоизвестной книге Шнайера мы читаем: "Против дифференциального и линейного криптоанализа ГОСТ вероятно более устойчив, чем DES". Основную оценку безопасности ГОСТа дали в 2000 году Габидулин и др. Их результаты очень впечатляющи: при заложенном уровне безопасности 2^256, достаточно пяти раундов для защиты ГОСТа от линейного криптоанализа. Более того, даже при замене S-блоков на тождественные и единственной нелинейной операции шифра — сложения по модулю 2^32 — шифр всё равно стоек против линейного криптоанализа после 6 раундов из 32. Дифференциальный криптоанализ ГОСТа выглядит сравнительно более лёгким и привлекает больше внимания. Для 2^128 уровня безопасности исследователи (Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001) предполагали достаточную стойкость на уровне 7 раундов. По их утверждению, взлом ГОСТа более чем на пяти раундах "крайне труден". Более того, двое японских исследователей показали, что классическая прямая дифференциальная атака с одной дифференциальной характеристикой имеет крайне малую вероятность для прохождения через большое число раундов. На основе факта изучения достаточно "хорошей" итеративной дифференциальной характеристики для ограниченного числа раундов (которая сама по себе имеет вероятность прохождения не лучше 2-11.4 на раунд), получено значения множества подходящих ключей менее половины. Для полнораундового ГОСТа такая атака с единственной характеристикой будет работать лишь с ничтожно малой частью ключей порядка 2-62 (и даже в этой малой части она будет иметь вероятность прохождения не более 2-360).

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

Атаки скольжения и отражения

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

Последние результаты

Новые атаки также используют отражение и фактически взломали ГОСТ, что и было представлено на конференции FSE 2011. Эти атаки также были открыты независимо автором данной работы. Атака требует 2^132 байтов памяти, что фактически хуже, чем более медленные атаки с меньшим требованием к памяти.

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

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

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

Алгебраические атаки на блочные и потоковые шифры могут быть представлены в виде проблемы решения большой системы Булевых алгебраических уравнений, которая следует геометрии и структуре частной криптографической схемы. Сама идея восходит к Шеннону. На практике была представлена для DES (впервые представлена автором данной работы) как метод формального кодирования и может взламывать 6 раундов всего на одном известном открытом тексте. Манипуляция с уравнениями происходит на основе алгоритмов XL, базисов Грёбнера, метода ElimLin, SAT-решателей.

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

Как взломать ГОСТ?

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

Практический результат пока скромен: 2^64 известных открытых текста и 2^64 памяти для хранения пар "открытый текст/шифртекст" позволяют взломать ГОСТ в 2^8 быстрее, чем простой перебор. Но в плане криптоанализа это делает полностью справедливым утверждение о том, что "ГОСТ взломан".

Выводы

ГОСТ спроектирован на обеспечение военного уровня безопасности на 200 лет вперёд. Большинство ведущих экспертов, изучавших ГОСТ, приходили к соглашению о том, что "несмотря на значительные криптоаналитические усилия на протяжении 20 лет, ГОСТ всё ещё не взломан". В 2010 году ГОСТ продвигают в ISO 18033 в качестве мирового стандарта шифрования.

Основа идей об алгебраическом криптоанализе возникла более 60 лет назад. Но только лишь за последние 10 лет были разработаны эффективные программные средства (частичного) решения множества NP-полных проблем. Было взломано некоторое число потоковых шифров. Только один блочный шифр был взломан этим методом — сам по себе слабый KeeLoq. В этой работе автор взламывает важный, реально используемый шифр ГОСТ. Он отмечает, что это первый случай в истории, когда алгебраическим криптоанализом был взломан стандартизированный государственный шифр.

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

Автор утверждает: очевидно, что ГОСТ имеет серьёзные изъяны и теперь не обеспечивает уровня стойкости, требуемого ISO. Множество атак на ГОСТ представлено в рамках подтверждения парадигмы редуцирования алгебраической сложности.

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

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

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