Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.6.1. "Тройной" DES, CAST и IDEA

Как показано в табл. 14.9, PGP предлагает три блочных шифра для шифрования сообщения — "тройной" DES, CAST и IDEA. Все три шифра оперируют 64-битовыми блоками открытого и шифрованного текстов. Размер ключа "тройного" DES составляет 168 бит, в то время как CAST и IDEA используют ключи длиной 128 бит.

14.6.1.1. Описание "тройного" DES

Стандарт шифрования данных (Data Encryption Standard — DES), описанный в разделе 14.3.5, использовался с конца 1970-х годов. Однако у многих вызывала беспокойство его защищенность, так как в нем применялся ключ относительно малого размера (56 бит). При использовании "тройного" алгоритма DES, шифруемое сообщение трижды пропускается через алгоритм DES (вторая операция проводится в режиме дешифрования). Каждая операция производится с помощью разных 56-битовых ключей. Как показано на рис. 14.21, это равносильно использованию ключа длиной 168 бит.

Рис. 14.21. Шифрование/дешифрование с помощью "тройного" алгоритма DES

14.6.1.2. Описание CAST

CAST — это семейство блочных шифров, разработанных Адамсом (Adams) и Тевересом (Tavares) [19]. PGP 5.0 использует версию CAST, известную как CASTS или CAST-128. В этой версии размер блока составляет 64 бит, а длина ключа — 128 бит. Алгоритм CAST использует шесть S-блоков с 8-битовым входом и 32-битовым выходом. Для сравнения, DES применяет восемь S-блоков с 6-битовым входом и 4-битовым выходом. S-блоки в CAST-128 были созданы для обеспечения существенно нелинейных преобразований, которые делают этот алгоритм практически не поддающимся криптоанализу [11].

14.6.1.3. Описание IDEA

Международный алгоритм шифрования данных (International Data Encryption Algorithm — IDEA) представляет собой блочный шифр, разработанный Ксуэйя Лай (Xuejia Lai) и Джеймсом Мэсси (James Massey) [19]. Это 64-битовый итерационный блочный шифр (включающий восемь итераций или циклов) с 128-битовым ключом. Защищенность IDEA зависит от использования трех типов арифметических операций над 16-битовыми символами: сложение по модулю 216, умножение по модулю 216 + 1 и побитовое исключающее ИЛИ. Для итерационных операций шифрования и дешифрования используется 128-битовый ключ. Как показано в табл. 14.10, начальный ключ К0делится на восемь 16-битовых подключей Zx(R), где х — номер подключа цикла R. Шесть из этих подключей используются в цикле 1, а оставшиеся два — в цикле 2. Затем К0 циклически сдвигается на 25 бит влево, в результате чего образуется ключ К1, который, в свою очередь, делится на восемь подключей. Первые 4 из этих подключей используются в цикле 2, а последние четыре — в цикле 3. Процесс продолжается, как показано в табл. 14.10, в результате чего в общей сложности появляется 52 подключа.

Таблица 14.10. Образование подключей в алгоритме IDEA

128-битовый ключ

(делится на восемь 16-битовых подключей)

Строка битов, из которой выводятся ключи

Z11Z21Z31Z41Z51Z61Z12Z22

Z32Z42Z52Z62Z13Z23Z33Z43

Z53Z63Z14Z24Z34Z44Z54Z64

Z15Z25Z35Z45Z55Z65Z16Z26

Z36Z46Z56Z66Z17Z27Z37Z47

Z57Z67Z18Z28Z38Z48Z58Z68

Z1out Z2out Z3out Z4out

K0 = исходный 128-битовый ключ

К1 = сдвиг K0 на 25 бит

К0 = сдвиг K1 на 25 бит

К0= сдвиг К2на 25 бит

К0= сдвиг К3на 25 бит

К0= сдвиг К4 на 25 бит

Первые 64 бит К6, где К6 = сдвиг К5на 25 бит

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

Таблица 14.11. Эволюция подключа алгоритма IDEA

Цикл

Набор подключей шифрования

Набор ключей дешифрования

1

2

3

4

5

6

7

8

Выходное преобразование

Z11Z21Z31Z41Z51Z61

Z12Z22Z32Z42Z52Z62

Z13Z23Z33Z43Z53Z63

Z14Z24Z34Z44Z54Z64

Z15Z25Z35Z45Z55Z65

Z16Z26Z36Z46Z56Z66

Z17Z27Z37Z47Z57Z67

Z18Z28Z38Z48Z58Z68

Z1out Z2out Z3out Z4out

(Z1out)-1- Z2out -Z3out (Z4out)-1 Z58Z68

(Z18 )-1 -Z28 -Z38 (Z48 )-1Z57Z67

(Z17 )-1 -Z27 -Z37 (Z47 )-1Z55Z66

(Z16 )-1 -Z26 -Z36 (Z46 )-1Z55Z65

(Z15 )-1 -Z25 -Z35 (Z45 )-1Z55Z65

(Z14 )-1 -Z24 -Z34 (Z44 )-1Z54Z64

(Z13 )-1 -Z23 -Z33 (Z43 )-1Z53Z63

(Z12)-1 -Z22 -Z32 (Z42 )-1Z52Z62

(Z11 )-1 -Z21 -Z31 (Z41 )-1

