Квантовая криптография: вчера, сегодня и завтра (часть 1)

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

Терзаемый любопытством, я запрыгнул на парижский скоростной поезд, чтобы совершить путешествие в саму колыбель квантовой криптографии: в Женеву. Именно в Женеве в реальных условиях была продемонстрирована работа алгоритма квантового распределения ключа (quantum key distribution - QKD). Именно в Женеве находится компания Id Quantique, которая специализируется на изготовлении продуктов безопасности, работающих по принципам квантовой физики. Именно Женева – резиденция исследовательского центра квантовой оптики GAP-Optique (при Женевском университете).

Моя цель понять, так что же такое квантовая криптография? Кто покупает QKD-системы? Зачем? Как повсеместное внедрение QKD отразится на противостоянии белых и черных хакеров. Каковы направления будущих исследований QKD?

Квантовый нарушитель

Пока поезд на всех парах мчался к пункту моего назначения, я размышлял (надо сказать, с долей неохоты) о современной криптографии. Существует множество способов защищать информацию, но меня интересовали только коммерческие асимметричные системы. Все криптографические системы можно разделить на два класса: симметричные и асимметричные. В асимметричных системах у меня есть два ключа: один из которых закрытый и я храню его дома под подушкой; второй ключ – открытый. Теперь, чтобы отправить мне зашифрованное сообщение, вам нужно зашифровать его отрытым ключом, я же смогу расшифровать сообщение, воспользовавшись своим закрытым ключом.

Простые числа (Внимание: дальше много математики)

В стойкой асимметричной системе нарушитель не сможет вычислить закрытый ключ, если ему известен только открытый ключ. Алгоритм RSA (названный в честь тройки своих создателей) считается стойкой асимметричной системой. Давайте взглянем, как работает RSA.

Сначала выберем два простых числа p и q, например, p = 13 и q = 17. Перемножив два числа, мы получим pq = 221.

Нам также понадобится второе чиcло: произведение p-1 и q-1, (p-1)(q-1)=192. Теперь в диапазоне от 1 до 192 выберем любое число, которое было бы взаимно простым с 221. Давайте в качестве такого числа возьмем 7.

Для того чтобы вычислить ключи, последовательно будем находить значения выражения (p‑1)(q-1)(1,2,3,…) + 1 до тех пор, пока мы не получим число, которое нацело делится на выбранное ранее число (в нашем случае на 7). При вычислении выражения у нас получится следующий ряд: 193, 385, 578… 385 делится на 7, и в результате дает 55.

Итак, мы получили два ключа: {7, 221} и {55, 221}. Но, не зная простых чисел, перемножением которых получено число 221, нам не удастся вычислить один ключ, зная только другой. Тем не менее, мы знаем произведение простых множителей, так что в качестве варианта можно попробовать факторизовать 221 и найти те самые простые множители.

Оказывается, разложение на множители не такая уж и простая задача. Я написал простенький скрипт, который позволяет узнать, как время нахождения простых множителей зависит от размера факторизируемого числа. Скрипт не оптимизирован и в нем используется метод перебора. Время загрузки Питона и необходимых библиотек ничтожно мало по сравнению со временем работы самого скрипта. Но тут важно скорее не само время работы, а то, насколько быстро время разложения на множители возрастает при увеличении размера факторизуемого числа.

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

Но наше преимущество перед нарушителем заключается в том, что время генерации ключа практически не зависит от размера простых множителей. Следовательно, чтобы сделать факторизацию практически неосуществимой, мы можем просто выбрать простые числа достаточно большой длины. И именно поэтому битовая длина ключей в ассиметричных системах такая большая.

Шор in da house

Питер Шор

Хорошо, мой скрипт действительно не отличается изысканностью. Другие бы попытались, и я не сомневаюсь, нашли бы способ оптимизировать скрипт. Но, так или иначе, никакая оптимизация не спасет от достаточно большой пары простых чисел. И вот тут на сцену выходят квантовые информационные технологии. Шор обнаружил, что на квантовом компьютере задачу разложения на множители можно решить за полиномиальное время. С тех пор алгоритм Шора стал источником развития как технологии QKD, так и классической криптографии.

Так как же работает алгоритм Шора? Скажу по правде, объяснить будет непросто. Ситуация усложняется еще и тем, что хотя я немного и разбираюсь в квантовой механике, к изучению алгоритма я подошел совсем с другой стороны, в отличие от людей, изучающих квантовые информационные технологии на профессиональном уровне. Не нужно и говорить, что алгоритм я опишу на примитивном уровне.

Допустим, у вас есть произведение двух простых чисел, например 221. Будем считать, что 221- это верхняя граница, и целых чисел больших 221 просто нет. Если мы перемножим два числа, и результат будет превышать границу, то в качестве результата мы будем брать целочисленный остаток от деления на 221, например, 15 * 15 = 225 – 221 = 4. Если мы умножим 2 на 2, то получим 4, и никаких дополнительных действий производить не нужно. Мы можем безнаказанно возводить двойку в степень до тех пор, пока не достигнем восьмой степени:2⁸=35. Понятно? Вот и отлично.

С точки зрения физики наша игра с числами будет иметь много общего с тем, как ведут себя волны в оптическом резонаторе. В оптическом резонаторе зеркала повернуты друг к другу отражающими поверхностями и отстоят друг от друга на расстоянии порядка длины волны. Если длина запущенной в резонатор волны чуть больше или чуть меньше, чем нужно, то фаза волны после пробегания от одного зеркала к другому и обратно немного отличается от начальной фазы. В результате происходит своеобразная интерференция волны самой с собой. В конце концов, в резонаторе останутся волны только определенной длины, другие же волны будут подавлены за счет интерференции.

КВАНТОВАЯ СУПЕРПОЗИЦИЯ Квантовая суперпозиция – это не что иное, как сложение волн. Допустим, у нас есть две волны, которые пересекаются во времени и пространстве. В каждой конкретной точке результирующая двух волн может находиться в любом из состоянии между полным погашением волн друг другом или максимальным усилением волн. Суперпозиция говорит нам, как складывать волны, и объясняет ту картину, которую мы можем наблюдать в природе.

Другими словами, любая волна с неподходящей длиной каждый раз получает дополнительную фазу в оптическом резонаторе. Алгоритм Шора преобразует задачу нахождения простых множителей в задачу нахождения дополнительной фазы, которая накапливается волнами при путешествии туда-обратно между зеркалами. Если произведение двух чисел слишком большое или слишком маленькое, то возникает ошибка. В терминах физики, такая ошибка называется фазовой ошибкой, и именно она приводит к деструктивной интерференции.

На практике (в действительности, о практике говорить не приходится, поскольку кроме модели пока ничего нет) в первую очередь с помощью классического алгоритма формируется список потенциальных множителей. Так для числа 221 нам сначала нужно исключить из пар множителей все квадраты (например, 11²), а затем составить множество возможных множителей. Квантовая часть работы алгоритма основывается на том факте, что квантовый бит (кубит) может находиться в суперпозиции нескольких состояний. В отличие от обычного бита, который в конкретный момент времени находится либо в состоянии логической единицы, либо логического нуля, значение кубита лежит между 0 и 1, и представляет собой вероятность того, что кубит находится в состоянии 1 при его измерении.

Затем квантовые операции изменяют вероятность каждого кубита. Регистр из восьми кубитов может представлять каждое значение из диапазона 0-255 одновременно. Но как только вы попытаетесь измерить значение регистра кубитов, вы получите только одно значение, которое зависит от амплитуды вероятности каждого из кубитов.

Во время выполнения алгоритма Шора над кубитами выполняется множество операций, которые приводят к интерференции состояний кубитов. Какая именно произойдет интерференция – конструктивная или деструктивная – зависит от того, является значение регистра множителем, в нашем случае, числа 221, или нет. При деструктивной интерференции вероятность проверяемого числа уменьшается, и, наоборот, при позитивной интерференции, вероятность увеличивается. Теоретически, алгоритм Шора работает намного быстрее всех существующих методов факторизации, так как мы проверяем все возможные множители одновременно.

