Криптоанализ завтрашнего дня

 

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

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

Даже если пользователи надлежащим образом применяют шифр RSA, у дешифровальщиков по-прежнему есть масса возможностей добыть информацию из перехваченного сообщения. Дешифровальщики продолжают пользоваться старыми, добрыми методами, как, например, анализ трафика; если им и не удастся понять содержание сообщения, то они сумеют как минимум определить, кто является его отправителем и кому оно направлено, что само по себе может сказать о многом. Более современной разработкой является так называемая темпест-атака, цель которой — обнаружение электромагнитных сигналов, излучаемых электронными схемами в дисплее компьютера. Если Ева припаркует фургон на улице неподалеку от дома Алисы, она сможет воспользоваться чувствительной темпест-аппаратурой и распознать любые нажатия на клавиши, которые выполняет Алиса на своем компьютере. Это позволит Еве перехватить сообщение в тот момент, когда оно вводится в компьютер, еще до того, как оно будет зашифровано. Чтобы защититься от темпест-атак, компании производят и поставляют экранирующие материалы, которые могут использоваться для облицовки стен комнаты в целях предотвращения прохождения электромагнитных сигналов. В Америке, прежде чем купить такой экранирующий материал, следует получить разрешение у правительства, что наводит на мысль, что такие организации, как ФБР, регулярно проводят слежку и наблюдение с применением темпест-аппаратуры.

Другие виды атак заключаются в использовании вирусов и «троянских коней»[33]. Ева могла бы создать вирус, который заразит программу PGP и тайно сядет в компьютере Алисы. В тот момент, когда Алиса воспользуется своим секретным ключом для дешифрования сообщения, вирус «проснется» и запишет этот ключ. Когда Алиса в следующий раз подключится к Интернету, вирус тайно отправит этот секретный ключ Еве, позволив ей тем самым дешифровать все сообщения, посылаемые после этого Алисе. «Троянский конь» — еще одна составленная Евой каверзная компьютерная программа, которая, на первый взгляд, действует как настоящая программа шифрования, но на самом деле обманывает пользователя. Например, Алиса считает, что переписывает подлинную копию PGP, в то время как в действительности она загружает одну из версий «троянского коня». Эта модифицированная версия выглядит точно так же, как и настоящая программа PGP, но содержит инструкции пересылать Еве копии всей расшифрованной корреспонденции Алисы. Как высказался Фил Циммерман: «Любой может модифицировать исходный код и создать имитацию программы PGP, представляющую собой лоботомированного зомби, которая хоть и выглядит как настоящая, но выполняет приказы своего дьявольского хозяина. Впоследствии эта версия PGP с «троянским конем» может получить широкое хождение, поскольку утверждается, что она якобы исходит от меня. Какое коварство! Вам следует приложить все усилия, чтобы получить свою копию PGP из надежного источника, чего бы вам этого ни стоило».

Одним из вариантов «троянского коня» является принципиально новый фрагмент программного обеспечения для шифрования, который выглядит вполне надежно, но в действительности содержит «черный ход», который иногда позволяет его разработчикам дешифровывать сообщения всех и каждого. В 1998 году в отчете Уэйна Мэдсена было обнародовано, что швейцарская криптографическая компания Крипто АГ установила «черные ходы» в некоторых из своих программных продуктов и предоставила правительству США подробные сведения о том, как пользоваться этими «черными ходами». В результате Америка оказалась способна прочесть сообщения некоторых стран. В 1991 году убийц Шахпура Бахтияра, бывшего премьер-министра Ирана, жившего в изгнании, задержали благодаря тому, что были перехвачены и дешифрованы с помощью «черного хода» иранские сообщения, зашифрованные с помощью оборудования Крипто АГ.

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

