Алгоритм симметричного шифрования DES

⇐ ПредыдущаяСтр 4 из 7Следующая ⇒

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

Зашифрование 64-битового блока данных T^о (входной параметр алгоритма) начинается с начальной перестановки битов в нем IP. Затем шифруемый блок разделяется на две 32-битовые части (старшую - L₀ и младшую - R₀ ), с которыми выполняются 16 раундов преобразования в соответствии с архитектурными принципами сети Файстеля. На каждом раунде старшая половина блока модифицируется путем побитового прибавления к ней по модулю 2 (операция Å ) результата вычисления функции шифрования ( f ), зависящей от младшей половины блока ( R_i _–1) и 48-битового ключевого элемента ( k_i ).

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

На последнем раунде происходит то же самое за исключением обмена значениями половин блока. Затем полублоки объединяются в полный блок, в котором выполняется конечная битовая перестановка ( IP ^–1), обратная начальной. Результат последней операции и является выходным значением цикла шифрования – зашифрованным блоком T ^ш. Шестнадцать 48-битовых ключевых элементов k_i, 1 ≤ i ≤ 16, используемых в цикле шифрования, являются параметрами алгоритма и вырабатываются из 56-битового ключа в ходе рассмотренной ниже процедуры генерации ключевой последовательности

Процедура расшифрования блока данных идентична процедуре зашифрования с тем отличием, что ключевые элементы в ней используются в порядке, обратном порядку их использования при зашифровании. Таким образом, если при зашифровании ключевые элементы используются в порядке возрастания номеров k ₁, k ₂, k ₃, k ₄, k ₅, k ₆, k ₇, k ₈, k ₉, k ₁₀, k ₁₁, k ₁₂, k ₁₃, k ₁₄, k ₁₅, k ₁₆, то при расшифровании они должны использоваться в обратном порядке:

k ₁₆, k ₁₅, k ₁₄, k ₁₃, k ₁₂, k ₁₁, k ₁₀, k ₉, k ₈, k ₇, k ₆, k ₅, k ₄, k ₃, k ₂, k ₁.

Начальная и обратная ей конечная битовые перестановки алгоритма DES являются стандартными и должны включаться в реализацию алгоритма в неизменном виде.

Схема преобразования данных (функция шифрования) приведена на рисунке 8.2.

На вход функции шифрования поступает 32-битовая половина шифруемого блока R_i_-1, и 48-битовый ключевой элемент k_i. Сначала 32-битовый блок данных расширяется до 48 битов дублированием некоторых двоичных разрядов (функция E). Затем полученный расширенный блок побитово суммируется по модулю 2 с ключевым элементом (операция " " ).

Алгоритм симметричного шифрования DES (продолжение)

Рис. 8.2. Функция шифрования – схема преобразования данных

Полученный в результате суммирования 48-битовый блок данных разделяется на восемь 6-битовых элементов данных, обозначенных h ₁, h ₂, …, h ₈ соответственно, причем h ₁ содержит шесть самых старших битов 48-битового блока, h ₂ – шесть следующих по старшинству битов и т.д., наконец, h ₈ – шесть самых младших битов блока. Далее каждое из значений h_i преобразуется в новое 4-битовое значение t_i с помощью соответствующего узла замен ( S_i ). После этого полученные восемь 4-битовых элементов данных вновь объединяются в 32-битовый блок в том же самом порядке их старшинства. Наконец, в полученном 32-битовом блоке выполняется перестановка битов ( IP ). Результат последней операции и является выходным значением функции шифрования.

В алгоритме DES ключевые элементы вырабатываются из ключа с использованием сдвигов и битовых выборок-перестановок. Таким образом, – и это очень важно, – ключевые элементы состоят исключительно из битов исходного ключа, " перетасованных" в различном порядке. Ключ имеет размер 64 бита, однако реально для выработки ключевых элементов используются только 56 из них. Самые младшие биты каждого байта ключа не попадают в ключевые элементы и служат исключительно для контроля четности.

Требования к электронной цифровой подписи

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

Например, предположим, что Алиса посылает Бобу аутентифицированное сообщение, и аутентификация осуществляется на основе общего секретного ключа. Рассмотрим возможные недоразумения, которые могут при этом возникнуть:

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

2. Алиса может отрицать, что она посылала сообщение Бобу. Так как Боб может подделать сообщение, у него нет способа доказать, что Алиса действительно посылала его.

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

1. Должна быть возможность проверить автора, дату и время создания подписи.

2. Должна быть возможность аутентифицировать содержимое во время создания подписи.

3. Подпись должна быть проверяема третьей стороной для разрешения споров.

На основании этих свойств можно сформулировать следующие требования к цифровой подписи:

1. Подпись должна быть битовым образцом, который зависит от подписываемого сообщения.

2. Подпись должна использовать некоторую уникальную информацию отправителя для предотвращения подделки или отказа.

3. Создавать цифровую подпись должно быть относительно легко.

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

5. Цифровая подпись должна быть достаточно компактной и не занимать много памяти.

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

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

Основные параметры DES

Название/статус

DES (Data Encryption Standard). Федеральный стандарт шифрования США в 1977-2001 годах.

Время/место разработки

Создан в 1972-1975 годы в исследовательской лаборатории корпорации IBM. В качестве федерального стандарта США принят в 1977 году. В декабре 2001 года утратил свой статус в связи с введением в действие нового стандарта.

Авторы

Группа под руководством д-ра. У.Тачмена.

Архитектура

Классическая сбалансированная сеть Фейстеля с начальной и конечной битовыми перестановками общего вида.

Параметры

размер блока, бит 64

размер ключа, бит 56 (64, 8 из которых служат для контроля четности)

число раундов 16

размер ключевого элемента, бит 48

число ключевых элементов 16 (равно числу раундов)

Патент

Не запатентован.

Особенности

Широкое использование битовых перестановок в DES делает алгоритм неудобным для программных реализаций на универсальных процессорах, а сами такие реализации крайне неэффективными. По сравнению с Российским стандартом шифрования DES содержит вдвое меньше раундов, однако его оптимальная реализация для процессоров линии Intel x86 уступает реализации Российского стандарта по скорости в 3-5 раз в зависимости от марки процессора, эта разница увеличивается от младших моделей к старшим. Кроме того, по единодушному мнению криптографов начальная и конечная битовые перестановки являются не более чем " украшениями" алгоритма т.е. бесполезны с криптографической точки зрения, а размера ключа в 56 бит явно недостаточно для обеспечения приемлемой стойкости, что регулярно демонстрируется успехами во взлома шифра путем подбора ключа методом прямого перебора с помощью распределенной сети или спецпроцессора.

НМАС

Код аутентичности сообщения (message authentication code – MAC ) – это функция, которая принимает на вход два аргумента: ключ К фиксированной длины и сообщение М произвольной длины и выдает значение фиксированной длины. Для обеспечения аутентификации сообщения пользователь отсылает не только сообщение М, но и код аутентичности этого сообщения С_K (M).

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

Функция вычисления МАС должна обладать следующими свойствами:

1. Должно быть вычислительно трудно, зная М и С_K (M), найти сообщение М′, такое, что С_K(M) = С_K(M′ ).

2. Значения С_K(M) должны быть равномерно распределенными в том смысле, что для любых сообщений М и M′ вероятность того, что С_K(M) = С_K(M′ ), должна быть равна 2^-n, где n – длина значения МАС.

НМАС

Еще один вариант использования хэш-функции для получения МАС состоит в том, чтобы определенным образом добавить секретное значение к сообщению, которое подается на вход хэш-функции. Такой алгоритм носит название НМАС, и он описан в RFC 2104.

При разработке алгоритма НМАС преследовались следующие цели:

· возможность использовать без модификаций уже имеющиеся хэш-функции;

· возможность легкой замены встроенных хэш-функций на более быстрые или более стойкие;

· сохранение скорости работы алгоритма, близкой к скорости работы соответствующей хэш-функции;

· возможность применения ключей и простота работы с ними.

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

Введем следующие обозначения:

Н – встроенная хэш-функция.

b – длина блока используемой хэш-функции.

n – длина хэш-кода.

K – секретный ключ. К этому ключу слева добавляют нули, чтобы получить b- битовый ключ K⁺.

Вводится два вспомогательных значения:

I_pad – значение '00110110', повторенное b/8 раз.

O_pad – значение '01011010', повторенное b/8 раз

Далее НМАС вычисляется следующим образом:

НМАС = Н ((K⁺ Å Opad) || H ((K⁺ Å Ipad) || M

Общая схема алгоритма DES

DES (Data Encryption Standard). Федеральный стандарт шифрования США в 1977-2001 годах.

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

На последнем раунде происходит то же самое за исключением обмена значениями половин блока. Затем полублоки объединяются в полный блок, в котором выполняется конечная битовая перестановка ( IP ^–1). Результат последней операции и является выходным значением цикла шифрования – зашифрованным блоком T ^ш. Шестнадцать 48-битовых ключевых элементов k_i, 1≤ i≤ 16, используемых в цикле шифрования, являются параметрами алгоритма и вырабатываются из 56-битового ключа в ходе рассмотренной ниже процедуры генерации ключевой последовательности.

Требования к хеш-функциям

Хэш-функция – это односторонняя функция, которая на вход принимает файл данных произвольной длины, а выдает результат фиксированной длины (128, 256, 512 или другое количество битов. Стандартной областью применения функций хеширования являются цифровые подписи. Вместо самого сообщения (которое может иметь слишком большую длину) подписывают хэш-код сообщения. Хэш-код создается функцией Н: h = H (M)

М - сообщение произвольной длины; h - хэш-код фиксир. длины.

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

1. Хэш-функция Н должна применяться к блоку данных любой длины.

2. Хэш-функция Н создает выход фиксированной длины.

3. Н (М) относительно легко (за полиномиальное время) вычисл. для любого значения М.

4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h.

5. Для любого данного х вычислительно невозможно найти y ≠ x, что H (y) = H (x).

6. Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x).

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

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

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

· перехватить сообщение и его зашифрованный хэш-код,

· вычислить хэш-код сообщения,

· создать альтернативное сообщение с тем же самым хэш-кодом,

· заменить исходное сообщение на поддельное.

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

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если, кроме того, выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака " день рождения".

⇐ Предыдущая 1 2 345 6 7 Следующая ⇒