Криптостойкость ГОСТ. Сравнение алгоритмов DES и ГОСТ

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

Главные различия между DESом и ГОСТом заключаются в следующем:

- в DES 56-битный ключ, а в ГОСТе — 256-битный. Если добавить секретные перестановки S-блоков, то полный объем секретной инфор­мации ГОСТа составит примерно 610 бит;

- в DES 16 циклов, а в ГОСТе - 32.

- DES использует сложную процедуру для генерации подключей из исходного ключа, в ГОСТе эта процедура очень проста;

- у S-блоков DES 6-битные входы и 4-битные выходы (таблицы 4х16=64), а у S-блоков ГОСТа 4-битные входы и выходы (таблицы 4х4=16). В обоих алгорит­мах используется по восемь S-блоков, но размер S-блока ГОСТа равен четвер­ти размера S-блока DES;

- в DES используются нерегулярные начальная и конечная перестановки, а в ГОСТе используется 11-битный циклический сдвиг влево.

Силовая атака на ГОСТ абсолютно бесперспективна. ГОСТ исполь­зует 256-битовый ключ, а если учитывать секретные S-блоки, то дли­на ключа будет еще больше.

Кроме того, ГОСТ, по-видимому, более устойчив к дифференци­альному и ли­ней­но­му криптоанализу, чем DES. Хотя слу­чайные S-блоки ГОСТа при неко­тором выборе не гаранти­руют высо­кой криптостойкости по сравнению с фиксиро­ванны­ми S –бло­ками DES, их секретность уве­личивает устойчивость ГОСТа к диффе­ренциаль­ному и линейному крип­тоанализу. К тому же эффективность этих криптоаналитических мето­дов зави­сит от ко­личества циклов преобразова­ния — чем больше циклов, тем труднее криптоа­на­лиз. ГОСТ использует в два раза больше циклов, чем DES, что, возможно, приводит к несостоятельности дифференци­аль­ного и линейного криптоанализа.

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

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

1.5. Алгоритм IDEA

Алгоритм шифрования IDEA (International Data Encryрtion Algorithm) разработан в 1989 г. в Швейцарии, в институте ETH Zurich. Алгоритм запатентован в Европе (Швейцария) и США. Держатель патента – фирма Ascom-Tech AG. Он исполь­зуется, в частности, в известной программе рgр.

Блок-схема алгоритма IDEA изображена на рис. 4.8. Он представляет собой вариант 64-битного итеративного блочного шифра со 128-битным ключом и восемью циклами криптографического преобразования. IDEA не соответствует схеме Фейстеля, однако процедура дешифрования выполняется аналогично процедуре шифрования.

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

1. Сложение по модулю 2, на схеме обозначено Å;

2. Сложение по модулю 2¹⁶, на схеме обозначено +, далее +;

3. Умножение по модулю (2¹⁶-1), на схеме обозначено - Ä.

Таким образом, цикловое отображение f (x, k) построено с исполь­зованием «смешивания» операций над различными алгебраическими структурами, что усложняет криптоанализ алгоритма.

Все операции выполняются над 16-битовыми подблоками, то есть каждый 64-битовый блок разбивается на 4 подблока. Входные подблоки первого цикла обозначим через x ₁, x ₂, x ₃, x ₄, подблоки выходного отображения (шифртекста) обозначим через y ₁, y ₂, y ₃, y ₄, ключевые подблоки i -го цикла обозначим через k ₁^{( i )}, k ₂^{( i )}, k ₃^{( i )}, …, k ₆^{( i )}, i = 1,2,...,8, ключевые подблоки выходного отображения k ₁⁽⁹⁾, k ₂⁽⁹⁾, k ₃⁽⁹⁾, k ₄⁽⁹⁾.

Опишем первый цикл работы алгоритма (остальные циклы реали­зуются ана­логично). В течение первого цикла шифрования реализуются следующие шаги вы­числений (для простоты вместо обозначения k_i ⁽¹⁾,будем использовать k_i, i =1,2, …,6).

Рисунок 4.8. Блок-схема алгоритма шифрования IDEA

Шаг 1. с₁= x ₁ Ä k ₁. Шаг 2. с₂= x ₂ + k ₂.  Шаг 3. с₃= x ₃ + k ₃.      

Шаг 4. с₄= x ₄ Ä k ₄. Шаг 5. с₅=с₁ Å с₃. Шаг 6. с₆=с₂ Å с₄.     

