Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

* * *

ВАВИЛОНСКОЕ ПОСЛАНИЕ

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

* * *

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

Обратите внимание, что некоторые окончательные биты отброшены, хотя они были правильно определены. Это потому, что получатель не был твердо уверен в их правильности, так как в тех случаях использовал неправильный вид поляризации.

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

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

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

В конце процесса отправитель и получатель договариваются о простой проверке.

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

32 сантиметра абсолютной секретности

Метод Брассара и Беннета безупречен с точки зрения теории, но когда эту теорию попытались применить на практике, она была встречена очень скептически.

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

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

Исторический эксперимент Беннета имел один очевидный недостаток: секрет посылался на расстояние менее шага. Передача шепотом была бы, наверное, столь же эффективна. Однако в последующие годы другие исследовательские группы увеличили это расстояние. В 1995 г. ученые из Университета Женевы использовали оптоволокно для передачи сообщений на 23 километра. В 2006 г. команда из Лос-Аламосской национальной лаборатории в США повторила этот процесс на расстоянии 107 километров. Хотя такие расстояния недостаточны для обычной связи, этот метод уже может быть использован в местах, где строжайшая тайна имеет первостепенное значение, например, в правительственных зданиях и офисах компаний.

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

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

Шифр Полибия

Этот шифр, один из древнейших, о котором у нас имеется подробная информация, основан на выборе пяти букв алфавита, служащих заголовками строк и столбцов таблицы размером 5 x 5, которая затем заполняется буквами алфавита. Шифр заменяет каждую букву алфавита парой букв, являющихся заголовками соответствующих столбца и строки. Первоначально использовался греческий алфавит из 24 букв, поэтому английские буквы I и J , как правило, комбинируются (см. таблицу, приведенную ниже, где для простоты в качестве заголовков используются буквы А — Е ).

Таблица заполняется по правилу, о котором договорились отправитель и получатель.

Рассмотрим, например, следующую таблицу:

Заметим, что шифроалфавит состоит из 25 букв (5 х 5). В качестве заголовков можно использовать и цифры (например, 1, 2, 3, 4 и 5). В этом случае таблица имеет вид:

Рассмотрим шифр Полибия на примере этих двух таблиц. Мы будем шифровать сообщение BLANKS («пробелы»). По первой таблице мы получим: