|
|
  |
Главная страница / Архитектура отрасли Алгоритм шифрования DES и его вариантыDES шифрует информацию блоками по 64 бита с помощью 64-битного ключа шифрования, в котором используется только 56 бит (процедура расширения ключа подробно описана ниже). Шифрование информации выполняется следующим образом (рис. 1): Этап 1. Над 64-битным блоком данных выполняется начальная перестановка согласно следующей таблице: Данная таблица означает, что значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита – в бит 2 и т. д. Этап 2. Результат предыдущей операции делится на 2 субблока по 32 бита (на рис. 1 обозначены A0 и B0), над которыми производятся 16 раундов следующих преобразований: Ai = Bi-1, Bi = Ai-1 +О f(Bi-1, Ki), где i – номер текущего раунда, Ki – ключ раунда, а +О – побитовая логическая операция «исключающее или» (XOR). Структура функции раунда f() приведена на рис. 2. Данная функция выполняется в несколько шагов: Шаг 1. Над 32-битным входом выполняется расширяющая перестановка EP (рис. 3). Данная операция решает две задачи: во-первых, расширяет входное значение до 48 бит для последующего сложения с ключом раунда; во-вторых, обеспечивает влияние «размножаемых» бит на 2 таблицы замен (описаны ниже) вместо одной, что ускоряет возникновение зависимости каждого бита шифртекста от каждого входного бита (2 [4]), что называется лавинным эффектом. Шаг 2. Результат предыдущего шага складывается с ключом раунда Ki операцией XOR. Шаг 3. Результат сложения разбивается на 8 фрагментов по 6 бит, каждый из которых прогоняется через соответствующую таблицу замен (S1 … S8). Таблицы замен являются фиксированными и описаны в стандарте (3 [24]). Каждая таблица содержит по 4 строки, содержащих по 16 значений от 0 до 15. Входное значение интерпретируется следующим образом: два крайних бита формируют номер строки (от 0 до 3), из которой выбирается число, расположенное в столбце, номер которого соответствует значению четырех остальных бит входа. Например, при двоичном входе 101100 (десятичное число 44) выбирается значение шестой ячейки второго столбца. Шаг 4. На последнем шаге 4-битные значения, полученные после выполнения замен, объединяются, после чего над ними выполняется операция P, представляющая собой простую перестановку согласно следующей таблице: Стоит отметить, что в последнем раунде алгоритма субблоки не меняются местами. Этап 3. Полученные субблоки A16 и B16 объединяются в 64-битный блок, над которым выполняется финальная перестановка данных согласно следующей таблице: Финальная перестановка является инверсной по отношению к начальной перестановке, выполняемой на этапе 1. Результат финальной перестановки и является блоком зашифрованных данных. Расшифрование данных алгоритмом DES выполняется абсолютно так же, как и зашифрование, однако с обратным порядком использования ключей раунда: в i-м раунде расшифрования используется ключ K(17-i). Схема процедуры расширения ключа показана на рис. 4. Ее задача – формирование 16 ключей раунда, которое выполняется следующим образом. Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 бит. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся бит ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом (3 [24]). Процедура извлечения 56 значащих бит 64-битного ключа на рис. 4 обозначена как E. Помимо извлечения, данная процедура выполняет еще и перестановку бит ключа согласно следующим таблицам: В результате перестановки формируются два 28-битных значения C и D. Верхняя таблица определяет выборку бит ключа для C, нижняя – для D. Затем выполняется 16 раундов преобразований, каждый из которых дает один из ключей раунда Ki. В каждом раунде производятся следующие действия: 1. Текущие значения C и D циклически сдвигаются влево на переменное число бит n. Для раундов 1, 2, 9 и 16 n = 1, в остальных раундах выполняется циклический сдвиг на 2 бита. 2. C и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда Ki. Сжимающая перестановка выполняется согласно следующей таблице: Сочетание циклического сдвига и сжимающей перестановки приводит к тому, что в каждом ключе раунда используется уникальный набор бит ключа шифрования. При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раунда в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на n' бит, где n' = 0 для первого раунда, n' = 1 для раундов 2, 9, 16 и n' = 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифрования ключи раунда K(17-i). Стоит сказать, что возможность выполнения расширения ключа «на лету» (особенно если эта возможность существует как при зашифровании, так и при расшифровании) считается достоинством алгоритмов шифрования, поскольку в этом случае расширение ключа можно выполнять параллельно шифрованию и не тратить память на хранение ключей раундов, кроме текущего. Несколько позже, в 1980 году был принят стандарт (4 [25]), определяющий режимы работы алгоритма DES. Можно сказать, что данный стандарт уточнял подробности реализации DES для различных применений. В стандарте были определены следующие режимы работы алгоритма DES: электронная кодовая книга ECB (Electronic Code Book); сцепление блоков шифра CBC (Cipher Block Chaining); обратная связь по шифртексту CFB (Cipher Feed Back); обратная связь по выходу OFB (Output Feed Back). Наиболее простым из них является режим ECB. Суть его состоит в том (рис. 5), что каждый блок шифруемых данных «прогоняется» через алгоритм шифрования отдельно и независимо от других блоков: Ci = Ek(Mi), где Ek – функция зашифрования на ключе k, Mi и Ci – блоки открытого текста и соответствующие им блоки шифртекста. Аналогично выполняется и расшифрование – блоки шифртекста обрабатываются поочередно и независимо. Данный режим плох тем, что если открытый текст содержит какое-либо количество блоков с одинаковым содержимым (например, некий большой массив, проинициализированный нулевыми или единичными битами), то и шифртекст будет содержать такое же количество одинаковых блоков. Это непозволительно, поскольку дает криптоаналитику информацию о структуре зашифрованной информации, что может существенно облегчить вскрытие алгоритма шифрования (т. е. получение открытого текста из зашифрованного или вычисление ключа шифрования). Поэтому данный режим должен использоваться только для шифрования ключей друг на друге в многоключевых схемах (1 [2]). Допускается также шифрование режимом ECB небольших фрагментов данных при условии их неповторяемости (5 [39]). Есть и еще один недостаток – в данном режиме алгоритм шифрует данные только поблочно. При необходимости, например, зашифровать алгоритмом DES 8 бит придется дополнить эти данные до 64-битного размера блока, зашифровать блок целиком, а при расшифровании отбросить дополняющие биты. Такое не всегда возможно. Достоинство режима ECB – простота реализации по сравнению с другими режимами. Однако, по словам Брюса Шнайера, «из-за своей простоты в большинстве существующих коммерческих программ используется режим ECB, хотя этот режим наиболее уязвим к вскрытию» (2 [4]). Существенно более стойким является режим CBC. В данном режиме (рис. 6) перед шифрованием каждого i-го блока шифруемых данных выполняется его побитовое сложение по модулю 2 с результатом шифрования предыдущего, i-1-го блока. То есть для режима CBC шифрование выглядит так: Ci = Ek(Mi +О Сi-1). Видно, что результат шифрования каждого блока зависит не только от содержимого шифруемого блока, но и от всех предыдущих блоков открытого текста. При шифровании первого блока открытого текста, вместо результата зашифрования предыдущего блока, используется вектор инициализации (IV – Initialization Vector): C1 = Ek(M1 +О IV). Варьируя значением IV, можно получать различные шифртексты для одинаковых открытых текстов. Естественно, при расшифровании шифртекста, полученного в данном режиме, IV должен быть известен. Это справедливо и для рассмотренных ниже режимов CFB и OFB. Аналогично предыдущему режиму, данные, размер которых меньше 64-битного блока, придется перед обработкой дополнять до 64 бит. Режим CBC используется непосредственно для зашифрования данных, в том числе в больших объемах. Кроме того, последний блок шифртекста CN может использоваться для контроля целостности сообщений, поскольку его значение зависит от содержимого всех блоков открытого текста, IV и ключа: CN = f(M1, M2, … MN, IV, k). Режим CFB более сложен в реализации, чем два предыдущих. Шифрование данных в этом режиме выполняется следующим образом (рис. 7): Шаг 1. Вектор инициализации IV записывается в регистр 1. Шаг 2. 64-битное содержимое регистра 1 зашифровывается алгоритмом DES, результат помещается в регистр 2. Шаг 3. Из регистра 2 выбираются L левых бит (1L64), которые накладываются операцией XOR на L-битный блок шифруемого текста. Результат данного шага – L-битный блок шифртекста. Шаг 4. Содержимое регистра 1 сдвигается влево на L бит. Шаг 5. Регистр 1 дополняется справа L-битным блоком шифртекста. При необходимости продолжить шифрование данных шаги 2 – 5 повторяются в цикле до обработки всех шифруемых данных. Фактически в данном режиме алгоритм DES на основе вектора инициализации, ключа шифрования и предыдущих блоков шифртекста генерирует псевдослучайную последовательность, которая накладывается на открытый текст. Поскольку операция XOR обладает следующим свойством: (x +О y) +О y = x, для любых значений x и y, то для расшифрования следует сгенерировать такую же последовательность. Не имея ключа и значения IV, такую же последовательность сгенерировать невозможно. Режим шифрования OFB похож на предыдущий (рис. 8): Шаг 1. Вектор инициализации IV записывается в регистр 1. Шаг 2. Содержимое регистра 1 зашифровывается алгоритмом DES, результат помещается в регистры 1 и 2. Шаг 3. Из регистра 2 выбираются L левых бит, которые накладываются операцией XOR на L-битный блок шифруемого текста, в результате получается L-битный блок шифртекста. При необходимости продолжить шифрование шаги 2 и 3 повторяются в цикле. Здесь описана более поздняя версия режима OFB (описанная в стандарте ISO 10116), согласно (4 [25]) в регистр 1 «возвращался» не полностью 64-битный результат зашифрования регистра 1, а младшие L бит (т. е. более похоже на режим CFB); исходный вариант режима OFB считается менее криптографически стойким, чем модифицированный (2, 5 [4, 39]). Существует и более простой режим OFB – «режим счетчика» (5 [39]), в котором обратная связь вообще отсутствует, а содержимое регистра 1 перед каждым его зашифрованием увеличивается на единицу. Аналогично режиму CFB, для расшифрования необходимо сгенерировать ту же последовательность и наложить ее на шифртекст. Отличие от предыдущего режима лишь в том, что значение регистра 1 заменяется в цикле его же зашифрованным содержимым. Отсюда проистекает важное свойство режима OFB – накладываемая на шифруемый текст последовательность зависит только от значения IV и ключа шифрования. То есть шифрующую последовательность можно сгенерировать заранее и, например, использовать ее в периоды максимальной нагрузки на шифрующий компьютер или устройство, восполняя последовательность в фоновом режиме. Такая возможность весьма важна для серверных компонент распределенных систем, поскольку позволяет существенно увеличить их пиковую производительность. Еще одно важное отличие режима OFB от остальных состоит в том, что при возникновении ошибки в одном бите шифртекста после расшифрования возникает ошибка только в одном бите расшифрованных данных, тогда как в остальных режимах ошибочно расшифруются один или два блока. Стоит сказать и о том, что в режимах OFB и CFB алгоритм DES можно использовать в качестве потокового шифра, установив L равным размеру символов потока (например, 1 или 8). Существуют и другие режимы работы, большинство которых является незначительной модификацией описанных выше и применяется существенно реже (2 [4]). Рассмотренные же режимы не привязаны к конкретному алгоритму – фактически любые алгоритмы блочного симметричного шифрования могут быть использованы (и используются) в данных режимах работы. Продолжение в следующих номерах 1. [2] Панасенко С.П., Батура В.П. Основы криптографии для экономистов: учебное пособие. Под ред. Л.Г. Гагариной. – М.: Финансы и статистика, 2005. – 176 с. 2. [4] Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002. – 816 с. 3. [24] FIPS 46-3. Data Encryption Standard (DES) // – Reaffirmed 1999 October 25. 4. [25] FIPS 81. DES Modes of Operation // – 1980. December 2. 5. [39] Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography// – CRC Press, 1996.Один из наиболее известных в мире криптологов Брюс Шнайер (Bruce Schneier) в своей знаменитой книге «Прикладная криптография» (2 [4]) так описал проблемы пользователей средств защиты информации в начале 70-х годов XX века (естественно, речь идет о пользователях по ту сторону «железного занавеса»): 1. Не было как общепринятого стандарта шифрования данных, так и просто достаточно широко используемых алгоритмов защиты информации, поэтому о совместимости между различными программными или аппаратными средствами шифрования не могло быть и речи. 2. Практически любое средство шифрования представляло собой «черный ящик» с недостаточно ясным содержимым: какой алгоритм шифрования используется, насколько он является криптографически стойким, грамотно ли он реализован, корректно ли создаются/хранятся/используются ключи шифрования, нет ли в средстве вставленных разработчиками недокументированных возможностей и т. д., – вся эта весьма важная информация для подавляющего большинства покупателей криптографических средств была недоступна. Данной проблемой озаботилось Национальное Бюро Стандартов (NBS – National Bureau of Standards) США. В результате в 1973 году был объявлен первый в истории открытый конкурс на стандарт шифрования. NBS было готово исследовать с целью выбора стандарта алгоритмы-претенденты, удовлетворяющие следующим критериям: алгоритм должен быть криптографически стойким; алгоритм должен быть быстрым; структура алгоритма должна быть четкой и ясной; стойкость шифрования должна зависеть только от ключа, сам алгоритм не должен быть секретным; алгоритм должен быть легко применим для различных целей; алгоритм должен легко реализовываться аппаратно на существующей элементной базе. Предполагалось, что заинтересованные организации или специалисты будут присылать в NBS подробные спецификации алгоритмов, достаточные для их реализации, т. е. не имеющие каких-либо «белых пятен». Предполагалось также, что алгоритм будет сертифицирован NBS для всеобщего использования, с него будут сняты все патентные и экспортные ограничения, в результате чего такой стандарт должен снять все проблемы совместимости средств шифрования. Кроме того, NBS брало на себя функции сертификации средств шифрования, т. е. «черные ящики» должны были безвозвратно уйти в прошлое. Фактически алгоритм-претендент оказался всего один: это был разработанный фирмой IBM алгоритм шифрования Lucifer. В течение двух лет проводилась доработка алгоритма: во-первых, NBS совместно с Агентством Национальной Безопасности (NSA – National Security Agency) США был проведен тщательный анализ алгоритма, результатом которого явилась его достаточно существенная переработка; во-вторых, принимались к рассмотрению комментарии и критические замечания от всех заинтересованных организаций и частных лиц. В результате совместной деятельности IBM, NBS и NSA в январе 1977 г. DES был опубликован как стандарт США (последняя версия этого стандарта (3 [24]) на алгоритм шифрования данных (кроме информации повышенной степени секретности). Алгоритм DES был запатентован фирмой IBM, однако NBS получило фактически бесплатную и неограниченную лицензию на использование данного алгоритма (3 [24]). Главная страница / Архитектура отрасли |