Неуязвимый шифр
В 1984 г. американец Чарльз Беннет и канадец Жиль Брассар выдвинули идею системы шифрования на основе передачи поляризованных фотонов. Сначала отправитель и получатель договариваются, как разным поляризациям поставить в соответствие 0 или 1. В нашем примере это будет функцией двух видов поляризации: первый вид, называемый прямолинейной поляризацией и обозначаемый символом +, где 1 соответствует вертикальной поляризации , а 0 — горизонтальной , второй вид, называемый диагональной поляризацией и обозначаемый символом х, ставит в соответствие 1 диагональную поляризацию слева направо вверх , а 0 — диагональную поляризацию слева направо вниз .
Например, сообщение 0100101011 будет передано следующим образом:
Если шпион перехватит передачу, ему придется использовать фильтр с фиксированной ориентацией х:
Как мы видим, не зная изначального вида поляризации, шпион не может извлечь полезную информацию из поляризации, определенной фильтром. Даже зная правило соответствия 0 и 1, используемое отправителем и получателем, шпион будет ошибаться в трети из случаев, в которых вид поляризации выбирается случайным образом (в таблице показаны все возможные комбинации при описанных условиях). Однако проблема заключается в том, что получатель находится не в лучшем положении, чем шпион.
Хотя отправитель и получатель могут обойти эту проблему, послав друг другу последовательность видов поляризаций с помощью какого-то защищенного метода, например, RSA шифрования, но тогда шифр будет уязвим для гипотетических квантовых компьютеров.
Чтобы преодолеть это последнее препятствие, Брассару и Беннету пришлось усовершенствовать свой метод. Если читатель помнит, ахиллесовой пятой полиалфавитных шифров, таких как квадрат Виженера, являлось использование коротких повторяющихся ключей, из-за которых в шифре возникали закономерности, что создавало небольшую, но достаточную возможность для криптоаналитика взломать шифр. Но что было бы, если бы ключ представлял собой случайный набор символов и был длиннее, чем само послание, а каждое сообщение, даже самое незначительное, для большей безопасности было бы зашифровано другим ключом? Тогда бы у нас получился неуязвимый шифр.
Первым человеком, предложившим использовать полиалфавитный шифр с уникальным ключом, был Джозеф Моборн. Вскоре после Первой мировой войны, будучи начальником службы связи американского криптографического отдела, Моборн придумал блокнот с ключами, каждый из которых содержал более 100 случайных символов. Такие блокноты выдавались отправителю и получателю с инструкцией уничтожать использованный ключ и переходить к следующему. Эта система, известная как шифрблокнот одноразового назначения, является, как мы уже говорили, неуязвимой, и это можно доказать математически. И действительно, самые секретные послания между главами государств шифруются с помощью этого метода.
Если одноразовые шифры блокнота так безопасны, почему же они не используются повсеместно? Почему же мы так беспокоимся из-за квантовых компьютеров и даже занимаемся манипуляциями с фотонами?
Оставив в стороне технические трудности генерации тысяч случайных одноразовых ключей для шифрования такого же количества сообщений, шифрблокнот одноразового назначения имеет такой же недостаток, как и другие классические алгоритмы шифрования: проблему распределения ключей, которую пытается решить современная криптография.
Однако передача информации с помощью поляризованных фотонов является идеальным способом безопасного обмена уникальными ключами. Но прежде чем передавать сообщение, необходимо сделать следующее.
1. Сначала получателю посылают случайную последовательность нулей и единиц через различные, случайным образом выбранные фильтры: вертикальные , горизонтальные , и диагональные .
2. Затем получатель измеряет поляризацию полученных фотонов, случайным образом чередуя прямолинейный (+) и диагональный (х) виды поляризации. Так как он не знает последовательности фильтров, используемых отправителем, большая часть нулей и единиц будет определена неправильно.
3. Наконец, отправитель и получатель связываются друг с другом в любой удобной им форме, не беспокоясь о безопасности канала, и обмениваются следующей информацией: во-первых, отправитель объясняет, какой вид поляризации — прямолинейный или диагональный — нужно использовать для каждого фотона, не раскрывая самой поляризации фотона (то есть не говоря, какой именно использовался фильтр). Со своей стороны получатель сообщает, в каких случаях он правильно определил вид. Как видно из предыдущей таблицы, если у отправителя и получателя виды поляризации совпали, можно быть уверенным, что нули и единицы переданы правильно. Наконец, уже в частном порядке каждый из них отбрасывает биты, соответствующие фотонам, для которых получатель неправильно определил вид поляризации.
* * *
ВАВИЛОНСКОЕ ПОСЛАНИЕ
Аргентинский писатель Хорхе Луис Борхес в коротком рассказе «Вавилонская библиотека» описал библиотеку, настолько большую, что на ее полках были все возможные книги: все романы, стихотворения и диссертации, опровержения этих диссертаций, а также опровержения опровержений, и так далее до бесконечности. Криптоаналитик, пытающийся расшифровать методом проб и ошибок послание, зашифрованное с помощью шифрблокнота одноразового назначения, окажется в подобном положении. Так как шифр выбран совершенно случайно, возможные расшифровки будут представлять из себя всевозможные тексты одинаковой длины: реальное сообщение, опровержение этого сообщения, то же сообщение со всеми существительными, замененными на другие той же длины, и так далее до бесконечности.
* * *
В результате этого процесса и отправитель, и получатель будут иметь одну и ту же совершенно случайно сгенерированную последовательность нулей и единиц, так как отправитель случайным образом выбирал поляризационные фильтры, а получатель тоже случайным образом выбирал виды поляризации. На следующем рисунке изображен простой 12-битовый пример описанного процесса.
Обратите внимание, что некоторые окончательные биты отброшены, хотя они были правильно определены. Это потому, что получатель не был твердо уверен в их правильности, так как в тех случаях использовал неправильный вид поляризации.
Если передача содержит необходимое число фотонов, последовательность нулей и единиц будет достаточно длинной, чтобы служить одноразовым ключом шифр-блокнота для шифрования сообщений нормальной длины.
Теперь представим себе шпиона, который перехватил и отправленные фотоны, и открытый разговор отправителя и получателя. Мы уже видели, что, не зная точно, какой поляризационный фильтр был использован отправителем сообщения, невозможно определить, когда поляризация была определена правильно. Открытый разговор отправителя и получателя также бесполезен, потому что в нем никогда не говорится о конкретных фильтрах.
Но самое главное, если шпион ошибется в выборе фильтра и тем самым изменит поляризацию фотонов, его вмешательство сразу будет раскрыто, и он уже ничего не сможет сделать, чтобы остаться незамеченным. Отправителю и получателю стоит только проверить достаточно длинную часть ключа, чтобы обнаружить любые манипуляции с поляризацией фотонов со стороны злоумышленников.
В конце процесса отправитель и получатель договариваются о простой проверке.
Выполнив три предварительных шага, описанных выше, и имея достаточное количество сохраненных битов, отправитель и получатель связываются друг с другом любым удобным способом и вместе проверяют группу битов (скажем, 100), выбранных из общего числа случайным образом. Если все 100 битов совпали, отправитель и получатель могут быть полностью уверены, что ни один шпион не перехватил их передачу, и выбирают некоторую последовательность в качестве одноразового шифра. В противном случае им придется повторить процесс.
32 сантиметра абсолютной секретности
Метод Брассара и Беннета безупречен с точки зрения теории, но когда эту теорию попытались применить на практике, она была встречена очень скептически.
В 1989 г., после более чем года напряженной работы, Беннет построил систему, состоящую из двух компьютеров, расположенных на расстоянии 32 сантиметра друг от друга, один из которых выступал в роли отправителя, а другой — получателя.
После нескольких часов проб и поправок эксперимент был признан успешным. Отправитель и получатель выполнили все этапы процесса, включая проверку шифра. Возможность квантовой криптографии была доказана.
Исторический эксперимент Беннета имел один очевидный недостаток: секрет посылался на расстояние менее шага. Передача шепотом была бы, наверное, столь же эффективна. Однако в последующие годы другие исследовательские группы увеличили это расстояние. В 1995 г. ученые из Университета Женевы использовали оптоволокно для передачи сообщений на 23 километра. В 2006 г. команда из Лос-Аламосской национальной лаборатории в США повторила этот процесс на расстоянии 107 километров. Хотя такие расстояния недостаточны для обычной связи, этот метод уже может быть использован в местах, где строжайшая тайна имеет первостепенное значение, например, в правительственных зданиях и офисах компаний.
Если не брать во внимание соображения, связанные с техническими ограничениями для отправки сообщений, возможность того, что передача будет подслушана, совершенно исключена даже на квантовом уровне. Этот квантовый шифр представляет собой окончательную победу тайны над ее разглашением, криптографов над криптоаналитиками. Все, о чем нам осталось теперь позаботиться — вопрос, во всяком случае, немаловажный — как применять этот мощный инструмент и кто в результате получит наибольшую выгоду.
Приложение
В этом приложении мы расскажем о различных классических криптографических шифрах, упоминаемых в предыдущих главах, но не описанных там достаточно подробно. Все они представляют различные криптографические методы и интересны даже в качестве развлечения. В завершении мы приведем процесс расшифровки из рассказа американского писателя Эдгара Аллана По, в котором блестяще проиллюстрировано применение частотного криптоанализа.