Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Новомосковский институт (филиал)

Государственного образовательного учреждения высшего профессионального образования

«Российский химико-технологический университет имени Д.И. Менделеева»

Кафедра: ВТИТ

РЕФЕРАТ

по курсу «МиСЗКИ»

«Американский стандарт шифрования DES»

Студент: Карпунин Р.А.

Преподаватель: Федоровская Т.М.

Новомосковск 2010

Содержание

• Введение
• 1. История
• 2. Блочный шифр
• 3. Преобразования Сетью Фейстеля
• 4. Схема шифрования алгоритма DES
• 4.1 Начальная перестановка
• 4.2 Циклы шифрования
• 4.3 Основная функция шифрования (функция Фейстеля)
• 4.4 Генерирование ключей k_i
• 4.5 Конечная перестановка
• 5. Схема расшифрования
• 6. Режимы использования DES
• 7. Криптостойкость алгоритма DES
• 7.1 Слабые ключи
• 7.2 Частично слабые ключи
• 7.3 Известные атаки на DES
• 8. Увеличение криптостойкости DES
• 9. Применение
• Литература


Введение

DES (DataEncryptionStandard) -- симметричный алгоритм шифрования, разработанный фирмой IBM и утвержденный правительством США в 1977 году как официальный стандарт (FIPS 46-3). DES имеет блоки по 64 бита и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

· режим электронной кодовой книги (ECB -- ElectronicCodeBook),

· режим сцепления блоков (СВС -- CipherBlockChaining),

· режим обратной связи по шифротексту (CFB -- CipherFeedBack),

· режим обратной связи по выходу (OFB -- OutputFeedBack).

1. История

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

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

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

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

2. Блочный шифр

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

Базовые преобразования:

· Сложное преобразование на одной локальной части блока;

· Простое преобразование между частями блока.

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

3. Преобразования Сетью Фейстеля

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

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

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

Схема шифрования алгоритма DES указана на Рис.3

Исходный текст -- блок 64 бит.

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

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

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

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

Таблица 1 Начальная перестановка IP

Полученный после начальной перестановки 64-битовый блок IP(T) участвует в 16-циклах преобразования Фейстеля.

-- 16 циклов преобразования Фейстеля:

Разбить IP(T) на две части L₀,R₀, где L₀,R₀ -- соответственно 32 старших битов и 32 младших битов блокаT₀ IP(T)= L₀R₀

Пусть T_{i ? 1} = L_{i ? 1}R_{i ? 1} результат (i-1) итерации, тогда результат i-ой итерации T_i = L_iR_i определяется:

L_i = R_{i ? 1}

Левая половина L_i равна правой половине предыдущего вектора L_{i ? 1}R_{i ? 1}. А правая половина R_i -- это битовое сложение L_{i ? 1} и f(R_{i ? 1},k_i) по модулю 2. В 16-циклах преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

4.3 Основная функция шифрования (функция Фейстеля)

Аргументами функции f являются 32-битовый вектор R_{i ? 1} и 48-битовый ключ ki, которые являются результатом преобразования 56-битового исходного ключа шифра k.

Для вычисления функции f используются функция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.

Функция Е расширяет 32-битовый вектор R_{i ? 1} до 48-битового вектора E(R_{i ? 1}) путём дублирования некоторых битов из R_{i ? 1}; при этом порядок битов вектора E(R_{i ? 1}) указан в таблице 2.

Таблица 2Функция расширения E

4.4 Генерирование ключей ki

Ключи k_i получаются из начального ключа k (64 бит = 8 байтов или 8 символов в ASCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определена как в таблице 3.

Таблица 3

Эта перестановка определяется двумя блоками C0 и D0 по 28 бит каждый. Первые 3 бита C0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D0 есть биты 63, 55, 47 расширенного ключа. Ci,Dii=1,2,3…получаются из Ci ? 1,Di ? 1 одним или двумя левыми циклическими сдвигами согласно таблице 4.

Таблица 4

6. Режимы использования DES

DES может использоваться в четырёх режимах.

1. Режим электронной кодовой книги (ECB -- ElectronicCodeBook): обычное использование DES как блочного шифра. Шифруемый текст разбивается на блоки, при этом, каждый блок шифруется отдельно, не взаимодействуя с другими блоками (см. Рис.6).

Рис. 6Режим электронной кодовой книги -- ECB

2. Режим сцепления блоков (СВС -- CipherBlockChaining) (см. Рис.7). Каждый очередной блок C_i i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста M_{i + 1}. Вектор C₀ -- начальный вектор, он меняется ежедневно и хранится в секрете.

Рис. 7Режим сцепления блоков -- СВС

3. Режим обратной связи по шифротексту (англ. CipherFeedBack) (см. Рис.8). В режиме CFB вырабатывается блочная «гамма» Z₀,Z₁,...Z_i = DES_k(C_{i ? 1}) . Начальный вектор C₀ является синхропосылкой и предназначен для того, чтобы разные наборы данных шифровались по-разному с использованием одного и того же секретного ключа. Синхропосылка посылается получателю в открытом виде вместе с зашифрованным файлом.

Рис. 8Режим обратной связи по шифротексту -- CFB

4. Режим обратной связи по выходу (OFB -- OutputFeedBack) (см. Рис.9). В режиме OFB вырабатывается блочная «гамма» Z₀,Z₁,... , i>=1

Рис. 9Режим обратной связи по выходу -- OFB

Достоинства и недостатки режимов:

§ Режим ECB прост в реализации, но возможно проведение криптоанализа по словарю.

§ В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста C_i приводит к искажению после расшифрования только соответствующего открытого блока M_i , поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.

§ В режимах CBC и CFB искажение при передаче одного блока шифрованного текстаСі приводит к искажению на приёмнике не более двух блоков открытого текста M_i,M_{i + 1.}Изменение M_i приводит к изменению всех остальных блоковM_{i + 1},M_{i + 2}… Это свойство используется для выработки кода аутентификации сообщения.

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

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

· Каждая строка каждого блока должна быть перестановкой множества {0, 1, 2, …, 15}

· S-блоки не должны являться линейной или афинной функцией своих аргументов.

· Изменение одного бита на входе S-блока должно приводить к изменению, по крайней мере, двух битов на выходе.

· Для каждого S-блока и любого аргумента х значение S(x) и должны различаться, по крайней мере, двумя битами.

Из-за небольшого числа возможных ключей (всего 256), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время. В 1998 году ElectronicFrontierFoundation используя специальный компьютер DES-Cracker, удалось взломать DES за 3 дня.

7.1 Слабые ключи

Слабыми ключами называется ключи k такие, что DES_k(DES_k(x)) = x, где x -- 64-битный блок.

Известны 4 слабых ключа, они приведены в таблице 7. Для каждого слабого ключа существует 2³² неподвижные точки, то есть, таких 64-битных блоков х, для которых DES_k(x) = x.

Таблица 7DES-Слабые ключи

Таблица 9Известные атаки на DES

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

§ Методы 2DES и 3DES основаны на DES, но увеличивают длину ключей (2DES -- 112 бит, 3DES -- 168 бит) и поэтому увеличивается криптостойкость.

§ Схема 3DES имеет вид DES(k₃,DES(k₂,DES(k₁,M))), где k₁,k₂,k₃ ключи для каждого шифра DES. Это вариант известен как в ЕЕЕ так как три DES операции являются шифрованием. Существует 3 типа алгоритма 3DES:

§ DES-EEE3: Шифруется три раза с 3 разными ключами.

§ DES-EDE3: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами.

§ DES-EEE2 и DES-EDE2: Как и предыдущие, за исключением того, что первая и третья операции используют одинаковый ключ.

Самый популярный тип при использовании 3DES -- это DES-EDE3, для него алгоритм выглядит так:

Зашифрование: .

Расшифрование:

При выполнении алгоритма 3DES ключи могут выбрать так:

§ k₁,k₂,k₃ независимы.

§ k₁,k₂ независимы, а k₁ = k₃

§ k₁ = k₂ = k₃.

§ Метод DESX создан Рональдом Ривестом и формально продемонстрированаKillian и Rogaway. Этод метод -- усиленный вариант DES, поддерживаемый инструментариемRSA Security. DESX отличается от DES тем, что каждый бит входного открытого текста DESX логически суммируется по модулью 2 с 64 битами дополнительного ключа, а затем шифруется по алгоритму DES. Каждый бит результата также логически суммируется по модулью 2 с другими 64 битами ключа. Главной причиной использования DESX является простой в вычислительном смысле способ значительного повысить стойкость DES к атакам полного перебора ключа.

§ Метод G-DES разработан Schaumuller-Bichl для повышения производительности DES на основе увеличения размером шфрованного блока. Заявлялось, что G-DES защищен так же как и DES. Однако,Biham и Shamir показали, что G-DES с рекомендуемыми параметрами легко взламывается, а при любых изменениях параметров шифр становится ещё менее защищен чем DES.

§ Ещё другой вариант DES использует независимыесуб-ключи. Различно от алгоритма DES, в котором на основе 56-битного секретного ключа пользователя алгоритм DES получает шестнадцать 48-битных суб-ключей для использования в каждом из 16 раундов, в этом варианте использует 768-битного ключа (разделенного на 16 48-битных подключей) вместо 16 зависимых 48-битных ключей, создаваемых по ключевому графику алгоритма DES. Хотя очевидно, что использование независимыхсуб-ключей значительно усложнит полный поиск ключа, но стойкость к атаке дифференциальным или линейным криптоанализом не намного превысит стойкость обычного DES. По оценке Biham для дифференциального криптоанализа DES с независимыми подключами требуется 2⁶¹ выбранных открытых текстов, в то время как для линейного криптоанализа требуется 2⁶⁰ известных открытых текстов.

9. Применение

DES был национальным стандартом США в 1977--1980 гг., но в настоящее время DES используется (с ключом длины 56 бит) только для устаревших систем, чаще всего используют его более криптоустойчивый вид (3DES, 2DES). 3DES является простой эффективной заменой DES, и сейчас он рассмотрен как стандарт. В ближайшее время DES и Triple DES будут заменены алгоритмом AES (AdvancedEncryptionStandard -- Расширенный Стандарт Шифрования). Алгоритм DES широко применяется для защиты финансовой информации: так, модуль THALES (Racal) HSM RG7000 полностью поддерживает операции TripleDES для эмиссии и обработки кредитных карт VISA, EuroPay и проч. Канальные шифраторы THALES (Racal) DataDryptor 2000 используют TripleDES для прозрачного шифрования потоков информации. Также алгогритм DES используется во многих других устройствах и решениях THALES-eSECURITY.

Литература

1. А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин Основы криптографии;

2. Menezes, PvanOorschot, S. Vanstone Handbook of Applied Cruptography;

3. Семенов Ю.А. Алгоритм DES;

4. Query for DES (http://everything2.com/title/DES).

Размещено на Allbest.ru