к какому типу преобразований относится алгоритм des

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

DES (Data Encryption Standard)

Содержание

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

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

17 марта 1975 года предложенный алгоритм DES был издан в Федеральном Регистре. В следующем году было проведено 2 открытых симпозиума по обсуждению этого стандарта, где подверглись жёсткой критике изменения, внесённые АНБ в алгоритм: уменьшение первоначальной длины ключа и S-блоки (блоки подстановки), критерии проектирования которых не раскрывались. АНБ подозревалось в сознательном ослаблении алгоритма с целью, чтобы АНБ могло легко просматривать зашифрованные сообщения. После чего сенатом США была проведена проверка действий АНБ, результатом которой стало заявление, опубликованное в 1978, в котором говорилось о том, что в процессе разработки DES АНБ убедило IBM, что уменьшенной длины ключа более чем достаточно для всех коммерческих приложений, использующих DES, косвенно помогало в разработке S-перестановок, а также, что окончательный алгоритм DES был лучшим, по их мнению, алгоритмом шифрования и был лишён статистической или математической слабости. Также было обнаружено, что АНБ никогда не вмешивалось в разработку этого алгоритма.

Часть подозрений в скрытой слабости 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 входного блока.

Получение 16 ключей по 48 бит из клача 56 бит

Описание функции F

В функции F находится вся не линейная часть, осуществляется она с помощью S и P преобразований. Функция представлена на рисунке 2. На вход поступает 32 бита, затем происходит функция расширения Е, которая описана в таблице.

Описание S преобразования

48 бит делится на подблоки по 6 бит (S-box). Функция S преобразует 6 бит в 4 бита. По таблице можно увидеть как определяется преобразование S.

Описание P преобразования

Перестановка P задана таблицей 6:

Конечная перестановка

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

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

Криптостойкость алгоритма DES

Нелинейность преобразований в DES средствами только S-блоков, в случае, если они имеют слабину, позволяет осуществлять контроль за шифрованной перепиской. Выбор S-блоков требует соблюдения нескольких условий:

Существуют 6 частично-слабых пар ключей, они приведены в таблице 9. Для каждого из 12 частично-слабых ключей существуют 2 32 <\displaystyle 2^<32>> «анти-постоянные точки», то есть такие блоки х, что
D E S k ( x ) = x

Для линейной и дифференциальной атак требуется достаточно большой объём памяти для сохранения выбранных (известных) открытых текстов до начала атак.

Увеличение криптостойкости алгоритма DES

Чтобы увеличивать криптостойкость DES появляются несколько вариантов: double DES (2DES), triple DES (3DES), DESX, G-DES.

Уязвимости алгоритма DES

Источник

Алгоритмы шифрования DES и AES

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

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

Шифрование

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

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

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

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

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

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

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

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

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

Источник

Программирование на C, C# и Java

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

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Алгоритм DES

Поговорим опять о шифровании. На этот раз рассмотрим алгоритм DES. DES – алгоритм блочного шифрования на основе сети Фейстеля, которая проходится 16 раз. DES может использоваться в нескольких режимах; мы рассмотрим режим “электронной кодовой книги” – ECB (electronic code book). Разработку будем вести на языке программирования C#.

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

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

Теперь же в основном используется 16-ти битная кодировка Юникода (UTF-16), поэтому, чтобы сохранить длину блока равную 8-ми символам, увеличим размер блока DES до 128 бит.

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

Итак, для того, чтобы зашифровать сообщение алгоритмом DES, необходимо выполнить следующую последовательность шагов:

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

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

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

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

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

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

На i-й итерации исходный блок делится пополам – левая часть обозначается L, правая R. Над R и ключом k_i вычисляется какая-либо выбранная логическая функция f (мы будем использовать XOR). Затем выполняется вычисление логической операции “исключающее или” над L и вычисленным ранее значением функции (L xor f). Старое значение R переносится в левую часть блока, а в правую часть заносится значение L xor f. И последняя операция раунда – нужно выполнить циклический сдвиг ключа: key_i+1 = key_i >> shiftKey (при расшифровке key_i-1 = key_i

Источник

Аппаратная реализация алгоритмов DES и TDES-EDE3

История

Алгоритм TDES (3DES, Tripple DES) был создан в 1978 году как улучшение алгоритма DES. По сравнению с последним улучшилась криптостойкость, но в три раза увеличилось время вычисления. Несмотря на то, что на сегодняшний день наиболее распространен алгоритм AES, который принят в качестве стандарта шифрования правительством США, алгоритм TDES широко используется. Например, даже сейчас его можно встретить в системных продуктах компании Microsoft.

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

Зачем я решил это сделать и описать

Действительно, эти алгоритмы уже очень глубоко исследован и не раз был описан и написан. Однако, когда я знакомился с этой темой и первый раз ради опыта решил реализовать этот алгоритм, я столкнулся с тремя проблемами. Во-первых, его аппаратная реализация ни разу не описывалась в русскоязычном пространстве, так что я решил заполнить этот пробел своей статьей. Во-вторых, большинство англоязычных статей на эту тему написаны для реализации на ПЛИС с использованием строенных ROM блоков памяти, а меня интересовала именно реализация «для кремния». И в-третьих большинство авторов приводят только часть исходного кода, но целиком исходников не так много. При этом написание этого модуля не является сложной логической задачей, но нужно безошибочно перенести все таблицы и преобразования в код. Так что отлавливать ошибки довольно рутинная и долгая задача.

Так же интересной задачей является написание тестовых векторов, которые при небольшом количестве смогли бы покрыть большую часть блока. Тестовые векторы для DES найти можно, например в [1], а вот для TDES-EDE3 мне найти ничего не удалось.

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

Начать знакомство с алгоритмом TDES необходимо с алгоритма DES. Приведу его краткое описание с нужными мне обозначениями.

DES является симметричным блочным алгоритмом с блоком размером 64 бит и ключом длинной 56 бит (либо расширенным ключом длинной 64 бит). Все таблицы преобразований и перестановок в удобном виде находятся в excel файле на моем гитхабе. Алгоритм шифрования представлен на рисунке 1 и состоит из следующих этапов:

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

16 раундов шифрования. Входной блок T₀ разбивается на старшую часть L₀ и R₀. Далее вычисления задаются рекуррентным соотношением:

Генерирование ключей k_i. В первую очередь исходный ключ расширяется добавлением бит в позиции 8, 16, 24, 32, 40, 48, 56, 64 таким образом, чтобы каждый байт содержал нечетное число единиц. Хотя на практике обычно все устроено наоборот. На вход подается уже расширенный 64-битный ключ, из которого потом выбираются значимые 56 бит. Это используется для обнаружения ошибок при передаче ключей, если такое необходимо. Далее, производится перестановка KI согласно таблице (она записана для 64-битного ключа), причем добавленные биты в перестановке не участвуют. Полученный блок делится на старшую и младшую части размером 28 бит. Для получения следующего ключа используется циклическая перестановка влево значений внутри каждой части на величину, зависящую от номера раунда: для первого, второго, девятого и шестнадцатого раундов происходит перестановка на два, для всех остальных на один.

Сам же ключ имеет длину 48 бит и выбирается из 56 битного вектора согласно преобразования KO.

Вычисление функции f. Аргументами функции f являются 32-битовый вектор R_(i-1) и 48-битный ключ k_i. Для вычисления функции f последовательно используются:

Функция расширения E. Расширяет 32-битовый вектор R_(i-1) до 48 бит согласно таблице преобразования E.

Xor с ключом.

Преобразование S. Полученный вектор делится на 8 блоков по 6 бит каждый. Каждый из восьми блоков преобразуется согласно S-таблицам. Пара старший и младший бит из блока определяют столбец, остальные четыре бита определяют строку.

Перестановка P. Производится перестановка согласно таблице P. В результате получается вектор длинной 32 бита.

Конечная перестановка OP. После 16 раундов шифрования производится конечная перестановка согласно таблице OP.

Расшифровка DES проводится в обратном порядке (рис. 2). В раундах используется обратное преобразование сетью Фейстеля.

Рис. 2. Схема расшифровки DES

Аппаратная реализация DES

Для написания быстрой аппаратной реализации буду использовать конвейер. За основу брал работу [2], однако генерирование ключа решил делать по-другому. Стоит обсудить стадии вычислений.

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

Самая долгая часть это раунд шифрования, а именно, вычисление функции f. Функция расширения не требует логических элементов в реализации, то же касается перестановки P. Так что потребуется время на xor с ключом, и, самое долгое, преобразование S.

Преобразование S буду реализовывать при помощи таблицы поиска.

Теперь можно обсудить конвейеризацию. Самый очевидный и практически удобный вариант разбить на стадии по каждому раунду (см. рис. 1). Так же удобно добавить входные триггеры, на рисунке это stage 0.

Перейду к блоку, который будет производить шифрование одного раунда. Это, во-первых, вычисление функции f, а во-вторых вычисление рекуррентного соотношения для R_i. На вход блока подается два вектора R_(i-1) и L_(i-1) длинны 32 бит и ключ k_i длинны 48 бит. На выходе блока формируется результат раунда R_i и L_i. Вычисление ключа сделаю в отдельном блоке. Весь код написан на языке System Verilog.

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

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

Так же понадобится реализация функции f_decrypt. Т.к. расшифровка производится обратной сетью Фейстеля, то по сути нужно просто поменять местами L_out и R_out в блоке f_encrypt. Так же придется изменить блок генерации ключей, т.к. теперь 16-й ключ нужен на первой стадии, 15-й на второй и т.д.

Все исходники загружены на мой гитхаб.

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

Имеет смысл проверить S-таблицы. Для этого я выпишу 512 = 64*8 тестовых вектора с ключом такие, что они покрывают все значения в S-таблице. Я использовал все ключи key = 64’h0, а тестовые векторы генерировал таким образом: выбираю S-таблицу, выбираю в ней ячейку, которую я хочу протестировать. Выписываю вектор, в котором нужные биты для для выбранной ячейки равны единицы, а все остальные равны нулю. Далее, я делаю обратную перестановку функции расширения E и полученный 32-битный вектор дополняю нулями до 64-битного. И, наконец, делаю обратную перестановку OP. Таким образом, каждый вектор последовательно пробегает каждую ячейку S-таблицы. С получившимися тестовыми векторами можно ознакомится в файле тестбенча на гитхабе.

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

Т.к. реализация у меня конвейеризированная, то в одном параллельном блоке по каждому отрицательному фронту я выставляю значения ключа и данных, а в другом параллельном блоке сначала жду 17 положительных фронтов (16 стадий вычисления и одна входная), а затем по каждому положительному фронту читаю значение и сравниваю с ожидаемым.

Теперь, у меня есть написанный и протестированный RTL модуля DES для шифрования и дешифровки.

Аппаратная реализация алгоритма TDES

Алгоритм TDES состоит из комбинации трех стадий шифрования и расшифровки. Наиболее распространен 3DES-EDE3 (encrypt-decrypt-encrypt) с тремя разными ключами. Таким образом, длина ключа 168 бит (расширенный 192 бит), размер блока все так же равен 64 бит.

Для реализации этого алгоритма нужно соединить блоки шифрования и расшифровки. При этом нужно добавить дополнительную цепочку триггеров для задержки ключа до следующих блоков на время исполнения 16 раундов. При таком соединении блоков будут последовательно происходить перестановки IP и OP, которые являются обратными. Однако при последующем синтезе эти перестановки будут оптимизированы и заменены прямыми соединениями. RTL блока находится в приложении.

Тестовые векторы строил следующим образом: взял тестовые векторы для DES шифратора, ключ из этих векторов есть ключ первой стадии TDES. Ключи второй и третьей стадии одинаковые и равны 64’hffffffffffffffff. Таким образом, я проверяю S-блоки первого шифрования TDES, т.к. далее идет расшифровка и шифрование с одинаковым ключом, то ожидаемый результат совпадает с результатом после первой стадии, а он же результат из тестов на DES. Таким же образом тестирую последнее шифрование TDES. Если сейчас все хорошо, то я считаю, что две части из трех работают правильно, а тогда я могу проверить S-блоки стадии расшифровки с теми же входными и ожидаемыми векторами, что и в DES и ключами равными 64’h0.

Таким образом получается 512*3 = 1536 тестовых вектора. Тестовые векторы для TDES находятся в файле тестбенча на гитхабе.

Я написал и протестировал RTL алгоритмов шифрования DES и TDES-EDE3. Так же я написал тестовые векторы для этих алгоритмов. Все исходники на гитхабе, надеюсь они помогут Вам в знакомстве или даже реализации этих алгоритмов. Спасибо за внимание!

Источник