Теоретическое открытие станет принципиально новым способом поиска секретного ключа Алисы. Секретный ключ Алисы состоит из чисел p и q, и они находятся путем разложения на множители открытого ключа N. Стандартный подход — поочередно проверять все простые числа, чтобы посмотреть, делится ли N на них, или нет, правда, как мы знаем, на это потребуется неоправданно много времени. Криптоаналитики пробовали отыскать способ быстрого разложения на множители — способ, который бы значительно сократил число шагов, необходимых для нахождения p и q, но до сих пор все их попытки выработать рецепт быстрого разложения на множители заканчивались неудачей. Веками математики изучали разложение на множители, но и сегодня способы разложения на множители ненамного лучше, чем античные методы. Более того, вполне может оказаться так, что существование существенного упрощения операции разложения на множители запрещается самими законами математики.

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

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

Чтобы объяснить принципы квантовых вычислений, полезно вернуться в конец восемнадцатого века к работе Томаса Юнга, английского энциклопедиста, сделавшего первый шаг в дешифровании египетской иероглифики. Юнг, член совета колледжа Эммануэль в Кембридже, частенько проводил послеобеденное время, отдыхая около пруда для уток рядом с колледжем. Как-то раз, как гласит предание, он обратил внимание на двух безмятежно плывущих бок о бок уток. Он заметил, что каждая из уток оставляла за собой на воде след в виде двух расходящихся веером волн, которые взаимодействовали друг с другом и создавали своеобразную картину, состоящую из участков, покрытых рябью, и участков со спокойной гладью воды. Когда гребень волны, идущей от одной из уток, встречался со впадиной между волнами, идущими от другой утки, в результате образовывался небольшой участок спокойной глади воды — гребень волны и впадина между волнами взаимно уничтожали друг друга. И наоборот, если в каком-то месте одновременно встречались две волны, то в результате образовывалась еще более высокая волна, если же в каком-то месте одновременно встречались две впадины, то образовывалась еще более глубокая впадина. Его это крайне заинтересовало, потому что утки напомнили ему об эксперименте, связанном с изучением природы света, который он провел в 1799 году.

В том эксперименте, как показано на рисунке 71 (а), Юнг освещал светом перегородку, в которой были две узкие вертикальные щели. На экране, расположенном на некотором расстоянии позади щелей, Юнг ожидал увидеть две светлые полоски — проекции щелей. Вместо этого он заметил, что свет от обеих щелей расходился веером, создавая на экране рисунок из нескольких светлых и темных полос. Такой рисунок в виде полос на экране озадачил его, но теперь он был уверен, что вполне смог бы дать ему объяснение, исходя из того, что он увидел на пруду для уток.

Юнг начал с предположения, что свет представляет собой волну. Но если свет, выходящий из двух щелей, ведет себя как волна, тогда эти волны ведут себя почти так же, как и волновые следы позади обеих уток. Более того, причиной появления светлых и темных полос на экране было то же самое взаимодействие, которое приводило к образованию высоких волн, глубоких впадин между волнами и участков со спокойной гладью воды. Юнг представил себе точки на экране, где встретились пик волны и впадина между волнами, что привело к их взаимному уничтожению и образованию темной полосы, и точки на экране, где встретились две волны (или две впадины), что вызвало их усиление и образование светлой полосы, как показано на рисунке 71 (b). Утки позволили Юнгу лучше понять природу света, в результате чего он опубликовал «Волновую теорию света» — нестареющий классический труд по физике.

 

Рис. 71 Эксперимент Юнга со щелями (вид сверху). На рисунке (a) видны световые волны, расходящиеся веером из двух щелей в перегородке, которые взаимодействуют между собой и образуют на экране рисунок в виде полос. На рисунке (b) показывается, как взаимодействуют между собой отдельные волны. Если на экране встречаются впадина между волнами и волна, то в результате образуется темная полоса. Если на экране встречаются две впадины между волнами (или две волны), то в результате образуется светлая полоса.

 

Сейчас нам известно, что свет действительно ведет себя как волна, но мы также знаем, что он ведет себя и как частица. То, как мы воспринимаем свет — в качестве волны или же частицы, — зависит от конкретной ситуации, и такая двойственность в поведении света называется корпускулярно-волновым дуализмом. Мы не будем далее обсуждать этот дуализм, просто укажем, что в современной физике световой пучок считается состоящим из бесчисленного множества отдельных частиц, называемых фотонами, которые и проявляют волновые свойства. При таком подходе мы можем трактовать эксперимент Юнга, как вылетающие из щели, а затем взаимодействующие с обратной стороны перегородки фотоны.

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

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

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

