Алгоритмы шифрования. Алгоритм DES. |
Автор megabax | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
04.08.2014 г. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Алгоритмы шифрования. Алгоритм DES.Как я уже говорил на прошлом уроке, алгоритм шифрования DES - это стандарт шифрования данных, который был разработан еще в 1974 году компанией IBM. Шифрование происходит на основе ключа длиной 64 бита, из которых 56 приходятся непосредственно на шифрование, а 8 бит - это системные разряды. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:
Разберем эти режимы более подробно. Режим электронной кодовой книги заключается в том, что каждый блок открытого текста заменяется блоком шифротекста. Еще этот метод называется методом простой замены. Недостаток ECB, в сравнении c другими режимами шифрования — сохранение статистических особенностей открытого текста. Например, если зашифровать таким методом картинку, то даже в зашифрованном виде сохраниться контру этой картинки. Рассмотрим это на примере. Исходная картинка (Источник: http://commons.wikimedia.org/wiki/File:Tux.jpg?uselang=ru): Картинка в зашифрованном виде (Источник http://commons.wikimedia.org/wiki/File:Tux_ecb.jpg?uselang=ru):
Картинка, зашифрованная другим методом шифрования (Источник http://commons.wikimedia.org/wiki/File:Tux_secure.jpg?uselang=ru): Режим сцепления блоков. Это более надежный метод, чем режим электронной кодовой книги. Его суть в том, что каждый блок открытого текста (кроме первого) побитово складывается по модулю 2 (операция XOR) с предыдущим результатом шифрования. Это усовершенствованный режим шифрования по сравнению с ECB: каждый блок открытого текста маскируется соответственно блоком шифротекста, полученном на предыдущем этапе. Однако и у него есть недостатки:
Режим обратной связи по шифротексту. Для шифрования следующего блока открытого текста он складывается по модулю 2 с перешифрованным (блочным шифром) результатом шифрования предыдущего блока. Криптостойкость этого метода определяется криптостойкостью используемого шифра. Фиксированные блоки открытого текста маскируются блоками шифротекста. Если в режиме СFВ с полноблочной обратной связью имеется два идентичных блока шифротекста, результат шифрования на следующем шаге будет тем же. Режим обратной связи по выходу. Режим (OFB)[5] обратной связи вывода превращает блочный шифр в синхронный шифрпоток: это генерирует ключевые блоки, которые являются результатом сложения с блоками открытого текста, чтобы получить зашифрованный текст. Так же, как с другими шифрами потока, зеркальное отражение в зашифрованном тексте производит зеркально отраженный бит в открытом тексте в том же самом местоположении. Это свойство позволяет многим кодам с исправлением ошибок функционировать как обычно, даже когда исправление ошибок применено перед кодированием. Шифр DES является блочным шифром. Входными данными для него служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований. Шифрование начинается с начальных перестановок, затем идет 16 циклов шифрование, после чего конечные перестановки. Начальные перестановки определяются следующей таблицей:
Иными словами, первые три бита после перестановок - это биты 58,50 и 42, а последние 23,15 и 7. Полученные таким образом данные участвую в 16-ти итерационных преобразованиях Фейстеля. Суть этих преобразований состоит в том, что мы разбиваем блок данных на две части по 32 бита: L(0) и R(0). Где L(0) - старшие биты, R0 - младшие. Весь блок мы обозначим T(0). Пусть T(i-1)=L(i-1)R(i-1) - это результат i-1 итерации, тогда результат i-ой итерации T(i)=L(i)R(i) определяется следующим образом: L(i)=R(i-1) R(i)=L(i) исключающее ИЛИ f((R(i-1),(k(i)) Где функция f - это функция шифрования. Ее аргументами являются 32-битный вектор R(i-1) и 48-битный ключ k(i), который является результатом преобразования 56- битного ключа k. Считается функция f по следующему алгоритму: 1. Вычисляется функция расширения E. 2. Производиться функция XOR (исключающее или) с ключом k. 3. Производиться преобразование S, состоящее из 8 преобразований S1, S2, S3, ... S8. 4. Перестановка P. И сейчас мы эти шаги рассмотрим более подробно. Функция расширения E является перестановкой согласно следующей таблице:
Таким образом, первые три бита вектора E(Ri-1) являются битами 32,1 и 2 вектора Ri-1. Стоит заметить, что некоторые биты дублируются. Полученный после перестановок вектор E(Ri-1) складывается по модулю 2 (применяется функция XOR) с ключами ki. Затем результат представляется в виде восьми последовательных блоков B1, B2, B3, ... B8. Каждый такой B блок является 6-битным блоком. Далее, каждый блок B трансформируется в блок B' с помощью преобразования S. Такое преобразование определяется следующей таблицей:
Предположим, что B3=101111 и мы ходим найти B'3. Первые и последние разряды являются двоичной записью числа a, лежит в диапазоне от 0 до 3. Средние 4 разряда представляют число b, лежащее в диапазоне от 0 до 15. Строки таблицы S3 нумеруются от 0 до 3, столбцы от 0 до 15. Пара чисел (а, b) определяет число, находящееся в пересечении строки а и столбца b. Двоичное представление этого числа дает B'3. В нашем случае двоичное значение числа a = 11. Десятичное 3. Для числа b двоичное значение 0111, десятичное 7. Таким образом, нам надо взять число на пересечении строки 3 и столбца 7. Это число 7. Далее идет перестановка P. Она задана следующей таблицей:
Согласно этой таблицы, первые четыре бита результатирующей функции P-преобразования - это 16,17,20,21. Ключи тоже получаются хитромудрым способом. Они делаются из исходного ключа k, путем разбиения его на 8 ключей ki. Восемь бит, находящихся в позициях 8, 16, 24, 32, 40, 48, 56, 64 убираются из ключа k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Далее делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64), согласно следующей таблице:
Эта перестановка определяется двумя блоками C0 и D0 по 28 бит в каждом. Первые три бита C0 это биты 59, 49 и 41 расширенного ключа. А первые три бита блока D0 - это биты 63,55,47 расширенного ключа. Ci, Di получаються из C(i-1), D(i-1) одним или двумя левыми циклическими сдвигами согласно таблице:
Ключи ki, i=1,...16 состоит из 48 бит, выбранных из битов 56-битного вектора CiDi согласно таблице ниже:
И завершает шифрование конечная перестановка IP-1. Она действует на T16 согласно следующей таблице
При расшифровке данных все действия выполняются в обратном порядке. В 16 циклах расшифрования, в отличие от шифрования c помощью прямого преобразования сетью Фейстеля, здесь используется обратное преобразование сетью Фейстеля. При этом производятся следующие шаги: R(i-1)=Li L(i-1)=Ri исключающее ИЛИ f(Li,ki) Ключи ki, функция f, перестановки IP и IP-1 точно такие же, как и в процессе шифрования.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее обновление ( 04.08.2014 г. ) |