История, развитие и основные характеристики систем с секретным ключом (DES, FEAL, IDEA, ГОСТ 28147-89)

По некоторым сведениям, история  этого шифра гораздо более давняя. Алгоритм, положенный впоследствии в основу стандарта, родился, предположительно, в недрах Восьмого Главного управления КГБ СССР (ныне в структуре ФСБ), скорее всего, в одном из подведомственных ему закрытых НИИ, вероятно, ещё в 1970-х годах в рамках проектов создания программных и аппаратных реализаций шифра для различных компьютерных платформ.

С момента опубликования ГОСТа  на нём стоял ограничительный  гриф «Для служебного пользования», и  формально шифр был объявлен «полностью открытым» только в мае 1994 года. История создания шифра и критерии разработчиков по состоянию на 2010 год не опубликованы.

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

• простой замены
• гаммирование
• гаммирование с обратной связью

Режим простой  замены

Для зашифрования в этом режиме открытый текст сначала разбивается на две половины (младшие биты — A, старшие биты — B^[2]). На i-ом цикле используется подключ K_i:

( = двоичное «исключающее или»)

Для генерации подключей  исходный 256-битный ключ разбивается  на восемь 32-битных блоков: K₁…K₈.

Ключи K₉…K₂₄ являются циклическим повторением ключей K₁…K₈ (нумеруются от младших битов к старшим). Ключи K₂₅…K₃₂ являются ключами K₈…K₁.

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

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

Функция вычисляется следующим образом:

A_i и K_i складываются по модулю 2³².

Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, то есть столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д.

Если S-блок выглядит так:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12 и на входе S-блока 0, то на выходе будет 1, если 4, то на выходе будет 5, если на входе 12, то на выходе 6 и т. д.

Выходы всех восьми S-блоков объединяются в 32-битное слово, затем  всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

Режим простой замены имеет  следующие недостатки:

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

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

Гаммирование

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

Выработка гаммы происходит на основе ключа и так называемой синхропосылки, которая задает начальное  состояние генератора. Алгоритм выработки  следующий:

1. Синхропосылка шифруется с использованием описанного алгоритма простой замены, полученные значения записываются в N₃ и N₄ - младшие и старшие биты соответственно.
2. К N₃ и N₄ прибавляются константы соответственно C₂ = 1010101₁₆ и C₁ = 1010104₁₆
3. N₃ и N₄ переписываются соответственно в N₁ и N₂, которые затем шифруются и использованием алгоритма простой замены. Полученный результат является 64 битами гаммы.
4. Шаги 2-4 повторяются в соответствии с длиной шифруемого текста.

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

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

Гаммирование  с обратной связью

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

Алгоритм шифрования следующий:

1. Синхропосылка заносится в регистры N₁ и N₂
2. Содержимое регистров N₁ и N₂ шифруется в соответствии с алгоритмом простой замены. Полученный результат является 64-битным блоком гаммы.
3. Блок гаммы складывается по модулю 2 с блоком открытого текста. Полученный шифротекст заносится в регистры N₁ и N₂
4. Операции 2-3 выполняются для оставшихся блоков требующего шифрования текста.

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

Достоинства ГОСТа

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

Недостатки ГОСТа

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

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

В октябре 2010 года на заседании 1-го объединенного технического комитета Международной организации по стандартизации (ISO/IEC JTC 1/SC 27) ГОСТ был выдвинут на включение  в международный стандарт блочного шифрования ISO/IEC 18033-3. В связи с  этим в январе 2011 года были сформированы фиксированные наборы узлов замены и проанализированы их криптографические  свойства. Однако ГОСТ не был принят в качестве стандарта, и соответствующие  таблицы замен не были опубликованы ^[8]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. DES (Data Encryption Standard)

DES (Data Encryption Standard) — симметричный алгоритм шифрования, разработанный фирмой 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).

Прямым развитием DES в  настоящее время является Triple DES.

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

Базовые преобразования:

• Сложное преобразование на одной локальной части блока.
• Простое преобразование между частями блока.

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

Режимы использования DES

DES может использоваться в четырёх режимах:

1. Режим электронной кодовой книги (ECB — Electronic Code Book): обычное использование DES как блочного шифра. Шифруемый текст разбивается на блоки, при этом, каждый блок шифруется отдельно, не взаимодействуя с другими блоками (см. Рис.7).

Рис.1 Режим электронной кодовой книги — ECB

 

2. Режим сцепления блоков (СВС — Cipher Block Chaining) (см. Рис.8). Каждый очередной блок i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста . Вектор — начальный вектор, он меняется ежедневно и хранится в секрете.

Рис.2 Режим сцепления блоков — СВС

3. Режим обратной связи по шифротексту (англ. Cipher Feed Back) (см. Рис.9). В режиме CFB вырабатывается блочная «гамма» . Начальный вектор является синхропосылкой и предназначен для того, чтобы разные наборы данных шифровались по-разному с использованием одного и того же секретного ключа. Синхропосылка посылается получателю в открытом виде вместе с зашифрованным файлом.

Рис.3 Режим обратной связи по шифротексту — CFB

 

4. Режим обратной связи по выходу (OFB — Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» , i>=1

Рис.4 Режим обратной связи по выходу — OFB

 

Достоинства и недостатки режимов:

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