Назначение и структура алгоритмов шифрования
Шифрование является основным методом защиты; рассмотрим его подробно далее.
Можно представить зашифрование в виде следующей формулы:
В стандарте ГОСТ 28147-89 (стандарт определяет отечественный алгоритм симметричного шифрования) понятие ключ определено следующим образом: «Конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований».
Ключ может принадлежать определенному пользователю или группе пользователей и являться для них уникальным. Зашифрованная с использованием конкретного ключа информация может быть расшифрована только с использованием только этого же ключа или ключа, связанного с ним определенным соотношением.
Аналогичным образом можно представить и расшифрование:
При отсутствии верного ключа k2 получить исходное сообщение M’ = M с помощью правильной функции D невозможно. Под словом «невозможно» в данном случае обычно понимается невозможность вычисления за реальное время при существующих вычислительных ресурсах.
В алгоритмах симметричного шифрования для расшифрования обычно используется тот же самый ключ, что и для зашифрования, или ключ, связанный с ним каким-либо простым соотношением. Последнее встречается существенно реже, особенно в современных алгоритмах шифрования. Такой ключ (общий для зашифрования и расшифрования) обычно называется просто ключом шифрования.
В асимметричном шифровании ключ зашифрования k1 легко вычисляется из ключа k2 таким образом, что обратное вычисление невозможно. Например, соотношение ключей может быть таким:
Такое соотношение ключей используется и в алгоритмах электронной подписи.
Основной характеристикой алгоритма шифрования является криптостойкость, которая определяет его стойкость к раскрытию методами криптоанализа. Обычно эта характеристика определяется интервалом времени, необходимым для раскрытия шифра.
Рассмотрим, как выглядят изнутри алгоритмы блочного симметричного шифрования.Структура алгоритмов шифрования
Существует и более сложная структура сети Фейстеля, пример которой приведен на рис. 3.
В отличие от сети Фейстеля, SP-сети обрабатывают за один раунд целиком шифруемый блок. Обработка данных сводится, в основном, к заменам (когда, например, фрагмент входного значения заменяется другим фрагментом в соответствии с таблицей замен, которая может зависеть от значения ключа Ki) и перестановкам, зависящим от ключа Ki (упрощенная схема показана на рис. 4).
Впрочем, такие операции характерны и для других видов алгоритмов шифрования, поэтому, на мой взгляд, название «подстановочно-перестановочная сеть» является достаточно условным.
Для структуры «квадрат» характерно представление шифруемого блока данных в виде двумерного байтового массива. Криптографические преобразования могут выполняться над отдельными байтами массива, а также над его строками или столбцами.
На рис. 5 приведен пример операции над блоком данных, выполняемой алгоритмом Rijndael.
Алгоритмы с нестандартной структурой, то есть те алгоритмы, которые невозможно причислить ни к одному из перечисленных типов. Ясно, что изобретательность может быть безгранична, поэтому классифицировать все возможные варианты алгоритмов шифрования представляется сложным. В качестве примера алгоритма с нестандартной структурой можно привести уникальный по своей структуре алгоритм FROG, в каждом раунде которого по достаточно сложным правилам выполняется модификация двух байт шифруемых данных (см. рис. 6).
Сеть Файстеля. Значение для криптографии. Вариации. Свойства.
Билет №1
Сеть Файстеля. Значение для криптографии. Вариации. Свойства.
Сеть Фе́йстеля (конструкция Фейстеля) — один из методов построения блочных шифров. Сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру, называющуюся ячейкой Фейстеля. При переходе от одной ячейки к другой меняется ключ, причём выбор ключа зависит от конкретного алгоритма. Операции шифрования и расшифрования на каждом этапе очень просты, и при определённой доработке совпадают, требуя только обратного порядка используемых ключей. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения. Большинство современных блочных шифров используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть.
Простое описание
Шифрование
Рассмотрим случай, когда мы хотим зашифровать некоторую информацию, представленную в двоичном виде вкомпьютерной памяти (например, файл) или электронике, как последовательность нулей и единиц.
Расшифрование
Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи идут в обратном порядке, то есть не от первого к N-ному, а от N-го к первому.
Алгоритмическое описание
,
где 
— некоторая функция, а 
— ключ 
-го раунда.
Результатом выполнения 
раундов является 
. Но обычно в -ом раунде перестановка 
и 
не производится, что позволяет использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования раундовой ключевой информации:
,
Небольшим изменением можно добиться и полной идентичности процедур шифрования и расшифрования.
Одно из преимуществ такой модели — обратимость алгоритма независимо от используемой функции , и она может быть сколь угодно сложной.
Математическое описание
Инволюция [4] — взаимно-однозначное преобразование, которое является обратным самому себе. Рассмотрим на примере: Пусть X — входной блок, а A — некоторое инволютивное преобразование, Y — результат. При однократном применении преобразования к входному блоку получится: 
, при применении преобразования к результату предыдущего преобразования получится: 
.
Пусть входной блок X=(L, R) состоит из двух подблоков (L и R) равной длины. Определим два преобразования 
(шифрование ключом K) и 
(перестановка подблоков). Введём обозначения: 
Докажем их инволютивность:
Рассмотрим сам процесс шифрования. Определим X как входное значение. Пусть 
— преобразование с ключом 
, а 
— выходное значение после i-го раунда. Тогда преобразование на i+1-м раунде можно записать в виде 
, кроме первого, где 
. Следовательно, выходное значение после m раундов шифрования будет 
. Можно заметить, что на последнем этапе не обязательно выполнять перестановку T.
Расшифрование ведётся применением всех преобразований в обратном порядке. В силу инволютивности каждого из преобразований обратный порядок даёт исходный результат:
.Достоинства и недостатки
Описание алгоритма
Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб— число b. Затем Алиса вычисляет значение [5] (1):
(1)
(2)
Пример
Алгоритм Диффи-Хеллмана так же может быть использован при шифровании с открытым ключом. В этом случае общая схема остаётся аналогичной приведённой выше, но с небольшими отличиями. Алиса не передаёт значения p, g и A Бобу напрямую, а публикует их заранее в качестве своего открытого ключа. Боб выполняет свою часть вычислений, после чего шифрует сообщение симметричным алгоритмом, используя K в качестве ключа, и передает шифротекст Алисе вместе со значением B.
Билет №1
Сеть Файстеля. Значение для криптографии. Вариации. Свойства.
Сеть Фе́йстеля (конструкция Фейстеля) — один из методов построения блочных шифров. Сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру, называющуюся ячейкой Фейстеля. При переходе от одной ячейки к другой меняется ключ, причём выбор ключа зависит от конкретного алгоритма. Операции шифрования и расшифрования на каждом этапе очень просты, и при определённой доработке совпадают, требуя только обратного порядка используемых ключей. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения. Большинство современных блочных шифров используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть.
Простое описание
Шифрование
Рассмотрим случай, когда мы хотим зашифровать некоторую информацию, представленную в двоичном виде вкомпьютерной памяти (например, файл) или электронике, как последовательность нулей и единиц.
Расшифрование
Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи идут в обратном порядке, то есть не от первого к N-ному, а от N-го к первому.
Алгоритмическое описание
,
где — некоторая функция, а — ключ -го раунда.
Результатом выполнения раундов является . Но обычно в -ом раунде перестановка и не производится, что позволяет использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования раундовой ключевой информации:
,
Небольшим изменением можно добиться и полной идентичности процедур шифрования и расшифрования.
Одно из преимуществ такой модели — обратимость алгоритма независимо от используемой функции , и она может быть сколь угодно сложной.
Математическое описание
Инволюция [4] — взаимно-однозначное преобразование, которое является обратным самому себе. Рассмотрим на примере: Пусть X — входной блок, а A — некоторое инволютивное преобразование, Y — результат. При однократном применении преобразования к входному блоку получится: , при применении преобразования к результату предыдущего преобразования получится: .
Пусть входной блок X=(L, R) состоит из двух подблоков (L и R) равной длины. Определим два преобразования (шифрование ключом K) и (перестановка подблоков). Введём обозначения:
Докажем их инволютивность:
Рассмотрим сам процесс шифрования. Определим X как входное значение. Пусть — преобразование с ключом , а — выходное значение после i-го раунда. Тогда преобразование на i+1-м раунде можно записать в виде , кроме первого, где . Следовательно, выходное значение после m раундов шифрования будет . Можно заметить, что на последнем этапе не обязательно выполнять перестановку T.
Расшифрование ведётся применением всех преобразований в обратном порядке. В силу инволютивности каждого из преобразований обратный порядок даёт исходный результат:
.Достоинства и недостатки
Погружение в крипту. Часть 4. Современные зарубежные шифры
Содержание статьи
В прошлый раз ты познакомился с великими и ужасными отечественными шифрами. Это был очень непростой урок, ведь эти криптосистемы стоят на страже государственной тайны. Скажешь, куда уж замудреннее? А вот сюда, пожалуйста! На самом деле не стоит пугаться, в этот раз не будем так глубоко погружаться в математику и рассматривать режимы шифрования — их принципы ты уже усвоил (ну или не усвоил). Пройдемся по самым топовым зарубежным шифрам и посмотрим, как же их применяют на практике.
Roadmap
Это четвертый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:
Чтобы не сесть в лужу с терминами, рекомендую освежить в памяти понятия поточных и блочных шифров, а также симметричного и асимметричного шифрования, блоков замены и сети Фейстеля.
Итак, первым в ряду зарубежных шифров рассмотрим 3DES, а точнее его ближайшего родственника DES (Data Encryption Standard), который хоть уже и не используется как таковой, но является предком 3DES.
DES разработан командой математиков научной лаборатории IBM, в которую входил уже знакомый нам Фейстель. Первая версия шифра получила имя «Люцифер», но затем он был модифицирован и в результате принят как официальный алгоритм шифрования данных (DEA). На протяжении более двадцати лет он оставался мировым стандартом, прежде чем его сменил Triple DES.
Рассмотрим, как работает алгоритм шифрования DES. Для этого необходимо вспомнить работу сети Фейстеля. DES — это сеть Фейстеля из 16 раундов с симметричными ключами шифрования. Длина блока текста — 64 бита, длина раундового ключа — 48 бит. Итак, пройдем основные этапы шифрования DES, опуская суровую математическую сторону:
Начальная и конечная перестановки не имеют никакого значения для криптографии в 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, объявленный в конце 1997 года, алгоритм Rijndael был разработан двумя бельгийскими криптографами — Йоаном Даменом (Joan Daemen) и Винсентом Рейменом (Vincent Rijmen).
Для обеспечения криптостойкости алгоритм Rijndael включает в себя повторяющиеся раунды, каждый из которых состоит из замен, перестановок и прибавления ключа. Однако, в отличие от DES, шифрование и расшифрование в этом алгоритме — процедуры разные.
AES оперирует 128-битными блоками данных и ключами по 128, 192 и 256 бит. Концептуально он отличается от DES, так как не базируется на сети Фейстеля, а представляет собой подстановочно-перестановочную сеть (SP-сеть), которую мы сейчас рассмотрим подробнее.
В AES байты открытого текста не делятся на две части, как в сети Фейстеля, а записываются в форму — матрицу (двумерный массив) байтов, расположенных таким образом:
| 0 | 4 | 8 | 12 | 16 |
| 1 | 5 | 9 | 13 | . |
| 2 | 6 | 10 | 14 | |
| 3 | 7 | 11 | 15 |
AES действует следующими операциями:
Сегодня AES является официальным стандартом правительства США для симметричного шифрования и применяется повсеместно. Фактически это один из самых универсальных зарубежных шифров на данный момент. Что касается безопасности AES, то и у него, как и большинства шифров, есть некоторые уязвимости, и криптоаналитики продолжают их искать. Однако, несмотря на это, AES живее всех живых.
IDEA (International Data Encryption Algorithm) — алгоритм блочного симметричного шифрования, который был предложен на замену стандарта DES. Начальная версия алгоритма IDEA появилась в 1990 году. Алгоритм запатентован в США и в большинстве европейских стран. Владеет патентом Ascom Tech, но в некоммерческих целях алгоритм можно использовать бесплатно.
Размер блока в этом шифре — 64 бита, длина ключа — 128. Стоит сразу сказать, что алгоритм IDEA — самый молодой из перечисленных и его математика очень сложна. Минутка криптографического словарика.
В IDEA эти свойства достигаются за счет применения независимых математических операций. В отличие от DES, главной операцией которого является XOR (сложение по модулю 2), IDEA предусматривает наличие:
Комбинирование этих трех операций обеспечивает комплексное преобразование входных данных, затрудняя криптоанализ IDEA по сравнению с DES.
В шифре IDEA выполняется восемь раундов, и в каждом раунде блок открытого текста подвергается преобразованию посредством математических операций. Любители «зреть в корень» могут позреть на схему одного раунда шифра IDEA, приведенную ниже. Блок текста, длиной 64 бита, делится на подблоки по 16 бит. Каждый такой полученный блочок поступает на вход раунда и подвергается сложному преобразованию.
Неповторимая IDEA
«Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени», — говорит Брюс Шнайер об алгоритме IDEA.
Действительно, IDEA отличается высокой стойкостью благодаря своим многочисленным математическим операциям. Кроме того, к достоинствам данного алгоритма относится высокая скорость зашифрования — почти в два раза выше, чем у алгоритма DES (в зависимости от платформы, на которой выполняется шифрование). Однако скорость расшифровки снижается из-за тяжелых операций вычисления, обратных умножению по модулю (2 16 + 1).
Разумеется, и на этот сложный шифр мудрые криптографы пытались провести всевозможные атаки. Успеха достиг Пол Хокер, который реализовал атаку, предполагая, что криптоаналитик не имеет прямого доступа к искомому ключу (например, ключ прошит в каком-либо аппаратном шифраторе или смарт-карте), но может изменять определенным образом различные фрагменты ключа.
Алгоритм IDEA не стал международным стандартом шифрования, как того желали его авторы. Однако его можно считать одним из наиболее распространенных в мире алгоритмов шифрования. IDEA используется во множестве приложений, в том числе в широко известном и распространенном протоколе защиты данных PGP.
Рыбы Брюса Шнайера
Брюс Шнайер — видная фигура криптографии наших дней. Он объездил полмира с лекциями и семинарами, его книги настойчиво рекомендуют тем, кто стремится знать криптографию. И конечно же, такой известный человек не хотел бы слыть сапожником без сапог — он сам входит в группу крипторазработчиков.
Мы вкратце познакомимся с одними из самых известных его детищ — алгоритмами шифрования Blowfish, Twofish и Threefish.
Blowfish
Первым на свет появился Blowfish. Как говорит сам Шнайер, этот алгоритм был разработан для реализации на больших микропроцессорах. Поэтому он компактен (всего 5 Кбайт памяти) и прост (использует простые математические операции — сложение, XOR и выборку из таблицы). Также алгоритм позволяет настраивать длину ключа (до 448 бит).
На 32-битных процессорах Blowfish выполняет шифрование значительно быстрее, нежели DES, однако на интеллектуальных платах в силу своей упрощенности он не особо применим. В основе Blowfish сеть Фейстеля из 16 раундов, которую ты уже должен хорошо понимать.
Алгоритм реализован в некоторых программных продуктах (FolderBolt, Nautilus, PGPfone), однако сейчас он уже теряет свою актуальность.
Twofish
За первой рыбой появились еще две — новый алгоритм Twofish был разработан Шнайером и компанией для участия в конкурсе AES. Работа Шнайера вышла в пятерку финалистов, однако победителем так и не стала, хотя обладала для этого всеми возможными плюсами. Это:
Однако по сравнению с Rijndael, занявшим пьедестал AES, Twofish был более сложным для анализа и обладал более низкой скоростью шифрования. Разработан этот алгоритм на основе Blowfish с некоторыми дополнениями и также представляет собой сеть Фейстеля.
На конкурсе шифр подвергли различным типам криптоанализа. По сравнению с остальными финалистами конкурса AES он оказался самым стойким. Однако его необычное строение и относительная сложность породили некоторые сомнения в качестве этой прочности. На данный момент Twofish используется еще реже, чем его предшественник.
Threefish
«В третий раз закинул старик в море невод. » и десять лет спустя получился шифр Threefish. На этот раз Шнайер решил переплюнуть AES и учел все недостатки предыдущего опыта. Криптограф не стал брать за основу сеть Фейстеля, а реализовал шифр на основе подстановочно-перестановочной сети (SP-сети), как в AES. Такая сеть основана на комбинации операций исключающего ИЛИ, сложения и циклического сдвига. В упрощенном виде все это выглядит так:
За счет простых операций Threefish значительно опережает в скорости AES. Кроме того, по заявлениям авторов, алгоритм имеет более высокий уровень безопасности, чем AES. Существует атака на 25 из 72 раундов Threefish, в то время как для AES — на 6 из 10. Так что Шнайер добился-таки своей победы, хоть и с опозданием.
Шифр послужил основой для создания хеш-функции Skein, которая участвовала в конкурсе на должность SHA-3. Сам Threefish широко используется и реализован в библиотеках для многих языков программирования.
Выводы
В заключение стоит сказать, что все западные криптографы, конечно, молодцы, разработали вагон и маленькую тележку различных алгоритмов шифрования. Какой-то более стойкий, какой-то более быстрый. Но пока все будут сравнивать их с DES и AES, потому что это классика.
В следующей статье познакомимся с электронными подписями, очень классным и важным средством криптографии.