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

 

Roadmap

Это третий урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:

  • Урок 1. Исторические шифры. Основы и исторические шифраторы. Как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины
  • Урок 2. Распределение ключей. Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
  • Урок 3. Современные отечественные шифры. Что такое сеть Фейстеля и какими бывают отечественные блочные шифры, используемые в современных протоколах, — ГОСТ 28147—89, «Кузнечик» (ты здесь)
  • Урок 4. Современные зарубежные шифры. В чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайера и как они работают
  • Урок 5. Электронная подпись. Виды электронных подписей, как они работают и как их использовать
  • Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи

 

Блочное и поточное шифрование

Как ты помнишь, шифр сдвига, замены, перестановки и шифр Вернама применяют операцию к каждому конкретному символу текста. Нужно сдвинуть — сдвигаем символ, применить ключ — применяем к символу, за ним к следующему символу и так далее, пока не зашифруем все символы открытого текста. Такой метод шифрования называется поточным — мы шифруем каждый символ в отдельности. Есть и другой подход: разбить исходный открытый текст на группы по несколько символов (блоки) и выполнять операции шифрования в каждом блоке. Это — блочный метод шифрования.

Чтобы отличие между блочными и поточными шифрами стало понятнее, приведем пример на простом шифре замены.

 

Поточное шифрование

Зашифруем поточным шифром замены слово CIPHER:

a b c d e f g h i j k l m n o p q r s t u v w x y z
b e x g w i q v l o u m p j r s t n k h f y z a d c

 

С I P H E R
X L S V W N

 

Зашифровали каждый символ и получили шифротекст. Проще простого.

 

Блочное шифрование

Зашифруем слово AVADAKEDAVRA. Поскольку шифр блочный, открытый текст разобьем на блоки по четыре символа: AVAD | AKED | AVRA. На практике блоки текста состоят из 64‒256 бит. Для каждого блока придумаем свою таблицу замены:

a b c d e f g h i j k l m n o p q r s t u v w x y z
b e x g w i q v l o u m p j r s t n k h f y z a d c

 

a b c d e f g h i j k l m n o p q r s t u v w x y z
p g x e n v c i l h u j b m r s w t k o f d z a y q

 

a b c d e f g h i j k l m n o p q r s t u v w x y z
x w b g s q i v l c u m p o r j t m k n f y h a z d

 

А теперь шифруем каждый из блоков соответствующим алфавитом:

A V A D
B Y B G
A K E D
P U N E
A V R A
X Y M X

 

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

 

Сеть Фейстеля

Теперь мы готовы перейти к очень важной теме, которая открывает дверь в бескрайний мир современных систем шифрования. Сеть Фейстеля — это метод блочного шифрования, разработанный Хорстом Фейстелем в лаборатории IBM в 1971 году. Сегодня сеть Фейстеля лежит в основе большого количества криптографических протоколов. Попробуем разобрать «на пальцах», что же она собой представляет.

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

  • Блок разбивается на две равные части — левую (L) и правую (R).
  • После разбиения левый подблок изменяется функцией f с использованием ключа K: x = f(L, K). В качестве функции можно представить себе какое угодно преобразование — например, старый добрый шифр сдвига с ключом K.
  • Полученный подблок складывается по модулю 2 с правым подблоком R, который до этого был не у дел: x = x⊕R.
  • Далее полученные части меняются местами и склеиваются.

Как видишь, все достаточно просто. Для того чтобы понять, как это работает, посмотри на схему:

Ячейка Фейстеля
Ячейка Фейстеля

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

Теперь посмотрим работу сети Фейстеля на примере. Возьмем слово AVADAKEDAVRA и разобьем его на два блока по шесть символов — AVADAK | EDAVRA. За функцию возьмем шифр сдвига на число позиций, определенных раундовым ключом. Пусть секретный ключ K = [1, 2]. В качестве раундовых ключей возьмем K[0] = 1, K[1] = 2. Для сложения по модулю 2 переведем текст в двоичный код согласно телеграфному алфавитику, которым вряд ли кто-то еще пользуется вообще.

Вот что получилось:

A V A D A K E D A V R A
00011 11110 00011 01001 00011 01111 00001 01001 00011 11110 01010 00011

 

Теперь прогоним через сеть Фейстеля из двух раундов первый блок:

Прогон первого блока
Прогон первого блока

Второй блок попробуй зашифровать сам, у меня получилось MOSSTR.

Расшифрование осуществляется точно так же: шифротекст разбивается на блоки и затем подблоки, левый подблок поступает в функцию, складывается по модулю 2 с правым, и затем подблоки меняются местами. Отличие заключается в том, что раундовые ключи подаются в обратном порядке, то есть в нашем случае в первом раунде применим ключ K = 2, а затем во втором раунде K = 1.

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

 

ГОСТ 28147—89 (Магма)

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

Основные характеристики: ключ 256 бит, блок 64 бита.

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

Продолжение доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все материалы на сайте

Подписка позволит тебе в течение указанного срока читать ВСЕ платные материалы сайта. Мы принимаем оплату банковскими картами, электронными деньгами и переводами со счетов мобильных операторов. Подробнее о подписке

Вариант 2. Купи один материал

Заинтересовала информация, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для материалов, опубликованных более двух месяцев назад.


5 комментариев

  1. schoolboy

    22.04.2016 at 03:58

    ГОСТ 28147—89; режим простой замены; пункт 2. Может не по модулю 232, а по модулю 2^32?

  2. hrapovd

    01.05.2016 at 14:06

    У ГОСТов один не достаток — нет толковых инструментов и библиотек для корпоративного ПО, на JAVA пожалуй только КРИПТО-ПРО JCP, но у них к сожалению еще последняя версия 2.х не сертифицирована в ФСБ. А сертифицированная, 1.х — работает на java 6…

  3. Anatoly

    10.07.2016 at 18:27

    конечно что-то непонятно но интересно

  4. fr00t

    16.01.2018 at 04:17

    В режимах имитовставки, гаммирования и гаммирования с обратной связью тоже, вероятно, молуль 2^32 подразумевается?

Оставить мнение

Check Also

Жесткая закалка Linux. Подбираем инструменты для комплексного аудита безопасности

В этом материале мы познакомимся с основными утилитами для Linux hardening. На русском язы…