Шаг 7. с₇=с₅ Ä k ₅. Шаг 8. с₈=с₆ + с₇.  Шаг 9. с₉=с₈ Ä k ₆.     

Шаг 10. с₁₀=  с₉+с₇.  Шаг 11. с₁₁=с₁ Å с₉. Шаг 12. с₁₂=с₃Å с₉.     

Шаг 13. с₁₃=с₂Å с₁₀. Шаг 14. с₁₄=с₄Å с₁₀.   

Входные подблоки следующего цикла есть с₁₁, с₁₃, с₁₂, с₁₄. После 8-го цикла реализуется выходное отображение:

Шаг 1. y₁= x ₁ ⁽⁹⁾Ä k ₁⁽⁹⁾.     Шаг 2. y₂= x ₂⁽⁹⁾ + k ₂⁽⁹⁾.

Шаг 3. y₃= x ₃⁽⁹⁾ + k ₃⁽⁹⁾.     Шаг 4. y₄= x ₄⁽⁹⁾ Ä k ₄⁽⁹⁾.

Шифрованным текстом является блок(y ₁, y ₂, y ₃, y ₄).

Ключевое расписание реализуется с помощью вычисления 52 ключевых под­блоков из 128-битового ключа K, на каждом цикле ис­пользуется по 6 подблоков ключа и при реализации выходного ото­бражения - 4 подблока ключа. Вначале 128-битовый ключ K пред­ставляется как 8 подблоков, которые в наших обозначениях равны

k ₁⁽¹⁾, k ₂⁽¹⁾, k ₃⁽¹⁾, k ₄⁽¹⁾, k ₅⁽¹⁾, k ₆⁽¹⁾, k ₁⁽²⁾, k ₂⁽²⁾,

где старшими битами подблоков являются левые биты. Далее 128-битовый ключ циклически сдвигается влево на 25 бит и снова разби­вается на 8 подблоков:

k ₃⁽²⁾, k ₄⁽²⁾, k ₅⁽²⁾, k ₆⁽²⁾, k ₁⁽³⁾, k ₂⁽³⁾, k ₃⁽³⁾, k ₄⁽³⁾.

Затем 128-битовый ключ снова циклически сдвигается влево на 25 бит и снова разбивается на 8 подблоков и т. д., пока не сгенери­руются все 52 подблока.

Подблоки ключа расшифрования (обозначим их через q_i ^{( r )}) опре­деляются следующим образом: первые четыре

-при r = 2,3,..., 8: (q₁ ^{( r )}, q₂ ^{( r )}, q₃ ^{( r )}, q₄ ^{( r )})=([ k ₁^{(10- r )} ]^-1, - k ₂^{(10- r )}, - k ₃^{(10- r )}, [ k ₄^{(10- r )} ]^-1),

-при r =1,9: (q₁ ^{( r )}, q₂ ^{( r )}, q₃ ^{( r )}, q₄ ^{( r )})=([ k ₁^{(10- r )} ]^-1, - k ₃^{(10- r )}, - k ₂^{(10- r )}, [ k ₄^{(10- r )} ]^-1),

и два последних (q₅ ^{( r )}, q₆ ^{( r )})=(k ₅^{( r )}, k ₆^{( r )}), r = 1,2,..., 8;

где z ^-1 есть обратный к z элемент относительно умножения по мо­дулю 2¹⁶+1 (обратным к 0 считаем 0); и - z есть обратный к z элемент относитель­но сложения по модулю 2¹⁶.

Алгоритм IDEA может работать в любом режиме блочного шифра, предусмотренном для алгоритма DES. Эффективность программной реали­зации IDEA не уступает DES. Производительность алгоритма IDEA превы­шает в 1,5-4 раза (в зави­симости от вычислителя) производительность DES-алгоритма.

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

Специфическая особенность IDEA – срав­нительная простота ана­лиза крипто­стой­кости алгорит­ма по отношению к дифференциальному крип­тоанализу. Результаты ус­пешного линей­ного криптоанализа также неиз­вестны. Методы анализа алгоритма IDEA, менее трудоемкие, чем полный перебор ключей, не известны. В ходе исследования крип­тостойкости IDEA было установ­лено, что существует подмножество из 2⁵¹ «слабых» клю­чей, которые могут быть раскрыты путем анализа процедуры шифрования на конкрет­ном ключе из данного подмножества. Результат, однако, не оказывает существенно­го влияния на практическую криптостойкость, так как мощность подмножества «слабых» ключей мала по сравнению с мощностью всего ключевого пространства (2¹²⁸ различных ключей).