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



страница29/32
Дата24.08.2017
Размер4,62 Mb.
1   ...   24   25   26   27   28   29   30   31   32

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

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

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

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

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

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

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

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

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

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

Квантовые деньги Виснера основывались главным образом на физике фотонов. Как показано на рисунке 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. Что еще хуже, так это то, что у Евы есть только один шанс точно измерить фотон. Фотон неделим, и поэтому она не может разделить его на два фотона и измерить их с помощью обеих схем.



Поделитесь с Вашими друзьями:
1   ...   24   25   26   27   28   29   30   31   32


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница