Современные симметричные криптосистемы. Стандарт шифрования данных DES. Алгоритм шифрования IDEA

2.4 Современные симметричные криптосистемы. Стандарт шифрования данных DES. Алгоритм шифрования IDEA 

1. Особенности современных симметричных криптосистем
2. Стандарт шифрования данных DES
3. Алгоритм шифрования IDEA

 

    1. Особенности современных симметричных криптосистем

    В шифрах необходимо использовать два общих принципа: рассеивание и перемешивание.

    Рассеивание представляет собой распространение влияния одного знака открытого текста на много знаков шифртекста, что позволяет скрыть статистические свойства открытого текста.

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

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

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

    2. Стандарт шифрования данных DES

    В 1977 году Национальное бюро Стандартов США (NBS) опубликовало стандарт шифрования данных Data Encryption Standard (DES), предназначенный для использования в государственных и правительственных учреждениях США для защиты от несанкционированного доступа важной, но несекретной информации. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 году был одобрен ANSI. С этого момента DES превращается в стандарт не только по названию (Data Encryption Standard), но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования/расшифрования информации в сетях передачи данных и на магнитных носителях. К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Программа DISKREET из пакета Norton Utilities, предназначенная для создания зашифрованных разделов на диске, использует именно алгоритм DES. "Собственный алгоритм шифрования" отличается от DES только числом итераций при шифровании.

    Основные  достоинства алгоритма DES:

• используется только один ключ длиной 56 бит;
• зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой, соответствующий стандарту DES;
• относительная простота алгоритма обеспечивает высокую скорость обработки информации;
• достаточно высокая стойкость алгоритма.

    DES осуществляет шифрование 64-битовых  блоков данных с помощью 56-битового  ключа. Расшифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности.

    Процесс шифрования заключается в начальной  перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).

    

    Рис.1. Обобщенная схема шифрования в алгоритме DES 

    Необходимо  сразу же отметить, что ВСЕ приводимые таблицы являются СТАНДАРТНЫМИ, а следовательно должны включаться в реализацию алгоритма DES в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис.2.

    

    Рис.2. Структура алгоритма шифрования DES 

    При описании алгоритма DES применены следующие  обозначения:

    L и R – последовательности битов (левая (left) и правая (right))

    Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с  помощью матрицы начальной перестановки IP (табл.1) следующим образом: бит 58 блока T становится битом 1, бит 50 - битом 2 и  т.д., что даст в результате: T(0) = IP(T).

    Полученная  последовательность битов T(0) разделяется  на две последовательности по 32 бита каждая: L(0) - левые или старшие  биты, R(0) - правые или младшие биты.

Таблица 1: Матрица начальной перестановки IP

58  50  42  34  26  18  10  02

60  52  44  36  28  20  12  04

62  54  46  38  30  22  14  06

64  56  48  40  32  24  16  08

57  49  41  33  25  17  09  01

59  51  43  35  27  19  11  03

61  53  45  37  29  21  13  05

63  55  47  39  31  23  15  07

    Затем выполняется шифрование, состоящее  из 16 итераций. Результат i-й итерации описывается следующими формулами:

     
где xor - операция ИСКЛЮЧАЮЩЕЕ ИЛИ.

    Правило для «исключающего или»: результат равен 0, если оба операнда равны; во всех остальных случаях результат равен 1.

    Функция f называется функцией шифрования. Ее аргументы - это 32-битовая последовательность R(i-1), полученная на (i-1)-ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.

    На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые  конкатенируют в 64-битовую последовательность R(16)L(16).

    Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP^-1 (табл.2).

Таблица 2: Матрица обратной перестановки IP^-1

40  08  48  16  56  24  64  32

39  07  47  15  55  23  63  31

38  06  46  14  54  22  62  30

37  05  45  13  53  21  61  29

36  04  44  12  52  20  60  28

35  03  43  11  51  19  59  27

34  02  42  10  50  18  58  26

33  01  41  09  49  17  57  25

    Матрицы IP^-1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP^-1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP^-1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

    Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP^-1, а затем над последовательностью бит R(16)L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.

    Итеративный процесс расшифрования может быть описан следующими формулами:

    На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0)R(0).

    Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки - исходная 64-битовая последовательность.

    Теперь  рассмотрим функцию шифрования f(R(i-1),K(i)). Схематически она показана на рис. 3.

 
Рис.3. Вычисление функции f(R(i-1), K(i))

    Для вычисления значения функции f используются следующие функции-матрицы:

• Е - расширение 32-битовой последовательности до 48-битовой,
• S1, S2, ... , S8 - преобразование 6-битового блока в 4-битовый,
• Р - перестановка бит в 32-битовой последовательности.

 

    Функция расширения Е определяется табл.3. В соответствии с этой таблицей первые 3 бита Е(R(i-1)) - это биты 32, 1 и 2, а последние - 31, 32 и 1.

Таблица 3:Функция расширения E

32  01  02  03  04  05

04  05  06  07  08  09

08  09  10  11  12  13

12  13  14  15  16  17

16  17  18  19  20  21

20  21  22  23  24  25

24  25  26  27  28  29

28  29  30  31  32  01

    Результат функции Е(R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48-битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). То есть:

E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .

    Функции S1, S2, ... , S8 определяются табл.4.

    К табл.4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 - номер столбца. Результатом Sj(B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.

    Например, если на вход матрицы S1 поступает 6-битовый блок B(1)=b1b2b3b4b5b6=100110, то 2-битовое число b1b6=10₍₂₎=2₍₁₀₎ указывает строку с номером 2 матрицы S1, а 4-битовое число b2b3b4b5=0011₍₂₎=3₍₁₀₎указывает столбец с номером 3 матрицы S1. Это означает, что в матрице S1 блок B(1)=100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8₍₁₀₎=1000₍₂₎.

    Применив  операцию выбора к каждому из 6-битовых  блоков B(1), B(2), ..., B(8), получаем 32-битовую  последовательность S1(B(1))S2(B(2))S3(B(3))...S8(B(8)).

    Наконец, для получения результата функции  шифрования надо переставить биты этой последовательности. Для этого применяется  функция перестановки P (табл.5). Во входной  последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 - битом 2 и т.д.

Таблица 5:Функция перестановки P

16  07  20  21

29  12  28  17

01  15  23  26

05  18  31  10

02  08  24  14

32  27  03  09

19  13  30  06

22  11  04  25

    Таким образом,

    f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))

    Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битовых ключей К(i), i=1...16. На каждой итерации используется новое значение ключа K(i), которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.

    Для удаления контрольных битов и  перестановки остальных используется функция G первоначальной подготовки ключа (табл.6).

Таблица 6 
Матрица G первоначальной подготовки ключа

57  49  41  33  25  17  09

01  58  50  42  34  26  18

10  02  59  51  43  35  27

19  11  03  60  52  44  36