Алгоритм шифрования des кратко

Обновлено: 05.07.2024

Аннотация: Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard. Эта система первой получила статус государственного стандарта в области шифрования данных. И хотя старый американский стандарт DES в настоящее время утратил свой официальный статус, этот алгоритм все же заслуживает внимания при изучении криптографии. Кроме того в этой лекции объясняется, что такое "двухкратный DES", атака "встреча посередине" и способы ее устранения. В этой же лекции кратко рассматривается новый стандарт США на блочный шифр – алгоритм Rijndael.

Цель лекции: познакомить студента с основными сведениями об алгоритме шифрования DES .

Основные сведения

Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard. Эта система первой получила статус государственного стандарта в области шифрования данных. Она разработана специалистами фирмы IBM и вступила в действие в США 1977 году. Алгоритм DES широко использовался при хранении и передаче данных между различными вычислительными системами; в почтовых системах, в электронных системах чертежей и при электронном обмене коммерческой информацией . Стандарт DES реализовывался как программно, так и аппаратно. Предприятиями разных стран был налажен массовый выпуск цифровых устройств, использующих DES для шифрования данных. Все устройства проходили обязательную сертификацию на соответствие стандарту.

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

Длина ключа в алгоритме DES составляет 56 бит . Именно с этим фактом связана основная полемика относительно способности DES противостоять различным атакам. Как известно, любой блочный шифр с закрытым ключом можно взломать, перебрав все возможные комбинации ключей. При длине ключа 56 бит возможны 2 56 разных ключей. Если компьютер перебирает за одну секунду 1 000 000 ключей (что примерно равно 2 20 ), то на перебор всех 2 56 ключей потребуется 2 36 секунд или чуть более двух тысяч лет, что, конечно, является неприемлемым для злоумышленников.

Однако возможны более дорогие и быстрые вычислительные системы, чем персональный компьютер . Например, если иметь возможность объединить для проведения параллельных вычислений миллион процессоров, то максимальное время подбора ключа сокращается примерно до 18 часов. Это время не слишком велико, и криптоаналитик, оснащенный подобной дорогой техникой, вполне может выполнить вскрытие данных, зашифрованных DES за приемлемое для себя время.

Вместе с этим можно отметить, что систему DES вполне можно использовать в небольших и средних приложениях для шифрования данных, имеющих небольшую ценность. Для шифрования данных государственной важности или имеющих значительную коммерческую стоимость система DES в настоящее время, конечно, не должна использоваться. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блочный шифр , названный AES (Advanced Encryption Standard), в основу которого был положен шифр Rijndael, разработанный бельгийскими специалистами. Этот шифр рассматривается в конце лекции.

Основные параметры DES: размер блока 64 бита, длина ключа 56 бит , количество раундов – 16. DES является классической сетью Фейштеля с двумя ветвями. Алгоритм преобразует за несколько раундов 64-битный входной блок данных в 64-битный выходной блок. Стандарт DES построен на комбинированном использовании перестановки, замены и гаммирования. Шифруемые данные должны быть представлены в двоичном виде.

Шифрование

Общая структура DES представлена на рис. 4.1. Процесс шифрования каждого 64-битового блока исходных данных можно разделить на три этапа:

начальная подготовка блока данных;
16 раундов "основного цикла";
конечная обработка блока данных.

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

На следующем (основном) этапе блок делится на две части (ветви) по 32 бита каждая. Правая ветвь преобразуется с использованием некоторой функции F и соответствующего частичного ключа, получаемого из основного ключа шифрования по специальному алгоритму преобразования ключей. Затем производится обмен данными между левой и правой ветвями блока. Это повторяется в цикле 16 раз.

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

Рассмотрим более подробно все этапы криптографического преобразования по стандарту DES.

Далее выполняется основной цикл преобразования, организованный по сети Фейштеля и состоящий из 16 одинаковых раундов. При этом в каждом раунде ( рис. 4.2) получается промежуточное 64-битное значение , которое затем обрабатывается в следующем раунде.

Левая и правая ветви каждого промежуточного значения обрабатываются как отдельные 32-битные значения, обозначенные L и R .

Вначале правая часть блока R_i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Эта операция приводит размер правой половины в соответствие с размером ключа для выполнения операции XOR . Кроме того, за счет выполнения этой операции быстрее возрастает зависимость всех битов результата от битов исходных данных и ключа (это называется "лавинным эффектом"). Чем сильнее проявляется лавинный эффект при использовании того или иного алгоритма шифрования, тем лучше.

Далее полученное 32-битовое значение обрабатывается с помощью перестановки Р (от англ. Permutation – перестановка ), которая не зависит от используемого ключа. Целью перестановки является максимальное переупорядочивание битов такое, чтобы в следующем раунде шифрования каждый бит с большой вероятностью обрабатывался другим S-блоком.

И, наконец, результат перестановки объединяется с помощью операции XOR с левой половиной первоначального 64-битового блока данных. Затем левая и правая половины меняются местами, и начинается следующий раунд.

После шестнадцати раундов шифрования выполняется конечная перестановка результата. Эта перестановка инверсна (обратна) начальной перестановке.

Режим шифрования электронной кодовой книги (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 входного блока.

Привет, %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 бита ключа вскрываются обычным перебором.

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

Алгоритм DES

Алгоритм DES. Описание

Алгоритм DES. Шаги

Расшифровка DES производится по аналогии. Используется обратное преобразование сетью Фейстеля.

Алгоритм DES. Сеть Фейстеля

Сеть Фейстеля используется в алгоритме DES для зашифровывания (прямое преобразование сетью) и расшифровывания (обратное преобразование). Эти преобразования изображены на рисунках 1 и 2 соответственно.

Рисунок 1. Прямое преобразование сетью Фейстеля

Рисунок 2. Обратное преобразование сетью Фейстеля

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

Как работает 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 итерациях позиции левого и правого подразделов меняются местами.

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