Давайте посмотрим, как разница в фазах волн может помочь нам найти простые множители: у 221 есть простые множители 17 и 13, а также множители 1 и 221. Последние множители (1 и 221) можно исключить еще в классической части алгоритма. Но, что насчет множителей 2 и 111? “Постойте, – скажите вы. – 2 и 111 не являются множителя 221. Их произведение равно 222.” Тем не менее, мы должны рассмотреть и такой вариант, поскольку квантовые алгоритмы относятся к классу вероятностных. 17 и 13 имеют наивысшую вероятность быть множителя 221, но вероятность фазовой ошибки для множителей 2 и 111 составляет всего 0,5%. Вероятность того, что алгоритм Шора возвратит неверный результат, достаточно велика. К сожалению, в яблочко попасть сложно (хотя и обнаружить “промах” можно довольно легко: перемножив 2 и 111 мы получим 222, а не 221). Нам нужно найти какой-либо способ повысить шансы получения правильного ответа.

Повысить вероятность правильного ответа можно несколькими способами. Во-первых, запустить алгоритм несколько раз, и в качестве правильного ответа выбрать наиболее часто встречающийся результат. Во-вторых, можно использовать выход первого запуска алгоритма в качестве входа для второго запуска. Вспомните о нашем почти правильном ответе (2 и 111). Вероятность фазовой ошибки после одного запуска алгоритма составляла 0,5%. Если мы запустим алгоритм второй раз, то фазовая ошибка накопится и составит уже 1%. Таким образом, после каждого последующего запуска алгоритма вероятность правильного ответа возрастает, а неправильных – уменьшается.

Простите, сэр, ваш квантовый компьютер съел мой пи 

КОГЕРЕНТНОСТЬ С первого взгляда понятие когеренции не вызывает никаких вопросов, но на самом деле все сложнее. Когерентность – это предсказуемость колебательной системы, то, насколько долго мы можем предсказывать состояние колебательной системы в пространстве и времени.

Должен заметить, что алгоритм Шора имеет строгое математическое обоснование, чем, собственно, грешат все современные криптографические алгоритмы. Но почему тогда я использую увертливые словечки и фразы типа “может”, “теоретически работает намного быстрее…”?

До недавних пор никому не удавалось зайти дальше демонстрационных моделей кубита и простых, но бесполезных моделей квантовых компьютеров.

Представьте, что у вас есть кубит в виде иона и вы хотите “обратить” состояние кубита так, чтобы вероятность нахождения в состоянии логической единицы инвертировалась (то есть если до “переворота” вероятность нахождения кубита в состоянии “1” составляла 30%, после “переворота” она составляла бы 70%).

Чтобы осуществить задуманное, нам нужно передать иону определенное количество энергии (или, говоря терминами физики, передать пи-импульс). Для передачи энергии нам понадобится световой луч низкой интенсивности и очень длинные импульсы света (скажем, в несколько микросекунд). Подойдут и менее длинные, но более интенсивные импульсы света: тогда количество операции в единицу времени будет больше.

Но чем выше интенсивность импульса, тем выше шанс, что произойдет что-нибудь нежелательное. Аналогично, чем сильнее мы будем растягивать пружину, тем больше вероятность, что она порвется. Хотя алгоритм Шора и требует гораздо меньше итерации для нахождения простых множителей, каждая итерация может потребовать намного больше времени на свое выполнение. Причем всё время выполнения все кубиты должны оставаться когерентными и находится в состоянии квантовой запутанности.

КВАНТОВАЯ ЗАПУТАННОСТЬ Многие люди неправильно понимают, что такое квантовая запутанность. Запутанность – это редкое и очень кратковременное явление. Квантовая запутанность представляет собой не что иное, как взаимосвязь двух совершенно отдельных квантовых объектов. Вы конечно, можете спросить, так зачем тогда беспокоится попусту насчет этой квантовой запутанности, если она встречается так редко? Ответ на вопрос лежит в недрах квантовой механики.

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

Если вы мельком взгляните на сравнение производительности классического и квантового алгоритмов, то поймете, каким бы медленным ни был квантовый алгоритм, он все равно раскроет ваши секреты задолго до того момента, пока вы состаритесь и умрете. Для 15-значного ключа RSA квантовый алгоритм лишь в два раза быстрее классического алгоритма. Другими словами, если тактовая частота квантового компьютера в 2 раза меньше обычного, то квантовый алгоритм будет работать почти столько же, сколько и его классический соперник. Если длина ключа 100 бит, то квантовый алгоритм превзойдет классический алгоритм уже в 8 раз, а, учитывая, что ключи RSA обычно имеет длину около 2000 бит, преимущество квантового алгоритма будет огромным, в независимости от тактовой частоты квантового компьютера.

