Алгоритмы с симметричным криптографическим ключом
В современной криптографии применяются те же основные идеи, что и в традиционной криптографии, то есть перестановка и подстановка, но акценты расставляются иначе. В традиционной криптографии применялись простые алгоритмы. Сегодня верно обратное: целью является создание настолько сложного и запутанного алгоритма шифрования, что даже если криптоаналитику попадут в руки целые горы зашифрованного текста, он не сможет извлечь из этого никакой пользы.
Первым классом алгоритмов шифрования, который мы изучим, будет класс алгоритмов с симметричным ключом. Он получил такое название благодаря тому, что для шифрации и дешифрации сообщений применяется один и тот же ключ. Мы подробно рассмотрим блочные шифры, которые принимают на входе n-битные блоки открытого текста и преобразуют их с использованием ключа в n-битный шифр.
Криптографические алгоритмы могут быть реализованы как аппаратно (что повышает скорость их работы), так и программно (для повышения гибкости). Несмотря на то, что большая часть наших размышлений касается алгоритмов и протоколов, не зависящих от конкретной реализации, нам кажется полезным рассмотрение принципов построения шифровальной аппаратуры. Подстановки и перестановки могут быть реализованы при помощи простых электрических цепей. На рис. 24 показано устройство, называющееся Р-блоком (литера Р означает permutation — перестановка) и используемое для перестановки восьми входных разрядов. Если пронумеровать входные биты сверху вниз (01234567), выход этого конкретного Р-блока будет выглядеть как 36071245. При помощи соответствующего внутреннего устройства Р-блока (распайки проводов) можно заставить его выполнять любую операцию перестановки практически со скоростью света, так как никакие вычисления в нем не производятся, а просто-напросто передается сигнал со входа на выход. Такое решение соответствует принципу Керкгофа: взломщик знает, что используется метод перестановки битов. Однако он не знает ключа, заключающегося в порядке перестановок.
Рис. 24. Работа S и P блоков
Подстановки (то есть замещения) выполняются S-блоками (S означает substitution — подстановка, замена), как показано на рис. 24. В данном примере на вход подается 3-битный открытый текст, а на выходе появляется 3-битный зашифрованный текст. Для каждого входного сигнала выбирается одна из восьми выходных линий декодера путем установки ее в 1. Все остальные линии устанавливаются в 0. Затем эти восемь линий проходят через Р-блок, представляющий собой вторую ступень S-блока. Третья ступень производит обратное кодирование одной из восьми линий в 3-битовое двоичное число. Такое устройство заменяет восьмеричные числа 01234567 на 24506713 соответственно. То есть 0 заменяется числом 2, 1 — числом 4 и т. д. Опять же, при соответствующей распайке проводов Р-блока внутри S-блока можно реализовать любой вариант подстановки. К тому же такое устройство может быть встроено в аппаратуру и работать на огромных скоростях, поскольку шифраторы и дешифраторы вносят лишь одну или две вентильных задержки (менее 1 не), а время распространения сигнала внутри Р-блока может быть менее 1 пс. Отметим, что P-блок является частным случаем S-блока.
Настоящая сила этих элементов становится очевидна, если сформировать каскад из этих устройств. Такое устройство называется продукционным шифром. На первом этапе (Р,) входные N линий меняются местами. Теоретически, вторая ступень могла бы быть S-блоком, отображающим одно N-разрядное число в другое N-разрядное число. Однако такое устройство должно содержать в средней стадии 2N перекрещенных проводов. Вместо этого вход имеет смысл разбивать на группы с меньшим количеством разрядов, с каждой из которых операция замены выполняется независимо. Хотя такой метод представляет собой лишь частный случай общего решения, его мощь достаточно высока. Выход продукционного шифра можно сделать сложной функцией входа, используя достаточно большое количество дополнительных ступеней.
Продукционные шифры, работающие с N-битными входами и производящие N-битные последовательности, широко распространены. Обычно значение N колеблется от 64 до 256.
Стандарт шифрования данных DES.
В январе 1977 году правительство Соединенных Штатов приняло продукционный шифр, разработанный фирмой IBM, в качестве официального стандарта для несекретных сведений. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), получил широкое распространение в промышленности для защиты информации. В своем исходном виде он уже больше не является надежным, но в модифицированном виде все еще полезен.
Рис. 25. Схема шифрования алгоритма DES
Схема DES-шифра показана на рис. 25. Открытый текст шифруется блоками по 64 бита, в результате чего на выходе получаются 64-битные блоки зашифрованного текста. Алгоритм, использующий 56-разрядный ключ, состоит из 19 отдельных этапов. На первом этапе выполняется независимая перестановка 64 разрядов открытого текста. Последний представляет собой обратную перестановку. Предпоследний этап меняет местами левые и правые 32 разряда. Остальные 16 этапов функционально идентичны, но управляются разными функциями входного ключа. Алгоритм был разработан так, чтобы дешифрация выполнялась тем же ключом, что и шифрование. Это обеспечивает соответствие алгоритма принципу симметричных ключей. Этапы при расшифровке просто выполняются в обратном порядке.
Рис. 26. Схема работы функции f
Операция, выполняемая на одном из промежуточных этапов, показана на рис. 26. На каждом этапе из двух порций по 32 разряда на входе формируются две порции по 32 разряда на выходе. Правая половина входа просто копируется в левые разряды выхода. Правые 32 выходных разряда представляют собой сумму по модулю 2 левой части входа и функции правой части входа и ключа данного этапа Кi. Вся сложность шифра заключается в этой функции. Функция состоит из четырех последовательно выполняемых шагов. Сначала из 32 разрядов правой части с помощью фиксированной перестановки и дублирования формируется 48-разрядное число Е. На втором шаге число Е и ключ К( складываются по модулю 2. Затем выход разделяется на восемь групп по шесть разрядов, каждая из которых преобразуется независимым S-блоком в 4-разрядные группы. Наконец, эти 8 * 4 разряда пропускаются через Р-блок.
На каждом из 16 этапов используются различные функции исходного ключа. Перед началом работы алгоритма к ключу применяется 56-разрядная перестановка. Перед каждым этапом ключ разделяется на две группы по 28 разрядов, каждая из которых вращается влево на число разрядов, зависящее от номера этапа. Ключ К, получается из результата этой операции при помощи еще одной перестановки 56 разрядов. На каждом этапе из 56 разрядов ключа выбираются 48 разрядов, которые также переставляются местами.
Иногда для повышения надежности DES используется метод, называемый побелкой. Он заключается в том, что перед передачей шифра каждый блок открытого текста складывается по модулю 2 с произвольным 64-битным ключом, затем отправляется в устройство DES, после чего получившийся шифр складывается по модулю 2 со вторым 64-битным ключом. На приемном конце побелка легко устраняется путем выполнения обратных операций (это возможно, если у получателя есть два побелочных ключа). Поскольку применение этого метода увеличивает длину ключа, полный перебор в пространстве значений ключа становится еще более длительным. Для побелки каждого блока применяется один и тот же ключ (то есть для каждого сообщения имеется только один побелочный ключ).
Стандарт шифрования данных DES был полон противоречий с самого момента его создания. Он основывался на шифре Люцифер (Lucifer), разработанном и запатентованном корпорацией IBM, с той разницей, что IBM использовала 128-разрядный, а не 56-разрядный ключ.
В 1977 году ученые Стэнфордского университета, занимающиеся исследованиями в области криптографии, Диффи (Diffie) и Хеллман (Hellman), разработали машину для взлома кода DES и оценили стоимость ее создания в 20 млн. долларов. По небольшому участку открытого текста и соответствующего ему зашифрованному тексту эта машина путем полного перебора 256 вариантов за один день могла найти 56-разрядный ключ. На сегодняшний день такая машина могла бы стоить около 1 млн. долларов.