Книга шифров. Тайная история шифров и их расшифровки

Сингх Саймон

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

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

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

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

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

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

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

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

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

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