Требование поддерживать когерентное состояние и квантовую запутанность имеет под собой твердую физическую основу. В идеале, система, выполняющая алгоритм Шора, должна находиться в когерентном и запутанном состоянии бесконечно долго. Но никто до сих пор не знает, как построить такую систему; множество ученых пытается, и, хотя непреодолимых ограничений нет, ученым придется решить множество проблем, прежде чем они достигнут своей цели.

Принципы работы алгоритма квантового распределения ключей

В основе алгоритма QKD лежит тот факт, что после измерения своего состояния фотон исчезает, другими словами, для измерения состояния, фотон должен быть поглощен детектором. В качестве примера рассмотрим ситуацию, когда Алиса и Боб хотят установить защищенный канал так, чтобы нарушитель Ева не смогла им помешать. В первую очередь Алисе и Бобу нужно сгенерировать закрытый ключ по законам квантовой физики. В дальнейшем закрытый ключ будет использоваться для шифрования сообщений.

ПОЛЯРИЗАЦИЯ Поляризация – более сложный синоним слова “ориентация”. Мы намеренно не используем термин “ориентация”, потому что термин “поляризация” позволит избежать нам громоздких объяснений. Термин “поляризация” имеет более широкое значение, им также называют ориентацию спина электрона, протона и нейтрона.

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

Затем Алиса отсылает фотоны Бобу, а Боб, в свою очередь, измеряет их. Но по правилам квантовой механики вы не можете просто спросить у фотона: “Какая у тебя поляризация?”. Вы должны задать вопрос по-другому: “Как ты поляризован: вертикально или горизонтально?”. Поэтому Боб выбирает между двумя базисами; и когда-то он спрашивает, какую именно из диагональных поляризаций имеет фотон, а когда-то, вертикальную или горизонтальную.

Если Алиса отправила Бобу вертикально поляризованный фотон, а Боб спросил у фотона, какую из диагональных поляризаций он имеет, то фотон будет случайно выбирать между ответами в 45 градусов и 135 градусов. Если же Алиса отправит горизонтально поляризованный фотон, а Боб спросит, поляризован ли фотон горизонтально или вертикально, то фотон всегда ответит, что он поляризован горизонтально. Другими словами, выбор базиса измерения влияет на ответ фотона. Если Алиса и Боб сделают одинаковый выбор, то фотон будет находиться либо в одном, либо в другом состоянии. Если же выбор базиса различался, то фотон, с точки зрения Боба, будет в суперпозиции двух состояний. Получается, что в первом случае процесс измерения детерминистический. Зная настройки своего оборудования, Алиса и Боб могут точно предугадать, какой из детекторов Боба сработает. Во втором случае, во время процесса измерения фотон случайным образом выбирает между двумя состояниями; и ни Алиса, ни Боб не могут точно предугадать результат измерений. Безопасность алгоритма QKD как раз и основывается на “непредсказуемости” фотона, и если нарушитель Ева попытается внедриться в процесс генерации ключа, то эта “непредсказуемость” будет только увеличиваться.

После того, как все фотоны получены, Боб располагает строкой из случайных чисел, но он понятия не имеет, какие именно числа понадобятся для генерации ключа. Для создания общего ключа Алиса и Боб открыто говорят о том, какой именно базис они выбрали для каждого бита, но выбор поляризации по-прежнему хранят в секрете. Алиса и Боб могут сравнить, в каких позициях они сделали одинаковый выбор. Биты, находящиеся в совпадающих позициях и используются для создания общего ключа.

