Квантовый протокол распределения ключей BB84

в 22:44, , рубрики: BB84, квантовая криптография, криптография, учебник

Данный текст будет являться новой главой для учебного пособия по защите информации кафедры радиотехники и систем управления МФТИ (ГУ). Полностью учебник доступен на github. На хабре я же планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам.

В 1984 году Чарлз Беннет (англ. Charles Henry Bennett) и Жиль Брассар (фр. Gilles Brassard) предложили новый квантовый протокол распределения ключа. Как и другие протоколы его целью является создание нового сеансового ключа, который в дальнейшем можно использовать в классической симметричной криптографии. Однако особенностью протокола является использование отдельных положений квантовой физики для гарантии защиты получаемого ключа от перехвата злоумышленником.

До начала очередного раунда генерации сеансового ключа предполагается, что у Алисы и Боба, как участников протокола, имеется:

  • квантовый канал связи;
  • классический канал связи.

Протокол гарантирует, что вмешательство злоумышленника в протокол можно заметить вплоть до тех пор, пока злоумышленник не сможет контролировать и на чтение, и на запись все каналы общения сразу.

Протокол состоит из трёх частей:

  • передача и приём фотона по квантовому каналу связи от Алисы к Бобу;
  • передача Бобом информации об использованных анализаторах;
  • передача Алисой информации о совпадении выбранных анализаторов и исходных поляризаций.

Генерация фотона

В первой части протокола с точки зрения физика-экспериментатора Алиса берёт единичный фотон и поляризует под одним из четырёх углов: 0, 45, 90 или 135. Будем говорить, что Алиса сначала выбрала базис поляризации («+» или «×»), а затем выбрала в этом базисе одно из двух направлений поляризации:

  • 0 («$rightarrow$») или 90 («$uparrow$») в первом базисе;
  • 45 («$nearrow$») или 135 («$nwarrow$») во втором базисе.

С точки зрения квантовой физики мы можем считать, что у нас есть система с двумя базовыми состояниями $|0rangle$ и $|1rangle$. Состояние системы в любой момент времени можно записать как $| psi rangle=cos alpha |0rangle + sin beta |1rangle$. Так как четыре выбранных Алисой возможных исходных состояния неортогональны между собой (точнее, не все попарно), то из законов квантовой физики следует два важных момента:

  • невозможность клонировать состояние фотона;
  • невозможность достоверно отличить неортогональные состояния друг от друга.

С точки зрения специалиста по теории информации можем считать, что у Алиса использует две независимые случайные величины XA и A с энтропией по 1 бит каждый, чтобы получить новую случайную величину YA=XA+A, передаваемую в канал связи.

H(A) = 1 бит, выбор базиса поляризации («+» или «×»)
H(X) = 1 бит, само сообщение, выбор одного из двух направлений поляризации в базисе.
H(YA) = H(X) + H(A) = 2 бит, посылаемое сообщение.

Действия злоумышленника

Как физик-экспериментатор Ева может попытаться встать посередине канала и что-то с фотоном сделать. Может попытаться просто уничтожить фотон или послать вместо него случайный. Хотя последнее приведёт к тому, что Алиса и Боб не смогут сгенерировать общий сеансовый ключ, полезную информацию Ева из этого не извлечёт.

Ева может попытаться пропустить фотон через один из поляризаторов и попробовать поймать фотон детектором. Если бы Ева точно знала, что у фотона может быть только два ортогональных состояния (например, вертикальная «$uparrow$» или горизонтальная «$rightarrow$» поляризация), то она могла бы вставить на пути фотона вертикальный поляризатор «$uparrow$» и по наличию сигнала на детекторе определить, была ли поляризация фотона вертикальной (1, есть сигнал) или горизонтальной (0, фотон через поляризатор не прошёл и сигнала нет). Проблема Евы в том, что у фотона не два состояния, а четыре. И никакое положение одного поляризатора и единственного детектора не поможет Еве точно определить, какое из этих четырёх состояний принимает фотон. А пропустить фотон через два детектора не получится. Во-первых, если фотон прошёл вертикальный поляризатор, то какой бы исходной у него не была поляризация («$nwarrow$», «$uparrow$», «$nearrow$»), после поляризатора она станет вертикальной «$uparrow$» (вторая составляющая «сотрётся»). Во-вторых, детектор, преобразуя фотон в электрический сигнал, тем самым уничтожает его, что несколько затрудняет его дальнейшие измерения.

Кроме того, двух или даже четырёх детекторов для одного фотона будет мало. Отличить между собой неортогональные поляризации «$uparrow$» и «$nearrow$» можно только статистически, так как каждая из них будет проходить и вертикальный «$uparrow$», и диагональный «$nearrow$» поляризаторы, но с разными вероятностями (100% и 50%).

С точки зрения квантовой физики Ева может попытаться провести измерение фотона, что приводит к коллапсу волновой функции (или же редукции фон Неймана) фотона. То есть после действия оператора измерения на волновую функцию фотона она неизбежно меняется, что приведёт к помехам в канале связи, которые могут обнаружить Алиса и Боб. Невозможность достоверно отличить неортогональные состояния мешают Еве получить полную информацию о состоянии объекта, а запрет клонирования мешает повторить измерение с дубликатом системы.

С точки зрения теории информации мы можем рассмотреть фактически передаваемое состояние фотона как некоторую случайную величину YA. Ева использует случайную величину E (выбор пары ортогональных направлений поляризатора – «+» либо «×») для получения величины YE как результата измерения YA. При этом для каждого заданного исходного состояния Ева получает на выходе:

  • аналогичное состояние с вероятностью 50% (вероятность выбора пары ортогональных направлений поляризатора, совпадающих с выбранной Алисой);
  • одно из двух неортогональных оригинальному состояний с вероятностью 25% каждое.

Таким образом условная энтропия величины Y', измеренной Евой, относительно величины Y, переданной Алисой, равна:

$H left( Y_E | Y_A right)=- frac{1}{2} log_2 frac{1}{2} - frac{1}{4} log_2 frac{1}{4} - frac{1}{4} log_2 frac{1}{4}=1,5~~text{бит}$

И взаимная информация между этими величинами равна:

$I left( Y_E ; Y_A right)=H left( Y_E right) - H ( Y_E | Y_A )=0,5 ~~text{бит}.$

Что составляет 25% от энтропии передаваемой по каналу случайной величины Y.

Если рассматривать величину XE, которую Ева пытается восстановить из YE, то с точки зрения теории информации ситуация ещё хуже:

  • при угаданной паре ортогональных направлений поляризатора с вероятностью 50% получаем исходную величину в половине случаев;
  • при неугаданной паре ещё в четверти случаев также получаем исходную величину (из-за случайного прохождения фотона через «неправильный» поляризатор).

Получается, что условная энтропия восстанавливаемой Евой последовательности XE относительно исходной XA равна:

$H left( X_E | X_A right)=- frac{3}{4} log frac{3}{4} – frac{1}{4} log frac{1}{4} ≈ 0,81~~text{бит}. $

И взаимная информация

$I left( X_E; X_A right)=H left( X_E right) - H left( X_E | X_A right) approx 0,19~~text{бит}.$

Что составляет ≈19% от энтропии исходной случайной величины XA.

Оптимальным алгоритмом дальнейших действий Евы будет послать Бобу фотон в полученной поляризации (передать далее в канал полученную случайную величину YE). То есть если Ева использовала вертикальный поляризатор «$uparrow$», и детектор зафиксировал наличие фотона, то передавать фотон в вертикальной поляризации «$uparrow$», а не пытаться вводить дополнительную случайность и передавать «$nwarrow$» или «$nearrow$».

Действия легального получателя

Боб, аналогично действиям Евы (хотя это скорее Ева пытается имитировать Боба), случайным образом выбирает ортогональную пару направлений поляризации («+» либо «×») и ставит на пути фотона поляризатор («$uparrow$» или «$nwarrow$») и детектор. В случае наличия сигнала на детекторе он записывает единицу, в случае отсутствия – ноль.

Аналогично Еве, можно сказать, что Боб вводит новую случайную величину B (отражает выбор базиса поляризации Бобом) и в результате измерений получает новую случайную величину XB. Причём Бобу пока неизвестно, использовал ли он оригинальный сигнал YA, переданный Алисой, или же подложный сигнал YE, переданный Евой:

  • XB1 = f ( YA, B );
  • XB2 = f ( YE, B ).

Далее Боб сообщает по открытому общедоступному классическому каналу связи, какие именно базисы поляризации использовались, а Алиса указывает, какие из них совпали с изначально выбранными. При этом сами измеренные значения (прошёл фотон через поляризатор или нет) Боб оставляет в секрете.

Можно сказать, что Алиса и Боб публикуют значения сгенерированных ими случайных величин A и B. Примерно в половине случаев эти значения совпадут (когда Алиса подтверждает правильность выбора базиса поляризации). Для тех фотонов, у которых значения A и B совпали, совпадут и значения XA и XB1. То есть

  • H ( XB1 | XA; A = B ) = 0 бит
  • I ( XB1; XA | A = B ) = 1 бит

Для тех фотонов, для которых Боб выбрал неправильный базис поляризации, значения XB1 и XA будут представлять собой независимые случайные величины (так как, например, при исходной диагональной поляризации фотона он пройдёт и через вертикальную, и через горизонтальную щель с вероятностью 50%):

  • H ( XB1 | XA; A ≠ B ) = 1 бит
  • I ( XB1; XA | A ≠ B ) = 0 бит

Рассмотрим случай, когда Ева вмешалась в процесс передачи информации между Алисой и Бобом и отправляет Бобу уже свои фотоны, но не имеет возможности изменять информацию, которой Алиса и Боб обмениваются по классическому каналу связи. Как и прежде, Боб отправляет Алисе выбранные базисы поляризации (значения B), а Алиса указывает, какие из них совпали с выбранными ею значениями A.

Но теперь, для того, чтобы Боб получил корректное значение XB2 (XB2 = XA), должны быть выполнены все следующие условия для каждого фотона:

  • Ева должна угадать базис поляризации Алисы (E = A)
  • Боб должен угадать базис поляризации Евы (B = E)

Рассмотрим, без ограничения общности, вариант, когда Алиса использовала диагональную поляризацию «×»:

Базис поляризации, использованный Алисой Базис поляризации, использованный Евой Базис поляризации, использованный Бобом результат
«×» «×» «×» принято без ошибок
«×» «×» «+» не принято
«×» «+» «×» принято с ошибками
«×» «+» «+» не принято

При этом Боб и Алиса будут уверены, что в первом и третьем случае (которые с их точки зрения ничем не отличаются), Боб корректно восстановил поляризацию фотонов. Так как все эти строки равновероятны, то получается, что у Боба и Алисы после выбора только фотонов с “угаданным” базисами (как они уверены) только половина поляризаций (значений XA и XB2) будет совпадать. При этом Ева будет эти значения знать. Количество известных Еве бит “общей” последовательности и доля ошибок в ней находятся в линейной зависимости от количества перехваченных Евой бит.

Вне зависимости от наличия или отсутствия Евы Алиса и Боб вынуждены использовать заранее согласованную процедуру исправления ошибок. Используемый код коррекции ошибок, с одной стороны, должен исправлять ошибки, вызванные физическими особенностями квантового канала. Но с другой стороны, если код будет исправлять слишком много ошибок, то он скроет от нас потенциальный факт наличия Евы. Доказано, что существуют такие методы исправления ошибок, которые позволяют безопасно (без опасности раскрыть информацию Еве) исправить от 7,5% (Майерз, 2001) до 11% ошибок (Ватанабе, Матсумото, Уйематсу, 2005).

Интересен также вариант, когда Ева может изменять информацию передаваемую не только по оптическому, но и по классическому каналам связи. В этом случае многое зависит от того, в какую сторону (от чьего имени) Ева может подделывать сообщения. В самом негативном сценарии, когда Ева может выдать себя и за Алису, и за Боба, будет иметь место полноценная атака “человек-посередине” (англ. Man-in-the-Middle), от которой невозможно защититься никаким способом, если не использовать дополнительные защищённые каналы связи, или не основываться на информации, переданной заранее. Однако, это будет уже совсем другой протокол.

Подводя итоги, квантовые протоколы распределения ключей (а именно ими пока что и ограничивается вся известная на сегодняшний день «квантовая криптография»), обладают как определёнными особенностями, так и фатальными недостатками, затрудняющими их использование (и ставящее под вопрос саму эту необходимость):

  • Любые квантовые протоколы (как и вообще любые квантовые вычисления) требуют оригинального дорогостоящего оборудования, которое пока что нельзя сделать частью commodity-устройств или обычного сотового телефона.
  • Квантовые каналы связи это всегда физические каналы связи. У них существует максимальная длина канала и определённый уровень ошибок. Для квантовых каналов (на сегодняшний день) не придумали «повторителей», которые бы позволили бы увеличить длину безусловно квантовой передачи данных.
  • Ни один квантовый протокол (на сегодняшний день) не может обходиться без дополнительного классического канала связи. Для такого связи требуются как минимум такой же уровень защиты, как и при использовании, например, криптографии с открытым ключом.
  • Для всех протоколов особую проблему представляет не только доказательство корректности (что является весьма нетривиальным делом в случае наличия «добросовестных» помех), но и инженерная задача по реализации протокола в «железе». В качестве краткой иллюстрации, например, не существует простого способа создать ровно один фотон. Недогенерация фотонов приводит, очевидно, к ошибкам передачи, а генерация дубля в том же временном слоте — к возможностью его перехвата злоумышленником без создания помех в канале.

Автор: Сергей Владимиров

Источник

Поделиться

* - обязательные к заполнению поля