Краткое описание шифра

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

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

Принцип работы алгоритма

Алгоритм принципиально не отличается от DES. В нем также происходят циклы шифрования (их 32) по схеме Фейстеля (Рис. 2.9.).

Рис. 2.9. Раунды шифрования алгоритма ГОСТ 28147-89.

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k 1 …k 8 . Ключи k 9 …k 24 являются циклическим повторением ключей k 1 …k 8 (нумеруются от младших битов к старшим). Ключи k 25 …k 32 являются ключами k 1 …k 8 , идущими в обратном порядке.

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

Функция f (A i ,K i ) вычисляется следующим образом: A i и K i складываются по модулю 2 32 , затем результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком . Общее количество S-блоков ГОСТа - восемь, т. е. столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая - на вход второго и т. д. Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов. Все восемь S-блоков могут быть различными. Фактически, они могут являться дополнительным ключевым материалом, но чаще являются параметром схемы, общим для определенной группы пользователей. В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, т.е. разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовала используемые в Интернет узлы замены.

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

Режимы работы алгоритма ГОСТ 28147-89

Алгоритм ГОСТ 28147-89 имеет четыре режима работы.

1. Режим простой замены принимает на вход данные, размер которых кратен 64-м битам. Результатом шифрования является входной текст, преобразованный блоками по 64 бита в случае зашифрования циклом «32-З», а в случае расшифрования - циклом «32-Р».

2. Режим гаммирования принимает на вход данные любого размера, а также дополнительный 64-битовый параметр - синхропосылку . В ходе работы синхропосылка преобразуется в цикле «32-З», результат делится на две части. Первая часть складывается по модулю 2 32 с постоянным значением 1010101 16 . Если вторая часть равна 2 32 -1, то её значение не меняется, иначе она складывается по модулю 2 32 -1 с постоянным значением 1010104 16 . Полученное объединением обеих преобразованных частей значение, называемое гаммой шифра, поступает в цикл «32-З», его результат порязрядно складывается по модулю 2 с 64-разрядным блоком входных данных. Если последний меньше 64-х разрядов, то лишние разряды полученного значения отбрасываются. Полученное значение подаётся на выход. Если ещё имеются входящие данные, то действие повторяется: составленный из 32-разрядных частей блок преобразуется по частям и так далее.

3. Режим гаммирования с обратной связью также принимает на вход данные любого размера и синхропосылку. Блок входных данных поразрядно складывается по модулю 2 с результатом преобразования в цикле «32-З» синхропосылки. Полученное значение подаётся на выход. Значение синхропосылки заменяется в случае зашифрования выходным блоком, а в случае расшифрования - входным, то есть зашифрованным. Если последний блок входящих данных меньше 64 разрядов, то лишние разряды гаммы (выхода цикла «32-З») отбрасываются. Если ещё имеются входящие данные, то действие повторяется: из результата зашифрования заменённого значения образуется гамма шифра и т.д.

4. Режим выработки имитовставки принимает на вход данные, размер которых составляет не меньше двух полных 64-разрядных блоков, а возвращает 64-разрядный блок данных, называемый имитовставкой. Временное 64-битовое значение устанавливается в 0, далее, пока имеются входные данные, оно поразрядно складывается по модулю 2 с результатом выполнения цикла «16-З», на вход которого подаётся блок входных данных. После окончания входных данных временное значение возвращается как результат.

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

В шифре ГОСТ 28147-89 используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одном из существующих в настоящее время компьютере общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт ГОСТ 28147-89 проектировался с большим запасом и по стойкости на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 .

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

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

В 2004 году группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7% 12 бит секретного ключа. Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрования. Как видно, данная атака практически бесполезна для реального вскрытия алгоритма.

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

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

Причина в том, что я его только недавно придумал и пока никому об этом не рассказывал. Однако производительность кода, так же как и производительность процессора, имеет объективные характеристики, которые поддаются измерениям. Эта статья - именно о производительности кода, выполняемого процессорным ядром.

В чем измеряется производительность кода? Поскольку я первый об этом заговорил, то по праву первооткрывателя буду его измерять в RTT-шках;).

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

