Но погодите, мы же забыли про Труди! Предположим, что ей очень хочется узнать, о чем говорит Алиса, поэтому она внедряет в линию связи свой детектор и передатчик. К несчастью для Труди, она тоже не знает, через какой базис пропускать каждый фотон. Лучшее, что она может сделать, — это выбрать базисы случайным образом, как Боб (илл. 8.12 (е)). Когда Боб открытым текстом сообщает Алисе, какие базисы он использовал, а та отвечает ему, какие из них верны, Труди, как и Боб, узнает, какие биты она угадала, а какие — нет. Как видно из рисунка, базисы Труди совпали с базисами Алисы в позициях 0, 1, 2, 3, 4, 6, 8, 12 и 13. Однако из ответа Алисы (илл. 8.12(г)) ей становится известно, что в одноразовый блокнот входят только биты 1, 3, 7, 8, 10, 11, 12 и 14. Четыре из них (1, 3, 8 и 12) были угаданы правильно, Труди их запоминает. Остальные биты (7, 10, 11 и 14) не были угаданы, и их значения остаются для Труди неизвестными. Таким образом, Бобу известен одноразовый блокнот, начинающийся с последовательности 01011001 (илл. 8.12 (д)), а все, что досталось Труди, — это обрывок 01?1??0? (илл. 8.12 (ж)).
Конечно, Алиса и Боб осознают, что Труди пытается захватить часть их одноразового блокнота, поэтому они стараются уменьшить количество информации, которая может ей достаться. Для этого они могут внести дополнительные изменения. Например, одноразовый блокнот можно поделить на блоки по 1024 бита и возвести каждый из блоков в квадрат, получая, таким образом, числа длиной 2048 бит. Затем можно использовать конкатенацию 2048-битных чисел в качестве одноразового блокнота. Имея лишь часть битовой строки, Труди никогда не сможет проделать эти преобразования. Действия над исходным одноразовым блокнотом, уменьшающие долю информации, получаемой Труди, называются усилением секретности (privacy amplification). На практике вместо поблочного возведения в квадрат применяются сложные преобразования, в которых каждый выходной бит зависит от каждого входного.
Бедная Труди. Помимо того что она не представляет, как выглядит одноразовый блокнот, она понимает, что ее присутствие ни для кого не секрет. В конечном итоге ей приходится передавать каждый принятый бит Бобу, чтобы он думал, будто разговаривает с Алисой. Проблема в том, что лучшее, что может сделать Труди, — это передавать каждый принятый квантобит с использованием поляризации, с помощью которой он был принят ею. При этом примерно в половине случаев поляризация будет неправильной, что приведет к появлению множества ошибок в одноразовом блокноте Боба.
Когда, наконец, Алиса начинает отправлять данные, она шифрует их, используя сложный код с упреждающей коррекцией ошибок. С точки зрения Боба, ошибка в одном бите одноразовой последовательности — это то же самое, что ошибка передачи данных, произошедшая в одном бите. В любом случае результат состоит в получении неправильного значения бита. С помощью упреждающей коррекции ошибок, возможно, удастся восстановить потерянную информацию, но помимо этого можно посчитать ошибки. Если их количество намного превышает ожидания (связанные с вероятностью возникновения ошибок оборудования), становится очевидно, что линию прослушивает Труди, и Боб может принять меры (например, сказать Алисе, чтобы она переключилась на радиоканал, вызвать полицию и т.д.). Если бы Труди могла скопировать фотон и обработать свою копию, а исходный фотон переслать Бобу в неизменном виде, у нее был бы шанс остаться незамеченной, но на сегодняшний день методы клонирования фотонов отсутствуют. Но даже если Труди удастся получить копию фотона, это никак не уменьшит значение квантовой криптографии в создании одноразовых блокнотов.
Хотя применение квантовой криптографии было продемонстрировано на примере 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 перекрещенных проводов в средней стадии). Хотя этот метод является лишь частным случаем, он достаточно эффективный. Выход продукционного шифра можно сделать сложной функцией входа, используя достаточно большое количество дополнительных ступеней.