Особенности программной реализации гост 28147-89

ГОСТ 28147‑89 описывает общий алгоритм шифрования, а также приводятся схемы реализации в виде операционного автомата. Такая схема не всегда подходит для программной реализации.

В частности, наиболее «неудобной» в реализации операцией оказалась операция замены в таблице замен. На рисунке (Рис. 2.8) показано действие этой операции. По сути, на вход таблицы замен подается 8 четырехразрядных двоичных чисел и на выходе получают 8 четырехразрядных чисел — значений из таблицы замен. Каждое число является индексом в массиве, где массив это строка таблицы. Т.е. если i‑ое число равно j, то оно заменяется на значение j‑ой ячейки i‑ой строки таблицы замен.

Рис. 2.8. – Работа таблицы замен

На практике гораздо удобнее пользоваться модифицированной таблицей замен. Если преобразовать таблицу по следующим формулам

, (2.4)

, (2.5)

то таблица и процесс замены будут выглядеть как на следующем рисунке (Рис. 2.9).

Рис. 2.9. ‑ Работа модифицированной таблицы замен

В результате вместо 8 однотипных операций будет выполняться только 2 однотипные операции, что скажется возрастанием скорости работы блока замен приблизительно в 4 раза. На самом деле, из‑за того, что ячейка таблицы замен стала 16‑ти разрядной, и того, что в результате такой модификации стало возможным работать с косвеннорегистровой индексацией по базе, скорость возрастает более чем в 4 раза.

Стандарт шифрования данных des (Data Encryption Standard)

Американский национальный институт стандартов (American National Standards Institute, ANSI) одобрил DES в качестве стандарта для частного сектора в 1981 году (ANSI X3.92.) [50], назвав его Алгоритмом шифрования данных (Data Encryption Algorithm, DEA).

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

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

На простейшем уровне алгоритм не представляет ничего большего, чем комбинация двух основных методов шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов (подстановка, а за ней - перестановка), зависящей от ключа. Такой блок называется этапом. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз (см. Рис. 2.10).

Рис. 2.10 DES.

Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-х. Изобилие повторений в алгоритме делает его идеальным для реализации в специализированной микросхеме. Первоначальные программные реализации были довольно неуклюжи, но сегодняшние программы намного лучше.

DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называемых функцией f, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая половины объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной).

На каждом этапе (Рис. 2.11) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f. Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов DES.

Рис. 2.11

Если B_i - это результат i-ой итерации, L_i и R_i - левая и правая половины B_i, K_i - 48-битовый ключ для этапа i, а f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:

L_i = R_i-1

R_i = L_i-1  f(R_i-1, K_i)