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

• Название: Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография
• Автор: Жуан Гомес
• Издательство: ООО «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0682-6; 978-5-9774-0639-0 (т. 2)

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

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

Эта книга — попытка рассказать читателю историю шифрования через призму развития математической мысли.

---

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

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

Неуязвимый шифр

В 1984 г. американец Чарльз Беннет и канадец Жиль Брассар выдвинули идею системы шифрования на основе передачи поляризованных фотонов. Сначала отправитель и получатель договариваются, как разным поляризациям поставить в соответствие 0 или 1. В нашем примере это будет функцией двух видов поляризации: первый вид, называемый прямолинейной поляризацией и обозначаемый символом +, где 1 соответствует вертикальной поляризации , а 0 — горизонтальной , второй вид, называемый диагональной поляризацией и обозначаемый символом х, ставит в соответствие 1 диагональную поляризацию слева направо вверх , а 0 — диагональную поляризацию слева направо вниз .

Например, сообщение 0100101011 будет передано следующим образом:

Если шпион перехватит передачу, ему придется использовать фильтр с фиксированной ориентацией х:

Как мы видим, не зная изначального вида поляризации, шпион не может извлечь полезную информацию из поляризации, определенной фильтром. Даже зная правило соответствия 0 и 1, используемое отправителем и получателем, шпион будет ошибаться в трети из случаев, в которых вид поляризации выбирается случайным образом (в таблице показаны все возможные комбинации при описанных условиях). Однако проблема заключается в том, что получатель находится не в лучшем положении, чем шпион.

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

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

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

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

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

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

1. Сначала получателю посылают случайную последовательность нулей и единиц через различные, случайным образом выбранные фильтры: вертикальные , горизонтальные , и диагональные .

2. Затем получатель измеряет поляризацию полученных фотонов, случайным образом чередуя прямолинейный (+) и диагональный (х) виды поляризации. Так как он не знает последовательности фильтров, используемых отправителем, большая часть нулей и единиц будет определена неправильно.

3. Наконец, отправитель и получатель связываются друг с другом в любой удобной им форме, не беспокоясь о безопасности канала, и обмениваются следующей информацией: во-первых, отправитель объясняет, какой вид поляризации — прямолинейный или диагональный — нужно использовать для каждого фотона, не раскрывая самой поляризации фотона (то есть не говоря, какой именно использовался фильтр). Со своей стороны получатель сообщает, в каких случаях он правильно определил вид. Как видно из предыдущей таблицы, если у отправителя и получателя виды поляризации совпали, можно быть уверенным, что нули и единицы переданы правильно. Наконец, уже в частном порядке каждый из них отбрасывает биты, соответствующие фотонам, для которых получатель неправильно определил вид поляризации.

* * *

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

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

* * *

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

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

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

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

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