Студент ответит - одну, его преподаватель подумает и скажет, что четыре, профессионал - что пока только двенадцать операций.

Так вот, программный код, который загружает все исполнительные устройства процессора одновременно на протяжении всего времени исполнения кода, будет иметь производительность 12 RTT-шек. Максимум! Честно признаюсь, такого кода я раньше не писал, но в этой статье попытаюсь сделать над собой усилие.

Я докажу, что код с одновременным выполнением двенадцати 32-битных операций - возможен

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно, будет иметь производительность в 1 RTT-шку. Такой производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня, и интерпретаторы виртуальных машин. Не нужно считать, что показатель загрузки процессора, который можно увидеть в диспетчере задач ОС, может служить объективным критерием эффективности кода. Загрузка ядра процессора может быть 100%, но при этом программный код будет использовать одно исполнительное устройство в нем (производительность 1 RTT). В этом случае при 100%-й загрузке процессорное ядро будет работать в 1/12 своей максимальной производительности. Другими словами, когда в диспетчере задач ОС Windows показывается максимальная загрузка процессора, его реальная производительность может варьироваться от 1 до 12 RTT. Увидев в окне производительности 100%-ю загрузку на каком-либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

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

Традиционная реализация ГОСТ 28147-89

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

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

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

По п. 1.2 ГОСТа этот блок реализует тетрадные (по четыре бита) перестановки в 32-битном слове, но архитектура процессора х86/64 и его система команд не способна эффективно манипулировать тетрадами.

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

В более продвинутых реализациях эти таблицы имеют размер 1024 байта (256 слов по четыре байта). Это сделано для того, чтобы реализовать в таблицах дополнительно циклический сдвиг на 11 позиций полученного в результате подстановки 32-битного слова (следующая операция алгоритма преобразования по ГОСТу). Пример реализации ГОСТа по данному методу показан в приложении 1 (на диске).

Информация блока подстановок является секретным компонентом криптофункции (как это сформулировано в ГОСТе, см. на рис. 2).

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

Короче говоря, ФСБ пропускает такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТу (п. 1.7). И это несмотря на общеизвестные методы взлома шифров через съем дампа памяти…

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

Но хватит лирики, важно в рамках рассматриваемой темы то, что этот программный код имеет производительность в 1 RTT-шку. Теперь напишем код с производительностью 2 RTT-шки.

Многопоточная реализация ГОСТ 28147-89

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

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

Однако существует и иной вариант параллельной обработки данных на одном- единственном ядре процессора. Поясню эту неочевидную мысль.

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

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра - планировщик, который просматривает исполняемый код форвардно, на глубину до 32–64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены.

Большинство программных последовательностей, генерируемых автоматически (компиляторами), не могут загрузить все АЛУ и FPU, находящиеся в ядре процессора. В этом случае оборудование процессора простаивает, что значительно снижает его результирующую производительность. Разработчики процессоров это понимают и вводят режимы увеличения частоты ядра, когда оборудование используется не полностью. Также для этого предназначены системы гипертрейдинга, и эту систему я буду использовать для «прессования» кода по максимуму в дальнейшем.

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

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

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

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

Далее показан пример с чередованием команд из разных потоков обработки. В этом случае команды, относящиеся к разным блокам данных, чередуются. Планировщик выбирает независимые друг от друга команды и передает их на выполнение в АЛУ1 и АЛУ2. Группировка команд первого и второго потока на этих АЛУ осуществляется автоматически, поскольку в алгоритм работы планировщика заложена группировка команд с зацеплением по общим данным на одном и том же исполнительном устройстве.

Чтобы такой программный код работал без простоев АЛУ, необходимо, чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX-регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков.

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

Метод параллельного шифрования эффективно реализуется только для 64-битного режима работы процессора, поскольку в этом режиме имеется достаточное количество РОН (целых 16 штук!). Пример реализации ГОСТа по данному методу показан в приложении 2 (на диске).

Ясно, что данная реализация ГОСТа имеет производительность кода 2 RTT-шки. А теперь посмотрим, как это сказывается на времени выполнения.

Цикл шифрования для одного потока (приложение 1) составляет 352 такта, и за это время обсчитывается 8 байт данных, для двухпоточной реализации ГОСТа (приложение 2) требуется 416 тактов процессора, но при этом обсчитывается 16 байт. Таким образом, результирующая скорость преобразования повышается с 80 до 144 мегабайт для процессора частотой 3,6 ГГц.

Интересная получается картина: код содержит ровно в два раза больше команд, а выполняется всего на 15% дольше, но, думаю, читатели уже поняли причину этого феномена…

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

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

Использование SSE-регистров и AVX-команд современных процессоров для реализации ГОСТ 28147-89

Современные процессоры архитектуры х86/64 имеют в своем составе набор регистров SSE размером 16 байт и специализированные FPU (как минимум два) для выполнения различных операций над этими регистрами. Возможна реализация ГОСТа на этом оборудовании, причем в этом случае узлы замены можно размещать не в виде таблиц в оперативной памяти, а непосредственно на выделенных SSE-регистрах.

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

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

Схема одного из возможных размещений узлов замены на SSE-регистрах показана на рис. 4.

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

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

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

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

Имея узлы хранения подстановок на SSE-регистрах и многовходовый коммутатор в блоках FPU, можно организовать следующее преобразование в блоке подстановок (рис. 5).

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

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

Работой коммутаторов управляет специальная трехадресная команда AVX VPSHUFB. Ее первый операнд является приемником информации из коммутаторов, второй - источником, к которому подключены входы коммутаторов. Третий операнд является управляющим регистром для коммутаторов, каждый байт которого ассоциирован с соответствующим коммутатором; значение в нем задает номер направления, с которого коммутатор считывает информацию. Описание этой команды из официальной документации Intel см. на рис. 5. На рис. 6 приведена схема работы этой команды - изображена только половина SSE-регистров, для второй половины все аналогично.

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

Программа с выборкой тетрад через коммутаторы FPU была написана, но я даже не стал помещать ее в приложение - слишком убого. Иметь регистр размером 128 бит и использовать в нем только 32 бита - непрофессионально.

Как говорится, «Наш финиш - горизонт», поэтому выжимать так выжимать... будем прессовать и складывать в пакеты!

Это не игра слов, а суровая FPUшная реальность - регистры SSE можно разбивать на равные части и выполнять над этими частями одинаковые преобразования одной командой. Для того чтобы процессор это понял, имеется магическая буковка «Р» - пакет, которая ставится перед мнемоникой команды, и не менее магические буковки «Q», «D», «W», «B», которые ставятся в конце и объявляют, на какие части разбиты в этой команде регистры SSE.

Нас интересует пакетный режим с разбивкой SSE-регистра на четыре 32-битных блока; соответственно, все команды будут иметь префикс «P», а в конце - символ «D». Это дает возможность одной процессорной командой параллельно обрабатывать сразу четыре блока по 32 бита, то есть в параллель рассчитывать четыре блока данных.

Программа, реализующая этот метод, имеется в приложении 3, там же - все пояснения.

Впрочем, прессовать так прессовать! В современных процессорах имеется как минимум два блока FPU, и для их полной загрузки можно использовать два потока независимых команд. Если грамотно чередовать команды из независимых потоков, то можно загрузить работой оба блока FPU полностью и получить сразу восемь параллельно обрабатываемых потоков данных. Такая программка была написана, и ее можно посмотреть в приложении 4, только смотреть нужно осторожно - можно слететь с катушек. Это, что называется, «код не для всех...».

Цена вопроса

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

Для четырех потоков была получена скорость выполнения 472 процессорных такта. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 59 мегабайт в секунду, а четыре потока соответственно со скоростью 236 мегабайт в секунду.

Для восьми потоков была получена скорость выполнения 580 процессорных тактов. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 49 мегабайт в секунду, а восемь потоков со скоростью 392 мегабайта в секунду.

Как может заметить читатель, код в примере № 3 имеет производительность 4 RTT, а код в примере № 4 имеет производительность 8 RTT. В этих примерах на SSE-регистрах закономерности те же, что и при использовании РОН, только планировщик снизил свою эффективность. Сейчас он обеспечивает 20%-е увеличение длительности при двукратном увеличении длины кода.

Причем эти результаты были получены с использованием универсальных AVX-команд, имеющихся как в процессорах Intel, так и в процессорах AMD. Если выполнить оптимизацию под процессор AMD, результат будет значительно лучше. Звучит поперек тренда, но тем не менее это правда, и вот почему: процессоры AMD имеют дополнительный набор команд, так называемое XOP-расширение, и в этом дополнительном наборе команд есть такие, которые значительно упрощают реализацию алгоритма ГОСТа.

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

Если речь зашла о дальнейшей оптимизации, нелишне помнить о наличии 256-битных регистров (YMM-регистры), используя которые можно теоретически еще удвоить скорость вычислений. Но пока это только перспектива, на данный момент процессоры очень сильно замедляются, когда выполняют 256-битные инструкции (FPU имеют ширину тракта 128 бит). Эксперименты показали, что на современных процессорах счет в 16 потоков на YMM-регистрах выигрыша не дает. Но это только пока, на новых моделях процессоров, несомненно, будет увеличено быстродействие 256-битных команд, и тогда использование 16 параллельных потоков станет целесообразно и приведет к еще большему увеличению скорости работы криптопроцедуры.

Теоретически можно рассчитывать на скорость 600–700 мегабайт в секунду при наличии в процессоре двух FPU с шириной рабочего тракта 256 бит каждый. В этом случае можно говорить о написании кода с эффективностью 16 RTT, и это не фантастика, а ближайшая перспектива.

Смешанный режим

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

Рассчитывать на прибавку в 50% здесь не приходится, узким местом становится кеш-память, где хранятся технологические маски, но прибавку в 100 дополнительных мегабайт все же получить можно. Этот вариант не приведен в приложениях (макросы аналогичны используемым в коде на 8 RTT), но он имеется в программных файлах. Так что если кто не верит в возможность шифрования со скоростью 500 мегабайт в секунду на одном процессорном ядре, пусть запустит тестовые файлы. Там же есть и тексты с комментариями, чтобы никто не подумал, что я лукавлю.

Такой фокус возможен только на процессорах Intel, у AMD только два блока FPU на два процессорных модуля (аналог режима гипертрейдинг). Но зато имеется еще четыре АЛУ, которые грех не использовать.

Можно загнать процессорные модули «Бульдозера» в режим, аналогичный режиму гипертрейдинга, но запускать на разных модулях в одном потоке преобразование на РОН, а в другом потоке на SSE-регистрах и получить те же 12 RTT. Этот вариант я не проверял, но, думаю, на AMD код в 12 RTT будет работать более эффективно. Желающие могут попробовать, тестовые программы можно подкорректировать для работы на «Бульдозерах» достаточно легко.

Кому это нужно?

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

Причем, как это ни странно, встроенное в процессоры шифрование по AES-алгоритму оказывается значительно медленнее, тесты показывают скорость на уровне 100–150 мегабайт в секунду, и это при аппаратной реализации алгоритма! Проблема заключается в однопоточном счете и блоке замен, который оперирует байтами (таблица из 256 строк). Так что ГОСТ оказывается эффективнее в реализации на архитектуре х86/64, кто бы мог подумать…

Это если говорить о достигнутом уровне скорости шифрования. А если иметь в виду теоретические изыски в области повышения эффективности кода, то скорее всего это никому не нужно. Специалистов уровня 3–6 RTT практически нет, компиляторы вообще генерят код на уровне 1–2,5 RTT, а основная масса программистов не знает ассемблера, а если и знает его правописание, то не понимает устройства современного процессора. А без этих знаний что ассемблер, что какой-нибудь там СИ-шарп - без разницы.

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

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

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

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

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

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

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

Режим гаммирования с обратной связью похож на режим гаммирования и отличается от него только способом выработки элементов гаммы. При гаммировании с обратной связью очередной 64-битный элемент гаммы вырабатывается как результат преобразования по базовому циклу алгоритма ГОСТ 28147-89 предыдущего блока зашифрованных данных. Для зашифрования первого блока массива данных элемент гаммы вырабатывается как результат преобразования по тому же циклу синхропосылки. Этим достигается зацепление блоков – каждый блок шифротекста в этом режиме зависит от соответствующего и всех предыдущих блоков открытого текста. Поэтому данный режим иногда называется гаммированием с зацеплением блоков . На стойкость шифра факт зацепления блоков не оказывает никакого влияния.

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

где f – базовый цикл по ГОСТ 28147-89; X i – 64-разрядный блок исходного текста; K – ключ .

В качестве имитовставки берется часть блока Y n , полученного на выходе, обычно 32 его младших бита.

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

Отличия алгоритмов шифрования по ГОСТ 28147-89 и DES

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

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

В шифре, реализуемом в ГОСТ 28147-89, используется 256-битовый ключ , и объем ключевого пространства составляет 2 256 . Даже если, как и в "Алгоритмы шифрования DES и AES" , предположить, что на взлом шифра брошены все силы вычислительного комплекса с возможностью перебора 10 12 (это примерно равно 2 40) ключей в одну секунду, то на полный перебор всех 2 256 ключей потребуется 2 216 секунд (это время составляет более миллиарда лет).

К уже отмеченным отличиям между алгоритмами DES и ГОСТ 28147 можно добавить также следующее. В основном раунде DES применяются нерегулярные перестановки исходного сообщения, в ГОСТ 28147 используется 11-битный циклический сдвиг влево. Последняя операция гораздо удобнее для программной реализации. Однако перестановка DES увеличивает лавинный эффект. В ГОСТ 28147 изменение одного входного бита влияет на один 4-битовый блок при замене в одном раунде, который затем влияет на два 4-битовых блока следующего раунда, три блока следующего и т.д. В ГОСТ 28147 требуется 8 раундов прежде, чем изменение одного входного бита повлияет на каждый бит результата; DES для этого нужно только 5 раундов.

Также следует отметить, что в отличие от DES , у ГОСТ 28147-89 таблицу замен для выполнения операции подстановки можно произвольно изменять, то есть таблица замен является дополнительным 512-битовым ключом.

Ключевые термины

ГОСТ 28147-89 – российский стандарт на блочный алгоритм симметричного шифрования .

Краткие итоги

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

Набор для практики

Вопросы для самопроверки

1. Для каких целей может использоваться алгоритм криптографического преобразования данных по ГОСТ 28147-89?
2. Перечислите основные параметры алгоритма симметричного шифрования по ГОСТ 28147-89.
3. Какие операции используются в блочном алгоритме шифрования по ГОСТ 28147-89?
4. Каковы основные отличия алгоритма шифрования по ГОСТ 28147-89 от алгоритма DES?
5. Какая информация, помимо секретного ключа, при условии использования стандартных алгоритмов ГОСТ 28147 -89 необходима для расшифровки сообщения?
6. В каких режимах может производиться шифрование данных с помощью алгоритма криптографического преобразования по ГОСТ 28147-89?
7. Что такое имитовставка ? Для каких целей может быть использована имитовставка ?

Упражнения для самопроверки

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

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

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

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

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

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

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

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

Введение.

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

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

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

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

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

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

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

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

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

Рис. 1

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

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

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

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

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

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

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

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

3. L = R, R = Sxor

L = 0101b, R = 1010b

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

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

Рис. 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практика.

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

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

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

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

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

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

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

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

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

Рис. 3

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

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

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

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

Рис. 4

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

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

; eax = R, ebx = ‘as28’

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

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

Рис. 5

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

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

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

Рис.6

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

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

Рис. 7

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

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

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

Рис. 8

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

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

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

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

L = 091b2b8bh, R = 01020304h

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

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

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

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

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

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

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

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

К 32-З =

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

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

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

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

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

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

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

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

Рис. 9

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

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

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

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

lea ebx,extented_table_simple

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Ross N. Williams:

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

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

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

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

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

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

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

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

Алгоритм ГОСТ 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: «Не спеши его хоронить».