Шифры DES и ГОСТ 28147-89

РЕФЕРАТ по курсу Математические методы в криптографии "Шифры DES и ГОСТ 28147-89" Содержание 1 Шифр DES 1.1 Краткая характеристика 1.2 История создания 1.3 Принцип работы алгоритма 1.4 Режимы использования шифра DES 1.5 Криптостойкость алгоритма 1.6 Увеличение криптостойкости алгоритма 11 1.7

Применение шифра DES 2 Шифр ГОСТ 28147-2.1 Краткое описание шифра 2.2 История создания 2.3 Принцип работы алгоритма 2.4 Сравнение шифров ГОСТ 28147-89 и DES 2.5 Достоинства алгоритма 2.6 Модификации алгоритма ГОСТ 2.7 Криптоанализ шифра 2.8 Критика шифра

ГОСТ 3 Список использованных источников 1 Шифр DES 1.1 Краткая характеристика DES (Data Encryption Standard) — Симметричный алгоритм шифрования, в котором один ключ используется как для шифрования, так и для расшифрования данных (в документах национального института стандартизации США (ANSI) криптосистема DES называется алгоритмом шифрования данных (DEA), а международная организация

по стандартизации, ссылаясь на шифр DES, пользуется аббревиатурой DEA-1). DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FIPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит.

Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов: • режим электронной кодовой книги (ECB — Electronic Code Book), • режим сцепления блоков (СВС — Cipher Block Chaining), • режим обратной связи по шифротексту (CFB — Cipher Feed Back), • режим обратной связи по выходу (OFB —

Output Feed Back). 1.2 История создания В 1972 году, после проведения исследования потребностей правительства США в компьютерной безопасности, американское НБС (Национальное Бюро Стандартов) — теперь переименовано ANSI (Национальный Институт Стандартов и Технологий) — определило необходимость в общеправительственном стандарте шифрования некритичной информации. Позже, 15 мая 1973 года, после консультации с

NSA (АНБ – Агентством национальной безопасности), НБС объявило конкурс на шифр, который удовлетворит строгим критериям проекта, но ни один конкурсант не обеспечивал выполнение всех требований. Второй конкурс был начат 27 августа 1974. На сей раз, шифр Lucifer, представленный IBM и развитый в течение периода 1973—1974 сочли приемлемым, он был основан на более раннем алгоритме Хорста Фейстеля. 17 марта 1975 года предложенный алгоритм

DES был издан в Федеральном Регистре. В следующем году было проведено 2 открытых симпозиума по обсуждению этого стандарта, где подверглись жёсткой критике изменения, внесённые АНБ в алгоритм: уменьшение первоначальной длины ключа и S-блоки (блоки подстановки), критерии проектирования которых не раскрывались. АНБ подозревалось в сознательном ослаблении алгоритма с целью, чтобы

АНБ могло легко просматривать зашифрованные сообщения. После чего сенатом США была проведена проверка действий АНБ, результатом которой стало заявление, опубликованное в 1978, в котором говорилось о том, что в процессе разработки DES АНБ убедило IBM, что уменьшенной длины ключа более чем достаточно для всех коммерческих приложений, использующих DES, косвенно помогало в разработке

S-перестановок, а также, что окончательный алгоритм DES был лучшим, по их мнению, алгоритмом шифрования и был лишён статистической или математической слабости. Также было обнаружено, что АНБ никогда не вмешивалось в разработку этого алгоритма. Часть подозрений в скрытой слабости S-перестановок была снята в 1990, когда были опубликованы результаты независимых исследований Эли Бихама (Eli Biham) и Ади

Шамира (Adi Shamir) по дифференциальному криптоанализу — основному методу взлома блочных алгоритмов шифрования с симметричным ключом. S-блоки алгоритма DES оказались намного более устойчивыми к атакам, чем, если бы их выбрали случайно. Это означает, что такая техника анализа была известна АНБ ещё в 70-х годах XX века. 1.3 Принцип работы алгоритма

Шифр DES является блочным шифром, основанном на шифре Фейстеля. Входными данными для блочного шифра служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых

преобразований. Базовые преобразования: • Сложное преобразование на одной локальной части блока. • Простое преобразование между частями блока. Так как преобразование производится поблочно, как отдельный шаг требуется разделение исходных данных на блоки необходимого размера. При этом вне зависимости от формата исходных данных, будь то текстовые документы, изображения или другие файлы, они должны быть интерпретированы в бинарный вид и только после этого разбиты на блоки.

Все вышеперечисленное может осуществляться как программными, так и аппаратными средствами. Как уже было сказано, шифр DES является модификацией шифра Фейстеля, еще называемым преобразованием сетью Фейстеля. Это преобразование над векторами (блоками) представляющими собой левую (старшую, L) и правую (младшую, R) половины регистра сдвига.

В алгоритме DES используются прямое преобразование сетью Фейстеля при шифровании (рисунок 1.1). Рисунок 1.1 – Прямое преобразование сетью Фейстеля. При расшифровании шифротекста используется обратное преобразование сетью Фейстеля (рисунок 1.2). Рисунок 1.2 – Обратное преобразование сетью Фейстеля. Полная схема работы шифра DES представлена на рисунке 1.3.

