Курс лекций «Проблемы безопасности в информационных технологиях»



жүктеу 4.51 Mb.
бет10/44
Дата13.09.2017
өлшемі4.51 Mb.
түріКурс лекций
1   ...   6   7   8   9   10   11   12   13   ...   44

Алгоритм DES


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

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

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




Рис.5 Схема шифрования алгоритма DES
Более подробная схема шифрования по алгоритму DES приведена на рис.6:


Рис.6 Подробная схема шифрования алгоритма DES

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

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

Рис.7 I-ый раунд DES
Каждую итерацию можно описать следующим образом:
Li = Ri-1

Ri = Li-1 F(Ri-1, Ki)
Где обозначает операцию XOR.
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-битное значение обрабатывается с помощью перестановки Р-box, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде шифрования с большой вероятностью каждый бит обрабатывался другим 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 используется в последнем раунде:
Ri-1 = Li
Li-1 = Ri F(Li, Ki)
Схема расшифрования приведена на рис.8:


Рис.8 Схема расшифрования алгоритма DES
DES может использоваться в четырёх режимах:

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

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


  • Режим сцепления блоков (СВС – Cipher Block Chaining). Каждый очередной блок Ci i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста Mi+1. Вектор C0 — начальный вектор, он меняется (н-р, ежедневно) и хранится в секрете.


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


  • Режим обратной связи по шифротексту (CFB – Cipher Feed Back). В режиме CFB вырабатывается блочная «гамма» Z0, Z1,... Zi=DESk(Ci-1) Ci=MiZi. Начальный вектор C0 является синхропосылкой и предназначен для того, чтобы разные наборы данных шифровались по-разному с использованием одного и того же секретного ключа. Синхропосылка посылается получателю в открытом виде вместе с зашифрованным файлом.




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



  • Режим обратной связи по выходу (OFB – Output Feed Back). В режиме OFB вырабатывается блочная «гамма» Z0, Z1,... Zi=DESk(Zi-1) Ci = Mi Zi, i>=1



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

На сегодня DES является, пожалуй, наиболее изученным алгоритмом шифрования. Если в собственно алгоритме явных изъянов обнаружено не было, то самым слабым местом DES считается недостаточная длина ключа (всего 56 бит). В далёком уже 1998 году, используя специальные аппаратные средства, удалось взломать DES всего за три дня полным прямым перебором всех ключей. Современные компьютеры, даже без специализированной аппаратной поддержки, сегодня справляются с этой задачей ещё быстрее.

Ещё одной неприятностью алгоритма DES являются т.н. «слабые ключи». Слабыми ключами называется ключи k такие, что DESk(DESk(x)) = x, где x — 64-битный блок. Известны 4 слабых ключа, они приведены в таблице ниже по тексту. Для каждого слабого ключа существует 232 неподвижные точки, то есть, таких 64-битных блоков х, для которых DESk(x) = x:


Слабые ключи (hex)

C0

D0

0101-0101-0101-0101

[0]28

[0]28

FEFE-FEFE-FEFE-FEFE

[1]28

[1]28

1F1F-1F1F-0E0E-0E0E

[0]28

[1]28

E0E0-E0E0-F1F1-F1F1

[1]28

[0]28

[0]28– обозначает вектор из 28 нулевых битов

В алгоритме DES существуют также т.н. частично слабые ключи. Частично-слабые ключи – это такие пары ключей (k1, k2), что DESk1(DESk2(x)) = x. Существуют 6 частично-слабых пар ключей, они приведены в таблице ниже по тексту. Для каждого из 12 частично-слабых ключей существуют 232 «анти-неподвижные точки», то есть такие блоки х, что DESk(x) = x̃.



C0

D0

Пары частично слабых ключей

C0

D0

[01]14

[01]14

01FE-01FE-01FE-01FE,----FE01-FE01-FE01-FE01

[10]14

[10]14

[01]14

[01]14

1FE0-1FE0-1FE0-1FE0,----E0F1-E0F1-E0F1-E0F1

[10]14

[10]14

[01]14

[0]28

01E0-01E0-01F1-01F1,----E001-E001-F101-F101

[10]14

[0]28

[01]14

[1]28

1FFE-1FFE-0EFE-0EFE,----FE1F-FE1F-FE0E-FE0E

[0]28

[1]28

[0]28

[01]14

011F-011F-010E-010E,----1F01-1F01-0E01-0E01

[0]28

[10]14

[1]28

[01]14

E0FE-E0FE-F1FE-F1FE,----FEE0-FEE0-FEF1-FEF1

[1]28

[10]14

Чтобы увеличитьь криптостойкость DES, было предложено несколько вариантов: double DES (2DES), triple DES (3DES), DESX, G-DES. Методы 2DES и 3DES основаны на DES, но увеличивают длину ключей (2DES — 112 бит, 3DES — 168 бит) и поэтому увеличивается криптостойкость. Но двойной DES (2DES), основанный на повторном применении DES с двумя разными ключами, подвержен т.н. «атаке посредине» и его реальная сложность взлома примерно равна сложности взлома обычного DES, т.е. 256.

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


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

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

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

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


Шифрование: C = Ek3(E(Ek1(P)))

Расшифрование: E(Ek2(EC)))

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



  • k1,k2,k3 независимы.

  • k1,k2 независимы, и k1 = k3

  • k1=k2=k3.

Triple DES является достаточно распространённой и популярной альтернативой DES и используется при управлении ключами в стандартах ANSI X9.17 и ISO 8732 и в PEM (Privacy Enhanced Mail). Известных криптографических атак на тройной DES на сегодня не существует. Стоимость подбора ключа в тройном DES равна 2112 (56 + 56).





Достарыңызбен бөлісу:
1   ...   6   7   8   9   10   11   12   13   ...   44


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет