По словам Филиппа Циммермана (см. «Безопасность для всех» на стр. 108), в «Книге кодов» Саймона Сингха говорится: «Современная криптография дает возможность создать такой шифр, который неуязвим ни для каких существующих форм криптоанализа». Как мы уже отмечали, даже самым быстрым компьютерам не под силу взломать методом перебора всех возможных вариантов такие алгоритмы шифрования, как RSA или DES, и даже такие системы, как, например, PGP. Может, какие-то математические лазейки позволят злоумышленникам упростить криптоанализ? Хотя исключить это предположение нельзя, считается, что такое маловероятно.

Прав ли Циммерман? Разрешился ли длившийся тысячелетиями конфликт между криптографами и криптоаналитиками?

Квантовые вычисления

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

Эта новая техническая революция основана на квантовой механике — теоретической науке, построенной в начале прошлого века такими учеными, как датчанин Нильс Бор (1885–1962), англичанин Поль Дирак (1902–1984), немцы Макс Планк (1858–1947), Вернер Гейзенберг (1901–1976), Эрвин Шрёдингер (1887–1961), и многими другими. Устройство Вселенной, постулируемое квантовой механикой, настолько парадоксально, что Альберт Эйнштейн, критикуя эту теорию, как-то воскликнул: «Бог не играет в кости». Несмотря на сомнения Эйнштейна, теория квантовой механики была много раз успешно протестирована, и ее правильность в настоящее время не вызывает сомнений. Большинство ученых считает, что на макроскопическом уровне — то есть на уровне звезд, домов и молекул — Вселенная подчиняется законам классической физики. Однако в квантовом мире — на уровне элементарных частиц, таких как кварки, фотоны, электроны и т. д. — действуют совсем другие законы, приводящие к поразительным парадоксам. Без этой теории не существовало бы ни ядерных реакторов, ни лазерных считывающих устройств. Не было бы никакого способа объяснить свечение солнца или работу ДНК.

Нильс Бор (слева) и Макс Планк , основатели квантовой физики, на фотографии, сделанной в 1930 г.

Кот, ни живой ни мертвый

На семинаре по квантовой физике, состоявшемся в 1958 г., Бор так ответил одному из выступающих: «Мы все согласны с тем, что эта теория является бредовой. Вопрос, который нас разделяет, состоит в том, является ли она бредовой настолько, чтобы иметь шанс оказаться правильной». Насколько, на самом деле, бредова квантовая механика? Возьмем, например, принцип суперпозиции состояний. Частица находится в суперпозиции состояний, если в один и тот же момент она находится в двух различных положениях или когда она одновременно имеет различное количество энергии. Однако когда наблюдатель производит измерения, частица всегда выбирает одно состояние или обладает определенным количеством энергии. Шрёдингер предложил мысленный эксперимент, известный как «кот Шрёдингера», чтобы проиллюстрировать этот очевидно парадоксальный принцип. Пусть в закрытом непроницаемом ящике находится кот. Внутри ящика имеется колба с ядовитым газом, связанная специальным устройством с радиоактивной частицей, так что если частица распадается, газ выходит из колбы и кот умирает. Вероятность того, что эта частица распадется в течение определенного периода времени, составляет 50 %. Эксперимент с такими параметрами зависит от поведения частицы и подчиняется законам квантовой физики.

« Кот Шрёдингера » — мысленный эксперимент, иллюстрирующий один из принципов квантовой теории, а именно принцип суперпозиции состояний.

Допустим, что определенный период времени прошел. Вопрос: жив кот или мертв? Или, на языке квантовой механики, в каком состоянии находится система «ящик-кот»? Ответ на этот вопрос состоит в том, что пока наблюдатель не откроет ящик и не «измерит» состояние системы, частица может находиться в суперпозиции состояний: быть распавшейся и нераспавшейся. Значит, и система находится в суперпозиции состояний: кот, строго говоря, может быть и жив, и мертв одновременно.

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

От бита к кубиту

Какая, однако, связь между суперпозицией состояний частиц и вычислениями, не говоря уже о криптографии? До 1984 г. никто даже не думал о связи между этими двумя областями. Примерно в то же время британский физик Дэвид Дойч выступил с революционной идеей: а что было бы, если бы компьютеры подчинялись законам квантовой механики, а не классической физики? Как повлиял бы принцип суперпозиции состояний частиц на вычисления?

Напомним, что обычные компьютеры обрабатывают минимальные единицы информации, называемые битами, допускающими два взаимоисключающих значения: 0 и 1. Квантовый компьютер, с другой стороны, в качестве минимальной единицы информации мог бы работать с частицей, находящейся в двух возможных состояниях. Например, спин электрона может быть направлен либо вверх, либо вниз. Такая частица будет иметь фантастическое свойство: представлять значение 0 (спин вниз) или значение 1 (спин вверх). По принципу суперпозиции состояний она может представлять оба значения одновременно. Эта новая единица информации получила название кубит (сокращение от «квантовый бит»), и работа с такими единицами открывает двери в мир супермощных компьютеров.

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