Рисунок 1.3 – Схема работы шифра DES. Вначале из исходного текста выделяется блок T длиной 64 бита (8 символов в формате ASCII), к которому применяется перестановка IP. Эта перестановка битов задана стандартом, хотя в принципе они могут быть различными. В результате получается блок IP(T), который разбивается на 2 равные части L0,R0, где L0,R0 — соответственно 32 старших битов и 32 младших битов блока.

Затем происходит 16 циклов (раундов) шифрования, на каждом из которых происходит прямое преобразование Фейстеля. Важную роль на этих этапах играет функция Фейстеля f, выполняющая шифрование. Аргументами функции f являются 32-битовый вектор Ri−1, 48 битовой ключ ki, которые являются результатом преобразования 56 битового исходного ключа шифра k. Для вычисления функции f используются функция расширения

Е, преобразование S, состоящее из 8 преобразований S-блоков S1, S2, …, S8, и перестановка P. Функция Е представляет собой 48-битовую таблицу. Она расширяет 32-битовый вектор Ri−1 до 48-битового вектора E(Ri−1) путём перестановки битов из Ri−1 и дублирования некоторых из них. Полученный после перестановки блок E(Ri−1) складывается по модулю 2 с ключами ki и затем

представляются в виде восьми последовательных блоков B1,B2 B8: E(Ri−1)= B1,B2 B8. Каждый Bj является 6-битовым блоком. Далее каждый из блоков Bj трансформируется в 4-битовый блок B'j с помощью преобразований Sj. Значение функции f(Ri−1,ki) (32 бит) получается перестановкой Р, применяемой к 32-битовому блоку B'1B'2 B'8. Значения функции

E, преобразований S1 – S8 и перестановки P заданы стандартом, как и в случае с перестановкой IP. Подробно схема работы функции f представлена на рисунке 1.4. Рисунок 1.4 – Схема работы функции f. Ключи ki получаются из начального ключа k (64 бит = 8 байтов или 8 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц.

Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Конечная перестановка IP-1 является обратной к перестановке IP. Она действует на T16 и используется для восстановления позиций. При расшифровке в раундах производятся обратные преобразования

Фейстеля, т. е. схема работы алгоритма практически не меняется, главное – проследить за использованием подключей в обратном порядке. 1.4 Режимы использования шифра DES DES может используется в четырёх режимах. 1. Режим электронной кодовой книги (ЕСВ — Electronic Code Book): обычное использование DES как блочного шифра. Шифруемый текст разбивается на блоки, при этом, каждый блок шифруется отдельно, не взаимодействуя с

другими блоками (рисунок 1.5). Рисунок 1.5 – Режим электронной кодовой книги – ECB 2. Режим сцепления блоков (СВС — Cipher Block Chaining)). Каждый очередной блок Ci i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста Mi+1. Вектор C0 — начальный вектор, он меняется ежедневно и хранится в секрете (рисунок 1.6). Рисунок 1.6 – Режим сцепления блоков — СВС 3. Режим обратной связи по шифротексту (CFB —

Cipher Feed Back). В режиме СFB вырабатывается блочная «гамма» Z0,Z1 Zi=DESk(Ci−1). Начальный вектор C0 сохраняется в секрете (рисунок 1.7). Рисунок 1.7 – Режим обратной связи с шифротексту – CFB 4. Режим обратной связи по выходу (OFB — Output Feed Back). В режиме OFB вырабатывается блочная «гамма»

Z0,Z1 , i>=1 (рисунок 1.8) Рисунок 1.8 – Режим обратной связи по выходу – OFB Достоинства и недостатки режимов: • Режим ECB прост в реализации, но возможно проведение криптоанализа • В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста Ci приводит к искажению после расшифрования только соответствующего открытого блока Mi, поэтому такие режимы используется для передачи по каналам связи с большим числом искажений. •

В режимах CBC и CFB искажение при передаче одного блока шифрованного текста Сi приводит к искажению на приёмнике не более двух блоков открытого текста Mi,Mi+1. Изменение Mi приводит к изменению всех остальных блоковMi+1,Mi+2… Это свойство используется для выработки кода аутентификации сообщения. 1.5 Криптостойкость алгоритма Нелинейность преобразований в

DES средствами только S-блоков, в случае, если они имеют слабину, позволяет осуществлять контроль над шифрованной перепиской. Выбор S-блоков требует соблюдения нескольких условий: • Каждая строка каждого блока должна быть перестановкой множества {0,1,2,……,15} • S-блоки не должны являться линейной или афинной функцией своих аргументов. • Изменение одного бита на входе S-блока должно приводить к изменению по крайней мере двух битов на выходе.

• Для каждого S-блока и любого аргумента х значение и должны различаться по крайней мере двумя битами. Из-за небольшого числа возможных ключей (всего 256), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время. В 1998 году The Electronic Foundation используя специальный компьютер DES-Cracker, удалось взломать DES за 3 дня. Это поставило под удар секретность правительственных документов,

