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



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

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

Разумеется, Алиса могла бы зашифровать список поляризационных схем с помощью шифра с общим ключом, например, 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 Все возможные случаи на втором этапе при обмене фотонами между Алисой и Бобом.

Эта согласованная случайная последовательность может использоваться в качестве ключа для шифра одноразового шифрблокнота. В главе 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 — для тех, кто посвятил себя делу дешифрования.

Если вы хотите больше узнать о задачах по дешифрованию, вы можете зайти на мой веб-сайт (www.simonsingh.com), где дается различная информация, в том числе и ссылка на сообщение, написанное победителями этого вызова: Фредриком Альмгреном, Гуннаром Андерсоном, Торбьерном Гранлундом, Ларсом Ивансоном и Стефаном Ульфбергом. Это сообщение прекрасно читается, но помните, что в нем, как и в других материалах на этом веб-сайте, используется много дополнительных сведений, которые вам, может, пока еще будут неинтересны.

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

Удачи вам, Саймон Сингх

Задача 1: Простой одноалфавитный шифр замены

Задача 2: Шифр Цезаря

Задача 3: Одноалфавитный шифр с омофонами

Задача 4: Шифр Виженера

Задача 5

Задача 6


Задача 7

Задача 8


Задача 9

Задача 10

Короткое сообщение

Длинное сообщение

Приложение А



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


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

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