Аргументация сторонников суперпозиции на этот счет следующая. Если мы не знаем, как ведет себя частица, то значит, могут одновременно реализовываться все вероятности. В случае фотона нам не известно, пролетит ли он через левую или же через правую щель, поэтому мы предполагаем, что он пролетает через обе щели одновременно. Каждая вероятность называется состоянием, а поскольку в данном случае с фотоном реализуются обе вероятности, то говорят, что он находится в суперпозиции состояний. Мы знаем, что один фотон испускается нитью накаливания, и мы знаем, что один фотон попадает на экран за перегородкой, но между этими событиями он каким-то образом разделяется на два «фотона-призрака», которые пролетают через обе щели. Суперпозиция может звучать и глупо, но она хотя бы дает объяснение появлению рисунка в виде полос, получающегося в эксперименте Юнга с отдельными фотонами. Сравните, классическое представление, состоящее в том, что фотон должен пролететь через одну из двух щелей — мы просто не знаем, через какую именно, — кажется более здравым, чем квантовое, но, к сожалению, оно не способно объяснить получающийся результат.

Эрвин Шредингер, получивший Нобелевскую премию по физике в 1933 году, придумал мысленный эксперимент, известный под названием «кошка Шредингера», который часто используется для объяснения концепции суперпозиции. Представьте себе кошку, находящуюся в ящике. Для этой кошки существуют два возможных состояния: мертвая или живая. Вначале мы достоверно знаем, что кошка находится в одном определенном состоянии, поскольку можем видеть, что она живая. В этот момент кошка не находится в суперпозиции состояний. Затем положим в ящик рядом с кошкой ампулу с цианидом и закроем крышку. Теперь для нас наступил период неведения, потому что не можем видеть кошку или определить ее состояние. Жива ли она, или же наступила на ампулу с цианидом и умерла? В обычной жизни мы бы сказали, что кошка либо мертва, либо жива, — мы только не знаем, что именно. Квантовая теория, однако, говорит, что кошка находится в суперпозиции из двух состояний: она и мертва, и жива, то есть она находится во всех возможных состояниях. Суперпозиция возникает только тогда, когда объект пропадает у нас из виду и является способом описания объекта в период неопределенности. Когда, в конечном итоге, мы откроем ящик, мы сможем увидеть, жива ли кошка или мертва. Это действие — мы смотрим на кошку — вынуждает ее перейти в одно из определенных состояний, и тут же суперпозиция исчезает.

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

Неважно, выбираем ли мы суперпозицию или многомировую интерпретацию, квантовая теория является сложной философской доктриной. Но несмотря на свою сложность, она показала себя самой успешной и практичной научной теорией, которая когда-либо появлялась. Квантовая теория помимо того, что способна объяснить результат, полученный в эксперименте Юнга, успешно объясняет и множество других явлений. Только квантовая теория дает возможность физикам рассчитать последствия ядерных реакций в атомных электростанциях; только квантовая теория может дать объяснение чудесам ДНК; только квантовая теория объясняет, почему светит Солнце; только квантовая теория может применяться при разработке лазера для считывания компакт-дисков в вашей стереосистеме. Так что нравится нам это или нет, но мы живем в квантовом мире.

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

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

 

Рис. 72 Дэвид Дойч

 

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

Чтобы получить представление о возможностях квантового компьютера, мы можем сравнить его эффективность с эффективностью работы обычного компьютера, посмотрев, что происходит, когда каждый из них используется для решения конкретной задачи. К примеру, компьютеры обоих типов могут решать задачу нахождения такого числа, в квадрате и кубе которого будут присутствовать, но ни разу не повторяться, все цифры от 0 до 9. Если мы проверим число 19, то получим, что 192 = 361, а 193 = 6859. Это число не удовлетворяет нашему требованию, поскольку в его квадрате и кубе используются только цифры 1, 3, 5, 6, 6, 8 и 9, то есть цифр 0, 2, 4 и 7 нет, а цифра 6 повторяется дважды.

Для решения этой задачи с помощью обычного компьютера оператор должен применить следующий подход. Оператор вводит число 1 и дает возможность компьютеру проверить его. После того как компьютер выполнит необходимые вычисления, он сообщает, удовлетворяет ли данное число критерию или нет. Число 1 критерию не удовлетворяет, поэтому оператор вводит число 2 и дает возможность компьютеру выполнить очередную проверку и так далее, пока не будет в конце концов найдено соответствующее число. Оказывается, что это будет число 69, поскольку 692 = 4761, а 693 = 328509, и в эти числах действительно по одному разу используется каждая из десяти цифр. На самом же деле 69 является единственным числом, удовлетворяющим нашему требованию. Ясно, что такой процесс занимает много времени, так как обычный компьютер может в каждый момент времени проверять только одно число. Если на проверку каждого числа компьютер затрачивает одну секунду, то, чтобы найти ответ, ему понадобится 69 секунд. Квантовому же компьютеру для нахождения ответа потребуется всего лишь 1 секунда.

Оператор начинает с того, что представляет числа особым образом с тем, чтобы воспользоваться мощью квантового компьютера. Один из способов заключается в представлении чисел посредством вращающихся частиц: многие элементарные частицы обладают собственным спином, и они могут вращаться либо с запада на восток, либо с востока на запад[34], подобно баскетбольному мячу, крутящемуся на кончике пальца. Когда частица вращается с запада на восток, она обозначает 1, а когда вращается с востока на запад, то 0. Поэтому последовательность вращающихся частиц представляет собой последовательность единиц и нулей, или двоичное число. К примеру, семь частиц, вращающихся соответственно на восток, восток, запад, восток, запад, запад, запад, сообща образуют двоичное число 1101000, которое соответствует десятичному числу 104. Комбинация из семи частиц, с учетом спинов, может представлять собой любое число между 0 и 127.

При использовании обычного компьютера оператор вводит одну конкретную последовательность спинов, например, на запад, запад, запад, запад, запад, запад, восток, которая соответствует числу 0000001, или просто десятичному числу 1. Далее оператор ждет, пока компьютер проверит это число, чтобы выяснить, удовлетворяет ли оно указанному выше критерию. После этого оператор вводит 0000010, что соответствует последовательности вращающихся частиц, обозначающих 2, и так далее. Как и раньше, числа должны будут вводиться каждый раз по одному, что, как мы знаем, потребует много времени. Однако если мы имеем дело с квантовым компьютером, у оператора имеется альтернативный, гораздо более быстрый способ ввода чисел. Поскольку каждая частица является элементарной, она подчиняется законам квантовой физики. Поэтому когда частица не наблюдаема, она может задать суперпозицию состояний, которая означает, что она вращается одновременно в обоих направлениях и тем самым представляет одновременно и 0, и 1. Или же мы можем представить себе частицу, которая попадает в два разных мира; в одном мире она вращается с запада на восток и представляет собой 1, в то время как в другом она вращается с востока на запад и представляет собой 0.

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

Когда все семь частиц находятся в суперпозиции, они фактически представляют все возможные сочетания спинов с вращением с запада на восток и с востока на запад. Эти семь частиц одновременно представляют собой 128 различных состояний, или 128 различных чисел. Оператор вводит семь частиц, когда они находятся в суперпозиции состояний, в квантовый компьютер, который после этого выполняет вычисления таким образом, как если бы он проверял все 128 чисел одновременно. Через 1 секунду компьютер выдаст число, 69, которое отвечает требуемому критерию. Оператор получает 128 вычислений «по цене одного».

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

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

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

