Лабораторная работа № 4. Комбинированные шифры

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

DES (Data Encryption Standard, стандарт шифрования данных) - федеральный стандарт шифрования США в 1977-2001 годах [5]. Несмотря на то, что в настоящий момент федеральным стандартом шифрования США является Rijndael, рассмотрение DES позволяет понять основные принципы блочного шифрования.

В алгоритме, лежащем в основе DES, используются методы замены, перестановки и гаммирования (сложение по модулю 2).

Открытое сообщение разбивается на блоки длиной 64 бита. Если длина сообщения не кратна 64, оно дополняется справа недостающим количеством битов.

Данные шифруются ключом длиной 56 бит. На самом деле ключ имеет размер 64 бита, однако реально для выработки ключевых элементов используются только 56 из них. Самые младшие биты каждого байта ключа (8-ой, 16-ый, …, 64-ый) не попадают в ключевые элементы и служат исключительно для контроля четности. Требуется, чтобы сумма битов каждого байта ключа была нечетной.

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

- электронная кодовая книга ЕСВ (Electronic Code Book);

- сцепление блоков шифра СВС (Cipher Block Chaining);

- обратная связь по шифртексту СРВ (Cipher Feed Back);

- обратная связь по выходу OFB (Output Feed Back).

Режим DES-ЕСВ. Открытое сообщение разбивают на 64-битовые блоки. Каждый из них шифруют независимо с ис­пользованием одного и того же ключа шифрования.

Общая схема шифрования блока изображена на рис.16 [6].

1. Шифрование 64-битового блока данных T начинается с начальной перестановки битов IP (табл. 5). В таблице указывается новое положение соответствующего бита. Таким образом, при выполнении начальной перестановки 58-ый бит станет 1-ым, 50-ый – 2-ым, 42-ой – 3-им и т.д.

2. Результат перестановки Т* разделяется на две 32-битовые части H₀ и L₀, с которыми выполняются 16 раундов преобразования.

3. В каждом раунде i старшая половина H_i-1 блока модифицируется путем побитового прибавления к ней по модулю 2 (Å) результата вычисления функции шифрования f, зависящей от младшей половины блока L_i–1 и 48-битового ключевого элемента k_i. Ключевой элемент k_i вырабатывается из ключа шифрования. Между раундами старшая и младшая половины блока меняются местами. В последнем раунде происходит то же самое за исключением обмена значениями половинок блока.

4. Полублоки H₁₆ и L₁₆ объединяются в полный блок Т**, в котором выполняется конечная битовая перестановка IP^–1 (табл.6), обратная начальной. Результат последней операции и является выходным значением цикла шифрования – зашифрованным блоком T'.

Все перестановки в таблицах IP и IP^-1 подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путём подбора ключа.

Схема функции шифрования f приведена на рис.17.

1. На вход поступает 32-битовая половина шифруемого блока L_i-1 и 48-битовый ключевой элемент k_i.

2. L_i-1 разбивается на 8 тетрад по 4 бита. Каждая тетрада по циклическому закону дополняется крайними битами из соседних тетрад до 6-битного слова. Цикличность означает, что первый бит L_i-1 добавляется последним в последнее слово, а последний бит L_i-1 добавляется первым в первое слово. Далее выполняется объединение тетрад в 48-битный блок X. Например, L_i-1=0111 0110 1… …0 1101, тогда Х=101110 101101 … 011010.

3. Х побитово суммируется по модулю 2 (Å) с ключевым элементом k_i.

4. 48-битовый блок данных H разделяется на восемь 6-битовых элементов, обозначенных h₁, h₂, …, h₈.

5. Каждое из значений h_j преобразуется в новое 4-битовое значение t_j с помощью соответствующего узла замены S_j (табл.8). Если на вход S_j поступает блок h_j=b₁b₂b₃b₄b₅b₆, то двухбитовое число b₁b₆ указывает номер строки матрицы, а четырёхбитовое число b₂b₃b₄b₅ - номер столбца в таблице узлов замен. В результате применения узла замены S_i к блоку h_i получается число (от 0 до 15), которое преобразуется в t_i. Например, в узел замены S₃ поступает h₃=101011. Тогда, номер строки равен 3 (b₁b₆=11), номер столбца – 5 (b₂b₃b₄b₅=0101), t₃=1001 (9).

6. Полученные восемь элементов t_i вновь объединяются в 32-битовый блок H’.

7. В H’ выполняется перестановка битов P (табл.7). Результат последней операции и является выходным значением функции шифрования L_i-1^’.

 

Таблица 7

Перестановка P

 

Таблица 8

Узлы замен

Номер столбца

Номер строки

S1

S2

S3

S4

S5

S6

S7

S8

 

Ключевые элементы вырабатываются из ключа с использованием сдвигов и битовых выборок-перестановок. Таким образом, ключевые элементы состоят исключительно из битов исходного ключа, «перетасованных» в различном порядке. Схема выработки ключевых элементов показана на рис.18.

1. Выработка ключевых элементов из ключа K начинается со входной выборки-перестановки битов PC₁ (табл.9), которая отбирает 56 из 64 битов ключа и располагает их в другом порядке.

2. Результат выборки-перестановки K* разделяется на две 28-битовые части: старшую С₀ и младшую D₀.

3. 16 раз выполняется процедура.

3а. В зависимости от номера итерации обе части циклически сдвигаются на 1 или 2 бита влево.

Таблица 10

Циклический сдвиг

Номер итерации

Сдвиг (бит)

 

3б. Из полученных блоков с помощью выходной битовой выборки-перестановки PC₂ отбираются первые 48 битов, которые и формируют очередной ключевой элемент.

Таблица 11

Перестановка PС₂

 

Алгоритмы шифрования и расшифрования DES-ECB в общем виде выражаются следующими схемами

 

T’ = DES(T) = IP(T) ® H₀ Å f(L₀, k₁), L₀ ® …

® H₁₅ Å f(L₁₅, k₁₆), L₁₅ ® IP^-1(2³²*L₁₆+ H₁₆), (8)

 

T = DES^-1(T’) = IP(T’) ® H₀ Å f(L₀, k₁₆), L₀ ® …

® H₁₅ Å f(L₁₅, k₁), L₁₅ ® IP^-1(2³²*L₁₆+ H₁₆). (9)

 

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

В 1993 г. Майкл Винер спроектировал машину стоимостью 1 млн. долларов, выполняющую лобовое вскрытие DES за 3.5 часа. В 1998 г. Electronic Frontier Foundation построена ЭВМ стоимостью 250 тыс. долларов, способная определять ключ DES в среднем за 112 часов. По неподтвержденным данным, Агентство национальной безопасности США уже в 1996 г. могло вскрывать ключ DES за 3-15 мин. с помощью устройства стоимостью 50000 долларов.

⇐ Предыдущая1234Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: