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

 

Roadmap

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

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

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

 

3DES

Итак, первым в ряду зарубежных шифров рассмотрим 3DES, а точнее его ближайшего родственника DES (Data Encryption Standard), который хоть уже и не используется как таковой, но является предком 3DES.

DES разработан командой математиков научной лаборатории IBM, в которую входил уже знакомый нам Фейстель. Первая версия шифра получила имя «Люцифер», но затем он был модифицирован и в результате принят как официальный алгоритм шифрования данных (DEA). На протяжении более двадцати лет он оставался мировым стандартом, прежде чем его сменил Triple DES.

Рассмотрим, как работает алгоритм шифрования DES. Для этого необходимо вспомнить работу сети Фейстеля. DES — это сеть Фейстеля из 16 раундов с симметричными ключами шифрования. Длина блока текста — 64 бита, длина раундового ключа — 48 бит. Итак, пройдем основные этапы шифрования DES, опуская суровую математическую сторону:

  1. Текст, как и при любом другом шифровании, разбивается на блоки по 64 бита.
  2. Из 56-битного ключа генерируется 16 48-битных раундовых ключиков.
  3. Каждый блок подвергается перестановке, то есть все биты входного блока перемешиваются согласно определенной таблице.
  4. Блок расщепляется на половинки и поступает в знакомую нам сеть Фейстеля, где прокручивается 16 раундов.
  5. Соединяем половинки.
  6. И еще одна перестановка.

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

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

Но вернемся к тройному DES, или Triple DES. В нем возникла необходимость, так как 56-битный ключ DES был уязвим к брутфорсу и с ростом вычислительных мощностей эта проблема вставала все острее. Используя доступную сегодня технологию, можно проверить один миллион ключей в секунду. Это означает, что потребуется более чем две тысячи лет, чтобы перебором дешифровать DES, используя компьютер только с одним процессором.

Но если взять компьютер с одним миллионом процессорных ядер, которые будут параллельно обрабатывать ключи, мы сможем проверить все множество ключей приблизительно за 20 часов. Когда был введен DES, стоимость такого компьютера равнялась нескольким миллионам долларов, но она быстро снизилась. Специальный компьютер был создан в 1998 году — и нашел ключ за 112 часов.

Чтобы решить проблему быстрого поиска ключа, умные зарубежные криптографы предложили использовать два ключа и применять DES дважды. Однако двойной DES оказался уязвим к атаке «встреча посередине». Чтобы реализовать эту атаку, злоумышленнику необходимо иметь открытый и соответствующий ему зашифрованный текст. Злоумышленник шифрует открытый текст на всех возможных ключах, записывая результаты в таблицу 1. Затем расшифровывает зашифрованный текст со всеми возможными ключами и записывает результат в таблицу 2. Далее злоумышленник ищет в таблицах 1 и 2 совпадения.

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

Совсем иначе дела обстоят с Triple DES. Использование трех ключей и применение алгоритмов в указанной на схеме последовательности продлило DES жизнь еще на несколько лет.

 

Замечательный DES

Так что же в DES такого замечательного? Этот алгоритм шифрования был подвергнут тщательному анализу. DES обладал двумя очень важными качествами блочных шифров — лавинностью и полнотой. Настало время расширить свой криптографический словарик!
Лавинный эффект означает, что небольшие изменения в исходном тексте (или ключе) могут вызвать значительные изменения в зашифрованном тексте.

Было доказано, что DES имеет все признаки этого свойства.

Исходный текст 0000000000000000 0000000000000001
Ключ 22234512987ABB23 22234512987ABB23
Зашифрованный текст 4789FD476E82A5F1 OA4ED5C15A63FEA3

Хотя два блока исходного текста не совпадают только самым правым битом, блоки зашифрованного текста отличаются на 29 бит. Это означает, что изменение приблизительно в 1,5% исходного текста вызывает изменение приблизительно 45% зашифрованного текста.

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

Где же применяется DES? Да почти везде, его реализации присутствуют в большинстве программных библиотек. Однако кто знает, насколько использование DES безопасно в наше время? Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, не вставило ли NSA в алгоритм лазейку, которая позволяет агентству легко дешифровывать перехваченные сообщения. Комитет по разведке сената США тщательно изучал этот вопрос и, разумеется, ничего не обнаружил, обвинения с NSA были сняты, результаты исследования тем не менее засекречены. Одним словом, в Америке еще долго крутились слухи и домыслы насчет того, стоит доверять DES или нет. Но, как я считаю, здесь ситуация описывается поговоркой «Умный не скажет, дурак не поймет». В конце концов NSA признало, что не могло доверить IBM столь важную миссию и внесло несколько корректировок вроде задания S-боксов.

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

 

AES

Победитель конкурса AES, объявленный в конце 1997 года, алгоритм Rijndael был разработан двумя бельгийскими криптографами — Йоаном Даменом (Joan Daemen) и Винсентом Рейменом (Vincent Rijmen).

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

AES оперирует 128-битными блоками данных и ключами по 128, 192 и 256 бит. Концептуально он отличается от DES, так как не базируется на сети Фейстеля, а представляет собой подстановочно-перестановочную сеть (SP-сеть), которую мы сейчас рассмотрим подробнее.

В AES байты открытого текста не делятся на две части, как в сети Фейстеля, а записываются в форму — матрицу (двумерный массив) байтов, расположенных таким образом:

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

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

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

Вариант 2. Купи одну статью

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


4 комментария

Подпишитесь на ][, чтобы участвовать в обсуждении

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

Check Also

Espruino Pico. Учимся программировать USB-микроконтроллер на JavaScript и делаем из него токен авторизации

Несмотря на огромное количество устройств на базе микроконтроллеров, созданных на волне ус…