что заставило искать новые алгоритмы шифрования. В алгоритме DES существуют слабые и частично-слабые ключи. Слабыми ключами называется ключи k такие что DESk(DESk(x)) = x, x — блок 64 бит. Частично-слабые ключи — пары ключей (k1,k2) такие, что DESk1(DESk2(x))=x. Известны 4 слабых ключа. Для каждого слабого ключа существует 232 «постоянные точки», то есть таких 64-битовых блоков х, в которых DESk(x) = x.

Существуют 6 частично-слабых пар ключей. Для каждого из 12 частично-слабых ключей существуют 232 «анти-постоянные точки», то есть такие блоки х, что . Основными методами взлома алгоритма являются: • Метод полного поиска требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и для его выполнения нужны 255 шагов. • Дифференциальный криптоанализ — первую такую атаку на

DES заявили Эли Бихам и Ади Шамир. Эта атака требует шифрования 247 открытых текстов, выбранных нападающим, и для её выполнения нужны 247 шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту. Сами авторы этой атаки Бихам и Шамир заявили, что считают DES защищенным для такой атаки. • Линейный криптоанализ разработан

Матсуи. Этот метод позволяет восстановить ключ DES с помощью анализа 243 известных открытых текстов, при этом требуется 243 шагов для выполнения. Первый экспериментальный криптоанализ DES, основанный на открытии Матсуи, был успешно выполнен в течение 50 дней на автоматизированных рабочих местах 12 HP 9735. Для линейной и дифференциальной атак требуется достаточно большой объём памяти для сохранения выбранных (известных) открытых текстов до начала атак.

1.6 Увеличение криптостойкости алгоритма С целью увеличения криптостойкости флгоритма DES было разработано несколько его модификаций: double DES (2DES), triple DES (3DES), DESX, G-DES. Методы 2DES и 3DES основаны на DES, но увеличивают длину ключей (2DES — 112 бит, 3DES — 168 бит) чем и увеличивают криптостойкость. Схема 3DES имеет вид DES(k3,DES(k2,DES(k1,M))), где k1,k2,k3 ключи для каждого шифра

DES. Это вариант известен как ЕЕЕ, так как три DES-операции осуществляют шифрование. Существует 3 типа алгоритма 3DES: DES-EEE3: Шифруется три раза с 3 разными ключами. DES-EDE3: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами. DES-EEE2 и DES-EDE2: Как и предыдущие, за исключением того, который первая и третья операции используют одинаковый ключ. Самый популярный тип при использовании 3DES — это

DES-EDE3, для него алгоритм выглядит так: Шифровка: Расшифровка: При выполнении алгоритма 3DES ключи могут выбрать так: k1,k2,k3 независимы. k1,k2 независимы, а k1 = k3 k1 = k2 = k3. Метод 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 с независимыми подключами требуется 261 выбранных открытых текстов, в то время как для линейного криптоанализа требуется 260 известных открытых текстов. 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-битных блоков:

k1…k8. Ключи k9…k24 являются циклическим повторением ключей k1…k8 (нумеруются от младших битов к старшим). Ключи k25…k32 являются ключами k1…k8, идущими в обратном порядке. После выполнения всех 32 раундов алгоритма, блоки A33 и B33 склеиваются (следует обратить внимание на то, что старшим битом становится A33, а младшим - B33) – результат есть результат работы алгоритма.

Функция f(Ai,Ki) вычисляется следующим образом: Ai и Ki складываются по модулю 232, затем результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, т. е. столько же, сколько и подпоследовательностей.

Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д. Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов. Все восемь S-блоков могут быть различными.

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

подключей ki. 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 вместо сложения по модулю 232. По результатам анализа сделан вывод о том, что GOST-H и GOSTA слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей. Есть весьма интересная модификация алгоритма, не являющаяся стандартом: таблицы

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

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

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

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

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

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

криптоанализ на связанных ключах, можно получить с вероятностью 91,7% 12 бит секретного ключа. Для атаки требуется 235 выбранных открытых текстов и 236 операций шифрования. Как видно, данная атака практически бесполезна для реального вскрытия алгоритма. Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования

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

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

Однако доказано, что секретные таблицы замен могут быть вычислены с помощью следующей атаки, которая может быть применена практически: 1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т.е. значения z = f(0), где f() – функция раунда алгоритма. Этот этап занимает порядка 232 операций шифрования. 2. С помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 211 операций.

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

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

таблиц замены, в которых узлы не являются перестановками, что может привести к чрезвычайному снижению стойкости шифра. 3 Список использованных источников 1. http://ru.wikipedia.org/wiki/DES 2. http://ru.wikipedia.org/wiki/%D0%93%D0%9 E%D0%A1%D0%A2_28147-89 3. http://shifrovanie.narod.ru/faq/GOST.htm l 4. http://pavel.przone.ru/gost89.html 5. http://www.inssl.com/standart-of-cipher. html 6. http://kaf401.rloc.ru/Criptfiles/gost281 47/GOST28147.htm