8 Квантовый прыжок в будущее
На протяжении двух тысячелетий создатели шифров прикладывали все усилия, чтобы сохранить секреты, дешифровальщики же старались сделать все возможное, чтобы их раскрыть. Между ними всегда шло острое соперничество: дешифровальщики отступали, когда шифровальщики чувствовали себя хозяевами положения, а создатели шифров, в свою очередь, придумывали новые, более стойкие виды шифрования, когда предыдущие оказывались скомпрометированными. Открытие криптографии с открытым ключом и политические споры, ведущиеся вокруг использования стойкой криптографии, приводят нас к сегодняшнему дню, и не вызывает сомнений, что в информационной войне побеждают криптографы. По словам Фила Циммермана, мы живем в «золотом веке» криптографии: «Сейчас в современной криптографии можно создать такие шифры, которые будут совершенно недоступны всем известным видам криптоанализа. И я полагаю, что так будет и впредь». Точку зрения Циммермана разделяет Уильям Кроуэлл, заместитель директора Агентства национальной безопасности: «Если все персональные компьютеры мира, а их примерно 260 миллионов, заставить работать над единственным сообщением, зашифрованным PGP, то для его дешифрования потребовалось бы в среднем время в 12 миллионов раз превышающее возраст Вселенной».
Впрочем, из прежнего опыта нам известно, что рано или поздно, но любой так называемый «нераскрываемый» шифр не смог устоять перед криптоанализом. Шифр Виженера назывался «нераскрываемым шифром», но Бэббидж взломал его; «Энигма» считалась неуязвимой до тех пор, пока поляки не выявили ее слабости. Так что же, криптоаналитики стоят на пороге нового открытия, или же прав Циммерман? Предсказывать будущее развитие любой технологии всегда рискованно, но когда дело касается шифров, это рискованно особенно. Мало того что мы должны предугадать, какие открытия состоятся в будущем, мы также должны постараться отгадать, какие открытия заключены в настоящем. Повествование о Джеймсе Эллисе и ШКПС дает нам понять, что уже и сейчас могут существовать поразительные достижения, скрытые за завесой правительственной секретности.
Эта заключительная глава посвящена рассмотрению нескольких футуристических идей, которые могут повысить или погубить конфиденциальность в двадцать первом столетии. В следующем разделе обсуждается будущее криптоанализа и, в частности, одна из идей, которая смогла бы дать возможность криптоаналитикам раскрыть все сегодняшние шифры. В последнем разделе данной книги, напротив, рассказывается о самой волнующей надежде криптографии — о системе, которая может гарантировать абсолютную секретность.
Криптоанализ завтрашнего дня
Несмотря на исключительную стойкость RSA и других современных шифров, роль криптоаналитиков в сборе разведывательной информации все так же важна. Доказательством успешности их деятельности служит тот факт, что сейчас спрос на криптоаналитиков выше, чем когда бы то ни было раньше, и АНБ по-прежнему является крупнейшим в мире работодателем для математиков.
Лишь незначительное количество передаваемой по всему миру информации надежно зашифровано; остальная же ее часть либо зашифрована плохо, либо не зашифрована вовсе. Причина этого заключается в быстро растущем числе пользователей Интернета, и пока что лишь немногие из них предпринимают адекватные меры предосторожности в том, что касается обеспечения секретности. А это, в свою очередь, означает, что организации, отвечающие за национальную безопасность, сотрудники правоприменяющих органов и вообще любой любопытствующий могут заполучить в свои руки больше информации, чем допустимо.
Даже если пользователи надлежащим образом применяют шифр RSA, у дешифровальщиков по-прежнему есть масса возможностей добыть информацию из перехваченного сообщения. Дешифровальщики продолжают пользоваться старыми, добрыми методами, как, например, анализ трафика; если им и не удастся понять содержание сообщения, то они сумеют как минимум определить, кто является его отправителем и кому оно направлено, что само по себе может сказать о многом. Более современной разработкой является так называемая темпест-атака, цель которой — обнаружение электромагнитных сигналов, излучаемых электронными схемами в дисплее компьютера. Если Ева припаркует фургон на улице неподалеку от дома Алисы, она сможет воспользоваться чувствительной темпест-аппаратурой и распознать любые нажатия на клавиши, которые выполняет Алиса на своем компьютере. Это позволит Еве перехватить сообщение в тот момент, когда оно вводится в компьютер, еще до того, как оно будет зашифровано. Чтобы защититься от темпест-атак, компании производят и поставляют экранирующие материалы, которые могут использоваться для облицовки стен комнаты в целях предотвращения прохождения электромагнитных сигналов. В Америке, прежде чем купить такой экранирующий материал, следует получить разрешение у правительства, что наводит на мысль, что такие организации, как ФБР, регулярно проводят слежку и наблюдение с применением темпест-аппаратуры.
Другие виды атак заключаются в использовании вирусов и «троянских коней». Ева могла бы создать вирус, который заразит программу PGP и тайно сядет в компьютере Алисы. В тот момент, когда Алиса воспользуется своим секретным ключом для дешифррвания сообщения, вирус «проснется» и запишет этот ключ. Когда Алиса в следующий раз подключится к Интернету, вирус тайно отправит этот секретный ключ Еве, позволив ей тем самым дешифровать все сообщения, посылаемые после этого Алисе. «Троянский конь» — еще одна составленная Евой каверзная компьютерная программа, которая, на первый взгляд, действует как настоящая программа шифрования, но на самом деле обманывает пользователя. Например, Алиса считает, что переписывает подлинную копию PGP, в то время как в действительности она загружает одну из версий «троянского коня». Эта модифицированная версия выглядит точно так же, как и настоящая программа PGP, но содержит инструкции пересылать Еве копии всей расшифрованной корреспонденции Алисы. Как высказался Фил Циммерман: «Любой может модифицировать исходный код и создать имитацию программы PGP, представляющую собой лоботомированного зомби, которая хоть и выглядит как настоящая, но выполняет приказы своего дьявольского хозяина. Впоследствии эта версия PGP с «троянским конем» может получить широкое хождение, поскольку утверждается, что она якобы исходит от меня. Какое коварство! Вам следует приложить все усилия, чтобы получить свою копию PGP из надежного источника, чего бы вам этого ни стоило».
Одним из вариантов «троянского коня» является принципиально новый фрагмент программного обеспечения для шифрования, который выглядит вполне надежно, но в действительности содержит «черный ход», который иногда позволяет его разработчикам дешифровывать сообщения всех и каждого. В 1998 году в отчете Уэйна Мэдсена было обнародовано, что швейцарская криптографическая компания Крипто АГ установила «черные ходы» в некоторых из своих программных продуктов и предоставила правительству США подробные сведения о том, как пользоваться этими «черными ходами». В результате Америка оказалась способна прочесть сообщения некоторых стран. В 1991 году убийц Шахпура Бахтияра, бывшего премьер-министра Ирана, жившего в изгнании, задержали благодаря тому, что были перехвачены и дешифрованы с помощью «черного хода» иранские сообщения, зашифрованные с помощью оборудования Крипто АГ.
Несмотря на то что и анализ трафика, и темпест-атаки, и вирусы, и «троянские кони» до сих пор представляют собой полезные способы сбора разведывательной информации, криптоаналитики понимают, что их подлинной целью является поиск способа взлома шифра RSA — краеугольного камня современного шифрования. Шифр RSA используется для защиты самых важных военных, дипломатических, коммерческих и криминальных сообщений — то есть как раз тех сообщений, дешифрование которых и представляет интерес для организаций, занятых сбором разведывательной информации. Криптоаналитикам, чтобы бросить вызов стойкому шифрованию RSA, потребуется совершить крупное теоретическое открытие или значительный технологический прорыв.
Теоретическое открытие станет принципиально новым способом поиска секретного ключа Алисы. Секретный ключ Алисы состоит из чисел р и q, и они находятся путем разложения на множители открытого ключа N. Стандартный подход — поочередно проверять все простые числа, чтобы посмотреть, делится ли N на них, или нет, правда, как мы знаем, на это потребуется неоправданно много времени. Криптоаналитики пробовали отыскать способ быстрого разложения на множители — способ, который бы значительно сократил число шагов, необходимых для нахождения р и q, но до сих пор все их попытки выработать рецепт быстрого разложения на множители заканчивались неудачей. Веками математики изучали разложение на множители, но и сегодня способы разложения на множители ненамного лучше, чем античные методы. Более того, вполне может оказаться так, что существование существенного упрощения операции разложения на множители запрещается самими законами математики.
В отсутствии надежды на теоретическое открытие, криптоаналитики были вынуждены искать какое-нибудь техническое новшество. Если явного способа сократить количество действий, требующихся для разложения на множители, нет, то тогда криптоаналитикам необходим способ, с помощью которого эти действия будут выполняться гораздо быстрее. С годами кремниевые чипы будут работать все быстрее и быстрее, удваивая свою скорость примерно каждые восемнадцать месяцев, но для того, чтобы хоть как-то повлиять на скорость разложения на множители, этого недостаточно; криптоаналитикам требуются устройства, которые были бы в миллионы раз быстрее современных компьютеров. Так что криптоаналитики рассчитывают на принципиально новый вид компьютера — квантовый компьютер. Если бы ученые смогли создать квантовый компьютер, это позволило бы выполнять вычисления с такой скоростью, что современный суперкомпьютер выглядел бы по сравнению с ним сломанными счетами.
Далее в этом разделе будет обсуждаться концепция квантового компьютера, и поэтому здесь вводятся некоторые принципы квантовой физики, называемой иногда квантовой механикой. Прежде чем двигаться дальше, обратите, пожалуйста, внимание на предупреждение, которое поначалу дал Нильс Бор, один из «отцов» квантовой механики: «Тот, кто способен размышлять о квантовой механике, не испытывая при этом головокружения, не понял ее». Другими словами, приготовьтесь к встрече с несколькими довольно причудливыми идеями.
Чтобы объяснить принципы квантовых вычислений, полезно вернуться в конец восемнадцатого века к работе Томаса Юнга, английского энциклопедиста, сделавшего первый шаг в дешифровании египетской иероглифики. Юнг, член совета колледжа Эммануэль в Кембридже, частенько проводил послеобеденное время, отдыхая около пруда для уток рядом с колледжем. Как-то раз, как гласит предание, он обратил внимание на двух безмятежно плывущих бок о бок уток. Он заметил, что каждая из уток оставляла за собой на воде след в виде двух расходящихся веером волн, которые взаимодействовали друг с другом и создавали своеобразную картину, состоящую из участков, покрытых рябью, и участков со спокойной гладью воды. Когда гребень волны, идущей от одной из уток, встречался со впадиной между волнами, идущими от другой утки, в результате образовывался небольшой участок спокойной глади воды — гребень волны и впадина между волнами взаимно уничтожали друг друга. И наоборот, если в каком-то месте одновременно встречались две волны, то в результате образовывалась еще более высокая волна, если же в каком-то месте одновременно встречались две впадины, то образовывалась еще более глубокая впадина. Его это крайне заинтересовало, потому что утки напомнили ему об эксперименте, связанном с изучением природы света, который он провел в 1799 году.
В том эксперименте, как показано на рисунке 71 (а), Юнг освещал светом перегородку, в которой были две узкие вертикальные щели. На экране, расположенном на некотором расстоянии позади щелей, Юнг ожидал увидеть две светлые полоски — проекции щелей. Вместо этого он заметил, что свет от обеих щелей расходился веером, создавая на экране рисунок из нескольких светлых и темных полос. Такой рисунок в виде полос на экране озадачил его, но теперь он был уверен, что вполне смог бы дать ему объяснение, исходя из того, что он увидел на пруду для уток.
Юнг начал с предположения, что свет представляет собой волну. Но если свет, выходящий из двух щелей, ведет себя как волна, тогда эти волны ведут себя почти так же, как и волновые следы позади обеих уток. Более того, причиной появления светлых и темных полос на экране было то же самое взаимодействие, которое приводило к образованию высоких волн, глубоких впадин между волнами и участков со спокойной гладью воды. Юнг представил себе точки на экране, где встретились пик волны и впадина между волнами, что привело к их взаимному уничтожению и образованию темной полосы, и точки на экране, где встретились две волны (или две впадины), что вызвало их усиление и образование светлой полосы, как показано на рисунке 71 (b). Утки позволили Юнгу лучше понять природу света, в результате чего он опубликовал «Волновую теорию света» — нестареющий классический труд по физике.
Рис. 71 Эксперимент Юнга со щелями (вид сверху). На рисунке (а) видны световые волны, расходящиеся веером из двух щелей в перегородке, которые взаимодействуют между собой и образуют на экране рисунок в виде полос. На рисунке (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 секунда.
Оператор начинает с того, что представляет числа особым образом с тем, чтобы воспользоваться мощью квантового компьютера. Один из способов заключается в представлении чисел посредством вращающихся частиц: многие элементарные частицы обладают собственным спином, и они могут вращаться либо с запада на восток, либо с востока на запад, подобно баскетбольному мячу, крутящемуся на кончике пальца. Когда частица вращается с запада на восток, она обозначает 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, разработал еще один мощный алгоритм. Алгоритм Гровера — это способ осуществления поиска в списке с невероятно высокой скоростью, что может казаться не особенно интересным, пока вы не поймете, что это именно то, что требуется для взлома шифра DES. Чтобы взломать шифр DES, необходимо выполнить поиск списка всех возможных ключей, чтобы найти правильный. Если обычный компьютер может проверять миллион ключей в секунду, то для раскрытия шифра DES ему потребуется свыше тысячи лет, в то время как квантовый компьютер с помощью алгоритма Гровера смог бы найти ключ менее, чем за четыре минуты.
Чисто случайно оба этих первых разработанных алгоритма для квантовых компьютеров оказались именно теми, которые криптоаналитики ставили на первое место в своих списках пожеланий. Хотя алгоритмы Шора и Гровера породили колоссальный оптимизм среди дешифровальщиков, но возникло также и чувство огромного разочарования, так как все еще не существовало такой вещи, как действующий квантовый компьютер, на. котором можно было бы реализовать эти алгоритмы. Не удивительно, что возможности самого грозного оружия в дешифровании разожгли аппетит таких организаций, как американское Управление перспективных оборонных исследований (DARPA) и Лос-Аламосская национальная лаборатория, которые отчаянно пытались создать устройства, которые смогли бы обращаться с кубитами точно так же, как кремниевые чипы оперируют с битами.
Справедливости ради следует отметить, что, хотя ряд новейших достижений укрепил дух исследователей, технология остается в высшей степени примитивной. В 1998 году Серж Харош из университета «Paris VI» показал подоплеку шумихи вокруг этих достижений, развеяв заверения, что до реально существующего квантового компьютера всего лишь несколько лет. Он заявил, что это напоминает бахвальство после кропотливой сборки первого слоя карточного домика, что следующие 15 000 слоев будут простой формальностью.
Только время покажет, будет ли и если будет, то когда, разрешена проблема создания квантового компьютера. А тем временем мы можем только строить предположения относительно того, какое влияние он окажет на мир криптографии. После 70-х годов благодаря таким шифрам, как DES и RSA, шифровальщики явно лидируют в состязании с дешифровальщиками. Эти виды шифров — ресурс огромной ценности, поскольку мы полагаемся на них, чтобы зашифровать свои электронные письма и защитить свое право на частную жизнь. Аналогичным образом, поскольку мы вступили в двадцать первое столетие, коммерческая деятельность будет все больше и больше проводиться через Интернет, а электронный рынок будет рассчитывать на стойкие шифры для защиты и контроля финансовых сделок. А поскольку информация становится самым ценным товаром в мире, участь государств в сфере экономики, политики и вооруженных сил будет зависеть от стойкости шифров.
Поэтому создание полностью работоспособного квантового компьютера создаст угрозу неприкосновенности нашей личной жизни, разрушит электронную коммерцию и уничтожит понятие национальной безопасности. Квантовый компьютер поставит под удар стабильность мира. Какая бы страна ни стала первой, она получит возможность отслеживать средства связи своих граждан, читать о намерениях своих конкурентов в коммерции, прослушивать планы своих противников. И несмотря на то, что квантовые вычисления находятся еще в. процессе зарождения, они представляют потенциальную опасность для личности, международного бизнеса и глобальной безопасности.
Квантовая криптография
В то время как криптоаналитики ожидают появления квантовых компьютеров, криптографы вовсю трудятся над своим собственным технологическим чудом — системой шифрования, которая вновь позволит обрести конфиденциальность, даже в противостоянии с мощью квантового компьютера.
Этот новый вид шифрования в корне отличен от тех, с которыми мы прежде сталкивались, то есть дает надежду на совершенную стойкость. Другими словами, у этой системы не будет изъянов и слабых мест, и она сможет навечно гарантировать абсолютную секретность. Более того, она основывается на квантовой теории — той самой теории, которая положена в основу квантовых компьютеров. Так что квантовая теория, с одной стороны, используется в компьютере, который сможет раскрыть все нынешние шифры, с другой же — это основа нового нераскрываемого шифра, названного квантовая криптография.
История квантовой криптографии начинается с любопытной идеи, высказанной в конце 60-х Стивеном Виснером, в то время еще аспирантом Колумбийского университета. Достойно сожаления, что идея Виснера значительно опередила свое время и никто ее не воспринял всерьез. Он до сих пор вспоминает реакцию своих наставников: «Я не получил никакой поддержки от своего научного руководителя — он вообще не проявил к ней интереса. Я показал ее еще нескольким людям — у них делались странные лица, и они возвращались к своим занятиям». Виснер предлагал поразительную концепцию квантовых денег, огромное преимущество которых заключалось в том, что подделать их было невозможно.
Квантовые деньги Виснера основывались главным образом на физике фотонов. Как показано на рисунке 73 (а), фотон во время своего движения производит колебания. Все четыре фотона летят в одном направлении, но в каждом случае угол колебаний различен. Угол колебаний называется поляризацией фотона, и лампочкой накаливания создаются фотоны всех поляризаций, что означает, что у части фотонов колебания будут происходить вверх-вниз, у части фотонов — влево-вправо, а у остальных колебания будут происходить при любых углах между этими направлениями. Для простоты предположим, что фотоны обладают только четырьмя возможными поляризациями, которые мы обозначим
.
Если на пути фотонов установить фильтр, называющийся поляризационным, то выходящий пучок света будет состоять из фотонов, которые колеблются в одном определенном направлении; другими словами, все фотоны будут иметь одну и ту же поляризацию. Мы можем рассматривать поляризационный фильтр как в некотором роде сито, а фотоны — как спички, беспорядочно рассыпанные по ситу. Спички проскользнут сквозь сито только в том случае, если они располагаются под нужным углом. Любой фотон, поляризованный в том же направлении, что и поляризация поляризационного фильтра, заведомо пройдет через него без изменений, а фотоны, поляризованные в направлении, перпендикулярном фильтру, будут задержаны.
К сожалению, аналогия со спичками не срабатывает, когда мы рассматриваем диагонально поляризованные фотоны, попадающие на поляризационный фильтр с вертикальной поляризацией. Хотя диагонально расположенные спички будут задержаны вертикальным ситом, совсем не обязательно, что это же самое произойдет с диагонально поляризованными фотонами, попадающими на поляризационный фильтр с вертикальной поляризацией. На самом деле, когда диагонально поляризованные фотоны встретятся с поляризационным фильтром с вертикальной поляризацией, то половина из них будет задержана, а половина пройдет через фильтр, причем те, которые пройдут, приобретут вертикальную поляризацию. На рисунке 73 (b) показаны восемь фотонов, попадающих на поляризационный фильтр с вертикальной поляризацией, а на рисунке 73 (с) показано, что через фильтр благополучно прошли только четыре из восьми фотонов. Прошли все вертикально поляризованные фотоны и половина диагонально поляризованных фотонов, а все горизонтально поляризованные фотоны задержаны.
Рис. 73 (а) Хотя колебания фотонов происходят во всех направлениях, мы, для простоты рассмотрения, предполагаем, что имеется только четыре различных направления, как показано на данном рисунке. (b) Лампочка испустила восемь фотонов, которые колеблются в различных направлениях. Говорят, что каждый фотон имеет поляризацию. Фотоны летят к поляризационному фильтру с вертикальной поляризацией, (с) По другую сторону фильтра уцелела только половина фотонов. Вертикально поляризованные фотоны прошли, а горизонтально поляризованные фотоны нет. Прошла половина диагонально поляризованных фотонов, после чего они стали вертикально поляризованными.
Именно такая способность задерживать определенные фотоны и объясняет, каким образом действуют поляроидные солнцезащитные очки. По сути, вы можете рассмотреть влияние поляризационных фильтров, экспериментируя с линзами от поляроидных солнцезащитных очков. Сначала вытащите одну линзу и зажмурьте или прикройте чем-нибудь один глаз, а вторым глазом смотрите через оставшуюся линзу. Не удивительно, что мир выглядит таким темным, ведь линза задерживает множество фотонов, которые иначе попали бы в ваш глаз. В этот момент все фотоны, попавшие в ваш глаз, имеют одну и ту же поляризацию. Затем держите вторую линзу перед линзой, через которую вы смотрите, и медленно вращайте ее. В определенный момент при вращении снятая линза не будет оказывать никакого влияния на количество света, который попадает в ваш глаз, потому что ее ориентация такая же, что и у закрепленной линзы — все фотоны, которые прошли через снятую линзу, пройдут также и через закрепленную линзу. Если теперь вы повернете снятую линзу на 90°, все станет совершенно черным. При таком расположении поляризация снятой линзы перпендикулярна поляризации закрепленной линзы, так что все фотоны, прошедшие через снятую линзу, задерживаются закрепленной линзой. Теперь, если вы повернете снятую линзу на 45°, то окажетесь в промежуточном положении, когда половина фотонов, прошедших через снятую линзу, сумеют пройти и через закрепленную линзу.
Виснер планировал воспользоваться поляризацией фотонов в качестве способа создания долларовых банкнот, которые никогда нельзя будет подделать. Его идея заключалась в том, чтобы в каждой долларовой банкноте было 20 ловушек для фотонов — крошечных устройств, способных захватить и удержать фотон. Он предположил, что банки могли бы использовать четыре поляризационных фильтра, ориентированных четырьмя различными способами (
), чтобы заполнить 20 ловушек 20 поляризованными фотонами; причем для каждой банкноты использовалась бы отличная от других последовательность поляризованных фотонов. К примеру, на рисунке 74 показана банкнота со следующей поляризационной последовательностью (
). Хотя на рисунке 74 эти поляризации показаны в явном виде, но в действительности они будут скрыты от взора. На каждой банкноте отпечатан также обычный номер серии — В2801695Е для долларовой банкноты, показанной на рисунке. Банк-эмитент может идентифицировать каждую долларовую банкноту в соответствии с ее поляризационной последовательностью и отпечатанным номером серии и составить список номеров серий и соответствующих поляризационных последовательностей.
Теперь фальшивомонетчик сталкивается с проблемой: он не может просто подделать долларовую банкноту с произвольным номером серии и случайной поляризационной последовательностью в ловушках для фотонов, поскольку такой пары в банковском списке нет, и банк обнаружит, что эта долларовая банкнота является фальшивой. Чтобы подделка была качественной, фальшивомонетчик должен в качестве образца использовать подлинную банкноту, каким-то образом измерить его 20 поляризаций, а затем сделать копию долларовой банкноты, взяв за образец номер серии и соответствующим образом заполнив ловушки для фотонов. Однако измерение поляризации фотонов является исключительно сложной задачей, и если фальшивомонетчик не сможет точно измерить их в подлинной банкноте-образце, то он не смеет надеяться сделать копию.
Чтобы понять всю сложность измерения поляризации фотонов, нам необходимо выяснить, как мы собираемся его выполнять. Единственный способ выяснить что-либо о поляризации фотона — это воспользоваться поляризационным фильтром. Чтобы измерить поляризацию фотона в определенной ловушке для фотонов, фальшивомонетчик выбирает поляризационный фильтр и ориентирует его в определенном направлении, скажем, вертикально,
. Если фотон, вылетающий из ловушки для фотонов, окажется вертикально поляризованным, он пройдет через поляризационный фильтр с вертикальной поляризацией, и фальшивомонетчик вполне справедливо предположит, что это вертикально поляризованный фотон.
Если же вылетающий фотон является горизонтально поляризованным, то через поляризационный фильтр с вертикальной поляризацией он не пройдет, и фальшивомонетчик вполне справедливо предположит, что это горизонтально поляризованный фотон. Однако может случиться так, что вылетающий фотон окажется диагонально поляризованным (
или
), и тогда он может как пройти через фильтр, так и не пройти через него; в любом случае фальшивомонетчик не сумеет определить его истинную природу. Фотон с поляризацией
может пройти через поляризационный фильтр с вертикальной поляризацией, и в этом случае фальшивомонетчик ошибочно предположит, что это вертикально поляризованный фотон. Но этот же самый фотон может не пройти через фильтр, и в этом случае фальшивомонетчик ошибочно предположит, что это горизонтально поляризованный фотон. С другой стороны, если фальшивомонетчик собирается измерить фотон в другой ловушке для фотонов, ориентируя фильтр диагонально, допустим,
, то этим он правильно определит природу диагонально поляризованного фотона, но безошибочно идентифицировать вертикально или горизонтально поляризованный фотон не сумеет.
Проблема для фальшивомонетчика состоит в том, что для определения поляризации фотона он должен правильно сориентировать поляризационный фильтр, но он не знает, какую ориентацию использовать, так как не знает поляризацию фотона. Такая парадоксальная ситуация свойственна физике фотонов. Представим себе, что фальшивомонетчик выбирает
-фильтр для измерения фотона, вылетающего из второй ловушки для фотонов, а фотон не проходит через фильтр. Фальшивомонетчик может быть уверен, что этот фотон не был
-поляризован, поскольку такой фотон прошел бы через фильтр. Однако фальшивомонетчик не может сказать, был ли этот фотон таким, который заведомо не прошел бы через фильтр, то есть
-поляризован, или же его поляризация была такова, что в половине случаев он будет задержан, то есть он был
- или
-поляризован.
Рис. 74 Квантовые деньги Стивена Виснера. Каждая банкнота является уникальной благодаря своему номеру серии, который можно легко видеть, и 20 ловушкам для фотонов, чье содержимое является загадкой. В ловушках для фотонов находятся фотоны с различными поляризациями. Банк знает поляризационные последовательности, соответствующие каждому номеру серии, фальшивомонетчик же — нет.
Сложность при измерении фотонов является одним из положений принципа неопределенности, открытым в 20-е годы немецким физиком Вернером Гейзенбергом. Он сформулировал свое в высшей степени специальное положение в виде простого утверждения: «Мы в принципе не можем знать настоящее во всех его подробностях». Это не означает, что мы не знаем всего, потому что у нас нет достаточно средств измерения или потому что наше оборудование плохо сконструировано. Напротив, Гейзенберг утверждал, что логически невозможно измерить все характеристики определенного объекта с абсолютной точностью. В нашем конкретном случае мы не можем с абсолютной точностью измерить все характеристики находящихся в ловушках фотонов. Принцип неопределенности — это еще одно причудливое следствие квантовой теории.
Квантовые деньги Виснера учитывают тот факт, что подделка денег является двухступенчатым процессом: во-первых, фальшивомонетчику необходимо провести измерение оригинальной банкноты с высокой точностью, а затем он должен сделать ее копию. За счет использования фотонов, долларовую банкноту теперь измерить точно стало невозможно, и поэтому на пути подделки денег возник барьер.
Наивный фальшивомонетчик полагает, что если он не может измерить поляризации фотонов в ловушках, то этого не сможет сделать и банк. Он может попробовать изготовить долларовые банкноты, заполняя ловушки для фотонов произвольной поляризационной последовательностью. Банк, однако, способен проверить подлинность банкнот. Он сверяет номер серии со своим тайным списком, чтобы выяснить, какие фотоны должны находиться в ловушках для фотонов. Поскольку банк знает, какие поляризации следует ожидать в каждой из ловушек, он может правильным образом сориентировать поляризационный фильтр для каждой ловушки и выполнить точное измерение. Если банкнота фальшивая, то есть когда фальшивомонетчик заполнил ловушки произвольной поляризационной последовательностью, это приведет к неправильным результатам измерений и банкнота будет признана подделкой. Например, если банк применяет
-фильтр для измерения фотона, который должен иметь
-поляризацию, но оказывается, что фотон задерживается фильтром, это означает, что фальшивомонетчик заполнил ловушку неправильным фотоном. Если же банкнота окажется подлинной, то банк повторно заполнит ловушки для фотонов соответствующими фотонами и вновь запустит ее в обращение.
Короче говоря, фальшивомонетчик не может измерить поляризации в подлинной банкноте, поскольку он не имеет представления, какого вида фотоны находятся в каждой из ловушек для фотонов, и не может поэтому знать, как сориентировать поляризационный фильтр, чтобы точно его измерить. С другой стороны, банк способен проверить поляризации в подлинной банкноте, потому что он сам изначально задал поляризацию, и поэтому знает, как сориентировать поляризационный фильтр для каждой из ловушек.
Квантовые деньги — это блестящая идея. И к тому же совершенно неосуществимая. Начать с того, что инженеры пока что не разработали способ улавливать в ловушки фотоны с заданными поляризованными состояниями на достаточно долгое время. Даже если такой способ и существует, реализовать его окажется слишком дорого. Защита каждой долларовой банкноты может стоить где-то около 1 млн долларов. Но несмотря на всю их нереализуемость, квантовая теория в квантовых деньгах применяется весьма любопытным способом, так что невзирая на отсутствие интереса и поддержки со стороны своего научного руководителя Виснер направил статью в научный журнал. Ее отвергли. Он направил статью в три других журнала; ее отвергли еще три раза. Виснер заявил, что они просто не разбираются в физике.
Казалось, что только один человек разделял заинтересованность Виснера концепцией квантовых денег. Это был его старый друг по имени Чарльз Беннет, который несколькими годами ранее окончил вместе с ним университет Брандейса. Беннета отличало любопытство, проявляемое им в различных областях науки. Он говорил, что уже в три года знал, что хочет быть ученым, и даже мать не смогла притушить его детское увлечение ею. Однажды она вернулась домой и обнаружила на плите кипящую кастрюлю с каким-то странным тушеным мясом. По счастью, она не соблазнилась попробовать его; как потом выяснилось, это были останки черепахи, которую юный Беннет кипятил в щелочи, чтобы отделить мясо от костей и получить великолепный образец ее скелета. В юношеском возрасте интересы Беннета простирались от биологии до биохимии, а к тому времени, как поступить в Брандейс, он решил посвятить себя химии. В аспирантуре Беннет вплотную занялся физической химией, а затем переключился на исследования в физике, математике, логике и, вдобавок, программировании.
Зная широту интересов Беннета, Виснер надеялся, что тот в полной мере оценит концепцию квантовых денег, и передал ему копию своей отвергнутой статьи. Беннет сразу же увлекся этой идеей, посчитав ее одной из самых прекрасных, с которыми он когда-либо сталкивался. В следующие десять лет он время от времени перечитывал статью, задаваясь вопросом, существует ли способ реализовать каким-либо образом эту гениальную идею. Даже став в начале 80-х научным сотрудником исследовательской лаборатории Томаса Дж. Уотсона компании IВМ, Беннет не перестал размышлять об идее Виснера. Журналы, может, и не хотели публиковать ее, но Беннета она увлекла.
Рис. 75 Чарльз Беннет.
Как-то раз Беннет рас казал об идее квантовых денег Жилю Брассарду, программисту из Монреальского университета. Беннет и Брассард, сотрудничавшие в различных исследовательских проектах, снова и снова обращались к статье Виснера, обсуждая ее сложности. Мало-помалу они начали осознавать, что идея Виснера смогла бы найти применение в криптографии. Для того чтобы Ева сумела дешифровать зашифрованное сообщение между Алисой и Бобом, она вначале должна перехватить его, что означает, что она должна каким-то образом точно определить содержимое передаваемого сообщения. Квантовые деньги Виснера были надежными, поскольку точно определить поляризацию фотонов, находящихся в ловушках в долларовой банкноте, было невозможно. Беннет и Брассард задались вопросом, что произойдет, если зашифрованное сообщение будет представлено, а затем передано с помощью поляризованных фотонов. Вроде бы, теоретически, Ева не сможет безошибочно прочесть зашифрованное сообщение, а раз не сможет прочесть зашифрованное сообщение, то не сможет и дешифровать его.
Беннет и Брассард стали придумывать систему, которая работала бы по следующему принципу. Представьте себе, что Алиса хочет отправить Бобу зашифрованное сообщение, которое состоит из последовательности 1 и 0. Вместо этих 1 и 0 она посылает фотоны с определенными поляризациями. У Алисы есть две возможных схемы, с помощью которых она может связать поляризации фотонов с 1 или 0. В первой схеме, называемой ортогональной [37]Иногда называют также прямолинейной. — Прим. пер.
или +-схемой, для представления 1 она посылает
, а для представления 0 —
. Во второй схеме, называемой диагональной или Х-схемой, для представления 1 она посылает
, а для представления 0 —
.
При отправке сообщения, представленного в двоичном виде, она постоянно переключается с одной схемы на другую совершенно непредсказуемым образом. Так что двоичное сообщение 1101101001 может быть передано следующим образом:
Алиса передает первую 1 с использованием +-схемы, а вторую 1 — с использованием Х-схемы. Так что в обоих случаях передается 1, но всякий раз она представляется различным образом поляризованными фотонами.
Если Ева захочет перехватить это сообщение, ей потребуется определить поляризацию каждого фотона, точно так же как и фальшивомонетчику необходимо определить поляризацию каждого фотона в ловушках для фотонов долларовой банкноты. Чтобы измерить поляризацию каждого фотона, Ева должна решить, каким образом сориентировать свой поляризационный фильтр по мере прихода каждого фотона. Она не может знать наверняка, какой схемой воспользовалась Алиса для каждого из фотонов, поэтому наугад выбирает ориентацию поляризационного фильтра, которая окажется неверной в половине случаев. А следовательно, она не сможет точно определить содержимое передаваемого сообщения.
Чтобы было проще представить себе затруднительность положения Евы, предположим, что в ее распоряжении имеются два типа детекторов для определения поляризации. +-детектор способен с абсолютной точностью измерять горизонтально и вертикально поляризованные фотоны, на не может достоверно измерить диагонально поляризованные фотоны и просто ошибочно считает их вертикально или горизонтально поляризованными фотонами. С другой стороны, Х-детектор может с абсолютной точностью измерять диагонально поляризованные фотоны но не способен надежно измерить горизонтально и вертикально поляризованные фотоны, ошибочно считая их диагонально поляризованными фотонами. Так, если для измерения первого фотона, имеющего
поляризацию, Ева использует Х-детектор, то она ошибочно посчитает его фотоном с поляризациями
или
. Если Ева ошибочно посчитала его
фотоном, то проблемы у нее не возникнет, потому что он также представляет собой 1, но вот если она ошибочно посчитала его
фотоном, то это станет для нее бедой, ибо этот фотон представляет собой 0. Что еще хуже, так это то, что у Евы есть только один шанс точно измерить фотон. Фотон неделим, и поэтому она не может разделить его на два фотона и измерить их с помощью обеих схем.
Похоже, что у данной системы есть ряд славных свойств. Ева не может быть уверенной в точном перехвате зашифрованного сообщения, так что у нее нет никакой надежды и дешифровать его. Правда, данной системе присуща серьезная и, видимо, неразрешимая проблема: Боб находится в том же положении, что и Ева, так как у него также нет возможности узнать, какой поляризационной схемой воспользовалась Алиса для каждого из фотонов, и поэтому он тоже будет ошибаться при приеме сообщения. Очевидное решение проблемы — это согласование Алисой и Бобом, какую поляризационную схему они будут применять для каждого фотона. Для вышеприведенного примера Алиса и Боб должны иметь список, или ключ, с помощью которого будет прочитано + х + х х х + + х х. Однако мы теперь вновь вернулись к той же старой проблеме распределения ключей: каким образом Алиса должна безопасно передать список поляризационных схем Бобу?
Разумеется, Алиса могла бы зашифровать список поляризационных схем с помощью шифра с общим ключом, например, RSA, а затем отправить его Бобу. Представьте, однако, что мы живем в то время, когда RSA взломан, возможно, в результате создания мощных квантовых компьютеров. Система Беннета и Брассарда должна быть независимой и не опираться на RSA. В течение долгих месяцев Беннет и Брассард пытались придумать способ обойти проблему распределения ключей. В 1984 году оба они стояли на платформе станции Кротон-Хармон неподалеку от исследовательской лаборатории Томаса Дж. Уотсона компании IBM. Они ожидали поезд, который доставил бы Брассарда обратно в Монреаль, и проводили время в непринужденной беседе о злоключениях и бедствиях Алисы, Боба и Евы. Приди поезд на несколько минут раньше, они бы помахали друг другу рукой на прощание, а проблема распределения ключей так и осталась бы нерешенной. Но вместо этого — эврика! — они создали квантовую криптографию — самый стойкий вид криптографии, который был когда-либо придуман.
По их способу для квантовой, криптографии требуется три подготовительных этапа. Хотя эти этапы не включают в себя отправку зашифрованного сообщения, с их помощью осуществляется безопасный обмен ключом, с помощью которого позднее можно будет зашифровать сообщение.
Этап 1. Алиса начинает передавать случайную последовательность из 1 и 0 (биты), используя для этого случайным образом выбираемые ортогональные (горизонтальная и вертикальная поляризации) и диагональные поляризационные схемы. На рисунке 76 показана такая последовательность фотонов, движущихся к Бобу.
Этап 2. Боб должен измерить поляризацию этих фотонов. Поскольку он не имеет представления, какой поляризационной схемой Алиса пользовалась для каждого из фотонов, то в произвольном порядке выбирает +-детектор и Х — детектор. Иногда Боб выбирает правильный детектор, иногда — нет. Если Боб воспользуется не тем детектором, то он вполне может неправильно распознать фотон Алисы. В таблице 27 указаны все возможные случаи. К примеру, в верхней строке для посылки 1 Алиса использует ортогональную схему и поэтому передает
; далее Боб использует правильный детектор, определяет
и выписывает 1 в качестве первого бита последовательности. В следующей строке действия Алисы те же самые, но Боб теперь использует неверный детектор, и поэтому он может определить
или
, что означает, что либо он верно выпишет 1, либо неверно — 0.
Этап 3. К этому моменту Алиса уже отправила последовательность 1 и 0, а Боб уже определил их; какие-то правильно, какие-то — нет. После этого Алиса звонит Бобу по обычной незащищенной линии и сообщает ему, какую поляризационную схему она использовала для каждого фотона, но не как она поляризовала каждый из фотонов. Так, она может сказать, что первый фотон был послан с использованием ортогональной схемы, но не скажет, какой это был фотон:
или
. Боб сообщает Алисе, в каких случаях он угадал с правильной поляризационной схемой. В этих случаях он, несомненно, измерил правильную поляризацию и верно выписал 1 или 0. В конечном итоге Алиса и Боб игнорируют все те фотоны, для которых Боб пользовался неверной схемой, и используют только те из них, для которых он угадал с правильной схемой. В действительности они создали новую, более короткую последовательность битов, состоящих только из правильных измерений Боба. Весь этот этап изображен в виде таблицы в нижней части рисунка 76.
Благодаря этим трем этапам, Алисе и Бобу удалось образовать общую согласованную последовательность цифр, 11001001, которая показана на рисунке 76. Ключевым для этой последовательности является то, что она случайна, поскольку получена из исходной последовательности Алисы, которая сама была случайной. Более того, события, когда Боб использует правильный детектор, сами являются случайными. Поэтому данная согласованная последовательность может использоваться в качестве случайного ключа. И вот теперь-то можно начать процесс зашифровывания.
Рис. 76 Алиса передает последовательность из 1 и 0 Бобу. Каждая 1 и каждый О представлены поляризованным фотоном в соответствии либо с ортогональной (горизонтальная и вертикальная поляризации), либо с диагональной поляризационной схемой. Боб измеряет каждый фотон с помощью либо своего ортогонального, либо диагонального детектора. Он выбирает правильный детектор для самого первого фотона и верно определяет его как 1. Однако для следующего фотона его выбор детектора неверен. По случайности он правильно определил его как 0, но позднее этот бит будет тем не менее отброшен, поскольку Боб не может быть уверен, что он измерил его правильно.
Таблица 27 Все возможные случаи на втором этапе при обмене фотонами между Алисой и Бобом.
#i_173.png
Эта согласованная случайная последовательность может использоваться в качестве ключа для шифра одноразового шифрблокнота. В главе 3 описывается, каким образом случайный набор букв или цифр — одноразовый шифрблокнот — может создать нераскрываемый шифр — не практически, а абсолютно нераскрываемый. Ранее говорилось, что единственная проблема с одноразовым шифрблокнотом — это сложность его безопасной доставки, но способ Беннета и Брассарда решает эту проблему. Алиса и Боб достигли договоренности об одноразовом шифрблокноте, а законы квантовой физики фактически не позволяют Еве успешно его перехватить. Теперь самое время стать на место Евы, после чего мы увидим, почему она не сумеет перехватить ключ.
Во время передачи Алисой поляризованных фотонов Ева пытается измерить их, но она не знает, использовать ли +-детектор или, может быть, Х — детектор. В половине случаев выбор детектора будет неверным. Это та же самая ситуация, в которой находится и Боб, поскольку он тоже в половине случаев выбирает неправильный детектор. Однако после этой передачи Алиса сообщает Бобу, какой схемой он должен был воспользоваться для каждого из фотонов, и они договариваются использовать только те фотоны, которые были измерены при использовании Бобом правильного детектора. Это, впрочем, ничем не поможет Еве, поскольку половину из этих фотонов она измерит не тем детектором, который был нужен, и поэтому неверно определит некоторые фотоны, которые составляют окончательный ключ.
Можно также рассматривать квантовую криптографию на примере колоды карт, а не поляризованных фотонов. У каждой игральной карты есть достоинство и масть, например, валет червей или шестерка треф, и, как правило, мы, взглянув на карту, сразу же видим ее достоинство и масть. Представьте, однако, что можно измерить либо только достоинство, либо только масть, но никак не обе вместе. Алиса берет карту из колоды и должна решить, что измерить: достоинство или масть. Предположим, что она решила измерить масть, которая является «пиками». Этой взятой картой оказалась четверка пик, но Алиса знает только, что это пики. После этого она передает карту по телефону Бобу. В этот момент Ева старается провести измерение карты, но, к сожалению, она решила измерить ее достоинство, которое является «четверкой». Когда карта приходит к Бобу, он решает измерить ее масть, которая по-прежнему «пики», и он записывает ее. После этого Алиса звонит Бобу и спрашивает его, масть ли он измерил, — а как раз это он и сделал, так что Алиса и Боб теперь знают, что у них есть некоторая общая информация: они оба на своих блокнотах сделали запись «пики». Ева же в своем блокноте сделала запись «четверка», что вообще не имеет никакой пользы.
После этого Алиса берет из колоды другую карту, скажем, короля бубей, но она, опять-таки, может измерить только один параметр. На этот раз она решает измерить ее достоинство, которое будет «король», и передает карту по телефону Бобу. Ева старается провести измерение карты и также делает выбор в пользу измерения ее достоинства — «король». Когда карта приходит к Бобу, он решает измерить ее масть, являющуюся «бубнами». После этого Алиса звонит Бобу и спрашивает его, достоинство ли карты он измерил, — и тот должен признать, что на этот раз он ошибся и измерил ее масть. Алиса и Боб не беспокоятся об этом, поскольку могут проигнорировать эту конкретную карту и повторить попытку с другой картой, наобум вытащенной из колоды. В этом последнем случае догадка Евы оказалась правильной, и она измерила то же, что и Алиса — «король», — но карта была отброшена, потому что Боб неправильно измерил ее. Таким образом Боб не беспокоится о сроих ошибках, так как они с Алисой могут условиться пропускать их, Ева же со своими ошибками осталась у разбитого корыта. После того как будут посланы несколько карт, Алиса и Боб имеют возможность договориться о последовательности мастей и достоинств, которые могут затем быть использованы в качестве основы для некоторого ключа.
Квантовая криптография позволяет Алисе и Бобу договориться о ключе, Ева же не может перехватить этот ключ, не сделав ошибок. Более того, у квантовой криптографии есть еще одно достоинство: она позволяет Алисе и Бобу определить, перехватывает ли Ева сообщения. Присутствие Евы в телефонной линии становится явным, потому что всякий раз, как она измеряет фотон, она рискует изменить его, и эти изменения видны Алисе и Бобу.
Допустим, что Алиса посылает
, а Ева измеряет его неправильно выбранным детектором — +-детектор. +-детектор преобразует поступающий
фотон, и тот на выходе детектора становится либо
, либо
фотоном, поскольку для фотона это единственная возможность пройти через детектор Евы. Если Боб измеряет этот видоизмененный фотон своим Х — детектором, то тогда он может либо зарегистрировать
, что на самом деле послала Алиса, или же он может получить
, то есть измерение окажется неверным. Для Алисы и Боба это окажется непонятной ситуацией, ведь Алиса послала диагонально поляризованный фотон, и Боб воспользовался нужным детектором, и все же он смог измерить его неверно. Короче говоря, когда Ева выбирает неправильный детектор, она «исказит» некоторые фотоны, и это заставит Боба сообщить по телефону об ошибках, даже если он воспользовался правильно выбранным детектором. Эти ошибки могут быть обнаружены, если Алиса и Боб выполняют обычную проверку на наличие ошибок.
Проверка на наличие ошибок проводится после трех предварительных этапов; к этому времени Алиса и Боб уже получили одинаковые последовательности из 1 и 0. Допустим, что они создали последовательность, состоящую из 1075 двоичных цифр. У Алисы и Боба есть только один способ проверить, что их соответствующие последовательности совпадают: Алиса звонит Бобу и зачитывает ему свою последовательность целиком. К сожалению, если Ева осуществляет перехват сообщений, она сможет перехватить и полный ключ. Ясно, что проверять всю последовательность неразумно, да в этом и нет необходимости. Вместо этого Алиса просто должна выбрать какие-нибудь произвольные 75 цифр и проверить только их. Если эти 75 цифр совпадают с теми, которые получил Боб, то весьма маловероятно, чтобы Ева смогла осуществить перехват в процессе первоначальной передачи фотонов. В действительности, вероятность того, что Ева подключилась к телефонной линии и не повлияла на измерения Боба этих 75 цифр, составляет менее одной триллионной. Ввиду того, что эти 75 цифр открыто обсуждались Алисой и Бобом, они просто отбрасывают их, и их одноразовый шифрблокнот таким образом сокращается с 1075 до 1000 двоичных цифр. С другой стороны, если Алиса и Боб обнаружат несоответствие среди этих 75 цифр, тогда им станет известно, что Ева осуществила перехват; в этом случае им придется отказаться полностью от этого одноразового шифрблокнота, перейти на другой телефон и начать все заново.
Подведем итог. Квантовая криптография является системой, которая обеспечивает секретность связи, не позволяя Еве безошибочно прочесть сообщение между Алисой и Бобом. Более того, если Ева попробует осуществить перехват, то Алиса и Боб смогут обнаружить ее присутствие. Тем самым квантовая криптография дает Алисе и Бобу возможность обменяться информацией и согласовать одноразовый шифрблокнот совершенно конфиденциальным образом, после чего они смогут использовать его в качестве ключа для зашифровываю«! сообщения. Этот способ состоит из пяти основных этапов:
(1) Алиса посылает Бобу последовательность фотонов, а Боб измеряет их.
(2) Алиса сообщает Бобу, в каких случаях он измерил их правильно. (Хотя Алиса и говорит Бобу, когда он выполнил правильное измерение, она не сообщает ему, каков должен быть правильный результат, так что, даже если подслушивать их разговор, это не представляет ровным счетом никакой опасности.)
(3) Чтобы создать пару идентичных одноразовых шифрблокнотов, Алиса и Боб отбрасывают те измерения, которые Боб выполнил неверно, и используют те из них, которые он выполнил правильно.
(4) Алиса и Боб проверяют неприкосновенность своих одноразовых шифрблокнотов путем сличения нескольких цифр.
(5) Если процедура проверки показала удовлетворительные результаты, они могут использовать одноразовый шифрблокнот для зашифровывания сообщения; если же проверка выявила ошибки, то им становится известно, что Ева осуществила перехват фотонов, и им следует начать все заново.
Статья Виснера о квантовых деньгах, спустя четырнадцать лет после того, как была отклонена научными журналами, послужила причиной появления абсолютно стойкой системы связи. Теперь, живя в Израиле, Виснер испытывает удовлетворение от того, что наконец-то его работа получила признание: «Вглядываясь назад, я думаю, смог ли бы сделать больше этого. Люди осудили меня за то, что я бросил это дело, за то, что я не приложил никаких дополнительных усилий для опубликования своей идеи; я полагаю, что они в какой-то мере правы, но я, был молодым аспирантом, и ко мне не было особого доверия. Во всяком случае, квантовые деньги, похоже, никого не интересовали».
Криптографы с энтузиазмом восприняли квантовую криптографию Беннета и Брассарда. Однако многие экспериментаторы считают, что эта система хорошо работает в теории, но окажется непригодной на практике. Они полагают, что из-за сложности обращения с отдельными фотонами эту систему реализовать будет невозможно. Но несмотря на эти критические замечания Беннет и Брассард убеждены, что квантовую криптографию можно заставить работать. На самом деле они настолько верят в нее, что создание аппаратуры их совершенно не беспокоит. Как однажды заявил Беннет: «Нет никакого смысла отправляться на Северный полюс, если вы знаете, что он находится там».
Однако растущий скептицизм в конечном счете вынудил Беннета представить доказательства, что система действительно может работать. В 1988 году он начал собирать компоненты, необходимые для создания квантовой криптографической системы и пригласил аспиранта Джона Смолина помочь ему собрать установку. Год спустя они уже готовы были попытаться послать первое сообщение, зашифрованное с помощью квантовой криптографии. Как-то поздним вечером они уединились в своей лаборатории, куда не мог извне проникнуть свет, а внутри все было черным, как смоль, что предохраняло от случайных фотонов, которые могли бы помешать эксперименту. Плотно пообедав, они были вполне готовы к работе на установке в течение всей длинной ночи. Они начали с того, что попытались послать поляризованные фотоны через комнату, а затем измерить их с помощью +-детектора и Х-детектора. Компьютер, в итоге названный «Алисой», контролировал передачу фотонов, а компьютер, названный «Бобом», принимал решение, какой из детекторов следовало использовать для измерения каждого фотон.
Примерно в 3 часа утра Беннет зарегистрировал первый квантовокриптографический обмен. «Алиса» и «Боб» сумели отправить и принять фотоны, они «обсудили» поляризационные схемы, которые использовала «Алиса», они отбросили те фотоны, которые были измерены «Бобом» с помощью неправильного детектора, и они согласовали одноразовый шифрблокнот, состоящий из оставшихся фотонов. «Не было никакого сомнения, что это будет работать, — заявил Беннет, — единственно, только наши пальцы могут оказаться слишком неуклюжими, чтобы построить ее». Эксперимент Беннета показал, что два компьютера — «Алиса» и «Боб» — смогли осуществить абсолютно секретную связь. Это был исторический эксперимент, несмотря на тот факт, что эти два компьютера находились на расстоянии всего лишь 30 см.
С момента эксперимента Беннета основной задачей стало создание квантовой криптографической системы, которая смогла бы работать на значительных расстояниях. Это не простая задача, поскольку фотоны «ведут себя нехорошо». Если Алиса передает фотон с определенной поляризацией по воздуху, то молекулы воздуха будут взаимодействовать с ним, приводя к изменению его поляризации, что недопустимо. Более подходящей средой для передачи фотонов является оптоволокно, и в настоящее время исследователи преуспели в применении его для создания квантовых криптографических систем, которые действуют на больших расстояниях. В 1995 году исследователям из Женевского университета удалось реализовать квантовую криптографию по оптоволоконному кабелю протяженностью 23 км от Женевы до города Нион.
Совсем недавно группа ученых из Лос-Аламосской национальной лаборатории в Нью-Мексико снова приступила к экспериментам с квантовой криптографией в воздухе. Их конечной целью является создание квантовой криптографической системы, которая сможет работать через спутники. Если они сумеют этого добиться, то это позволит создать абсолютно стойкую глобальную связь. Пока что Лос-Аламосской группе удалось передать квантовый ключ через воздух на расстояние 1 км.
Нынче эксперты по безопасности задаются вопросом, сколько пройдет времени, пока квантовая криптография не станет реальностью. Сегодня квантовая криптография не дает никаких преимуществ, так как шифр RSA уже обеспечивает нам доступ к практически неразрываемому шифрованию. Однако как только квантовые компьютеры станут реальностью, то RSA и все другие современные шифры окажутся бесполезными и квантовая криптография превратится в необходимость. Так что гонка продолжается. Действительно важным является вопрос: вовремя ли появится квантовая криптография, чтобы спасти нас от квантовых компьютеров, или же между созданием квантовых компьютеров и появлением квантовой криптографии возникнет брешь. До сих пор квантовая криптография была более передовой технологией. Эксперимент в Швейцарии с оптоволоконными кабелями продемонстрировал, что вполне реально создать систему, которая позволит обеспечить секретную связь между финансовыми учреждениями в пределах одного города. Более того, в настоящее время можно уже создать канал линии передачи с использованием квантовой криптографии между Белым домом и Пентагоном. Не исключено, что такой канал уже существует.
Квантовая криптография означала бы конец противостоянию между шифровальщиками и дешифровальщиками, и шифровальщики оказались бы победителями. Квантовая криптография является нераскрываемой системой шифрования. Возможно, что это покажется преувеличением, особенно в свете предыдущих подобных заявлений. За последние две тысячи лет криптографы в разное время были уверены, что одноалфавитный шифр, многоалфавитный шифр и машинные шифры, как, например, шифр «Энигмы», были нераскрываемыми. В каждом из этих случаев криптографы в конце концов убеждались в своей неправоте, поскольку их заявления основывались исключительно на том факте, что в какой-то момент истории сложность шифров опережала мастерство и методы криптоаналитиков. Оглядываясь в прошлое, мы можем видеть, что криптоаналитики рано или поздно, но находили способ взлома всех этих шифров или создавали метод, который помогал их взломать.
Однако заявление, что квантовая криптография является стойкой, качественно отличается от всех прежних заявлений. Квантовая криптография является не просто практически нераскрываемой, она нераскрываема совершенно. Квантовая теория — самая удачная теория в истории физики — подразумевает, что Ева никогда не сможет безошибочно перехватить криптографический ключ одноразового использования, который был создан Алисой и Бобом. Ева не сможет даже попытаться перехватить криптографический ключ одноразового использования без того, чтобы Алиса и Боб не были предупреждены о ее действиях. На самом деле, если бы сообщение, защищенное с использованием квантовой криптографии, оказалось бы когда-нибудь расшифровано, это означало бы, что квантовая теория ошибочна, что имело бы ужасающие последствия для физиков — им пришлось бы заново пересмотреть свое понимание действия самых фундаментальных законов Вселенной.
Если смогут быть созданы квантовые криптографические системы, способные действовать на значительных расстояниях, развитие шифров остановится. Поиск обеспечения секретности закончится. Данная технология для обеспечения безопасной связи будет доступна правительству, вооруженным силам, предприятиям, компаниям и обществу. Останется только один вопрос: позволят ли нам правительства воспользоваться данной технологией? И каким образом правительства станут осуществлять управление квантовой криптографией, чтобы обогатить информационный век, но при этом не защитить преступников?
Вызов читателям. Задачи по дешифрованию
Вызов читателям в виде задач по дешифрованию — это десять зашифрованных сообщений, которые я поместил в первом издании «Книги шифров», вышедшем в 1999 году. Помимо интеллектуального удовлетворения от разгадки всех десяти сообщений, была назначена премия в размере 10000 фунтов стерлингов для того, кто первым решит все задачи. Они были в конечном итоге решены 7 октября 2000 года, через один год и один месяц напряженных усилий любителей и профессионалов — дешифровальщиков со всего мира.
Задачи по дешифрованию остались частью этой книги. Премии за их решение больше нет, но я бы посоветовал читателям попробовать свои силы в дешифровании каких-нибудь из них. Предполагалось, что сложность этих десяти задач будет постепенно возрастать, хотя многие дешифровальщики посчитали, что задача 3 сложнее задачи 4. Шифры в этих задачах различны и охватывают целые столетия, так что в начале использованы старинные шифры, раскрыть которые достаточно просто, тогда как в последних задачах используются современные шифры, и для них потребуется гораздо больше усилий. Короче говоря, задачи (ступени) с 1 по 4 предназначены для любителей, задачи с 5 по 8 — для подлинных энтузиастов, а 9 и 10 — для тех, кто посвятил себя делу дешифрования.
Если вы хотите больше узнать о задачах по дешифрованию, вы можете зайти на мой веб-сайт (), где дается различная информация, в том числе и ссылка на сообщение, написанное победителями этого вызова: Фредриком Альмгреном, Гуннаром Андерсоном, Торбьерном Гранлундом, Ларсом Ивансоном и Стефаном Ульфбергом. Это сообщение прекрасно читается, но помните, что в нем, как и в других материалах на этом веб-сайте, используется много дополнительных сведений, которые вам, может, пока еще будут неинтересны.
Основная цель вызова состояла в том, чтобы пробудить интерес людей, заинтересовать их криптографией и взломом шифров. Тот факт, что вызов приняли тысячи человек, доставляет мне огромное удовлетворение. В настоящее время действие вызова формально закончилось, но я надеюсь, он будет по-прежнему будить интерес среди новых читателей, тех, кто захочет проверить свое мастерство и умение во взломе шифров.
Удачи вам, Саймон Сингх
Задача 1: Простой одноалфавитный шифр замены
Задача 2: Шифр Цезаря
#i_181.png
Задача 3: Одноалфавитный шифр с омофонами
#i_182.png
Задача 4: Шифр Виженера
Задача 5
Задача 6
Задача 7
#i_191.png
Задача 8
#i_193.png
#i_194.png
Задача 9
Задача 10
Короткое сообщение
Длинное сообщение
#i_197.png
Приложение А
Первый абзац романа Жоржа Перека «А Void» в переводе Гилберта Адэра.
Today, by radio, and also on giant hoardings, a rabbi, an admiral notorious for his links to masonry, a trio of cardinals, a trio, too, of insignificant politicians (bought and paid for by a rich and corrupt Anglo-Canadian banking corporation), inform us all of how our country now risks dying of starvation. A rumor, that’s my initial thought as I switch off my radio, a rumor or possibly a hoax. Propaganda, I murmur anxiously — as though, just by saying so, I might allay my doubts — typical politicians’ propaganda. But public opinion gradually absorbs it as a fact. Individuals start strutting around with stout clubs. ‘Food, glorious food!’ is a common cry (occasionally sung to Bart’s music), with ordinary hard-working folk harassing officials, both local and national, and cursing capitalists and captains of industry. Cops shrink from going out on night shift. In Macon a mob storms a municipal building. In Rocadamour ruffians rob a hangar full of foodstuffs, pillaging tons of tuna fish, milk and cocoa, as also a vast quantity of com — all of it, alas, totally unfit for human consumption. Without fuss or ado, and naturally without any sort of trial, an indignant crowd hangs 26 solicitors on a hastily built scaffold in front of Nancy’s law courts (this Nancy is a town, not a woman) and ransacks a local journal, a disgusting right-wing rag that is siding against it. Up and down this land of ours looting has brought docks, shops and farms to a virtual standstill.
Впервые опубликован во Франции под названием «La Disparition» («Исчезновение») издательством Denoel в 1969 году, а в Великобритании — издательством Harvill в 1994 году. Copyright © by Editions Denoel 1969; в английском переводе © Harvill 1994. Воспроизведено с разрешения Harvill Press.
Приложение B
Некоторые элементарные советы по выполнению частотного анализа
(1) Начните с подсчета частоты появления каждой из букв шифртекста. Примерно пять букв должны появляться с частотой менее 1 процента, и они, вероятно, представляют собой j, k, q, x и z. Одна из букв должна появляться с частотой более 10 процентов, и она, по-видимому, представляет собой е. Если шифртекст не подчиняется этому распределению частот, то, возможно, исходное сообщение написано не на английском языке. Вы можете определить, какой это язык, если проанализируете частотное распределение букв в шифртексте. К примеру, в итальянском языке обычно есть три буквы с частотностью более 10 процентов и 9 букв с частотностью менее 1 процента. В немецком языке буква е имеет чрезвычайно высокую частотность — 19 процентов, поэтому любой шифртекст, в котором одна из букв встречается столь же часто, является, вполне возможно, немецким. После того как вы определили язык, для выполнения частотного анализа вам следует воспользоваться соответствующей таблицей частотности букв для данного языка. Если у вас есть нужная таблица частотности букв, то нередко удается дешифровать даже шифртексты на неизвестном языке.
(2) Если установлена взаимосвязь с английским языком, но, как часто и происходит, сразу же открытый текст не появляется, тогда обратите внимание на пары повторяющихся букв. В английском языке чаще всего повторяющимися буквами будут ss, ее, tt, ff, ll, mm и оо. Если в шифртексте имеются какие-либо повторяющиеся символы, то вы можете считать, что они представляют собой одну из этих пар.
(3) Если в шифртексте имеются пробелы между словами, то постарайтесь определить слова, состоящие из одной, двух или трех букв. Единственными словами в английском языке, состоящими из одной буквы, являются а и I. Чаще всего встречающимися двухбуквенными словами будут of, to, in, it, is, Ьe, аs, аt, so, we, hе, Ьу, ог, оn, dо, if, me, my, up, an, go, no, us, am. Наиболее часто появляющиеся трехбуквенные слова — the и and.
(4) Если удастся, подготовьте таблицу частотности букв для сообщения, которое вы стараетесь дешифровать. Например, в военных донесениях стремятся опускать местоимения и артикли, и отсутствие таких слов, как I, hе, а и the, будет снижать частотность некоторых из чаще всего встречающихся букв. Если вы знаете, что работаете с военным донесением, вам следует использовать таблицу частотности букв, созданную на основе других военных донесений.
(5) Одно из самых полезных для криптоаналитика умений — это способность благодаря собственному опыту или чисто интуитивно — распознавать слова или даже целые фразы. Аль-Халил, один из первых арабских криптоаналитиков, продемонстрировал свои способности, когда взломал греческий шифртекст. Он предположил, что шифртекст начинается с приветствия «Во имя бога». Установив, что эти буквы соответствуют определенному фрагменту шифртекста, он смог использовать их в качестве лома и раскрыть остальной шифртекст. Это получило название криб.
(6) В некоторых случаях наиболее часто встречающейся буквой в шифртексте может быть Е, следующей по частоте появления — Т и так далее. Другими словами, частотность букв в шифртексте уже совпадает с частотностью букв в таблице. По-видимому, буква Е в шифртексте является действительно е, и то же самое, похоже, справедливо и для других букв, и все же шифртекст выглядит тарабарщиной. В этом случае вы столкнулись не с шифром замены, а с шифром перестановки. Все буквы остались теми же самыми, но находятся они не на своих местах.
Хорошей книгой, в которой даются начальные сведения, является «Криптоанализ» Хелен Фош Гаинэ (Dover). Наряду с советами в ней также представлены таблицы частотности букв для различных языков и приведен перечень чаще всего встречающихся слов в английском языке.
Приложение C
Так называемый Библейский код
В 1997 году книга Майкла Дроснина «Библейский код» вызвала ажиотаж в мире. Дроснин объявил, что в Библии скрыты сообщения, которые можно найти, проводя поиск по эквидистантным последовательностям букв. Если мы возьмем произвольный текст, выберем начальную букву, а затем будем двигаться вперед, перепрыгивая каждый раз через определенное количество букв, то получим эквидистантную последовательность. Так, например, в этом разделе мы могли бы начать с буквы «М» в слове Майкл и всякий раз перепрыгивать, допустим, через четыре буквы. Если бы мы отмечали каждую пятую букву, то у нас образовалась бы эквидистантная последовательность mesahirt…
Хотя в данной конкретной эквидистантной последовательности не содержится никаких осмысленных слов, Дроснин написал об открытии поразительного количества содержащихся в Библии эквидистантных последовательностей, которые не только дают осмысленные слова, Но и образуют целые предложения. Согласно Дроснину, эти предложения представляют собой библейские предсказания. К примеру, он утверждал, что обнаружил упоминание об убийстве Джона Ф. Кеннеди, Роберта Кеннеди и Анвара Садата. В одной из эквидистантных последовательностей имя Ньютона упоминается рядом с силой тяжести, а в другом Эдисон связывается с электрической лампочкой. Несмотря на то что книга Дроснина основывается на статье, опубликованной Дороном Витцумом, Элияху Рипсом и Йоавом Розенбергом, она гораздо более претенциозна по своим заявлениям и тем навлекла на себя массу критики. Основным поводом послужило то, что изучаемый текст был огромным; стоит ли удивляться, что меняя исходную точку и величину прыжка, в достаточно большом тексте могут появляться осмысленные фразы.
Брендан МакКей из Австралийского Национального университета постарался продемонстрировать необоснованность метода Дроснина путем поиска эквидистантных последовательностей в «Моби Дике» и обнаружил тринадцать сообщений, касающихся убийства известных людей, в том числе Троцкого, Ганди и Роберта Кеннеди. Более того, в текстах на иврите просто обязано быть исключительно огромное число эквидистантных последовательностей, потому что в них преимущественно нет гласных. А это означает, что толкователи могут вставлять гласные в тех местах, которые кажутся им подходящими, благодаря чему задача получения предсказаний упрощается.
Приложение D
Шифр Pigpen
Одноалфавитный шифр замены, существовавший в том или ином виде в течение целых столетий. Шифр Pigpen, например, использовался франкмасонами для обеспечения секретности своих документов еще в восемнадцатом веке, но и по сей день применяется школьниками. В шифре не производится замена одной буквы другой; здесь каждая буква заменяется символом по следующему образцу.
Чтобы зашифровать определенную букву, определите ее местонахождение в одной из четырех сеток, а затем нарисуйте ту часть сетки, которая соответствует этой букве. Таким образом:
#i_199.png
Если вы знаете ключ, то расшифровать шифр Pigpen легко. Если же нет, то его легко взломать с помощью:
Приложение E
Шифр Плейфера
Шифр Плейфера стал известным благодаря Леону Плейферу, первому барону Плейферу из Сент-Эндрюса, однако придумал его сэр Чарльз Уитстон, один из первооткрывателей электрического телеграфа. Оба они жили неподалеку друг от друга, буквально через Хаммерсмитский мост, и нередко встречались, чтобы поделиться своими мыслями о криптографии.
В шифре каждая пара букв открытого текста заменяется другой парой букв. Чтобы зашифровать и передать сообщение, отправитель и получатель должны вначале условиться между собой о ключевом слове. К примеру, в качестве ключевого слова мы можем использовать имя Уитстона — CHARLES. Затем, перед тем как приступить к зашифровыванию, буквы алфавита, начиная с ключевого слова, вписываются в квадрат 5 x 5, при этом буквы I и J объединяются вместе:
Далее сообщение разбивается на пары букв, или диграфы. Во всех диграфах обе буквы должны быть различными. Для этого, как показано в следующем примере, в слове hammersmith между удвоенной буквой m вставляется дополнительная буква х. Кроме того, к концу предложения дописывается еще одна дополнительная буква х, чтобы вместо остающейся одиночной буквы также получался диграф:
Теперь можно приступать к зашифровыванию. Все диграфы относятся к одной из трех категорий: (а) обе буквы находятся в одной строке, (б) обе буквы находятся в одном столбце, (в) обе буквы находятся в разных строках и столбцах. Если обе буквы находятся в одной строке, то каждая из них заменяется соседней, стоящей справа от нее буквой; таким образом mi преобразуется в NK. Если одна из букв находится в конце строки, то она заменяется первой буквой строки; тем самым ni становится GK. Если обе буквы находятся в одном столбце, то каждая из них заменяется буквой, находящейся непосредственно под ней; так что вместо ge получается OG. Если одна из букв является нижней буквой столбца, то она заменяется верхней буквой столбца; таким образом vе заменяется на CG.
Если же буквы диграфа находятся в разных строках и столбцах, шифровальщик поступает по-другому. Чтобы зашифровать первую букву, двигайтесь вдоль строки, в которой находится первая буква, пока не достигнете столбца, в котором находится вторая буква; после чего замените первую букву буквой, находящейся на пересечении этой строки и столбца. Чтобы зашифровать вторую букву, двигайтесь вдоль строки, в которой находится вторая буква, пока не достигнете столбца, в котором находится первая буква; после чего замените вторую букву буквой, находящейся на пересечении этой строки и столбца. Таким образом, mе станет GD, а еt преобразуется в DO. Полностью зашифрованное сообщение примет вид:
Получатель, которому известно ключевое слово, может легко расшифровать шифртекст, просто выполняя ту же операцию в обратном порядке. К примеру, зашифрованные буквы, находящиеся в одной строке, расшифровываются путем замены их буквами, стоящими слева от них.
Плейфер был не только ученым, но и выдающимся общественным деятелем (вице-спикер палаты общин, министр почт и специальный уполномоченный по здравоохранению, который помог заложить современную основу санитарии), и его попросили поддержать идею Уитстона среди политических деятелей самого высокого ранга. Он впервые упомянул об этом на обеде в 1854 году перед принцем Альбертом и будущим премьер-министром лордом Пальмерстоном, а позднее представил Уитстона заместителю министра иностранных дел. К сожалению, заместитель министра посетовал, что эта система слишком сложна для использования в условиях сражения, на что Уитстон заявил, что смог бы научить этому способу мальчиков из ближайшей начальной школы за 15 минут. «Вполне возможно, что это и так, — ответил заместитель министра, — но вы никогда не сумеете научить этому никого из атташе».
Плейфер продолжал настаивать, и в конце концов британское военное министерство втайне приняло эту систему и, по-видимому, впервые использовало ее в англо-бурской войне. Хотя какое-то время она была эффективной, шифр Плейфера оказался далеко не неуязвимым. Его можно было атаковать, отыскивая в шифртексте чаще всего появляющиеся диграфы и предполагая, что они представляют собой чаще всего встречающиеся диграфы в английском языке: th, Ье, аn, in, ег, ге, еs.
Приложение F
Шифр ADFGVX
Особенность шифра ADFGVX состоит в том, что здесь осуществляется и замена, и перестановка. Зашифровывание начинается с того, что рисуется сетка 6 x 6, и 36 квадратов заполняются 26 буквами и 10 цифрами в произвольном порядке. Каждая строка и столбец сетки задается одной из шести букв: А, О, Р, в, V или X. Расположение элементов в сетке служит в качестве части ключа, поэтому получателю, чтобы расшифровать сообщение, необходимо знать, как они в ней располагаются.
На первом этапе зашифровывания следует взять каждый символ сообщения, определить его положение в сетке и заменить его буквами, которые обозначают строку и столбец. Так, 8 будет заменено на АА, а р — на AD. Ниже, в качестве примера, показано зашифрованное этим способом короткое сообщение:
Пока что это — использование простого одноалфавитного шифра замены, и, чтобы взломать сообщение, достаточно воспользоваться частотным анализом. Однако второй этап — применение перестановки, что делает криптоанализ гораздо сложнее. Перестановка зависит от ключевого слова, которым, в нашем случае, будет слово MARK и которое должно быть известно получателю.
Перестановка производится следующим способом. Вначале в верхней строке незаполненной сетки записываются буквы ключевого слова. Далее, как показано ниже, под этим словом построчно записывается зашифрованный текст, полученный на первом шаге зашифровывания. Затем столбцы сетки переставляются местами таким образом, чтобы буквы ключевого слова шли в алфавитном порядке. После этого, двигаясь сверху вниз поочередно по каждому столбцу, выписываются буквы, которые и образуют окончательный вид шифртекста.
В этом виде шифртекст будет затем передан с помощью кода Морзе; получателю, чтобы восстановить первоначальный текст, потребуется выполнить действия, обратные зашифровыванию. Шифртекст состоит всего лишь из шести букв (т. е. А, D, F, G, V, X), так как этими буквами обозначаются строки и столбцы исходной сетки 6 x 6. Люди часто удивляются, почему были выбраны именно эти буквы, а не, скажем, А, В, С, D, Е и F. Все дело в том, что если буквы А, D, F, G, V и X представить в виде точек и тире кода Морзе, то они будут существенно отличаться одна от другой; тем самым выбор этих букв минимизирует опасность появления ошибок во время передачи.
Приложение G
Слабости повторного использования одноразового шифрблокнота
По причинам, изложенным в главе 3, шифртексты, зашифрованные с помощью шифра из одноразового шифрблокнота, являются нераскрываемыми. Однако это относится к одноразовому шифрблокноту, который используется один, и только один раз. Если же мы сумели перехватить два различных шифртекста, которые были зашифрованы с помощью одного и того же одноразового шифрблокнота, мы сможем дешифровать их следующим образом.
Мы, вероятно, будем правы, если предположим, что в первом шифртексте где-то есть слово the, и поэтому криптоанализ начинается с допущения, что все сообщение целиком состоит из последовательности слов the. Далее мы полагаем, что искомый одноразовый шифрблокнот преобразует всю эту последовательность слов the в первый шифртекст. Это станет нашим исходным предположением об одноразовом шифрблокноте. Но как же мы сможем узнать, какие части этого одноразового шифрблокнота правильны?
Мы можем применить наше исходное предположение об одноразовом шифрблокноте ко второму шифртексту и посмотреть, имеет ли какой-нибудь смысл получающийся открытый текст. Если нам улыбнется удача, мы сможем распознать несколько фрагментов слов во втором открытом тексте, что укажет нам, что соответствующие части одноразового шифрблокнота верны. А это, в свою очередь, укажет нам, в каких местах первого сообщения должны стоять the.
Восстанавливая фрагменты слов, которые мы отыскали во втором открытом тексте, до полных слов, мы можем узнать больше об одноразовом шифрблокноте, а затем выявить новые фрагменты в первом открытом тексте. Путем восстановления этих фрагментов в первом открытом тексте, мы можем узнать еще больше об одноразовом шифрблокноте, а затем определить новые фрагменты во втором открытом тексте. Мы можем продолжать этот процесс до тех пор, пока не расшифруем оба открытых текста.
Это очень напоминает дешифрование сообщения, зашифрованного шифром Виженера с использованием ключа, состоящего из нескольких слов, что было показано в главе 3, где ключом являлось CANADABRAZILEGYPTCUBA.
Приложение H
Решение кроссворда, опубликованного в «Дейли Телеграф»
#i_207.png
Упражнения для заинтересовавшихся читателей
Некоторые самые значительные дешифрования в истории были сделаны непрофессионалами. Так, Георг Гротефенд, положивший начало дешифрованию клинописи, был школьным учителем. Для тех читателей, кого влечет последовать по его стопам, есть несколько письменностей, которые по-прежнему представляют загадку. Линейное письмо А — минойская письменность — успешно противостоит всем попыткам дешифрования, отчасти из-за недостаточности материала. Этрусская письменность не страдает от этой проблемы — для изучения имеется более 10 000 надписей, — но и она также ставит в тупик ученых с мировым именем. Равно непостижимо и иберийское письмо — еще одна доримская письменность.
Самое любопытное древнее европейское письмо обнаружено на единственном фестосском диске, найденном в южной части Крита в 1908 году. На этой круглой табличке, датируемой примерно 1700 годом до н. э., с каждой стороны сделана надпись, идущая в виде спирали. Знаки на диске выполнены не вручную, а оттиснуты с помощью множества печатей; это пример самого древнего в мире использования «пишущей машинки». Удивительно то, что больше никогда ничего похожего не находили, и потому для дешифрования имеется очень ограниченная информация: всего лишь 242 символа, разделенных на 61 группу. Однако отпечатанный на пишущей машинке документ подразумевает массовое производство, так что есть надежда, что археологи в конце концов отыщут склад подобных дисков и прольют свет на эту неподдающуюся письменность.
За пределами Европы одной из самых значительных задач является дешифрование письменности бронзового века протоиндийской цивилизации, которую можно обнаружить на тысячах печатей, начиная с третьего тысячелетия до н. э. На каждой печати изображено какое-либо животное и имеется короткая надпись, но что они означают — до сих пор ставит в тупик всех специалистов. В одном необычном случае надпись обнаружили на большой деревянной доске, и она была выполнена гигантскими буквами 37 см высотой. Это мог быть самый древний в мире рекламный щит. Что, в свою очередь, означает, что грамотность не являлась привилегией исключительно элиты, и возникает вопрос, о чем же говорится в объявлении? Вероятнее всего, что это была часть рекламной кампании по выборам короля, и если бы можно было установить его личность, то этот рекламный щит проложил бы путь к остальной части письменности.
Приложение J
Математика RSA
Ниже в несложном виде дается математическое описание принципа шифрования и дешифрования с помощью RSA.
(1) Алиса выбирает два гигантских простых числа р и q. Простые числа должны быть громадными, но мы, для простоты, предположим, что Алиса выбрала числа р = 17, q = 11. Она должна хранить эти числа в секрете.
(2) Алиса перемножает их и получает число N. В нашем случае N = 187. Теперь она выбирает еще одно число — е; в нашем случае она выбрала е = 7.
(е и (р- 1) х (q — 1) должны быть взаимно простыми, но это — техническая сторона дела).
(3) Алиса может теперь опубликовать е и N в чем-то сродни телефонному справочнику. Поскольку эти два числа необходимы для зашифровывания, они должны быть доступны всем, кто захочет зашифровать сообщение для Алисы. Вместе эти числа называются открытым ключом. (Это число е может являться частью открытого ключа не только Алисы, но и любого другого человека. Однако у всех остальных должны быть иные значения N, которые зависят от выбора р и q.)
(4) Перед тем как приступить к зашифровыванию сообщения, оно должно быть вначале преобразовано в число М. Например, слово заменяется на двоичные цифры ASCII-кода, а эти двоичные цифры могут рассматриваться как десятичное число. После этого М зашифровывается, образуя шифртекст С, по формуле:
С= M e (mod N)
(5) Представьте, что Боб хочет послать Алисе простой поцелуй — всего лишь букву X. В ASCII-коде она представляется числом 1011000, которое эквивалентно 88 в десятичном виде. Поэтому М — 88.
(6) Чтобы зашифровать это сообщение, Боб начинает разыскивать открытый ключ Алисы и находит, что N= 187, а е = 7. Это дает ему формулу шифрования, необходимую, чтобы зашифровывать сообщения для Алисы. При М= 88 формула имеет вид:
С = 887 (mod 187)
(7) Вычислить ее на калькуляторе непросто, поскольку дисплей не способен справиться с такими огромными числами. В модулярной арифметике есть, однако, способ вычисления экпоненциальных функций. Мы знаем, что, поскольку 7 = 4 + 2+ 1, то:
887 (mod 187) = [884 (mod 187) х 882 (mod 187) х 881] (mod 187)] (mod 187) 881 = 88 = 88 (mod 187)
882 = 7744 = 77 (mod 187)
884 = 59969536 = 132 (mod 187)
887 = 881 х 882 х 884 = 88 х 77 х 132 = 894432 = 11 (mod 187)
Теперь Боб отправляет Алисе зашифрованный текст: С = 11.
(8) Мы знаем, что экпоненциальные функции в модулярной арифметике являются односторонними функциями, поэтому двигаться в обратном направлении и восстановить из С = 11 исходное сообщение М исключительно сложно. Так что Ева дешифровать сообщение не сможет.
(9) Алиса, однако, способна расшифровать его, поскольку у нее есть определенная специальная информация: ей известны значения р и q. Она вычисляет особое число d — ключ для расшифровывания, иначе известный как ее секретный ключ. Число d рассчитывается по следующей формуле:
е х d = 1 (mod (р- 1) $х (q — 1))
7 х d (mod 16 $x 10)
7 x d = 1 (mod 160)
d = 23
(Вычислить значение d не просто, но с помощью метода, известного как алгоритм Евклида, Алиса сможет быстро и без труда найти d.)
(10) Чтобы расшифровать сообщение, Алиса просто воспользуется следующей формулой:
М= С d (mod 187)
М= 1123 (mod 187)
M = [111(mod 187) х 112(mod 187) х 114(m od 187) х 1116(mod 187)] (mod 187)
M = 11 х 121 х 55 х 154 (mod 187)
М = 88 = Х в виде ASCII-кода
Ривест, Шамир и АДлеман создали специальную одностороннюю функцию — функцию, которая может быть обращена только тем человеком, который имеет доступ х сугубо конфиденциальной информации, то есть к значениям чисел р и q. Каждая функция может быть индивидуализирована путем выбора р и q, которые перемножаются для получения N. Эта функция позволяет всем зашифровывать сообщения для конкретного лица, используя для этого полученное им число N, но только тот, кому предназначено это сообщение, сможет расшифровать его, поскольку только он знает р и q, следовательно, только он знает ключ для расшифровывания d.
Словарь специальных терминов
ASCII — американский стандартный код для обмена информацией; стандарт для перевода букв и других символов в числа.
DES — стандарт шифрования данных, разработан IBM и принят в качестве стандарта в 1976 году.
Pretty Good Privacy (PGP) («Вполне достаточная секретность») — алгоритм компьютерного шифрования, разработанный Филом Циммерманом на основе RSA.
RSA — первая система, которая удовлетворяла условиям шифрования с открытым ключом; была придумана Роном Ривестом, Ади Шамиром и Леонардом Адлеманом в 1977 году.
Агентство национальной безопасности (АНБ) — подразделение министерства обороны США, отвечающее за безопасность американских средств связи и за проникновение в линии связи других стран.
Алгоритм шифрования — любой общий процесс зашифровывания, который может быть строго определен выбором ключа.
Декодировать — преобразовать закодированное сообщение обратно в исходное.
Депонирование ключей — схема, когда пользователи отдают на хранение копии своих секретных ключей заслуживающему доверия третьему лицу, эскроу-агенту, который передает их сотрудникам правоприменяющих органов только в определенных ситуациях, например, по распоряжению суда.
Дешифровать — преобразовать зашифрованное сообщение обратно в исходное сообщение. Формально данный термин относится только к получателю данного сообщения, который знает ключ, необходимый для того, чтобы получить открытый текст, но в действительности также относится к криптоанализу, при котором дешифрование осуществляется противником, перехватившим сообщение.
Длина ключа — при компьютерном шифровании используются ключи, которые являются числами. Длина ключа относится к количеству цифр или битов в ключе и, таким образом, указывает самое большое число, которое может быть использовано в качестве ключа, задавая тем самым число возможных ключей. Чем больше длина ключа (или чем больше число возможных ключей), тем больше времени потребуется криптоаналитику, чтобы проверить все ключи.
Закодировать — преобразовать исходное сообщение в закодированное.
Зашифровать — преобразовать исходное сообщение в зашифрованное.
Квантовый компьютер — чрезвычайно мощный компьютер, который использует квантовую теорию, в частности, теорию, что объект может одновременно находиться во многих состояниях (суперпозиция), или теорию, что объект может одновременно находиться во многих мирах. Если бы ученые смогли создать квантовый компьютер, это поставило бы под угрозу стойкость всех нынешних шифров, за исключением шифра одноразового шифрблокнота.
Квантовая криптография — нераскрываемая форма криптографии, в которой применяется квантовая теория, в частности, принцип неопределенности, который гласит, что нельзя измерить все параметры объекта с абсолютной точностью. Квантовая криптография гарантирует безопасный обмен случайной последовательностью битов, которая затем используется в качестве основы для шифра одноразового шифрблокнота.
Ключ — элемент, который преобразует общий алгоритм шифрования в конкретный способ шифрования. Вообще говоря, противник может знать алгоритм шифрования, используемый отправителем и получателем, но следует приложить все силы, чтобы он не узнал ключ.
Код — система, предназначенная для скрытия содержания сообщения путем замены каждого слова или фразы в исходном сообщении другим символом или набором символов. Таблица замен содержится в кодовой книге. (Другое определение кода: это любая форма шифрования, которая не обладает внутренней гибкостью, то есть существует только один ключ — кодовая книга.)
Кодовая книга — таблица замен слов или фраз в исходном сообщении.
Криптоанализ — наука получения открытого текста из шифртекста без знания ключа.
Криптография — наука зашифровывания сообщения или наука скрытия содержания сообщения. Иногда этот термин используется в более широком смысле для обозначения науки, так или иначе связанной с шифрами, и является другим названием криптологии.
Криптография с асимметричным ключом — вид криптографии, в которой ключ, необходимый для зашифровывания, не совпадает с ключом, требующимся для расшифровывания. Описывает системы шифрования с открытым ключом, такие как RSA.
Криптография с симметричным ключом — вид криптографии, в которой ключ, необходимый для зашифровывания, совпадает с ключом, необходимым для расшифровывания. Данным термином описываются все традиционные виды шифрования, то есть те, которые использовались до 70-х годов.
Криптология — наука тайнописи во всех ее проявлениях; включает в себя как криптографию, так и криптоанализ.
Многоалфавитный шифр замены — шифр замены, при котором шифралфавит меняется в процессе шифрования, например, шифр Виженера. Изменение шифралфавита задается ключом.
Обмен ключами Диффи-Хеллмана-Меркля — процесс, при котором отправитель и получатель могут договориться о секретном ключе по незащищенному каналу. После согласования ключа отправитель, чтобы зашифровать сообщение, может воспользоваться таким, например, шифром, как DES.
Одноалфавитный шифр замены — шифр замены, при котором шифралфавит остается неизменным на протяжении всего процесса шифрования.
Одноразовый шифрблокнот — единственная известная форма шифрования, являющаяся нераскрываемой. Она основана на случайном ключе, длина которого равна длине сообщения. Каждый ключ может использоваться один, и только один раз.
Омофонический шифр замены — шифр, в котором существует несколько возможных замен для каждой буквы открытого текста. Здесь принципиальным является то, что, если, скажем, существует шесть возможных замен для буквы открытого текста а, то эти шесть символов могут представлять собой только букву а. Этот шифр является одним из видов одноалфавитного шифра замены.
Открытый ключ — в системе шифрования с открытым ключом — ключ, применяемый получателем сообщения для того, чтобы зашифровать его. Открытый ключ доступен всем.
Открытый текст — исходное сообщение до зашифровывания.
Распределение ключей — процесс, обеспечивающий получение доступа отправителя и получателя к ключу, требующемуся для зашифровывания и расшифровывания сообщения; при этом принимаются меры, чтобы ключ не попал в руки противника. До изобретения шифрования с открытым ключом распределение ключей являлось главной проблемой с точки зрения безопасности их доставки.
Секретный ключ — в системе шифрования с открытым ключом — ключ, применяемый получателем сообщения для того, чтобы расшифровать его. Секретный ключ должен храниться в секрете.
Стеганография — наука, связанная с сокрытием наличия существующего сообщения, в отличие от криптографии, которая используется для скрытия содержания сообщения.
Цифровая подпись — способ удостоверения авторства электронного документа. Нередко создается автором, зашифровывающим документ своим секретным ключом.
Шифр — любая система, предназначенная для скрытия содержания сообщения путем замены каждой буквы в исходном сообщении другой буквой. Система должна обладать некоторой внутренней гибкостью, известной как ключ.
Шифр Виженера — многоалфавитный шифр, который был разработан около 1500 года. Квадрат Виженера состоит из 26 отдельных шифралфавитов, каждый из которых смещен на одну позицию, а ключевое слово задает, каким из шифралфавитов следует пользоваться для зашифровывания каждой буквы сообщения.
Шифр замены — система шифрования, в которой каждая буква сообщения заменяется другим символом, но в сообщении остается на своем месте.
Шифр замены Цезаря — первоначально так обозначался шифр, в котором каждая буква в сообщении заменяется буквой, отстоящей в алфавите на три позиции дальше. В более общем смысле, это шифр, в котором каждая буква в сообщении заменяется буквой, находящейся в алфавите на х позиций дальше, где х является числом от 1 до 25.
Шифр перестановки — система шифрования, в которой каждая буква сообщения остается сама собой, но меняет свое место в сообщении.
Шифралфавит — перестановка обычного алфавита (или алфавита открытого текста), который после этого задает, как зашифровывается каждая буква в исходном сообщении. Шифралфавит может также состоять из чисел или любых других символов, но в любом случае им обусловливаются замены букв в исходном сообщении.
Шифртекст — сообщение (или открытый текст) после зашифровывания.
Шифрование с открытым ключом — система криптографии, в которой преодолены проблемы, связанные с распределением ключей. Для шифрования с открытым ключом требуется асимметричный шифр для того, чтобы каждый пользователь мог создать открытый ключ для зашифровывания и секретный ключ для расшифровывания.
Благодарности
При написании этой книги мне выпала честь встретиться с некоторыми из самых выдающихся в мире создателей кодов и теми, кто их взламывает, начиная с тех, кто трудился в Блечли-Парке, до тех, кто и в настоящее время разрабатывает шифры, которые обогатят информационный век. Я бы хотел поблагодарить Уитфилда Диффи и Мартина Хеллмана, выбравших время, чтобы рассказать мне, когда я был в солнечной Калифорнии, о своей работе. Точно также в огромной степени помогли мне Клиффорд Кокс, Малькольм Уильямсон и Ричард Уолтон во время моей поездки в хмурый Челтенхем. В частности, я выражаю признательность группе информационной безопасности колледжа Ройял Холоуэй в Лондоне, позволившей мне посетить магистерский курс по информационной безопасности. Профессор Фред Пайпер, Саймон Блэкберн, Джонатан Тулиани и Фозан Мирца — все они дали мне бесценные знания о кодах и шифрах.
Когда я был в Вирджинии, мне повезло, и я совершил экскурсию по следам сокровища Биля под руководством Питера Виемейстера, знатока этой загадки. Кроме того, музей округа Бедфорд и Стивен Коварт из Ассоциации шифров Биля и сокровищ помогли мне провести исследование данного предмета. Я также благодарен Дэвиду Дойчу и Мишель Моска из оксфордского центра квантовых вычислений, Чарльзу Беннету и его группе из исследовательской лаборатории Томаса Дж. Уотсона компании IВМ, Стивену Виснеру, Леонарду Адлеману, Рональду Ривесту, Паулю Ротемунду, Джиму Джиллольи, Паулю Лейланду и Нейлу Барретту.
Дерек Таунт, Алан Стрипп и Дональд Дейвис любезно объяснили мне, каким образом в Блечли-Парке взломали Энигму; помог мне также и Блечли-Парк Траст, члены которого регулярно читают просветительские лекции по различным вопросам. Доктор Мохаммед Мрайати и доктор Ибрагим Кади занимались вопросами, касающимися первых достижений арабов в криптоанализе, и были так добры, что выслали мне соответствующие документы. В ежеквартально выходящем журнале «Криптология» также были размещены статьи об арабском криптоанализе, а также о множестве других криптографических тем, и мне хотелось бы поблагодарить Брайана Винкеля за присланные мне старые экземпляры журналов.
Я бы посоветовал читателям посетить национальный криптологический музей неподалеку от Вашингтона в округе Колумбия и бункер Черчилля в Лондоне, и надеюсь, что вы будете столь же увлечены, как и я во время своего приезда. Благодарю хранителей и библиотекарей этих музеев за помощь в моих исследованиях. Когда мне не хватало времени, Джеймс Ховард, Бинду Матур,
Притги Сагу, Анна Сингх и Ник Шеринг — все они помогали мне разыскать важные и интересные статьи, книги и документы, и я признателен им за их усилия. Выражаю также свою благодарность Энтони Буономо с www.verti- go.co.uk, который помог мне создать мой веб-сайт.
Я не только расспрашивал специалистов, но и полагался на многочисленные книги и статьи. В списке для дальнейшего прочтения приведены некоторые из моих источников, но он не является ни абсолютно полной библиографией, ни установленным списком рекомендованной литературы. Напротив, в него всего лишь входит материал, который может быть интересен широкому кругу читателей. Из всех книг, с которыми мне пришлось встретиться в своих исследованиях, я бы хотел особо выделить одну: «Взломщики кодов» Дэвида Кана. В этой книге документально отражены почти все криптографические события истории, и благодаря этому она является бесценным источником.
Различные библиотеки, учреждения и отдельные лица предоставили мне фотографии. Все они перечислены в списке лиц и организаций, предоставивших фотографии для данной книги, но особую благодарность я хотел бы выразить Салли МакКлейн за фотографии радистов-навахо, профессору Еве Бранн за то, что она нашла единственную известную фотографию Алисы Кобер, Джоан Чедвик за фотографию Джона Чедвика и Бренду Эллис за то, что позволила мне позаимствовать фотографии Джеймса Эллиса. Хочу также поблагодарить Хью Уайтмора, позволившего мне использовать цитату из его пьесы «Взлом шифра» по книге Эндрю Ходжеса «Алан Тьюринг — Энигма».
Мне бы хотелось поблагодарить друзей и семью, которые терпели меня более двух лет, пока я писал эту книгу. Нейл Бойнтон, Дон Дзедзы, Соня Холбраад, Тим Джонсон, Ричард Сингх и Эндрю Томпсон — все помогали мне остаться в здравом уме в то время, как я пробивался через запутанные криптографические концепции. Бернадетт Алвес, в частности, обеспечивала меня богатой смесью из моральной поддержки и критических замечаний. Вглядываясь назад, выражаю также признательность всем людям и организациям, благодаря которым я состоялся как профессионал, в том числе Веллингтон Скул, Королевскому колледжу и группе физики высоких энергий Кембриджского университета, Дану Пурвис из Би-би-си, которая впервые ввела меня в курс дела на телевидении, и Роджеру Хайфилду в «Дейли Телеграф», кто вселил в меня мужество написать первую статью.
Наконец, мне выпала огромная удача работать с некоторыми из превосходных людей в издательской системе. Патрик Уолш — это агент, отличающийся любовью к науке, заботой о своих авторах и безграничным энтузиазмом. Он связал меня с самыми лучшими и самыми талантливыми издателями — это, главным образом, касается Fourth Estate, чьи сотрудники сносят мой постоянный поток вопросов с большим присутствием духа. Последнее, но не менее важное, — мои редакторы Кристофер Поттер, Лео Холлис и Петернелле ван Арсдале — помогли мне следовать ясным путем по предмету, чей путь сквозь три тысячелетия был так извилист. За это я благодарен чрезвычайно.