Криптография

Как работает криптография? На чем основаны классические криптографические алгоритмы? Какие у них бывают уязвимости и как квантовые технологии способны изменить положение дел в данной области? Что такое квантовая криптография, и какие новые возможности она несет, а также как обстоят дела с их практической реализацией сегодня – об этом рассказ Дмитрия Кронберга, кандидата физико-математических наук, сотрудника отдела математических методов методов квантовых технологий Математического института им. В. А. Стеклова Российской академии наук.

Стенограмма записи (выполнена с использованием систем распознавания речи):

Криптография – это наука о защите данных от прослушивания. Технически, как правило, в криптографии перехватчика (того кто хочет получить несанкционированный доступ к данным) ставят перед сложной задачей. Обычно это математически сложная задача, вычислительно сложная.

Известной сложной задачей является задача факторизации чисел. Все мы знаем из школы, что числа можно перемножить в столбик. Это быстрый алгоритм перемножения двух чисел. Вот также можно разделить одно число на известное число. Эта обратная операция тоже выполняется в столбик, довольно быстро. Однако, если нам не известны сомножители, то разложить число на простые множители мы быстро не можем. Это очень сложная операция, которая требует либо перебора очень большого количества чисел, либо другие более сложные операции. Но их всё равно оказывается очень много. Быстрых алгоритмов разложения числа на простые сомножители ещё не предъявлено, поэтому в самой известной криптографической схеме RSA перехватчик ставится именно перед этой задачей, – разложить числа на простые сомножители. Зная некоторые дополнительные секреты, легитимные пользователи могут это сделать. Однако перехватчик этого сделать не может за обозримое время. И поэтому эта схема является секретной. 

Тем не менее, классическая криптографии стоит перед некоторыми угрозами. Угроза заключается в том, что мы всё-таки когда-нибудь найдём алгоритм, например, быстрого разложения числа на простые сомножители. И наша задача, которая нам казалась сложной в течение многих десятилетий, окажется не сложной. Или у нас так сильно разовьется вычислительная техника, что некоторые алгоритмы, которые были связаны со сложностью решения некоторых задач перебором большого количества вариантов, окажутся не секретными. Как это произошло, например, с криптографической схемой DES, которая была предложена в семидесятые годы. Но затем компьютеры стали намного мощнее и к середине 90-х эта схема потеряла свою секретность. Более того – в девяносто четвёртом году был предложен алгоритм факторизации чисел на квантовом компьютере, который показал, что если у перехватчика есть квантовый компьютер, то он может за очень небольшое количество действий (относительно классического разложения чисел на сомножители) решить задачу разложения чисел на простые сомножители. Это происходит не потому, что квантовый компьютер быстро работает, а потому что ему нужно меньше операций для того, чтобы решить эту задачу. Это очень сильно увеличило интерес к созданию квантового компьютера.
Алгоритм RSA настолько распространен, что только ради взлома RSA стоит разрабатывать квантовый компьютер. Помимо этого сообщество заинтересовалось альтернативными способами шифрования, альтернативными способами обеспечения секретности. 

Один из этих способов это квантовая криптография, которая была предложена еще в 1984 году. Правда, первые семь лет этому уделялось мало внимания. Она (квантовая криптография) использует тоже сложную задачу, которая в принципе не решаема. Это задача получения информации из неортогональных квантовых состояний. Задача, которую никто не может решить. Принципиально запрещено получать полную информацию из неортогонального набора квантовых состояний и это используется в квантовой криптографии.

Важный принцип в квантовой механике – принцип неопределенности Гейзенберга, который в своей наиболее известной формулировке говорит о том, что мы не можем достоверно измерить и координату и импульс некоторой частицы. 

Мы можем приготовить частицу с известным значением координат. И если мы измерим координаты, то получим заранее определенное значение. Однако если мы у этой частицы будем измерять импульс, то получим любое произвольное число, которое заранее никак предсказать не можем. Точно так же мы можем (заранее) измерить импульс этой частицы (приготовив частицу с известным импульсом). Измерив импульс, мы получим заранее известное значение. Однако, если измерим координату этой частицы, то получим тоже произвольное число, которое никак нами не предсказуемо.
Измерить одновременно координату и импульс мы не можем. И это не потому что у нас  плохие измерительные приборы, а потому что не существует частиц с определённой координатой и импульсом одновременно. Похожий принцип используется в квантовой криптографии. Можно это проиллюстрировать так. Пусть у нас есть четыре возможных состояний частицы. Два из них имеют определенную координату. И мы можем их различить измерением, которое различает координату. А два других состояния имеют определенный импульс, и мы можем их различить тем изменением, которое определяет импульс. Однако, если мы измерение, различающее координаты, применим к двум последним состояниям с определенным импульсом, мы их никак не различим. Что для первого, что для второго значения импульсов это будет абсолютно произвольное число, никак не связанное с состоянием системы. Точно также, если у системы определенный импульс, а мы измеряем его координату, мы никакой полезной информации о координате получить не сможем. Соответственно, если у нас четыре сигнала описываются известными значениями координаты и импульса, то мы не сможем получить достоверную информацию о каждом из этих четырёх сигналов. У нас обязательно будет какая-то неопределенность. Полную информацию мы извлечь не сможем. И это ключевой важнейший запрет для квантовой криптографии.
Более того, вообще любое измерение квантовой системы – это взаимодействие с системой. И система после этого меняется. Когда мы измеряем частицу, например, мы измерили импульс частицы, получили некоторое число. Если мы эту же частицу сразу же померяем ещё раз (импульс частицы), то мы получим ровно то же значение импульса, потому что после измерения импульса частица перешла в собственное состояние. Это состояние – система с определенным импульсом, который померился. Мы испортили частицу измерением. При измерении у нас есть, грубо говоря, только одна попытка измерить эту систему. Других попыток у нас нет. И если перехватчик несанкционированно пытается измерить нашу частицу, он нарушит состояние частицы. И по тому, насколько изменённое состояние пришло на приёмную сторону, мы можем понять – насколько много информации получил перехватчик.
Вот я рассказал про принцип неопределённости для координаты и импульса. Но не только эти характеристики удовлетворяют соотношениям неопределённостей. Это ещё и энергия, и время, это ещё и фаза, и интенсивность состояния в квантовой оптике.
А вот то, что используется в оригинальном протоколе квантовой криптографии BB84, который был предложен Беннетом и Брассаром в 1984 году, – это поляризация вдоль разных осей фотона. Мы можем приготовить фотон с поляризацией вертикальной или горизонтальной и эти две поляризации мы прекрасно различим, – для этого существуют измерения. Можно приготовить фотон с диагональной и антидиагональной поляризацией и эти две поляризации мы тоже можем прекрасно различить, – для этого тоже есть прибор. Однако, если мы первый прибор для измерения поляризации вертикальной или горизонтальной применим к диагональным поляризациям, то мы не получим никакой полезной информации. Аналогично, если мы будем применять прибор для измерения диагональной поляризации к вертикальной и горизонтальной поляризации, – мы тоже не получим никакой полезной информации. Все четыре возможных состояния (вертикальные, горизонтальные и диагональные, антидиагональные поляризации) мы их различить не сможем никак. Это принципиально запрещено в квантовой механике. И это используют в квантовой криптографии в протоколе BB84. Легитимные пользователи тоже не могут достоверно различить все четыре состояния. Однако, у них есть очень хорошая возможность потом поговорить по открытому  каналу, который может всеми прослушиваться, в том числе перехватчиком, но информацию в этом открытом канале перехватчик изменять не может. Они говорят по открытому каналу и приёмная сторона – Боб – говорит, какое измерение он использовал (он использовал первый прибор, который отличает вертикальную поляризацию от горизонтальной, или он использовал второй прибор, который отличает диагональную и антидиагональную поляризацию). Если Алиса, которая передаёт информацию (обычно в криптографии Алиса передаёт информацию Бобу, а Ева – это перехватчик который подслушивает эту информацию). Так вот, если Алиса использовала тот же базис для приготовления состояний, тот же набор векторов, тогда она говорит: “Отлично, ты получил всю информацию, мы оставляем эту посылку.” Если получилось так, что Алиса использовала один набор векторов, один базис, например, вертикальную или горизонтальную поляризацию, а Боб измерял диагональную-антидиагоналную поляризацию, то никакой полезной информации они друг другу передать не могли и они эту посылку могут отбросить. Вот это действие доступно легитимным пользователям – они могут поговорить друг с другом и отбросить посылки, где у них плохая передача информации. И это действие недоступное перехватчику. С перехватчиком никто по телефону не будет связываться, никто не будет отбрасывать посылки, где у перехватчика не получилось извлечь информацию. Поэтому перехватчик оказывается в проигрышной позиции по сравнению с легитимными пользователями. Поэтому он вообще имеет меньше информации. Если перехватчик очень агрессивно измерял все состояния, то он нарушил состояния, которые переписывались. И по величине ошибки, которую могут оценить легитимные пользователи, они могут понять, сколько информации перехватчик получил о сигнале. Если эта информация велика, если она больше, чем информация легитимных пользователей, тогда выполнение протокола невозможно. Они прекращают выполнение протокола и считают этот ключ не секретным. Если же ошибка невелика, то Алиса и Боб знают больше, чем знает перехватчик. И в этом случае они могут сжать ключ так, чтобы о сжатом ключе перехватчик уже ничего не знал. То есть они могут исправить свои ошибки во-первых, а во-вторых, они могут усилить секретность, то есть они могут уменьшить длину своего ключа, но так, что о сжатом ключе перехватчик уже не будет знать вовсе ничего.
Таким образом, квантовая криптография решает очень важную задачу о распределении секретных ключей. То есть это не передача данных пока что между Алисой и Богом происходит, а распределение секретного ключа, который неизвестен никому, кроме Алисы и Боба. После этого, уже с помощью классических методов криптографии, они могут передать полностью секретную информацию. Например, в режиме одноразового шифроблокнота. Это абсолютно стойкая криптографическая система, которая требует распределения ключа между легитимными пользователями. И эта задача решается именно квантовой криптографией.