Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан (бесплатные полные книги TXT) 📗
Теперь представим себе шпиона, который перехватил и отправленные фотоны, и открытый разговор отправителя и получателя. Мы уже видели, что, не зная точно, какой поляризационный фильтр был использован отправителем сообщения, невозможно определить, когда поляризация была определена правильно. Открытый разговор отправителя и получателя также бесполезен, потому что в нем никогда не говорится о конкретных фильтрах.
Но самое главное, если шпион ошибется в выборе фильтра и тем самым изменит поляризацию фотонов, его вмешательство сразу будет раскрыто, и он уже ничего не сможет сделать, чтобы остаться незамеченным. Отправителю и получателю стоит только проверить достаточно длинную часть ключа, чтобы обнаружить любые манипуляции с поляризацией фотонов со стороны злоумышленников.
В конце процесса отправитель и получатель договариваются о простой проверке.
Выполнив три предварительных шага, описанных выше, и имея достаточное количество сохраненных битов, отправитель и получатель связываются друг с другом любым удобным способом и вместе проверяют группу битов (скажем, 100), выбранных из общего числа случайным образом. Если все 100 битов совпали, отправитель и получатель могут быть полностью уверены, что ни один шпион не перехватил их передачу, и выбирают некоторую последовательность в качестве одноразового шифра. В противном случае им придется повторить процесс.
32 сантиметра абсолютной секретности
Метод Брассара и Беннета безупречен с точки зрения теории, но когда эту теорию попытались применить на практике, она была встречена очень скептически.
В 1989 г., после более чем года напряженной работы, Беннет построил систему, состоящую из двух компьютеров, расположенных на расстоянии 32 сантиметра друг от друга, один из которых выступал в роли отправителя, а другой — получателя.
После нескольких часов проб и поправок эксперимент был признан успешным. Отправитель и получатель выполнили все этапы процесса, включая проверку шифра. Возможность квантовой криптографии была доказана.
Исторический эксперимент Беннета имел один очевидный недостаток: секрет посылался на расстояние менее шага. Передача шепотом была бы, наверное, столь же эффективна. Однако в последующие годы другие исследовательские группы увеличили это расстояние. В 1995 г. ученые из Университета Женевы использовали оптоволокно для передачи сообщений на 23 километра. В 2006 г. команда из Лос-Аламосской национальной лаборатории в США повторила этот процесс на расстоянии 107 километров. Хотя такие расстояния недостаточны для обычной связи, этот метод уже может быть использован в местах, где строжайшая тайна имеет первостепенное значение, например, в правительственных зданиях и офисах компаний.
Если не брать во внимание соображения, связанные с техническими ограничениями для отправки сообщений, возможность того, что передача будет подслушана, совершенно исключена даже на квантовом уровне. Этот квантовый шифр представляет собой окончательную победу тайны над ее разглашением, криптографов над криптоаналитиками. Все, о чем нам осталось теперь позаботиться — вопрос, во всяком случае, немаловажный — как применять этот мощный инструмент и кто в результате получит наибольшую выгоду.
Приложение
В этом приложении мы расскажем о различных классических криптографических шифрах, упоминаемых в предыдущих главах, но не описанных там достаточно подробно. Все они представляют различные криптографические методы и интересны даже в качестве развлечения. В завершении мы приведем процесс расшифровки из рассказа американского писателя Эдгара Аллана По, в котором блестяще проиллюстрировано применение частотного криптоанализа.
Шифр Полибия
Этот шифр, один из древнейших, о котором у нас имеется подробная информация, основан на выборе пяти букв алфавита, служащих заголовками строк и столбцов таблицы размером 5 x 5, которая затем заполняется буквами алфавита. Шифр заменяет каждую букву алфавита парой букв, являющихся заголовками соответствующих столбца и строки. Первоначально использовался греческий алфавит из 24 букв, поэтому английские буквы I и J, как правило, комбинируются (см. таблицу, приведенную ниже, где для простоты в качестве заголовков используются буквы А — Е).
Таблица заполняется по правилу, о котором договорились отправитель и получатель.
Рассмотрим, например, следующую таблицу:
Заметим, что шифроалфавит состоит из 25 букв (5 х 5). В качестве заголовков можно использовать и цифры (например, 1, 2, 3, 4 и 5). В этом случае таблица имеет вид:
Рассмотрим шифр Полибия на примере этих двух таблиц. Мы будем шифровать сообщение BLANKS («пробелы»). По первой таблице мы получим:
В заменяется парой АВ.
L заменяется парой СА.
А заменяется парой АА.
N заменяется парой СС.
К заменяется парой BE.
S заменяется парой DC.
Зашифрованное сообщение имеет вид ABCAAACCBEDC. Если мы используем таблицу с цифрами, то получим: «123111332543».
Шифр Гронсфельда
Этот шифр, изобретенный голландцем Мостом Максимилианом Бронкхорстом, графом Гронсфельд, использовался в Европе в XVII в. Это полиалфавитный шифр, аналогичный квадрату Виженера, но менее сложный (и менее надежный). Чтобы зашифровать сообщение, рассмотрим следующую таблицу.
Далее, для каждой буквы в нашем сообщении мы выбираем случайным образом число от 0 до 9. Для сообщения MATHEMATICAL («математический») мы выбираем случайным образом 12 чисел, например: 1, 2, 3, 4, 3, 6, 7, 8, 9, 0, 1, 2. Этот набор чисел и будет ключом шифра. Теперь вместо каждой буквы сообщения мы поставим букву из строки с соответствующим номером (см. таблицу на предыдущей странице).
Буква М будет заменена буквой Р (взятой из строки номер 1 в столбце М), и так далее. Мы получим сообщение PFASRDTQKEDQ. Буква А исходного сообщения будет зашифрована как F, Т, и D. Как и для всех полиалфавитных шифров, эта система шифрования устойчива к методу перебора всех возможных вариантов и к частотному анализу. Количество ключей в шифре Гронсфельда для алфавита из 26 букв составляет 26! х 10 = 4,03 х 10 26.
Шифр Плейфера
Создатели этого шифра лорд Лайон Плейфер и сэр Чарльз Уитстон (также изобретатель электромагнитного телеграфа) были друзьями и соседями и разделяли любовь к криптографии. Их метод напоминает знаменитый шифр Полибия и тоже использует таблицу из пяти строк и пяти столбцов. В качестве первого шага каждая буква сообщения заменяется на пару букв в соответствии с ключом из пяти различных букв. В нашем примере эти пять букв будут JAMES. В случае алфавита с 26 символами мы получаем следующую таблицу:
Далее текст сообщения разбивается на пары букв или биграммы. Две буквы каждой биграммы должны быть разными. Чтобы избежать возможных совпадений, мы используем букву X. Мы также используем эту букву, чтобы завершить биграмму в случае, если последняя буква не имеет пары.
