Современные симметричные криптосистемы. Стандарт шифрования данных 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

--------------------------

63  55  47  39  31  23  15

07  62  54  46  38  30  22

14  06  61  53  45  37  29

21  13  05  28  20  12  04

    Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49, ..., 44, 36 ключа K, а D(0) будет состоять из битов 63, 55, ..., 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1...16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в табл.7.

    Полученное  значение вновь "перемешивается" в соответствии с матрицей H (табл.8).

Таблица 8:Матрица H завершающей обработки ключа

14  17  11  24  01  05

03  28  15  06  21  10

23  19  12  04  26  08

16  07  27  20  13  02

41  52  31  37  47  55

30  40  51  45  33  48

44  49  39  56  34  53

46  42  50  36  29  32

    Ключ K(i) будет состоять из битов 14, 17, ..., 29, 32 последовательности C(i)D(i). Таким образом:

K(i) = H(C(i)D(i))

    Блок-схема  алгоритма вычисления ключа приведена  на рис.4.

 
Рис.4. Блок-схема алгоритма вычисления ключа K(i) 

    Восстановление  исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ K(15), затем - K(14) и так далее.

    Режимы  работы алгоритма DES

    Чтобы воспользоваться алгоритмом DES для решения разнообразных криптографических задач, разработаны четыре рабочих режима:

• электронная кодовая книга (Electronic Codebook ) - ECB;
• сцепление блоков шифра (Cipher Block Chaining) - CBC;
• обратная связь по шифртексту (Cipher Feedback) - CFB;
• обратная связь по выходу (Output Feedback) - OFB.

    DES-ECB

    В этом режиме исходный файл M разбивается  на 64-битовые блоки (по 8 байтов): M = M(1)M(2)...M(n). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования (рис.5). Основное достоинство этого алгоритма - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков.

    

 
Рис.5. Работа алгоритма DES в режиме ECB

    DES-CBC

    В этом режиме исходный файл M также, как и в режиме ECB, разбивается на 64-битовые блоки: M = M(1)M(2)...M(n). Первый блок M(1) складывается по модулю 2 с 64-битовым начальным вектором IV, который меняется ежедневно и держится в секрете. Полученная сумма затем шифруется с использованием ключа DES, известного и отправителю, и получателю информации. Полученный 64-битовый блок шифртекста C(1) складывается по модулю 2 со вторым блоком исходного текста, результат шифруется и получается второй 64-битовый блок шифртекста C(2) и т.д. Процедура повторяется до тех пор, пока не будут обработаны все блоки исходного текста (рис.6).

 
Рис.6. Работа алгоритма в режиме CBC

    Таким образом для всех i = 1...n блок шифртекста C(i) определяется следующим образом:

    Очевидно, что последний 64-битовый блок шифртекста является функцией секретного ключа, начального вектора и каждого бита открытого  текста независимо от его длины. Этот блок шифртекста называют кодом аутентификации сообщения (КАС).

      Код КАС может быть легко проверен получателем, владеющим секретным ключом и начальным вектором, путем выполнения процедуры, выполненной отправителем. Посторонний, однако, не может осуществить генерацию КАС, который воспринялся бы получателем как подлинный, чтобы добавить его к ложному сообщению, либо отделить КАС от истинного сообщения для использования его с измененным или ложным сообщением.

    Достоинство данного режима состоит в том, что он не позволяет накапливаться ошибкам при передаче. Блок M(i) является функцией только C(i-1) и C(i). Поэтому ошибка при передаче приведет к потере только двух блоков исходного текста.

    DES-CFB

    В этом режиме размер блока может отличаться от 64. Исходный файл M считывается последовательными t-битовыми блоками (t <= 64): M = M(1)M(2)...M(n) (остаток дописывается нулями или пробелами).

    64-битовый  сдвиговый регистр (входной блок) вначале содержит вектор инициализации  IV, выровненный по правому краю. Для каждого сеанса шифрования используется новый IV.

    Для всех i = 1...n блок шифртекста C(i) определяется следующим образом:

    C(i) = M(i) xor P(i-1) ,

где P(i-1) - старшие t битов операции предыдущего зашифрованного сообщения - DES(С(i-1)), причем C(0)=IV.  

    Обновление  сдвигового регистра осуществляется путем  удаления его старших t битов и дописывания справа C(i).

    Восстановление  зашифрованных данных также выполняется относительно просто: P(i-1) и C(i) вычисляются аналогичным образом и

    M(i) = C(i) xor P(i-1)

    Блок-схема  режима CFB приведена на рис.7.

    

 
Рис.7. Работа алгоритма DES в режиме CFB

    DES-OFB

    Режим OFB очень похож на режим CFB.

    Отличие от режима CFB состоит только в методе обновления сдвигового регистра. В  данном случае это осуществляется путем  удаления его старших t битов и дописывания справа P(i-1) (рис.8).

    

 
Рис.8. Блок-схема  алгоритма DES в режиме OFB

    Каждому из рассмотренных режимов свойственны  свои достоинства и недостатки, что  обусловливает области их применения.

    Режим ECB хорошо подходит для шифрования ключей. Режимы CBC и CFB пригодны для аутентификации данных. Режим CFB, кроме того, предназначен для шифрования отдельных символов. Режим OFB нередко используется в спутниковых системах связи.

    Одним из наиболее важных применений алгоритма DES является защита сообщений электронной  системы платежей (ЭСП) при операциях  с широкой клиентурой и между  банками. 
 

    3. Алгоритм шифрования IDEA

    Алгоритм IDEA (International Data Encryption Algorithm) является блочным шифром. Он оперирует 64-битовыми блоками открытого текста. Несомненным достоинством алгоритма IDEA является то, что его ключ имеет длину 128 бит. Один и тот же алгоритм используется и для шифрования, и для дешифрования.

    Первая  версия алгоритма IDEA была предложена в 1990 г., ее авторы - Х.Лей и Дж.Мэсси. Первоначальное алгоритм назывался PES (Proposed Encryption Standard). Улучшенный вариант этого алгоритма, разработанный в 1991 г., получил название IPES (Improved Proposed Encryption Standard). В 1992 г. IPES изменил свое имя на IDEA. Алгоритм IDEA использует при шифровании процессы смешивания и рассеивания, которые легко реализуются аппаратными и программными средствами.

    В IDEA используются следующие математические операции:

• поразрядное сложение по модулю 2 (операция "исключающее ИЛИ"); операция обозначается как (+);
• сложение беззнаковых целых по модулю 2¹⁶  (модуль 65536); операция обозначается как [+];
• умножение беззнаковых целых по модулю (2¹⁶+1) (модуль 65536); причем блок из 16 нулей рассматривается как 2¹⁶; операция обозначается как (·).

    Все операции выполняются над 16-битовыми субблоками.

    Эти три операции несовместимы в том  смысле, что:

• никакая пара из этих трех операций не удовлетворяет ассоциативному закону,  
  например a[+](b(+)c)#(a[+]b)(+)c;
• никакая пара из этих трех операций не удовлетворяет дистрибутивному закону, например a[+](b(·)c)#(a[+]b)(·)(a[+]с).

    Комбинирование  этих трех операций обеспечивает комплексное  преобразование входных данных, существенно затрудняя криптоанализ IDEA по сравнению с DES, который базируется исключительно на операции "исключающее ИЛИ".

    Общая схема алгоритма IDEA приведена на рис.9. 64-битовый блок данных делится на четыре 16-битовых субблока. Эти четыре субблока становятся входом в первый цикл алгоритма. Всего выполняется восемь циклов. Между циклами второй и третий субблоки меняются местами. В каждом цикле выполняется следующая последовательность операций:

    (·) - умножение субблока X1 и первого подключа.

    [+] - сложение субблока X2 и второго подключа.

    [+] - сложение субблока X3 и третьего подключа.

    (·) - умножение субблока X4 и четвертого подключа.

    (+) - сложение результатов шагов  1 и 3.

    (+) - сложение результатов шагов  2 и 4.

    (·) - умножение результата шага 5 и  пятого подключа.

    [+] - сложение результатов шагов  6 и 7.

    (·) - умножение результата шага 8 и  шестого подключа.

    [+] - сложение результатов шагов  7 и 9.

    (+) - сложение результатов шагов  1 и 9.

    (+) - сложение результатов шагов  3 и 9.

    (+) - сложение результатов шагов  2 и 10.

    (+) - сложение результатов шагов  4 и 10.

    

 
Рис.9. Cхема алгоритма IDEA (режим шифрования)

    Выходом цикла являются четыре субблока, которые получаются как результаты выполнения шагов 11, 12, 13 и 14. В завершение цикла второй и третий субблоки меняются местами (за исключением последнего цикла). В результате формируется вход для следующего цикла.

    После восьмого цикла осуществляется заключительное преобразование выхода: