28552

Симметричные методы шифрования DES

Доклад

Информатика, кибернетика и программирование

Функция перестановки одна и та же для каждого раунда но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа. Последовательность преобразований отдельного раунда Теперь рассмотрим последовательность преобразований используемую на каждом раунде. Создание подключей Ключ для отдельного раунда Ki состоит из 48 битов. На каждом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита в зависимости от номера раунда.

Русский

2013-08-20

63.46 KB

7 чел.

20 Симметричные методы шифрования DES

Принципы разработки

Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта (FIPS PUB 46).

DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом из них выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.


Рис. 4. Общая схема DES

Справа на рисунке показан способ, которым используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

Шифрование

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

Начальная перестановка и ее инверсия определяются стандартной таблицей. Если М - это произвольные 64 бита, то X = IP (M) - переставленные 64 бита. Если применить обратную функцию перестановки Y = IP-1 (X) = IP-1 (IP(M)), то получится первоначальная последовательность битов.

Последовательность преобразований отдельного раунда

Теперь рассмотрим последовательность преобразований, используемую на каждом раунде.


Рис. 5. I-ый раунд DES

64-битный входной блок проходит через 16 раундов, при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:

Li = Ri-1
R
i =Li-1 F (Ri-1, Ki)

Где обозначает операцию XOR.

Таким образом, выход левой половины Li равен входу правой половины Ri-1. Выход правой половины Ri является результатом применения операции XOR к Li-1 и функции F, зависящей от Ri-1 и Ki.

Рассмотрим функцию F более подробно.

Ri, которое подается на вход функции F, имеет длину 32 бита. Вначале Ri расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения

. . . efgh ijkl mnop . . .

то в результате расширения получается сообщение

. . . defghi hijklm lmnopq . . .

После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом Ki. Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.

Подстановка состоит из восьми S-boxes, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Значение в строке 1 и столбце 13 равно 5, т.е. выходом является 0101.

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

Создание подключей

Ключ для отдельного раунда Ki состоит из 48 битов. Ключи Ki получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таблицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каждом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являющееся входом функции F (Ri-1, Ki).

Дешифрование

Процесс дешифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, но ключи Ki используются в обратной последовательности. K16 используется на первом раунде, K1 используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет Li||Ri. Тогда соответствующий вход (16-i)-ого раунда дешифрования будет Ri||Li.

После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 был R16||L16. Выходом этой стадии является незашифрованный текст.

Проверим корректность процесса дешифрования. Возьмем зашифрованный текст и ключ и используем их в качестве входа в алгоритм. На первом шаге выполним начальную перестановку IP и получим 64-битное значение Ld0||Rd0. Известно, что IP и IP-1 взаимнообратны. Следовательно

Ld0||Rd0 = IP (зашифрованный текст)
Зашифрованный текст = IP
-1 (R16||L16)
L
d0||Rd0 = IP (IP-1(R16||L16)) = R16||L16 

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

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

L16 = R15
R
16 = L15 F (R15, K16)

При дешифровании:

Ld1 = Rd0 = L16 = R15
R
d1 = Ld0 F (Rd0, K16)
= R
16 F (Rd0, K16)
= (L
15 F (R15, K16)) F (R15, K16)

XOR имеет следующие свойства:

(A B) C = A (B C)
D
D =0
E
0 = E

Таким образом, мы имеем Ld1 = R15 и Rd1 = L15. Следовательно, выход первого раунда процесса дешифрования есть L15||R15, который является перестановкой входа 16-го раунда шифрования. Легко показать, что данное соответствие выполняется все 16 раундов. Мы можем описать этот процесс в общих терминах. Для i-ого раунда шифрующего алгоритма:

Li = Ri-1
R
i = Li-1 F (Ri-1, Ki)

Эти равенства можно записать по-другому:

Ri-1 = Li
L
i-1 = Ri F (Ri-1, Ki) = Ri F (Li, Ki)

Таким образом, мы описали входы i-ого раунда как функцию выходов.

Выход последней стадии процесса дешифрования есть R0||L0. Чтобы входом IP-1 стадии было L0||R0, необходимо поменять местами левую и правую части. Но

IP-1(L0||R0) = IP-1 (IP (незашифрованный текст)) = незашифрованный текст

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


 

А также другие работы, которые могут Вас заинтересовать

