Справедливости ради отмечу, что кое-кто все же решил заплатить за использование турбокодов. Например, они применяются в технологиях мобильной связи 3G и 4G и для защиты данных, передаваемых с Марсианского разведывательного спутника (МРС), запущенного NASA в 2005 году и по-прежнему остающегося на связи с Землей. Предполагается, что МРС станет первым звеном в сети, которую в NASA называют “межпланетным интернетом” и которая будет передавать сигналы с множества международных космических кораблей, улетающих все дальше в Солнечную систему[230]. Турбокоды также используются в Сети дальней космической связи, куда входят радиостанции, играющие важнейшую роль в коммуникации со многими межпланетными космическими кораблями NASA. Теперь, когда скорость связи приблизилась к пределу Шеннона, это может показаться прозаичным, но в момент публикации теории, лежащей в основе турбокодов, никто не верил, что такое вообще возможно. Всерьез их приняли лишь тогда, когда у скептиков не получилось доказать, что они не работают.
При этом скепсис был вполне обоснован. Не было никакого математического подтверждения тому, что турбокоды окажутся функциональными. Как и код с малой плотностью проверок на четность, предложенный Галлагером, они были инженерным решением: набором инструкций, в котором не объяснялось, почему соответствующие действия дадут нужный результат. Хотя оба кода позволяли приблизиться к пределу Шеннона, на математиков их работа особого впечатления не производила. А вот с “полярными кодами”, родившимися в голове Эрдала Арыкана, все обстояло иначе.
Арыкан – турецкий профессор электрической и электронной инженерии. В 2008 году он работал над алгоритмом декодирования информации и понял, что используемые им техники можно также применить для достижения предела Шеннона. У него ушло два года на проработку деталей, но теперь эти техники используются в новейшем протоколе шифрования мобильной связи в цифровых сетях. Этот протокол пятого поколения (5G) называется стандартом передачи данных 5G NR (
Иметь математически доказуемую схему для коррекции ошибок неплохо, но вовсе не обязательно. Как выяснили первые пользователи турбокодов, если система работает, этого вполне достаточно. Но есть в теории информации такая область, в которой без математических доказательств никак не обойтись. Это криптография.
Криптографию – науку о шифровании и дешифровании секретных сообщений – можно, пожалуй, назвать самым недооцененным разделом математики. Наша свобода и наше благополучие зависят от нашей способности обеспечивать конфиденциальность связи. В конце концов, конфиденциальность имеет принципиальное значение как в работе правительства, так и при совершении покупок в интернете. Она лежит в основе безопасного мобильного банкинга, который позволяет фермерам в Руанде вести дела и зарабатывать на жизнь. Она играет ключевую роль при подготовке облав на торговцев кокаином, помогая колумбийским агентствам по борьбе с оборотом наркотиков проводить операции. Разоблачителям, которые пытаются привлечь внимание к проблеме коррупции, нужно шифровать свою переписку в мессенджерах. Шифрование – важнейший ресурс, который сродни кислороду информационной эпохи.
Полученный во время войны опыт быстро подсказал Шеннону, что математика теории информации может показывать, насколько хорошо – или плохо – будет работать система шифрования. В 1949 году он изложил свои идеи в статье “Теория связи в секретных системах”, которая представляла собой переработанную версию засекреченного документа, составленного им в 1945 году[232]. В статье разбирается ситуация, когда “сообщение, подлежащее шифрованию, состоит из последовательных дискретных символов, каждый из которых выбран из некоего конечного множества. Эти символы могут быть буквами или словами некоторого языка, амплитудными уровнями «квантованной» речи или видеосигнала и так далее”. Шеннон отметил, что секреты, зашифрованные символами, – в отличие от тех, что скрываются с помощью невидимых чернил или шифруются с применением специальных технологий, например аппарата, способного в обратном порядке воспроизводить записанную речь, – можно проанализировать математически. Но главное – он продемонстрировал, что математический анализ может показать, есть ли вообще смысл взламывать шифр. Иными словами, он вывел математику криптоанализа и того, стоит ли игра с шифром свеч.
Это невероятно важно, поскольку говорит вам, куда лучше всего направить свои силы. Если следовать указаниям Шеннона, можно изменить ход истории, как показывает Специальное донесение о шифре “Фиш”.
Оно было отправлено в военное министерство США в декабре 1944 года под грифом “совершенно секретно” и содержало свежие данные о том, как обстоят дела с получением доступа к зашифрованным сообщениям, которые немецкие радисты отправляли во время Второй мировой войны[233]. Британские криптографы прозвали этот канал связи “Фиш”. Донесение составил Альберт Смолл из войск связи армии США, которого командировали в британский шифровальный центр в Блетчли-парке, чтобы помочь коллегам со взломом шифров. Он явно пребывал под впечатлением. В первом абзаце своего донесения он сообщает, что успехи наблюдаются каждый день. Он объяснил их “британским математическим гением, превосходными инженерными навыками и незыблемым здравым смыслом” и назвал “выдающимся вкладом в криптоаналитическую науку”.
Но был ли этот вклад действительно выдающимся? Главная цель состояла в том, чтобы взломать шифр немецкой машины “Лоренц”, пришедшей на смену “Энигме” и устроенной еще сложнее. Теоретически машина “Лоренц” могла создавать совершенно случайные криптографические ключи. Их смешивали с сообщениями, напечатанными “открытым текстом”, с помощью принципов логики Джорджа Буля, развитых в магистерской диссертации Шеннона: клапанными комбинациями вентилей И, НЕ и ИЛИ, которые вместе формировали вентиль Исключающее ИЛИ.
Теоретически в результате должен был получаться шифр, который невозможно взломать. Союзникам оставалось лишь надеяться, что на практике шифр окажется не столь совершенным, как в теории. Так и случилось. Немецкие телеграфисты допускали ошибки при использовании машины “Лоренц”, а сами машины настраивались таким образом, что в их броне возникали другие бреши.
И тут на сцену вышел
История математического криптоанализа вообще-то началась не с Шеннона. Самой известной ее отправной точкой считается 850 год, когда арабский математик и философ Абу Юсуф Якуб ибн Исхак аль-Кинди провел статистический анализ информации в своем “Трактате о дешифровке криптографических сообщений”. Он показал, что зашифрованный текст часто можно прочитать, применив статистические инструменты, например частотный анализ. Зная, какие буквы или слова встречаются чаще всего (например, буква “e” в английском языке), можно найти в зашифрованном сообщении подставленные вместо них символы и приступить к взлому шифра.
Со времен аль-Кинди людям, которые стремились сохранить что-либо в тайне, всегда приходилось находить новые неожиданные способы подставлять символы в текст. Но гарантию дает лишь один способ: разработка кода, в котором алгоритм подстановки для шифрования и дешифрования сообщения – “ключ” – нельзя угадать. Идеальный ключ предполагает совершенно случайные подстановки, содержит не меньше символов или битов, чем начальное сообщение, известен только отправителю и получателю и используется только один раз, чтобы невозможно было подвергнуть его статистическому анализу. В криптографических кругах его называют одноразовым блокнотом.
В своей статье Шеннон показал, что доказуемо надежны лишь такие методы шифрования, которые математически эквивалентны одноразовому блокноту. Однако, хотя его невозможно взломать, одноразовый блокнот ужасно неудобен. Как убедиться, что никто, кроме отправителя и получателя, не имеет доступ к идеальному криптографическому ключу? Нужно либо привлечь к задаче курьеров, которым можно в полной мере доверять, либо организовать встречу отправителя и получателя, чтобы они поделились друг с другом ключом, прежде чем разойтись. Если только они не будут встречаться перед каждым следующим сеансом связи (но в таком случае они вполне могли бы просто шепотом обменяться информацией), им придется заготовить целый набор ключей, которые они будут хранить и использовать при необходимости. Но тогда необходимо убедиться, что хранилище надежно и что им известно, какой именно ключ применять при получении нового сообщения.
Из-за этих трудностей практического характера единственный математически надежный метод шифрования используется редко. Вместо него все прибегают к несовершенным шифрам. Это не так уж плохо, учитывая, что более серьезные проблемы обычно возникают из-за несовершенства задействованных в процессе людей. Как и при работе с шифром “Лоренц”, польским математикам удалось взломать немецкий код “Энигма” (после чего они сообщили о своем прорыве британским разведчикам) главным образом не потому, что шифровальные машины “Энигма” были несовершенны, а потому, что связисты повторялись в своих действиях и становились предсказуемыми – например, завершали многие сообщения фразой “Хайль Гитлер”.
Возникает любопытный вопрос: в какой степени ухищрения, необходимые для практичного шифрования с помощью одноразового блокнота, умаляют его надежность? Для ответа на него нужно учитывать диапазон вариантов доступных символов, размер ключа, с помощью которого осуществляется шифрование, а также число зашифрованных сообщений, перехватываемых при передаче. Шеннон представил попытку взломать шифр методом грубой силы, который перебирает все возможные комбинации случайных ключей и ищет на выходе осмысленные слова и фразы. Затем он ввел понятие “интервал однозначности” – количество зашифрованных символов, которые необходимо перехватить, чтобы метод сработал. Этот интервал зависит от того, какие есть варианты при выборе ключа, а также от статистических характеристик языка. Если сообщение на английском передается с помощью простого шифра подстановки, по подсчетам Шеннона, вы сможете расшифровать его, имея около 30 символов.
30 символов – не так уж много, правда? Именно поэтому никто сегодня и не работает с простыми шифрами, которые в своих примерах рассматривал Шеннон. Какой же подход используют вместо этого?
Ответ может вас удивить. Хотя современная криптография дьявольски сложна, новейшие методики основаны на поразительно простой идее, которая возвращает нас в первую главу. Она такова: умножение проще деления.
Если я попрошу вас умножить 3 на 7, вы почти сразу назовете ответ: 21. Но стоит мне попросить вас разложить 21 на множители – целые числа, которые при перемножении дают 21, – и вам уже придется подумать подольше.
ebooksa