Криптографический стандарт DES

В 1973 г. Национальное бюро стандартов США начало разработку программы по созданию стандарта шифрования данных на ЭВМ. Был объявлен конкурс среди фирм разработчиковСША, который выиграла фирма IBM, представившая в 1974 году алгоритм шифрования, известный под названием DES(Data Encryption Standart).

В этом алгоритме входные 64-битовые векторы, называемые блоками открытого текста, Преобразуются в выходные 64-битовые векторы, называемые блоками шифротекста, с помощью двоичного 56-битового ключа К. Число различных ключей DES-алгоритма равно 256>7*1016.

Алгоритм реализуется в течение 16 аналогичных циклов шифрования, где на I-ом цикле используется цикловой ключ Ki, представляющий собой алгоритмически вырабатываемую выборку 48 битов из 56 битов ключа Ki, I=1,2,…,16.

Шифр DES имеет длину блока исходных данных p равную 64 битам и ключ сложения по модулю 2 длиной 56 бит. Ключ, реализующий подстановку, является ключом длительного пользования, который выбирается по специальным критериям. Схема преобразования представлена на рис. 9.1. На этом рисунке: p ― блок открытого текста. В этом блоке предполагается, что открытый текст разбивается на части по 64 бита. Каждые 64 бита подвергаются всем преобразованиям, которые приведены на рис. 9.1.

Рис. 9.1. Структура шифра DES

Это соответствует режиму шифрования «прямая замена», когда 64 бита обрабатываются независимо друг от друга и после всех преобразований появляется 64 бита зашифрованного текста. На выходе схемы преобразования находится блок с - блок шифрованного текста. Кроме этих блоков в схему преобразования входят: IP - блок начальной перестановки, IP–1 - блок конечной перестановки, f - функция криптографического преобразования, L - левые полублоки, Ri - правые полублоки, i = 0, 1, 2, …, 15. Блок открытого текста (64 бита) подвергается начальной пере- становке, согласно табл. 9.1. В соответствии с этой таблицей 58 бит открытого текста становится первым битом, 50 бит становится вторым битом, 42 бит - третьим, а первый бит открытого текста перемещается на 40 позицию и т. д. После блока начальной перестановки полученные, 64 бита разбиваются на две половины по 32 бита, и получаются, соответственно, левый полублок L и правый полублок R.

Таблица 9.1.

Биты, находящиеся в правом полублоке R, подвергаются крип- тографическому преобразованию с помощью функции f(R, k), завися- щей от ключа и складываются по модулю 2 с данными из левого по- лублока. Затем данные в этих полублоках меняются местами. Эта процедура в шифре DES повторяется 16 раз. Таким образом, в общем виде раундовая функция шифрования на i-м шаге представлена на рис. 9.2.

Рис. 9.2. Раундовая функция i-го шага шифрования DES

На рис. 9.2. Li и Ri ― левый и правый полублоки, полученные в результате i-й итерации, ki - 48-битный ключ, а f - функция криптографического преобразования, выполняющая все подстановки, перестановки и операцию сложения по модулю 2 с ключом.

Алгоритм обеспечивает высокую стойкость, однако недавние результаты показали, что современная технология позволяет создать вычислительное устройство стоимостью около 1 млн. долларов США, способное вскрыть секретный ключ с помощью полного перебора в среднем за 3,5 часа.

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

DES-алгоритм явился первым примером широкого производства и внедрения технических средств в области защиты информации. Национальное бюро стандартов США проводит проверку аппаратных реализаций DES-алгоритма, предложенных фирмами-разработчиками, на специальном тестирующем стенде. Только после положительных результатов проверки производитель получает от Национального бюро стандартов сертификат на право реализации своего продукта. К настоящему времени аттестовано несколько десятков изделий, выполненных на различной элементарной базе.

Основные области применения DES-алгоритма:

хранение данных на компьютерах (шифрование файлов, паролей);

аутентификация сообщений (имея сообщение и контрольную группу, несложно убедиться в подлинности сообщения;

электронная система платежей (при операциях с широкой клиентурой и между банками);

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

Позднее появилась модификация DESa — Triple Des («тройной DES» — так как трижды шифрует информацию «обычным» DESом) свободен от основного недостатка прежнего варианта — короткого ключа; он здесь в два раза длиннее. Но зато, как оказалось, Triple DES унаследовал другие слабые стороны своего предшественника: отсутствие возможности для параллельных вычислений при шифровании и низкую скорость.

Вопрос №10. ГОСТ 28147-89

В 1989 году в СССР был разработан блочный шифр для использования в качестве государственного стандарта шифрования данных. Разработка была принята и зарегистрирована как ГОСТ 28147-89. Алгоритм был введен в действие в 1990 году. И хотя масштабы применения этого алгоритма шифрования до сих пор уточняются, начало его внедрения, в частности в банковской системе, уже положено. Алгоритм несколько медлителен, но обладает весьма высокой стойкостью.

В общих чертах ГОСТ 28147 аналогичен DES. Блок-схема алгоритма ГОСТ отличается от блок-схемы DES-алгоритма лишь отсутствием начальной перестановки и число циклов шифрования (32 в ГОСТ против 16 в DES-алгоритме).

Ключ алгоритма ГОСТ - это массив, состоящий из 32-мерных векторов X1, X2,…X8. Цикловой ключ i-го цикла Ki равен Xs, где ряду значений i от 1 до 32 соответствует следующий ряд значений s:

1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,8,7,6,5,4,3,2,1.

Шифр ГОСТ 28147-89 (далее будем обозначать этот шифр как шифр ГОСТ) является классическим примером итерационного блочного шифра Фейстеля с разрядностью блока данных, равной 64 бита. Объем ключевого пространства ГОСТ равен 2256. Ключевая информация представляет собой массив данных размерности 256 бит. Каждый массив из 256 бит представляется как массив из восьми 32 разрядных элементов {km}, m = 0, 1, 2,..., 7. Таблица замен S представляет собой набор из восьми одномерных массивов {Sm}, m = 0, 1, 2,..., 7, так называемых узлов замены, каждый из которых определяет алгоритм работы 4-разрядного блока подстановок (S-блока). На вход блока замен поступает 32 битовая последовательность, которая разбивается на восемь 4 битовых подпоследовательностей. Каждый S-блок представляет собой таблицу из шестнадцати строк, каждая из которых содержит по четыре бита заполнения в строке. Заполнение в строке представляет собой некоторую переста- новку чисел от 0 до 15. Первая 4 битовая подпоследовательность попадает на вход первого S-блока, вторая 4 битовая подпоследовательность поступает на вход второго S-блока и т. д. Пусть соответствующий S-блок представляет собой последовательность из 16 десятичных чисел в интервале от 0 до 15, расположенных в следующем порядке:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12.

Если на вход S-блока подается 4 битовая подпоследовательность, равная 0, то на его выходе будет 1. При подаче на вход S-блока 4 битовой подпоследовательности, равной 4 на выходе будет 5. Если на вход S-блока подается 4 битовая подпоследовательность, равная 12, то на выходе будет 6 и т. д. Пример реализации блока замен шифра ГОСТ приведен в табл. 1.14

Выходы всех восьми S-блоков объединяются в 32-битное слово. После этого слово циклически сдвигается влево (к старшим разрядам) на 11 битов. Все восемь S-блоков могут быть различными. Более подробно структура основного шага криптопреобразования шифра ГОСТ показана рис. 10.1, где di - 64-битовый блок данных на i-м раунде криптопреобразования, L и R - соответственно, левый и правый 32 битовые полублоки блока d i, X - 32-разрядный ключевой массив, «+» - операция побитового сложения по модулю 2

Рис. 10.1- Раундовая функция шифра ГОСТ

В качестве исходных данных каждый шаг криптообразования получает 64 разрядный бок данных d = (L, R) и 32 разрядный ключ X, в качестве которого используется один из элементов ключевого массива km (рис. 10.2). Более подробно преобразования, осуществляемые с правой половиной R в функции f, представлены на рис. 10.2, где суммирование осуществляется по модулю 232, а R 11 представляет собой циклический сдвиг на 11 разрядов влево. В ходе выполнения одного шага криптопреобразования данные в правой половине блока R подвергаются следующим преобразованиям. Сложение по модулю 232 данных полублока R и ключа X.

Рис. 10.2- Раундовая функция шифра ГОСТ с учетом блока замен

Разбиение результата S на восемь 4 битовых блоков, поблочной замене по таблице замен, формированию из получившихся блоков нового значения S. Циклический сдвиг результата S на 11 разрядов влево. Поразрядное сложение по модулю 2 результата S и данных, записанных в левой половине блока L. Данные в правой половине блока R становятся новым значением элемента L, а значение результата предыдущей операции, описанной в предыдущем пункте, становится новым значением элемента R (рис. 10.1). В шифре ГОСТ предусмотрено, что последовательно осуществляется 32 таких раунда. Описанный выше алгоритм функционирования называется режимом простой замены, когда блоки открытого текста обрабатываются независимо друг от друга. Кроме того, в шифре ГОСТ предусмотрены режимы работы, аналогичные рассмотренным выше режимам шифра DES, которые обладают повышенной криптографической стойкостью. Шифр DES являлся прототипом для шифра ГОСТ 28147-89

В шифре ГОСТ используется 256-битовый ключ и объем ключевого пространства составляет 2256. Ни на одной из существующих в настоящее время или предполагаемых к реализации в недалеком будущем компьютерной системе общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт проектировался с большим запасом, по стойкости он на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 256 (и неудивительно: его ключ длиной 32 байта (256 бит) вчетверо больше ключа DES. Необходимое же на перебор всех ключей время при этом возрастает не в четыре раза, а в 25632-8=25624, что выливается уже в астрономические цифры), чего явно недостаточно. В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес.