Криптографические алгоритмы могут быть реализованы как аппаратно (что повышает скорость их работы), так и программно (для повышения гибкости). Несмотря
на то что большая часть наших размышлений касается алгоритмов и протоколов, не зависящих от конкретной реализации, нам кажется полезным рассмотрение принципов построения криптографической аппаратуры. Подстановки и перестановки могут быть реализованы при помощи простых электрических цепей. На рис. 8.5, а показано устройство, называющееся P-блоком (литера P означает permutation — перестановка) и используемое для перестановки восьми входных разрядов. Если пронумеровать входные биты сверху вниз (01234567), выход этого конкретного P-блока будет выглядеть как 36071245. При помощи соответствующего внутреннего устройства P-блока (распайки проводов) можно заставить его выполнять любую операцию перестановки практически со скоростью света, так как никакие вычисления в нем не производятся, а просто-напросто передается сигнал с входа на выход. Такое решение соответствует принципу Керкгофа: взломщик знает, что используется метод перестановки битов. Однако он не знает ключа, заключающегося в порядке перестановок.
Рис. 8.5. Основные элементы продукционных шифров: P-блок (а); S-блок (б); продукционный шифр (в)
Подстановки (то есть замещения) выполняются S-блоками (S означает substitution — подстановка, замена), как показано на рис. 8.5, б. В данном примере на вход подается 3-битный открытый текст, а на выходе появляется 3-битный зашифрованный текст. Для каждого входного сигнала выбирается одна из восьми выходных линий декодера путем установки ее в 1. Все остальные линии устанавливаются в 0. Затем эти восемь линий проходят через P-блок, представляющий собой вторую ступень S-блока. Третья ступень производит обратное кодирование одной из восьми линий в 3-битовое двоичное число. Такое устройство заменяет восьмеричные числа 01234567 на 24506713 соответственно. То есть 0 заменяется числом 2, 1 — числом 4 и т. д. Опять же, при соответствующей распайке проводов P-блока внутри S-блока можно реализовать любой вариант подстановки. К тому же такое устройство может быть встроено в аппаратуру и работать на огромных скоростях, поскольку шифраторы и дешифраторы вносят лишь одну или две вентильных задержки (менее 1 нс), а время распространения сигнала внутри P-блока может быть менее 1 пс.
Настоящая сила этих элементов становится очевидна, если сформировать каскад из этих устройств, как показано на рис. 8.5, в. Получившееся в результате устройство называется продукционным шифром (product cipher). В данном примере на первом этапе (P1) 12 входных линий меняются местами. На второй ступени вход разбивается на четыре группы из трех бит, с каждой из которых операция замены выполняется независимо (S1 до S4). Данный метод представляет собой составление большего S-блока из нескольких меньших S-блоков. Данный способ достаточно целесообразен, так как небольшие S-блоки удобны при аппаратной реализации (то есть восьмиразрядный S-блок может быть реализован как 256-разрядная таблица перекодировки), но большие S-блоки строить неудобно (например, двенадцатиразрядный S-блок потребует как минимум 212 = 4096 перекрещенных проводов в средней стадии). Хотя такой метод представляет собой лишь частный случай общего решения, его мощь достаточно высока. Выход продукционного шифра можно сделать сложной функцией входа, используя достаточно большое количество дополнительных ступеней.
Продукционные шифры, работающие с k-битными входами и производящие k-битные последовательности, широко распространены. Обычно значение k колеблется от 64 до 256.
8.2.1. Стандарт шифрования данных DES
В январе 1977 года правительство Соединенных Штатов приняло продукционный шифр, разработанный фирмой IBM, в качестве официального стандарта для несекретных сведений. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), широко использовался в промышленности для защиты информации. В своем исходном виде он уже больше не является надежным, но в модифицированном виде все еще полезен. Сейчас мы объясним принципы его работы.
Схема шифра DES показана на рис. 8.6, а. Открытый текст шифруется блоками по 64 бита, в результате чего на выходе получаются 64-битные блоки зашифрованного текста. Алгоритм, использующий 56-разрядный ключ, состоит из 19 отдельных этапов. На первом этапе выполняется независимая перестановка 64 разрядов открытого текста. Последний представляет собой обратную перестановку. Предпоследний этап меняет местами левые и правые 32 разряда. Остальные 16 этапов функционально идентичны, но управляются разными функциями входного ключа. Алгоритм был разработан так, чтобы дешифрация выполнялась тем же ключом, что и шифрование. Это обеспечивает соответствие алгоритма принципу симметричных ключей. Этапы при расшифровке просто выполняются в обратном порядке.
Операция, выполняемая на одном из промежуточных этапов, показана на рис. 8.6, б. На каждом этапе из двух порций по 32 разряда на входе формируется две порции по 32 разряда на выходе. Правая половина входа просто копируется в левые разряды выхода. Правые 32 выходных разряда представляют собой сумму по модулю 2 левой части входа и функции правой части входа и ключа данного этапа K. Вся сложность алгоритма заключается в этой функции.
Функция состоит из четырех последовательно выполняемых шагов. Сначала из 32 разрядов правой части R{ — 1 с помощью фиксированной перестановки и дублирования формируется 48-разрядное число E. На втором шаге число E и ключ K складываются по модулю 2. Затем выход разделяется на восемь групп по шесть разрядов, каждая из которых преобразуется независимым S-блоком в 4-разрядные группы. Наконец, эти 8 х 4 разряда пропускаются через P-блок.
На каждом из 16 этапов используются различные функции исходного ключа. Перед началом работы алгоритма к ключу применяется 56-разрядная перестановка. Перед
каждым этапом ключ разделяется на две группы по 28 разрядов, каждая из которых вращается влево на число разрядов, зависящее от номера этапа. Ключ K получается из результата этой операции при помощи еще одной перестановки 56 разрядов. На каждом этапе из 56 разрядов ключа выбираются 48 разрядов, которые также переставляются местами.
Рис. 8.6. Стандарт шифрования данных DES: а — общий вид; б — детализация одного из этапов
Иногда для повышения надежности DES используется метод, называемый побелкой (whitening). Он заключается в том, что перед передачей шифра каждый блок открытого текста складывается по модулю 2 с произвольным 64-битным ключом, затем отправляется в устройство DES, после чего получившийся шифр складывается по модулю 2 со вторым 64-битным ключом. На приемном конце побелка легко устраняется путем выполнения обратных операций (это возможно, если у получателя есть два побелочных ключа). Поскольку применение этого метода увеличивает длину ключа, полный перебор в пространстве значений ключа становится еще более длительным. Обратите внимание: для побелки каждого блока применяется один и тот же ключ (то есть для каждого сообщения имеется только один побелочный ключ).
Стандарт шифрования данных DES был полон противоречий с самого момента его создания. Он основывался на шифре Люцифер (Lucifer), разработанном и запатентованном корпорацией IBM, с той разницей, что IBM использовала 128-разрядный ключ, а не 56-разрядный. Когда федеральное правительство Соединенных Штатов пожелало стандартизировать какой-нибудь шифр для несекретного применения, оно «пригласило» IBM на «обсуждение» этого вопроса с Агентством национальной безопасности NSA (National Security Agency, известное как АНБ США), являющимся самым крупным в мире работодателем в области математики и криптологии. Агентство национальной безопасности США настолько секретно, что существует даже такая популярная шутка:
