Алгоритм DES

Самый популярный тип при использовании 3DES — это DES-EDE3, для него алгоритм выглядит так:

Шифровка:

Расшифровка:

При выполнении алгоритма 3DES ключи  могут выбрать так:

k₁,k₂,k₃ независимы.

k₁,k₂ независимы, а k₁ = k₃

k₁ = k₂ = k₃.

Метод DESX создан Рональдом Ривестом. Этод метод — усиленный вариант DES, поддерживаемый инструментарием RSA Security. DESX отличается от DES тем, что каждый бит входного открытого текста DESX логически суммируется по модулю 2 с 64 битами дополнительного ключа, а затем шифруется по алгоритму DES. Каждый бит результата также логически суммируется по модулю 2 с другими 64 битами ключа. Главной причиной использования DESX является простой в вычислительном смысле способ значительного повысить стойкость DES к атакам полного перебора ключа.

Метод G-DES разработан для повышения производительности DES на основе увеличения размером шифрованного блока. Заявлялось, что G-DES защищен так же, как и DES. Однако Бихам и Шамир показали, что G-DES с рекомендуемыми параметрами легко взламывается, а при любых изменениях параметров шифр становится ещё менее защищен, чем DES.

Ещё другой вариант DES использует независимые суб-ключи. Различно от алгоритма DES, в котором на основе 56-битового секретного ключа пользователя алгоритм DES получает шестнадцать 48-битных суб-ключей для использования в каждом из 16 раундов, в этом варианте использует 768-битный ключа (разделенного на 16 48-битных подключей) вместо 16 зависимых 48-битных ключей, создаваемых по ключевому графику алгоритма DES. Хотя очевидно, что использование независимых суб-ключей значительно усложнит полный поиск ключа, но стойкость к атаке дифференциальным или линейным криптоанализом не намного превысит стойкость обычного DES. По оценке Бихама для дифференциального криптоанализа DES с независимыми подключами требуется 2⁶¹ выбранных открытых текстов, в то время как для линейного криптоанализа требуется 2⁶⁰ известных открытых текстов.

1.7 Применение  шифра DES

DES был национальным  стандартом США в 1977—1980 гг., но  в настоящее время DES используется (с ключом длины 56 бит) только для устаревших систем, чаще всего используют его более криптоустойчивый вид (3DES, 2DES). 3DES является простой эффективной заменой DES, и сейчас он рассмотрен как стандарт. В ближайшее время DES и Triple DES будут заменены алгоритмом AES (Advanced Encryption Standard — Расширенный Стандарт Шифрования). Алгоритм DES широко применяется для защиты финансовой информации: так, модуль THALES (Racal) HSM RG7000 полностью поддерживает операции TripleDES для эмиссии и обработки кредитных карт VISA, EuroPay и проч. Канальные шифраторы THALES (Racal) DataDryptor 2000 используют TripleDES для прозрачного шифрования потоков информации. Также алгогритм DES используется во многих других устройствах и решениях THALES-eSECURITY.

2 Шифр ГОСТ 28147-89

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

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

2.2 История  создания

История создания этого  алгоритма – тайна, покрытая мраком. По свидетельству причастных к его реализациям и использованию людей, алгоритм был разработан в 70-е годы в 8-м Главном Управлении КГБ СССР, тогда он имел гриф «Совершенно Секретно». Затем гриф был понижен до «Секретно», а когда в 89-м году алгоритм был проведен через Госстандарт и стал официальным государственным стандартом, гриф с него был снят, однако алгоритм оставался под грифом «Для Служебного Пользования». Формально шифр был объявлен «полностью открытым» только в мае 1994 года. К сожалению, история создания шифра и критерии разработчиков до сих пор не опубликованы.

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

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

 

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

 

Для генерации подключей  исходный 256-битный ключ разбивается на восемь 32-битных блоков: k₁…k₈. Ключи k₉…k₂₄ являются циклическим повторением ключей k₁…k₈ (нумеруются от младших битов к старшим). Ключи k₂₅…k₃₂ являются ключами k₁…k₈, идущими в обратном порядке.

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

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

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

2.4 Сравнение шифров ГОСТ 28147-89 и DES

Сравнение основных характеристик этих двух алгоритмов приведены в таблице 2.1.

 

Параметр	ГОСТ	DES
Размер блока шифрования	64 бита	64 бита
Длина ключа	256 бит	56 бит
Число раундов	32	16
Узлы замен (S-блоки)	не фиксированы	фиксированы
Длина ключа для одного раунда	32 бита	48 бит
Схема выработки раундового ключа	простая	сложная
Начальная и конечная перестановки битов	нет	есть

Таблица 2.1 – Сравнение  основных характеристик алгоритмов ГОСТ и DES.

 

Функция шифрования ГОСТа гораздо проще функции шифрования DES, она не содержит операций битовых перестановок, коими изобилует DES и которые крайне неэффективно реализуются на современных универсальных процессорах (хотя очень просто аппаратно – путем разводки проводников в кристалле или на плате). В силу сказанного, при вдвое большем количестве раундов (32 против 16) программная реализация ГОСТа на процессорах Intel x86 более чем в 2 раза превосходит по быстродействию реализацию DES. Естественно, сравнивались близкие к оптимуму по быстродействию реализации.

На каждом раунде шифрования используется "раундовый ключ", в DES он 48-битовый и вырабатывается по относительно сложному алгоритму, включающему битовые перестановки и замены по таблице, в ГОСТе он берется как фрагмент ключа шифрования. Длина ключа шифрования в ГОСТе равна 256 битам, длина раундового ключа - 32 битам, итого получаем, что ключ шифрования ГОСТа содержит 256/32=8 раундовых ключей. В ГОСТе 32 раунда, следовательно, каждый раундовый ключ используется 4 раза, порядок использования раундовых ключей установлен в ГОСТе и различен для различных режимов.

Таблица замен в ГОСТе – аналог S-блоков DES – представляет собой таблицу (матрицу) размером 8x16, содержащую число от 0 до 15. В каждой строке каждое из 16-ти чисел должно встретиться ровно 1 раз. В отличие от DES, таблица замен в ГОСТе одна и та же для всех раундов и не зафиксирована в стандарте, а является сменяемым секретным ключевым элементом.

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

2.5 Достоинства алгоритма

К основным достоинствам данного алгоритма можно отнести:

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

2.6 Модификации алгоритма ГОСТ

Есть две основные модификации алгоритма ГОСТ: GOST-H и GOSTA.

В модификации GOST-H относительно оригинального алгоритма изменен порядок использования подключей, а именно, в раундах с 25-го по 32-й подключи используются в прямом порядке, т.е. точно так же, как и в предыдущих раундах алгоритма.

В 20-раундовом алгоритме GOSTA в раундах для наложения ключа используется операция XOR вместо сложения по модулю 2³².

По результатам анализа  сделан вывод о том, что GOST-H и GOSTA слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей.

Есть весьма интересная модификация алгоритма, не являющаяся стандартом: таблицы S₁…S₈ обязательно должны быть различными; в каждом раунде алгоритма должна выполняться их перестановка по определенному закону. Данная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т.е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.

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

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

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

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

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

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

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

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