два базиса, играет важную роль в квантовой криптографии.
В каждом базисе Алиса обозначает одно из направлений нулем, а другое единицей. В нашем примере вертикальному направлению она присвоила значение 0, а горизонтальному — 1. Затем, независимо от этого, для направления «нижний левый — верхний правый» Алиса выбрала значение 0, а для направления «верхний левый — нижний правый» — 1. Она отправляет эти варианты Бобу в виде открытого текста, прекрасно понимая, что ее сообщение может прочитать злоумышленник.
Теперь Алиса составляет одноразовый блокнот, допустим, с помощью генератора случайных чисел (это отдельная сложная тема), и передает его Бобу. Передача производится поразрядно, для каждого бита один из двух базисов выбирается случайным образом. Для передачи бита фотонная пушка испускает один фотон, поляризованный так, чтобы он мог пройти через базис, выбранный для этого бита. Например, базисы могут выбираться в такой последовательности: диагональный, прямолинейный, прямолинейный, диагональный, прямолинейный и т.д. Чтобы с помощью этих базисов передать одноразовый блокнот, состоящий из последовательности 1001110010100110, посылаются фотоны, показанные на илл. 8.12 (а). Для конкретного одноразового блокнота и последовательности базисов поляризация, которая используется для каждого бита, определяется однозначно. Биты, передаваемые одним фотоном за один раз, называются кубитами (qubits).
Боб не знает, какой базис нужно использовать, поэтому он применяет их в случайном порядке для каждого прибывающего фотона; см. илл. 8.12 (б). Если базис для фотона выбран верно, Боб получает правильный бит. В противном случае значение бита будет случайным, так как фотон, проходя через поляризатор, повернутый на 45 градусов относительно его собственной поляризации, с одинаковой вероятностью попадет на направление, соответствующее единице или нулю. Эта особенность фотонов является фундаментальным свойством в квантовой механике. Таким образом, некоторые биты будут получены правильно, некоторые — нет, но Боб не понимает, какие из них корректны. Полученный им результат показан на илл. 8.12 (в).
Илл. 8.12. Пример квантовой криптографии
Чтобы выяснить, какие базисы подставлены правильно, а какие — нет, Боб открытым текстом сообщает Алисе, что именно он использовал при приеме каждого бита. Затем она отвечает ему (также открытым текстом), какие базисы он подобрал верно (илл. 8.12 (г)). Владея этой информацией, Алиса и Боб могут составить битовую строку корректных предположений (илл. 8.12 (д)). В среднем длина этой строки равна половине полной длины исходной строки, но поскольку это знают обе стороны, они могут использовать строку корректных предположений в качестве одноразового блокнота. Все, что Алисе надо сделать, — это передать битовую строку, длина которой немного превышает удвоенную длину одноразового блокнота. Проблема решена.
Но погодите, мы же забыли про Труди! Предположим, что ей очень хочется узнать, о чем говорит Алиса, поэтому она внедряет в линию связи свой детектор и передатчик. К несчастью для Труди, она тоже не знает, через какой базис пропускать каждый фотон. Лучшее, что она может сделать, — это выбрать базисы случайным образом, как Боб (илл. 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 пс.