Чтобы проиллюстрировать это, представим, что в специальном контейнере находятся 32 электрона в суперпозиции состояний. Применяя достаточно сильные электрические импульсы, мы можем изменить спин электрона сверху вниз. Тогда эти 32 электрона — кубиты нашего квантового компьютера — будут представлять все возможные комбинации спина вверх (1) и спина вниз (0) одновременно. В результате поиск нужного числа выполняется за один раз, так как находит все возможные варианты. Если мы увеличим количество кубитов до, например, 250, количество одновременных операций, которые могут быть выполнены, составит примерно 1075 — чуть больше, чем предполагаемое число атомов в нашей Вселенной.

Работы Дойча доказали, что квантовые компьютеры теоретически возможны.

Над тем, чтобы они в один прекрасный день стали реальностью, работают десятки институтов и исследовательских групп по всему миру. До сих пор, однако, не удалось преодолеть технические трудности и построить устойчивый квантовый компьютер.

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

* * *

«БОЛЬШОЙ БРАТ» XXI ВЕКА.

Результатом создания жизнеспособного квантового компьютера станет не просто крах современной криптографии. Такая вычислительная мощность на службе государственных или частных интересов может сместить баланс сил в мире. Битва за то, чтобы стать первой страной, развившей такие технологии, может легко превратиться в еще одну технологическую гонку, похожую на гонки второй половины XX в.: за выход в космос и гонку вооружений. Логично предположить, что любой прогресс в этой области будет держаться в тайне из соображений национальной безопасности. Может, в каком-то уголке мира, в холодных подземных туннелях, уже готов к запуску квантовый компьютер, который навсегда изменит нашу жизнь?

ПРОЩАЙ, DES, ПРОЩАЙ

Через два года после того, как Шор продемонстрировал, что квантовый компьютер может взломать шифр RSA, другой американец, Лов Гровер , сделал то же самое с еще одним столпом современной криптографии, алгоритмом DES. Гровер разработал программу, которая позволила квантовому компьютеру найти правильное числовое значение из списка возможных значений за время, равное квадратному корню из времени, которое нужно для этого обычному компьютеру. Другой широко используемый алгоритм, который станет жертвой квантового компьютера, — это RC5, стандарт, используемый в браузерах компании Microsoft.

Конец криптографии?

Квантовые вычисления приведут к смерти современной криптографии. Возьмем в качестве примера звезду современных алгоритмов шифрования — RSA. Напомним, чтобы взломать шифр RSA методом перебора всех возможных вариантов, нужно разложить на множители произведение двух очень больших простых чисел.

Эта операция чрезвычайно трудоемкая, и пока не существует математической лазейки для ее решения. Может ли квантовой компьютер взять на себя задачу разложения числа на простые числа, которые использует шифр RSA? Американский ученый Питер Шор в 1994 г. дал на этот вопрос утвердительный ответ. Шор разработал алгоритм для квантового компьютера, способный разложить большие числа на множители за намного меньшее время, чем самый мощный обычный компьютер.

Если это поразительное устройство когда-либо будет построено, алгоритм Шора кирпичик за кирпичиком разрушит мощное криптографическое здание, построенное на RSA, и наступит день, когда вся самая тайная информация на планете станет явной. Все современные системы шифрования постигнет та же участь. Но, перефразируя Марка Твена, мы можем сказать, что слухи о смерти криптоанализа «сильно преувеличены».

Квантовая механика взяла, квантовая механика дала

Одной из основ квантовой механики является принцип неопределенности, открытый Вернером Гейзенбергом в 1927 г. Хотя его точная формулировка очень сложна, сам Гейзенберг обобщил его следующим образом: «Мы в принципе не можем знать настоящее во всех подробностях». Более точно: невозможно определить с любой степенью точности те или иные свойства частицы в любой момент времени. Возьмем, например, частицы света (фотоны). Одной из их основных характеристик является поляризация — технический термин, связанный с колебаниями электромагнитных волн. [Хотя фотоны поляризованы во всех направлениях, в нашем примере мы будем считать, что они имеют поляризацию четырех типов: вертикальную , горизонтальную , по диагонали слева направо вниз , по диагонали слева направо вверх . Принцип Гейзенберга утверждает, что для определения поляризации фотона нужно пропустить его через фильтр, или «щель», которая, в свою очередь, может быть горизонтальной, вертикальной и диагональной: слева направо вниз или слева направо вверх. Фотоны, поляризованные горизонтально, пройдут горизонтальный фильтр без изменений, а поляризованные вертикально этот фильтр не пройдут. Что касается фотонов, которые поляризованы по диагонали, то половина из них пройдет через этот фильтр, поменяв поляризацию с диагональной на горизонтальную, а другая половина этот фильтр не пройдет. Это будет происходить случайным образом. Более того, после того как фотон пройдет фильтр, невозможно будет с уверенностью сказать, какова была его первоначальная поляризация.

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

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

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

Неуязвимый шифр

В 1984 г. американец Чарльз Беннет и канадец Жиль Брассар выдвинули идею системы шифрования на основе передачи поляризованных фотонов. Сначала отправитель и получатель договариваются, как разным поляризациям поставить в соответствие 0 или 1. В нашем примере это будет функцией двух видов поляризации: первый вид, называемый прямолинейной поляризацией и обозначаемый символом +, где 1 соответствует вертикальной поляризации , а 0 — горизонтальной , второй вид, называемый диагональной поляризацией и обозначаемый символом х, ставит в соответствие 1 диагональную поляризацию слева направо вверх , а 0 — диагональную поляризацию слева направо вниз .

Например, сообщение 0100101011 будет передано следующим образом:

Если шпион перехватит передачу, ему придется использовать фильтр с фиксированной ориентацией х:

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

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

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

Первым человеком, предложившим использовать полиалфавитный шифр с уникальным ключом, был Джозеф Моборн. Вскоре после Первой мировой войны, будучи начальником службы связи американского криптографического отдела, Моборн придумал блокнот с ключами, каждый из которых содержал более 100 случайных символов. Такие блокноты выдавались отправителю и получателю с инструкцией уничтожать использованный ключ и переходить к следующему. Эта система, известная как шифрблокнот одноразового назначения, является, как мы уже говорили, неуязвимой, и это можно доказать математически. И действительно, самые секретные послания между главами государств шифруются с помощью этого метода.

Если одноразовые шифры блокнота так безопасны, почему же они не используются повсеместно? Почему же мы так беспокоимся из-за квантовых компьютеров и даже занимаемся манипуляциями с фотонами?

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

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

1. Сначала получателю посылают случайную последовательность нулей и единиц через различные, случайным образом выбранные фильтры: вертикальные , горизонтальные , и диагональные .

2. Затем получатель измеряет поляризацию полученных фотонов, случайным образом чередуя прямолинейный (+) и диагональный (х) виды поляризации. Так как он не знает последовательности фильтров, используемых отправителем, большая часть нулей и единиц будет определена неправильно.

3. Наконец, отправитель и получатель связываются друг с другом в любой удобной им форме, не беспокоясь о безопасности канала, и обмениваются следующей информацией: во-первых, отправитель объясняет, какой вид поляризации — прямолинейный или диагональный — нужно использовать для каждого фотона, не раскрывая самой поляризации фотона (то есть не говоря, какой именно использовался фильтр). Со своей стороны получатель сообщает, в каких случаях он правильно определил вид. Как видно из предыдущей таблицы, если у отправителя и получателя виды поляризации совпали, можно быть уверенным, что нули и единицы переданы правильно. Наконец, уже в частном порядке каждый из них отбрасывает биты, соответствующие фотонам, для которых получатель неправильно определил вид поляризации.

* * *

ВАВИЛОНСКОЕ ПОСЛАНИЕ

Аргентинский писатель Хорхе Луис Борхес в коротком рассказе «Вавилонская библиотека» описал библиотеку, настолько большую, что на ее полках были все возможные книги: все романы, стихотворения и диссертации, опровержения этих диссертаций, а также опровержения опровержений, и так далее до бесконечности. Криптоаналитик, пытающийся расшифровать методом проб и ошибок послание, зашифрованное с помощью шифрблокнота одноразового назначения, окажется в подобном положении. Так как шифр выбран совершенно случайно, возможные расшифровки будут представлять из себя всевозможные тексты одинаковой длины: реальное сообщение, опровержение этого сообщения, то же сообщение со всеми существительными, замененными на другие той же длины, и так далее до бесконечности.

* * *

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

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

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

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

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

В конце процесса отправитель и получатель договариваются о простой проверке.

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

32 сантиметра абсолютной секретности

Метод Брассара и Беннета безупречен с точки зрения теории, но когда эту теорию попытались применить на практике, она была встречена очень скептически.

В 1989 г., после более чем года напряженной работы, Беннет построил систему, состоящую из двух компьютеров, расположенных на расстоянии 32 сантиметра друг от друга, один из которых выступал в роли отправителя, а другой — получателя.

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

Исторический эксперимент Беннета имел один очевидный недостаток: секрет посылался на расстояние менее шага. Передача шепотом была бы, наверное, столь же эффективна. Однако в последующие годы другие исследовательские группы увеличили это расстояние. В 1995 г. ученые из Университета Женевы использовали оптоволокно для передачи сообщений на 23 километра. В 2006 г. команда из Лос-Аламосской национальной лаборатории в США повторила этот процесс на расстоянии 107 километров. Хотя такие расстояния недостаточны для обычной связи, этот метод уже может быть использован в местах, где строжайшая тайна имеет первостепенное значение, например, в правительственных зданиях и офисах компаний.

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