Еще одна проблема была вызвана тем, что ученые не знали, как запрограммировать квантовый компьютер, и поэтому не были уверены, какого рода вычисления он способен производить. Однако в 1994 году Питеру Шору из AT&T Bell Laboratories штата Нью-Джерси удалось составить пригодный для квантового компьютера алгоритм. Замечательной новостью для криптоаналитиков было то, что алгоритм Шора описывал ряд шагов, которые могли бы быть использованы квантовым компьютером для разложения на множители гигантского числа, то есть как раз то, что требовалось для взлома шифра RSA. Когда Мартин Гарднер опубликовал задачу по RSA в «Сайентифик Америкен», потребовалась работа шести сотен компьютеров в течение нескольких месяцев, чтобы разложить на множители число, состоящее из 129 цифр. Для сравнения, с помощью алгоритма Шора можно было разложить на множители число, в миллион раз большее, за время, в миллион раз меньшее. К сожалению, он не мог продемонстрировать свой алгоритм для разложения на множители, поскольку по-прежнему не было такого инструмента, как квантовый компьютер.

В 1996 году Лов Гровер, также из Bell Laboratories, разработал еще один мощный алгоритм. Алгоритм Гровера — это способ осуществления поиска в списке[35]с невероятно высокой скоростью, что может казаться не особенно интересным, пока вы не поймете, что это именно то, что требуется для взлома шифра DES. Чтобы взломать шифр DES, необходимо выполнить поиск списка всех возможных ключей, чтобы найти правильный. Если обычный компьютер может проверять миллион ключей в секунду, то для раскрытия шифра DES ему потребуется свыше тысячи лет, в то время как квантовый компьютер с помощью алгоритма Гровера смог бы найти ключ менее, чем за четыре минуты.

Чисто случайно оба этих первых разработанных алгоритма для квантовых компьютеров оказались именно теми, которые криптоаналитики ставили на первое место в своих списках пожеланий. Хотя алгоритмы Шора и Гровера породили колоссальный оптимизм среди дешифровальщиков, но возникло также и чувство огромного разочарования, так как все еще не существовало такой вещи, как действующий квантовый компьютер, на. котором можно было бы реализовать эти алгоритмы. Не удивительно, что возможности самого грозного оружия в дешифровании разожгли аппетит таких организаций, как американское Управление перспективных оборонных исследований (DARPA) и Лос-Аламосская национальная лаборатория, которые отчаянно пытались создать устройства, которые смогли бы обращаться с кубитами точно так же, как кремниевые чипы оперируют с битами.

Справедливости ради следует отметить, что, хотя ряд новейших достижений укрепил дух исследователей, технология остается в высшей степени примитивной. В 1998 году Серж Харош из университета «Paris VI»[36]показал подоплеку шумихи вокруг этих достижений, развеяв заверения, что до реально существующего квантового компьютера всего лишь несколько лет. Он заявил, что это напоминает бахвальство после кропотливой сборки первого слоя карточного домика, что следующие 15 000 слоев будут простой формальностью.

Только время покажет, будет ли и если будет, то когда, разрешена проблема создания квантового компьютера. А тем временем мы можем только строить предположения относительно того, какое влияние он окажет на мир криптографии. После 70-х годов благодаря таким шифрам, как DES и RSA, шифровальщики явно лидируют в состязании с дешифровальщиками. Эти виды шифров — ресурс огромной ценности, поскольку мы полагаемся на них, чтобы зашифровать свои электронные письма и защитить свое право на частную жизнь. Аналогичным образом, поскольку мы вступили в двадцать первое столетие, коммерческая деятельность будет все больше и больше проводиться через Интернет, а электронный рынок будет рассчитывать на стойкие шифры для защиты и контроля финансовых сделок. А поскольку информация становится самым ценным товаром в мире, участь государств в сфере экономики, политики и вооруженных сил будет зависеть от стойкости шифров.

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

 

Квантовая криптография

 

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

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

История квантовой криптографии начинается с любопытной идеи, высказанной в конце 60-х Стивеном Виснером, в то время еще аспирантом Колумбийского университета. Достойно сожаления, что идея Виснера значительно опередила свое время и никто ее не воспринял всерьез. Он до сих пор вспоминает реакцию своих наставников: «Я не получил никакой поддержки от своего научного руководителя — он вообще не проявил к ней интереса. Я показал ее еще нескольким людям — у них делались странные лица, и они возвращались к своим занятиям». Виснер предлагал поразительную концепцию квантовых денег, огромное преимущество которых заключалось в том, что подделать их было невозможно.