28776. Место Средневековья во всемирно-историческом процессе 28.35 KB
  Место Средневековья во всемирноисторическом процессе. Как видно в оценке средневековья присутствуют крайности. Поразному определяются и временные рамки Средневековья. К тому же внутри тысячелетнего периода Средневековья принято выделять три этапа: Раннее Средневековье – Vв.
28777. Формирование древнерусской государственности. Принятие христианства и его влияние на дальнейшее развитие страны 111.82 KB
  Это тем более очевидно что классовые общества и государства в Скандинавии сложились позже чем на Руси и серьезно повлиять на формирование НовгородскоКиевской Руси варяги не могли.Роль варяжского элемента в ранних государственных структурах Древней Руси 4. И пошли за море к варягам к руси. Сказали Руси чудь славяне кривичи и весь: Земля велика и обильна а порядка в ней нет.
28778. Эволюция древнерусской государственности в XI-XII вв. Международные связи древнерусских земель 25.18 KB
  Международные связи древнерусских земель. Ее причинами были: раздел территории на уделы между наследниками различных ветвей Дома Рюриковичей происходил в результате действовавшего принципа по старшинству к старшему в роду; постоянные княжеские усобицы в основе которых часто лежали политические амбиции тех или иных конкретных лиц не согласных с лествичным правом; рост крупного землевладения укреплявший чувство уверенности в своих силах у крупных владетелей обладавших значительными материальными ресурсами; натуральный характер...
28779. Борьба народов Руси с иноземными захватчиками в XII в. 66.86 KB
  Борьба народов Руси с иноземными захватчиками в XII в. XIII век в истории Руси это время вооруженного противостояния натиску с востока монголотатары и северозапада немцы шведы датчане. Встают два важных вопроса: почему русские княжества проявив героизм и мужество не смогли дать отпор завоевателям Какие последствия имело для Руси иго Ответ на первый вопрос очевиден: конечно имело значение военное превосходство монголотатар жесткая дисциплина отличная конница прекрасно налаженная разведка и др. Другие подчеркивают...
28780. Держава Чингисхана и монгольские завоевания. Иго и дискуссия о его роли в становлении Русского государства 29.73 KB
  Влияние монголотатарского ига на развитие русских земель. Упомянув кратко о зависимости русских князей от ханских ярлыков и сбора налогов Соловьев отмечал что нет причины признавать значительное влияние монголов на русскую внутреннею администрацию поскольку мы не видим никаких его следов. произошло не благодаря а вопреки Орде с точки зрения на монгольское иго в современной исторической науке: Традиционная история рассматривает его как бедствие для русских земель. Нашествие кочевников сопровождались массовыми разрушениями русских городов...
28781. Начало самодержавия в России. Внутренняя и внешняя политика Ивана IV. Альтернативы развития страны: «Избранная Рада » и опричнина 17.93 KB
  Внутренняя и внешняя политика Ивана IV. Царствование Ивана Грозного принято условно делить на две части сильно отличающиеся друг от друга по внутренней политике. Это знаменовало формирование на Руси нового типа традиционного общества – сословнопредставительной монархии Постоянным же совещательным органом при царе служила еще со времен Ивана III Боярская дума состоявшая из бояр. Первый Земский собор орган сословного представительства обеспечивающий связь центра и мест речь Ивана IV с лобного места: осуждение неправильного боярского...
28782. Смута: социальная катастрофа или время альтернатив? Причины и последствия смутного времени. Начало династии Романовых 18.58 KB
  Смутное время началось после смерти Федора Ивановича последнего царя из рода Рюрика 6 января 1598 г. Русская армия в это время готовилась выйти на помощь Смоленску который с сентября 1609 года был осаждён войсками польского короля Сигизмунда III. Поляки и запорожцы овладели городами северской земли; население Стародуба и Почепа полностью погибло во время вражеского штурма; Чернигов и НовгородСеверский сдались.
28783. Понятие модернизации, ее виды и циклы. Особенности петровской модернизации 14.86 KB
  Первым этапом такой модернизации в России стали реформы Петра I Великого Основными предпосылками реформ были: 1 тупик развития 2 необходимость выхода к морям для развития экономики. Именно с этой даты ведется отсчет истории России как великой державы. Превращение России в великую и морскую державу символизировало принятие Петром Великим наследственного императорского титула.
28784. Реформы Петра I. Каково соотношение модернизационных и традиционных начал в политике Петра 13.47 KB
  Каково соотношение модернизационных и традиционных начал в политике Петра Модернизация в России – догоняющая.