Сообщение делится на 64-битовые блоки данных. Затем эти блоки делятся на четыре 16-битовых подблока: М1, М2, М3и М4. Последовательность таких четырех подблоков становится входом первого цикла алгоритма IDEA. Эти данные используются для всех восьми циклов. Как показано в табл. 14.11, в каждом цикле применяются разные множества из шести подключей. После завершения цикла второй и третий 16-битовые блоки данных переставляются. После завершения восьмого цикла четыре подблока дают окончательное выходное преобразование. Для упрощения записи в представлении Zx(R) в табл. 14.10 и 14.11 опущены круглые скобки.

Каждый цикл состоит из шагов, показанных в табл. 14.12. Окончательные значения, полученные на шагах 11-14, образуют выход цикла. Два внутренних 16-битовых подблока данных переставляются (за исключением последнего цикла), затем эти четыре подблока составляют вход следующего цикла. Этот метод в общей сложности включает 8 циклов. После восьмого цикла окончательное выходное преобразование имеет следующий вид.

1. М1Z1out (первый подключ выходного преобразования)

2. М2Z2out

3. М3Z3out

4. М4Z4out

Таблица 14.12. Шаги каждого цикла алгоритма IDEA

1. М1Z1(R).

2. М2Z2(R).

3. М3Z3(R).

4. М4Z4(R).

5. К результатам шагов (1) и (3) применяется операция XOR[3].

6. К результатам шагов (2) и (4) — операция XOR.

7. Результат шага (5) умножается на Z5(R).

8. Складываются результаты шагов (6) и (7).

9. Результат шага (8) умножается на Z6(R).

10. Складываются результаты шагов (7) и (9).

11. К результатам шагов (1) и (9) применяется операция XOR.

12. К результатам шагов (3) и (9) — операция XOR.

13. К результатам шагов (2) и (10) — операция XOR.

14. К результатам шагов (4) и (10) — операция XOR.

Пример 14.8. Первый цикл шифра ШЕЛ

Пусть сообщение (слово "HI") сначала нужно записать в шестнадцатеричной форме. Начнем с ASCII-кода, представленного на рис. 2.3, на котором бит 1 представляет собой самый младший разряд. Затем добавим равный нулю восьмой бит старшего разряда, который обычно используется для проверки четности, и выполним необходимое преобразование, взяв по четыре бита (порядок — от старшего разряда до младшего). Таким образом, буква "Н" в сообщении преобразуется в 0048, а буква "I" — в 0049. Для этого примера выберем 128-битовый ключ К0, выраженный восемью группами подключен из 4-разрядных шестнадцатеричных чисел: К0 = 0008 0007 0006 0005 0004 0003 0002 0001, где крайний правый подключ представляет самый младший разряд. Используя этот ключ и шифр IDEA, найдите выход цикла 1.

Решение

Сначала сообщение делится на 64-битовые блоки данных. Каждый из этих блоков затем делится на подблоки Mi, где i = 1, ..., 46, каждый из которых содержит 16-битовые или 4-значные шестнадцатеричные цифры. В этом примере длина сообщения "HI" равна всего 16 бит; следовательно, (используя шестнадцатеричное обозначение) М1 = 4849 и М =М3 =М4 = 0000. Сложение производится по модулю 216, а умножение - по модулю 216 + 1.128 - битовый ключ, определенный для первого цикла, делится на восемь 16-битовых подключен, начиная с младшей группы шестнадцатеричных кодов: Z1(1) = 0001, Z2(1) = 0002, Z3(1) = 0003, Z4(1) = 0004, Z5(1) = 0005, Z6(1) = 0006, Z1(2) = 0007 и Z2(2) = 0008.

Шаги, обозначенные в табл. 14.11, дают следующие результаты.

1. М1 Z1 = 48490001 = 4849.

2. М2 Z2 = 0000 + 0002 = 0002.

3. М3 Z3 = 0000 + 0003 = 0003.

4. М4 Z4 = 00000004 = 0000.

5. К результатам шагов (1) и (3) применяется операция XOR, в результате чего получится следующее: 4849 XOR 0003 = 484А.

0100 1000 0100 1001 (4849 из шестнадцатеричной системы переведено в двоичную)

XOR 0000 0000 0000 0011 (0003 из шестнадцатеричной системы переведено в двоичную)

_________________

0100 1000 0100 1010

Обратное преобразование в шестнадцатеричную систему дает следующее: 484А (где А — шестнадцатеричное обозначение двоичного числа 1010).

6. К результатам шагов (2) и (4) применяется операция XOR: 0002 XOR 0000 = 0002.

7. Результат шага (5) умножается на Z5: 484A0005 = 6971.

8. Результаты шагов (6) и (7) складываются: 0002 + 6971 = 6973.

9. Результат шага (8) умножается на Z6: 69730006 = 78В0.

10. Результаты шагов (7) и (9) складываются: 6971 + 78В0 = Е221.

11. К результатам шагов (1) и (9) применяется операция XOR: 4849 XOR 78B0 = 30F9.

12. К результатам шагов (3) и (9) применяется операция XOR: 0003 XOR 78B0 = 78В3.

13. К результатам шагов (2) и (10) применяется операция XOR: 0002 XOR E221 = Е223.

14. К результатам шагов (2) и (10) применяется операция XOR: 0000 XOR E221 = Е221.

Выход цикла 1 (результат шагов 11-14): 30F9 78ВЗ Е223 Е221. Перед началом цикла 2 переставляются два внутренних слова выхода цикла 1. Затем производится еще семь циклов и выполняется окончательное выходное преобразование.



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.