Стандарт шифрования данных des доклад

Обновлено: 30.06.2024

Режим шифрования электронной кодовой книги (ECB — Electronic Code Book),
Режим шифрования сцепления блоков (СВС — Cipher Block Chaining),
Режим шифрования обратной связи по шифротексту (CFB — Cipher Feed Back),
Режим шифрования обратной связи по выходу (OFB — Output Feed Back),

Содержание

История блочного шифра DES

В 1972 году, после проведения исследования потребностей правительства США в компьютерной безопасности, американское НБС (Национальное Бюро Стандартов) — теперь переименовано НИСТ (Национальный Институт Стандартов и Технологий) — определило необходимость в общеправительственном стандарте шифрования некритичной информации. 15 мая 1973 года, после консультации с АНБ (Агентством национальной безопасности), НБС объявило конкурс на шифр, который удовлетворит строгим критериям проекта, но ни один конкурсант не обеспечивал выполнение всех требований. Второй конкурс был начат 27 августа 1974. На сей раз, шифр Lucifer, представленный IBM и развитый в течение периода 1973—1974 сочли приемлемым, он был основан на более раннем алгоритме Хорста Фейстеля.

Часть подозрений в скрытой слабости S-перестановок была снята в 1990, когда были опубликованы результаты независимых исследований Эли Бихама (Eli Biham) и Ади Шамира (Adi Shamir) по дифференциальному криптоанализу — основному методу взлома блочных алгоритмов шифрования с симметричным ключом. S-блоки алгоритма DES оказались намного более устойчивыми к атакам, чем, если бы их выбрали случайно. Это означает, что такая техника анализа была известна АНБ ещё в 70-х годах XX века.

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

Схема шифрования алгоритма DES

Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.

Начальная перестановка

Исходный текст T (блок 64 бит)преобразуется c помощью начальной перестановки IP которая определяется таблицей 1:

По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока.

Аннотация: В этой лекции мы обсуждаем Стандарт шифрования данных (DES — DATA ENCRIPTION STANDARD) — современный блочный шифр с симметричными ключами. Наши основные цели для этой лекции: рассмотреть короткую историю DES; определить основную структуру DES; описать детали основных элементов DES; описать процесс генерации ключей для раундов; провести анализ DES. Особое внимание уделяется тому, как DES использует шифр Файстеля, чтобы достигнуть перемешивания и рассеивания на выходе из битов исходного текста к битам зашифрованного текста.

8.1. Введение

Стандарт шифрования данных (DES) — блочный шифр с симметричными ключами , разработан Национальным Институтом Стандартов и Технологии ( NIST – National Institute of Standards and Technology ).

История

В 1973 году NIST издал запрос для разработки предложения национальной криптографической системы с симметричными ключами .

Предложенная IBM модификация проекта, названная Lucifer, была принята как DES . DES были изданы в эскизном виде в Федеральном Регистре в марте 1975 года как Федеральный Стандарт Обработки Информации (FIPS – Federal Information Processing Standard).

После публикации эскиз строго критиковался по двум причинам. Первая: критиковалась сомнительно маленькая длина ключа (только 56 битов), что могло сделать шифр уязвимым к атаке "грубой силой". Вторая причина: критики были обеспокоены некоторым скрытым построением внутренней структуры DES .

DES был наконец издан как FIPS 46 в Федеральном Регистре в январе 1977 года. Однако FIPS объявил DES как стандарт для использования в неофициальных приложениях. DES был наиболее широко используемым блочным шифром с симметричными ключами , начиная с его публикации. Позже NIST предложил новый стандарт ( FIPS 46-3), который рекомендует использование тройного DES (трехкратно повторенный шифр DES ) для будущих приложений. Как мы увидим далее, в лекциях 9-10, предполагается, что более новый стандарт AES заменит DES .

Общие положения

Как показано на рис. 8.1. , DES — блочный шифр .

На стороне шифрования DES принимает 64 -битовый исходный текст и порождает 64 -битовый зашифрованный текст; на стороне дешифрования DES принимает 64 -битовый зашифрованный текст и порождает 64 -битовый исходный текст. На обеих сторонах для шифрования и дешифрования применяется один и тот же 56 -битовый ключ.

8.2. Структура DES

Рассмотрим сначала шифрование , а потом дешифрование . Процесс шифрования состоит из двух перестановок ( P -блоки) — они называются начальные и конечные перестановки, — и шестнадцати раундов Файстеля. Каждый раунд использует различные сгенерированные 48 -битовые ключи. Алгоритм генерации будет рассмотрен в этой лекции позднее. Рисунок 8.2 показывает элементы шифра DES на стороне шифрования.

Начальные и конечные перестановки

Рисунок 8.3 показывает начальные и конечные перестановки ( P -блоки). Каждая из перестановок принимает 64 -битовый вход и переставляет его элементы по заданному правилу. Мы показали только небольшое число входных портов и соответствующих выходных портов. Эти перестановки — прямые перестановки без ключей, которые инверсны друг другу. Например, в начальной перестановке 58 -й бит на входе переходит в первый бит на выходе. Аналогично, в конечной перестановке первый входной бит переходит в 58 -й бит на выходе. Другими словами, если между этими двумя перестановками не существует раунда, 58 -й бит, поступивший на вход устройства начальной перестановки, будет доставлен на 58 -й выход финальной перестановкой.

Правила перестановки для этого P -блока показаны в таблице 8.1. Таблицу можно представить как 64 -элементный массив. Заметим, что работу с таблицей мы обсуждали, значение каждого элемента определяет номер входного порта, а порядковый номер (индекс) элемента определяет номер выходного порта.

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

Найдите выход начального блока перестановки, когда на вход поступает шестнадцатеричная последовательность, такая как

Результат в шестнадцатеричном исчислении

Докажем, что начальные и финальные перестановки инверсны друг другу. Преобразуем полученную выходную последовательность во входную.

Единичные биты — 25 и 63 , другие биты равны нулю. В конечной перестановке 25 -й бит переходит в 64 -й, а 63 -й — в 15 -й. Результат

Начальные и конечные перестановки – это прямые P -блоки, которые инверсны друг другу. Они не имеют значения для криптографии DES.

Как работает DES? Эта статья покажет процесс шифрования DES шаг за шагом на простом примере. С момента появления DES многие алгоритмы шифрования (методы изменения данных) приняли DES-подобные методы. После того, как вы поймете преобразования в DES, вы, несомненно, сможете понять дверные проемы в этих современных алгоритмах шифрования.

Но перед этим давайте сначала разберемся с историей разработки DES.

Национальное бюро стандартов родило DES

В мае 1973 года, в течение срока полномочий Никсона, Национальное бюро стандартов США выпустило красный заголовочный файл, в котором запрашивался алгоритм шифрования для защиты данных во время передачи. Национальное бюро стандартов долго ждали, и никто не делал ставок. До 6 августа 1974 года, за три дня до ухода Никсона, IBM разработала набор кодов, разработанных его собственной семьей. Люцифер (Венера) Вещи. После оценки Агентством безопасности США 15 июля 1977 года в качестве стандарта шифрования данных DES был принят вариант LUCIFER.

DES был быстро принят нецифровыми СМИ, такими как шифрование сигналов в телефонных линиях. В те годы Международная организация специй IFF использовала DES для шифрования секретных рецептов, передаваемых по телефонным линиям. ( “With Data Encryption, Scents Are Safe at IFF,” Computerworld 14, No. 21, 95 (1980) ）

В то же время, как вторая по величине банковская индустрия, которая нуждается в шифровании после правительства, DES также широко используется в качестве стандарта, а Американский национальный институт стандартов ANSI разработал спецификации шифрования для всей банковской индустрии. Принят в 1980 году ANSI X3.92 Определяет применение алгоритма DES.

Некоторые предварительные примеры DES

DES обрабатывает биты или двоичные числа. Мы знаем, что каждые четыре бита составляют шестнадцатеричное число. DES шифрует набор 64-битной информации, которая представляет собой 16 шестнадцатеричных чисел. Для обеспечения шифрования DES также использует 64-битные длинные шифры. Однако каждые 8 бит в ключе игнорируются, что приводит к правильной длине ключа 56 бит в DES. Однако в любом случае один блок на 64 бита является вечной организацией DES.

Например, если наш открытый текст:

Выбранный ключ DES:

Мы можем получить зашифрованный текст:

Если вы используете тот же ключ DES для вышеуказанного зашифрованного текста

Если мы расшифруем его, мы получим исходный текст.

Этот пример прост и понятен, потому что наш открытый текст имеет длину 64 бита, а открытый текст может быть длиной до 64 бит. Но в большинстве случаев открытый текст в реальной жизни не является 64-битным (16 шестнадцатеричных цифр) Целые кратные.

Например, для этого текста:

Обычный текст в шестнадцатеричном формате:

Обратите внимание, что первые 72 шестнадцатеричных числа здесь представляют английский язык, но 0D представляет возврат каретки, 0A представляет перевод строки и конец текстового файла. Затем мы добавляем 0 в конец этого шестнадцатеричного кода, чтобы получить ровно 80 шестнадцатеричных цифр:

Если мы используем тот же ключ:

Зашифровав эти данные, мы получим следующий зашифрованный текст:

Это секретный код, который может быть передан или сохранен. Расшифруйте, чтобы получить оригинал Your lips are smoother than vaseline «(Представьте, насколько благодарной была бы Клинтон, если бы любовница Клинтона зашифровала неоднозначные данные.)

Как именно работает DES

DES - это алгоритм шифрования на основе блоков, который означает, что длина входных и выходных данных составляет 64 бита. Другими словами, DES производит максимум 2 64 Метод трансформации. Каждый 64-битный блок разделен на две 32-битные секции: левую половину L и правую половину R. (Эта сегментация выполняется только в определенных операциях.)

Например, возьмите открытый текст M как

Здесь M шестнадцатеричный, записывающий M в двоичном виде, мы получаем 64-битный блок:

Первая цифра М равна 0, а последняя цифра 1. Мы читаем слева направо.

DES использует 56-битный ключ для управления этим 64-битным блоком. Секретный ключ на самом деле хранится как 64 бита, но каждые 8 бит не используются (то есть первый 8, 16, 24, 32, 40, 48, 56 и 64-разрядные Не используются). Тем не менее, мы по-прежнему помечаем ключ как 64 бита от 1 до 64 бит в следующей операции. Тем не менее, вы можете увидеть, что упомянутые 8 будут игнорироваться при создании подраздела.

Например, возьмите шестнадцатеричный ключ K как

Мы можем получить его двоичную форму (1 - 0001, 3 - 0011. И так далее, и каждые восемь бит записываются в группу. Таким образом, последний бит каждой группы не используется.)

Шаг 1: Создайте 16 подразделов, каждый длиной 48 бит

Этот 64-битный ключ сначала преобразуется в соответствии с таблицей PC-1.

Поскольку первый элемент в таблице - 57, 57-й бит исходного ключа изменится на 1-й бит нового ключа K +. Аналогично, 49-й бит исходного ключа преобразуется во 2-й бит нового ключа . 4-й бит исходного ключа преобразуется в последний бит нового ключа. Обратите внимание, что только 56 бит исходного ключа будут вводить новый ключ, и в таблице выше всего 56 элементов.

Например, для оригинального ключа:

Мы получим новый 56-битный ключ:

Затем разделите этот ключ на левую и правую части,C₀ и D₀На каждой половине 28 цифр.

Например, для нового ключа мы получаем:

Для того же определенияC₀ и D₀ И теперь мы создаем 16 блоковC_n и D_n , 1 n , Каждая параC_n и D_nОба по предыдущей пареC_n-1 и D_n-1Иди сюда В частности, дляn = 1, 2, …, 16 В результате предыдущей смены используйте следующую таблицу для выполнения некоторых операций левой смены. Что такое левый сдвиг? Сдвиг влево означает сдвиг всех битов, кроме первого влево, и перемещение первого до последнего.

Это означает, например,C₃ and D₃ЗдесьC₂ and D₂Сдвинуты, в частности, на 2 левых смены;C₁₆ and D₁₆ Это изC₁₅ and D₁₅Получено за 1 левую смену. Во всех случаях сдвиг влево должен сдвигать все биты на один бит влево, так что положение бита после сдвига становится 2, 3,…, 28, 1 。

Например, для исходного подразделаC₀ and D₀И мы получаем:

Теперь мы можем получить новый ключ для n-го раундаK_n （ 1 n A. В частности, для каждой пары дочерних ключейC_nD_nВыполните преобразование в соответствии с таблицей ПК-2:

Каждая пара дочерних ключей имеет 56 бит, но ПК-2 использует только 48 из них.

Например, для комбинированного ключа первого раунда имеем:

После преобразования ПК-2 получаем:

Аналогично для других ключей:

Шаг 2: зашифруйте каждый 64-битный блок данных

Для незашифрованных данных M вычисляем начальное преобразование IP (Initial permutation). IP генерируется путем повторного преобразования каждого бита данных M. Процесс генерации определяется следующей таблицей. Индекс таблицы соответствует индексу новых данных. Значение х в таблице указывает, что новые данные поступают из x-го бита старых данных.

Например, выполняя начальное преобразование для блока М, мы получаем:

Следующим шагом является преобразование IP в 32-битную левую половину.L₀ 32-битная правая половинаR₀ 。

Например, для приведенного выше примера мы получаем:

Таким образом, мы получаем последний блок, которыйn = 16 L₁₆R₁₆, Этот процесс прост, мы берем правильные 32 бита результата предыдущей итерации как левые 32 бита текущей итерации. Для правых 32 битов текущей итерации, XOR это с выводом функции f предыдущей итерации.

Например, для n = 1 имеем:

Определите E как вывод функции E и запишите его в 8 групп по 6 бит в каждой. Эти биты генерируются путем выбора определенных битов ввода, и конкретный порядок выбора реализуется следующим образом:

Другими словамиE ( R_n-1 ) Первые три бита отR_n-132-е, 1-е и 2-е место.E ( R_n-1 2 бита в конце взяты изR_n-132-й и 1-й.

Например, учитываяR₀ Мы можем рассчитатьE ( R₀ ) ：

(Обратите внимание, что каждые 4 бита ввода расширяются до каждых 6 битов вывода.)

Затем в функции f мы берем выводE ( R_n-1 ) И секретный ключK_nВыполните операцию XOR:

Например,K₁ , E ( R₀ ) И у нас есть:

каждыйB_i Это 6-битный пакет, теперь мы рассчитываем

Среди нихS_i(B_i) Относится к выводу i-го блока S.

Для вычисления каждой функции SS1, S2,…, S8Возьмите 6-битный блок в качестве входного и выходного 4-битного блока. решитьS₁Форма выглядит следующим образом:

еслиS₁ Является ли функция, определенная в этой таблице, B является 6-битным блоком, то вычислениеS₁(B) Метод заключается в следующем: двоичное число в сочетании с первой и последней цифрами B определяет десятичное число от 0 до 3 (или от 00 до 11 двоичного числа). Пусть это число будет я. Среднее 4-значное двоичное число B представляет собой десятичное число от 0 до 15 (двоичное от 0000 до 1111). Пусть это число будет j. Просмотрите таблицу, чтобы найти число в строке i и столбце j, которое является числом от 0 до 15, и оно может Единственный 4-битный блок представлен. Этот блок является функциейS₁ Выход из входа BS₁(B), Например, для вводаB = 011011 Первая цифра 0, а последняя цифра 1, что определяет, что номер строки - 01, что равно 1 в десятичном виде. Средние 4 цифры - 1101, что означает 13 в десятичном виде, поэтому номер столбца - 13. Взглянув на первый ряд и 13-й столбец таблицы, мы получим число 5. Это определяет выход, 5 - двоичный 0101, поэтому выход - 0101. То естьS₁ (011011) = 0101 。

Аналогично, определите эти 8 функцийS₁,…,S₈Таблица выглядит так:

Пример: для первого раунда мы получаем выходные данные этих 8 S-блоков:

K₁ + E(R₀) = 011000 010001 011110 111010 100001 100110 010100 100111.

Последний шаг функции f - выполнить преобразование на выходе блока S для получения окончательного значения:

Преобразование P определяется следующей таблицей. P вводит 32-битные данные и генерирует 32-битный вывод, подписываясь:

Например, для вывода 8 S-блоков:

f = 0010 0011 0100 1010 1010 1001 1011 1011

= 1100 1100 0000 0000 1100 1100 1111 1111
+ 0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 0100 1010 0110 0101 0100 0100

На следующей итерации нашL₂ = R₁Это результат, который мы только что рассчитали. После этого мы должны рассчитатьR₂ = L₁ + f(R₁, K₂)Завершил 16 итераций. После 16-й итерации у нас есть блокL₁₆ and R₁₆, Затем мы меняем порядок двух блоков, чтобы получить 64-битный блок:

Затем выполните окончательное преобразование IP -1 Его определение показано в следующей таблице:

Например, если мы используем вышеуказанный метод, чтобы получить левый и правый два блока 16-го раунда:

Мы меняем два блока и затем выполняем окончательное преобразование:

Написано в шестнадцатеричном формате, чтобы получить:

Это открытый текстM = 0123456789ABCDEF Зашифрованная формаC = 85E813540F0AB405 。

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

Привет, %username%!
Многим известно, что стандартом по умолчанию в области симметричного шифрования долгое время считался алгоритм DES. Первая успешная атака на этот неубиваемый алгоритм была опубликована в 1993 году, спустя 16 лет после принятия его в качестве стандарта. Метод, который автор назвал линейным криптоанализом, при наличии 2 47 пар открытых/зашифрованных текстов, позволяет вскрыть секретный ключ шифра DES за 2 43 операций.
Под катом я попытаюсь кратко изложить основные моменты этой атаки.

Линейный криптоанализ

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

В первую очередь злоумышленник производит исследование шифра и находит т.н. статистический аналог, т.е. уравнение следующего вида, выполняющееся с вероятностью P ≠ 1/2 для произвольной пары открытый/закрытый текст и фиксированного ключа:
P_I1 ⊕ P_I2 ⊕… ⊕ P_Ia ⊕ C_I1 ⊕ C_I2 ⊕… ⊕ C_Ib = K_I1 ⊕ K_I2 ⊕… ⊕ K_Ic (1),
где P_n, C_n, K_n — n-ые биты текста, шифртекста и ключа.
После того как подобное уравнение будет найдено атакующий может восстановить 1 бит информации о ключе, используя следующий алгоритм

Алгоритм 1
Пусть T — количество текстов, для которых левая часть уравнения (1) равняется 0, тогда
Если T>N/2, где N — число известных открытых текстов.
Предположить, что K_I1 ⊕ K_I2 ⊕… ⊕ K_Ic = 0 (когда P>1/2) или 1 (когда P 1/2) или 0 (когда P 2 +(1-12/64) 2 .
С учетом того, что X(1) = PR и X(3) = CR получаем статистический аналог
СL[3, 8, 14, 25] ⊕ CR[17] ⊕ PL[3, 8, 14, 25] ⊕ PR[17] = K1[26] ⊕ K3[26] (5),
который выполняется с вероятностью (12/64) 2 +(1-12/64) 2 =0.7.
Описанный выше статистический аналог можно представить графически следующим образом (биты на рисунке пронумерованы справа налево и начиная с нуля):

Все биты в левой части уравнения известны атакующему, следовательно он может применить алгоритм 1 и узнать значение K1[17] ⊕ K3[17]. Покажем как с помощью данного статистического аналога можно вскрыть не 1, а 12 бит ключа шифрования K.

Атака на DES с известным открытым текстом

Приведем способ с помощью которого можно расширить атаку и получить сразу 6 бит подключа первого раунда.
Составляя уравнение (5) мы принимали во внимание тот факт, что нам неизвестно значение F1(PR, K1)[3, 8, 14, 25]. Поэтому мы использовали его статистический аналог K1[26] ⊕ PR[17].
Вернем вместо выражения K1[26] ⊕ PR[17] значение F1(PR, K1)[3, 8, 14, 25] и получим следующее уравнение:
СL[3, 8, 14, 25] ⊕ CR[17] ⊕ PL[3, 8, 14, 25] ⊕ F1(PR, K1)[3, 8, 14, 25] = K3[26] (6), которое будет выполняться с вероятностью 12/64. Вероятность изменилась так как мы оставили только статистический аналог из третьего раунда, все остальные значения фиксированы.

Выше мы уже определили, что на значение F1(PR, K1)[3, 8, 14, 25] оказывают влияние входные биты 5-го S-блока, а именно биты ключа K1[25~30] и биты блока PR[16~21]. Покажем каким образом обладая только набором открытых/закрытых текстов можно восстановить значение K1[25~30]. Для этого воспользуемся алгоритмом 2.

Алгоритм 2
Пусть N — количество известных перед атакой пар открытый/закрытый текст. Тогда для вскрытия ключа необходимо проделать следующие шаги.
For (i=0; i 44 пар текстов. Остальные 44 бита ключа вскрываются обычным перебором.

Читайте также: