Компьютерные сети. 6-е изд. - Эндрю Таненбаум
Шрифт:
Интервал:
Закладка:
Хотя применение квантовой криптографии было продемонстрировано на примере 60-километрового оптоволокна, для этого требуется сложное и дорогое оборудование. В то же время сама идея выглядит многообещающе, особенно если решить проблемы с масштабированием и уровнем необходимых затрат. Чтобы узнать больше о квантовой криптографии, см. работу Клэнси и др. (Clancy et al., 2019).
8.5. Алгоритмы с симметричным ключом
В современной криптографии применяются те же базовые принципы, что и в традиционной (перестановка и подстановка), но акценты расставлены иначе. Когда-то криптографы использовали простые алгоритмы шифрования. Сегодня, напротив, они стремятся создать настолько сложный и запутанный алгоритм, что даже если криптоаналитику попадут в руки целые горы зашифрованного текста, он не сможет извлечь из него никакой пользы без ключа.
Первый класс алгоритмов шифрования, который мы изучим, — алгоритмы с симметричным ключом (symmetric-key algorithms). Их название говорит о том, что для шифрования и дешифрования сообщений применяется один и тот же ключ. На илл. 8.9 показан пример использования алгоритма с симметричным ключом. В частности, мы подробно рассмотрим блочные шифры (block ciphers), которые принимают на входе n-битные блоки открытого текста и преобразуют их с использованием ключа в n-битный шифр.
Криптографические алгоритмы можно реализовать как аппаратно (что повышает скорость их работы), так и программно (для повышения гибкости). Несмотря на то что в основном мы рассматриваем алгоритмы и протоколы вне зависимости от конкретной реализации, в данном случае интересно обсудить шифровальное оборудование. Подстановки и перестановки могут осуществляться при помощи простых электрических цепей. На илл. 8.13 (а) показан P-блок (P означает «permutation» — «перестановка»). Это устройство используется для перестановки восьми входных разрядов. Если пронумеровать входные биты сверху вниз (01234567), выход данного P-блока будет выглядеть как 36071245. При определенной распайке проводов P-блок может выполнить любую операцию перестановки практически со скоростью света, так как никакие вычисления в нем не производятся, он лишь обеспечивает распространение сигнала.
Илл. 8.13. Базовые элементы продукционных шифров: (а) P-блок; (б) S-блок; (в) продукционный шифр
Это соответствует принципу Керкгоффса: взломщик знает, что используется метод перестановки битов, но он не знает, в каком порядке эти биты располагаются.
Подстановки выполняются S-блоками (S означает «substitution» — «подстановка, замена»), как показано на илл. 8.13 (б). В данном примере на вход подается 3-битный открытый текст, а на выходе появляется 3-битный зашифрованный текст. Для каждого входного сигнала выбирается одна из восьми выходных линий декодера путем установки ее в 1. Все остальные линии устанавливаются в 0. Затем эти восемь линий проходят через P-блок, представляющий собой вторую ступень S-блока. Третья ступень производит обратное кодирование одной из восьми линий в 3-битное двоичное число. При таком устройстве проводки восьмеричные числа 01234567 заменяются на 24506713 соответственно. То есть 0 заменяется числом 2, 1 — числом 4 и т.д. Опять же, при соответствующей распайке проводов P-блока внутри S-блока можно реализовать любой вариант подстановки. Помимо этого, P-блок может быть встроен в оборудование и работать на огромных скоростях, поскольку шифраторы и дешифраторы вносят лишь одну или две вентильные задержки (менее 1 нс), а время распространения сигнала внутри P-блока вполне может быть менее 1 пс.
Эффективность этих базовых элементов становится очевидной, если расположить каскадом целый ряд блоков (илл. 8.13 (в)), создав продукционный шифр (product cipher). В нашем примере на первом этапе (P1) 12 входных линий меняются местами. На второй ступени вход разбивается на четыре группы из 3 бит, с каждой из которых операция замены выполняется независимо (S1–S4). Такое расположение позволяет составить большой S-блок из множества мелких. Это хороший способ, так как небольшие S-блоки удобны при аппаратной реализации (к примеру, восьмиразрядный S-блок можно представить в виде 256-разрядной таблицы перекодировки), однако большие S-блоки довольно трудно построить (например, 12-разрядный S-блок потребует минимум 212 = 4096 перекрещенных проводов в средней стадии). Хотя этот метод является лишь частным случаем, он достаточно эффективный. Выход продукционного шифра можно сделать сложной функцией входа, используя достаточно большое количество дополнительных ступеней.
Продукционные шифры, работающие с k-битными входами и производящие k-битные последовательности, широко распространены. В частности, часто применяются шифры с k, равным 256. Аппаратная реализация обычно имеет не семь, как на илл. 8.13 (в), а по крайней мере 20 физических этапов. Программная реализация совершает минимум восемь циклических итераций, каждая из которых производит S-блочные подстановки в подблоках блока данных длиной от 64 до 256 бит, после чего производится перестановка, которая перемешивает результаты S-блоков. Часто также производятся две дополнительные перестановки в начале и в конце. В литературе эти итерации называются раундами.
8.5.1. Стандарт шифрования данных DES
В январе 1977 года правительство США приняло продукционный шифр, разработанный IBM, в качестве официального стандарта для незасекреченной информации. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), широко применялся в промышленности для защиты информации. Хотя в своем исходном виде он уже небезопасен, его модифицированная версия по-прежнему изредка используется. Эффективность исходной версии сомнительна: изначально длина ключа равнялась 128 бит, но после консультаций с АНБ компания IBM «добровольно» уменьшила ее до 56 бит, что, по мнению криптографов, было слишком мало даже для того времени. Алгоритм DES действует практически так же, как показано на илл. 8.13 (в), но использует блоки большего размера. Открытый текст (в двоичном виде) разбивается на 64-битные блоки, каждый из которых шифруется по отдельности путем выполнения перестановок и подстановок, параметризованных 56-битным ключом в каждом из 16 последовательных раундов. По сути, это очень большой моноалфавитный подстановочный шифр на базе алфавита с 64-битными символами (о которых мы поговорим чуть позже).
Уже в 1979 году стало ясно, что 56-битный ключ слишком короткий, и IBM разработала обратно совместимую схему увеличения длины ключа за счет одновременного использования двух 56-битных ключей, что в совокупности давало 112-битный ключ (Такман; Tuchman, 1979). Эта новая схема, названная тройным DES (Triple DES), используется до сих пор (илл. 8.14).
Илл. 8.14. (а) Тройное шифрование с помощью DES. (б) Дешифрование
Возникает два резонных вопроса. Первый: почему здесь используется два, а не три ключа? Второй: для чего выполняется шифрование, дешифрование и затем снова шифрование? Ответ следующий. В случае, когда компьютеру, использующему тройной DES, необходимо связаться с компьютером, на котором