Следующим шагом необходимо выяснить, вмешивалась ли Ева в процесс генерации ключа. Чтобы обнаружить нарушителя, Алиса публикует некоторый участок закрытого ключа. Как же тогда можно обнаружить Еву? Допустим, что Ева перехватывала фотоны, случайно выбирала базис и измеряла поляризацию перехваченного фотона. Но Ева не знает, какой именно базис выбрала Алиса. Когда Ева пытается воссоздать состояние фотона Алисы, Ева ошибается примерно в половине случаев. Следовательно, количество совпадений между Алисой и Бобом уменьшится вдвое. Ева, конечно, может схитрить, и перехватывать каждый второй фотон; количество совпадений между Алисой и Бобом тогда останется примерно тем же. Но чем меньше фотонов перехватывает Ева, тем меньше информации о ключе она получает.

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

Один фотон, по требованию.

Хотя путешествие из Парижа в Женеву было быстрым и комфортабельным, мой визит в компанию ID Quantique не задался с самого начала: я потерялся, и мне пришлось перенести встречу с компанией. ID Quantique – это небольшая, женевская компания, офис которой скорее похож на лабораторию. Повсюду пирамиды из ящиков, а само помещение пропитано атмосферой, будто бы говорящей ”мы слишком заняты, чтобы думать о чем, то кроме выпуска нашего продукта”.

Одной из наиболее интересующих меня вещей было то, какой источник света используется при генерации ключа. Насколько я понял из принципов работы QKD, для того, чтобы Ева не смогла перехватить ключ, требуется источник одиночных фотонов. Но источники одиночных фотонов имеют множество недостатков: они ненадежны, они производят недостаточное количество фотонов в секунду, и достаточно трудно убедиться, что фотоны перемещаются в правильном направлении.

Ответ Мэтью Легрэ был прост: “Мы используем источник псевдо одиночных фотонов”. Я был шокирован ответом, поскольку источник псевдо фотонов - это лазер, аттенюатор которого помещен в поток света таким образом, что большинство света поглощается. Можно настроить источник так, что в каждый конкретный отрезок времени будет испускаться только один фотон. Но статистика когерентного источника говорит, что если лазер испускает одиночный фотон, то, скорее всего, лазер сразу же испустит и второй фотон. Другими словами, не существует способа убедиться, что в определенный отрезок времени будет испущен только один фотон. Так как же будет работать QKD в таких условиях?

Легрэ пустился в объяснения. Представьте, что мы уменьшим мощность нашего лазера так, что 90% всего времени света в оптоволокне вообще не будет, 9% времени в оптоволокне будет всего один фотон, и в оставшееся время – больше одного фотона. При таких условиях, если Ева решит перехватить ключ, то незаметно для Алисы и Боба Еве удастся получить несколько бит ключа.

Но существует уловка, позволяющая решить проблему перехвата. Представьте, что у нас есть очень слабый источник фотонов, и Ева способна перехватить 5% всех битов, переданных по каналу. При передаче последовательности из 160 бит, Ева получит 8 бит, и, поскольку значение каждого бита статистически независимо, мы можем с высокой долей уверенности сказать, что в двух случаях Ева будет знать значение пары смежных битов. Теперь, если Алиса и Боб выполнят математическую операцию над всеми парами битов, то длина последовательности уменьшится до 80 бит.

В исходной последовательности Ева знала 5% битов, но теперь, после уменьшения последовательности, она знает всего 2 бита из 80 или 2,5% ключа. В действительности, все даже намного лучше, потому что мы не знаем точно, с какой именно позиции в исходной последовательности Алиса и Боб начали производить математическую операцию. Следовательно, для каждой из двух битовых пар, вероятность того, что Ева знает оба бита из пары, составляет 50%. Другими словами, Ева знает 2.5% ключа с 25% вероятностью, и 1.25% ключа с 50% вероятностью.

Операция усечения последовательности, называемая также усилением секретности, может выполняться несколько раз. На каждом шаге длина ключа уменьшается вдвое, а информация, которую получила Ева из исходной последовательности, становится все менее и менее точной. Тогда мы можем сначала сгенерировать ключ, длина которого много больше необходимой, а затем уменьшить его до ключа, который все же будет достаточно длинным для предотвращения атаки перебором. В таком случае процесс генерации ключа станет более безопасным.

Но здесь нужно сказать еще об одной очень важной вещи. Количество бит, которые сможет получить нарушитель и количество необходимых усечений последовательности сильно зависит от статистических параметров источника света. Поэтому важно с высокой точностью измерить статистику фотонов в источнике света.   

Продолжение следует...