Искусство большего. Как математика создала цивилизацию - Майкл Брукс
Но был ли этот вклад действительно выдающимся? Главная цель состояла в том, чтобы взломать шифр немецкой машины “Лоренц”, пришедшей на смену “Энигме” и устроенной еще сложнее. Теоретически машина “Лоренц” могла создавать совершенно случайные криптографические ключи. Их смешивали с сообщениями, напечатанными “открытым текстом”, с помощью принципов логики Джорджа Буля, развитых в магистерской диссертации Шеннона: клапанными комбинациями вентилей И, НЕ и ИЛИ, которые вместе формировали вентиль Исключающее ИЛИ.
Теоретически в результате должен был получаться шифр, который невозможно взломать. Союзникам оставалось лишь надеяться, что на практике шифр окажется не столь совершенным, как в теории. Так и случилось. Немецкие телеграфисты допускали ошибки при использовании машины “Лоренц”, а сами машины настраивались таким образом, что в их броне возникали другие бреши.
И тут на сцену вышел Colossus. Этот первый в мире программируемый электронный компьютер, который стал прародителем прекрасно знакомых нам машин, разработал телекоммуникационный инженер Томми Флауэрс[234]. Он тоже задействовал вентили Исключающее ИЛИ и мог безошибочно осуществлять 100 миллиардов булевых операций. Он получал данные с телетайпной ленты, которая протягивалась со скоростью около 50 километров в час. Эти хитрые инженерные решения привели к тому, что, когда 5 февраля 1944 года Colossus ввели в эксплуатацию, на взлом постоянно меняющегося шифра “Лоренц” стали уходить уже часы, а не целые дни. Флауэрс, однако, знал, что может усовершенствовать свой компьютер, и уже 1 июня появился Colossus Mk II. После переработки он стал таким же быстрым, как первая микросхема, которую Intel предложит тридцать лет спустя.
Colossus Mk II сыграл ключевую роль в успехе высадки в Нормандии. Он применялся для расшифровки радиосообщений, которыми Гитлер обменивался со своими генералами. Через четыре дня после его ввода в эксплуатацию курьер из Блетчли-парк доставил генералу Дуайту Эйзенхауэру телеграмму прямо во время заседания штаба. В телеграмме говорилось, что различные меры военной дезинформации в преддверии высадки в Нормандии сработали. Из разведданных, полученных с помощью Colossus, Гитлер полагал, что неминуемое наступление случится на востоке, и направил огромное количество войск в эти регионы – далеко от того места, где планировалась высадка. Поскольку первая армия США должна была высадиться в самой западной точке выбранного прибрежного участка, телеграмма наверняка обрадовала Эйзенхауэра. Он повернулся к членам штаба и объявил: “Выдвигаемся завтра”. Много лет спустя Эйзенхауэр отметил, что работа по взлому шифров в Блетчли-парке сократила войну на два года и спасла сотни тысяч жизней. Не стоит и сомневаться, что Джорджу Булю, а может, и Готфриду Лейбницу есть чем гордиться.
Полная конфиденциальность
История математического криптоанализа вообще-то началась не с Шеннона. Самой известной ее отправной точкой считается 850 год, когда арабский математик и философ Абу Юсуф Якуб ибн Исхак аль-Кинди провел статистический анализ информации в своем “Трактате о дешифровке криптографических сообщений”. Он показал, что зашифрованный текст часто можно прочитать, применив статистические инструменты, например частотный анализ. Зная, какие буквы или слова встречаются чаще всего (например, буква “e” в английском языке), можно найти в зашифрованном сообщении подставленные вместо них символы и приступить к взлому шифра.
Со времен аль-Кинди людям, которые стремились сохранить что-либо в тайне, всегда приходилось находить новые неожиданные способы подставлять символы в текст. Но гарантию дает лишь один способ: разработка кода, в котором алгоритм подстановки для шифрования и дешифрования сообщения – “ключ” – нельзя угадать. Идеальный ключ предполагает совершенно случайные подстановки, содержит не меньше символов или битов, чем начальное сообщение, известен только отправителю и получателю и используется только один раз, чтобы невозможно было подвергнуть его статистическому анализу. В криптографических кругах его называют одноразовым блокнотом.
В своей статье Шеннон показал, что доказуемо надежны лишь такие методы шифрования, которые математически эквивалентны одноразовому блокноту. Однако, хотя его невозможно взломать, одноразовый блокнот ужасно неудобен. Как убедиться, что никто, кроме отправителя и получателя, не имеет доступ к идеальному криптографическому ключу? Нужно либо привлечь к задаче курьеров, которым можно в полной мере доверять, либо организовать встречу отправителя и получателя, чтобы они поделились друг с другом ключом, прежде чем разойтись. Если только они не будут встречаться перед каждым следующим сеансом связи (но в таком случае они вполне могли бы просто шепотом обменяться информацией), им придется заготовить целый набор ключей, которые они будут хранить и использовать при необходимости. Но тогда необходимо убедиться, что хранилище надежно и что им известно, какой именно ключ применять при получении нового сообщения.
Из-за этих трудностей практического характера единственный математически надежный метод шифрования используется редко. Вместо него все прибегают к несовершенным шифрам. Это не так уж плохо, учитывая, что более серьезные проблемы обычно возникают из-за несовершенства задействованных в процессе людей. Как и при работе с шифром “Лоренц”, польским математикам удалось взломать немецкий код “Энигма” (после чего они сообщили о своем прорыве британским разведчикам) главным образом не потому, что шифровальные машины “Энигма” были несовершенны, а потому, что связисты повторялись в своих действиях и становились предсказуемыми – например, завершали многие сообщения фразой “Хайль Гитлер”.
Возникает любопытный вопрос: в какой степени ухищрения, необходимые для практичного шифрования с помощью одноразового блокнота, умаляют его надежность? Для ответа на него нужно учитывать диапазон вариантов доступных символов, размер ключа, с помощью которого осуществляется шифрование, а также число зашифрованных сообщений, перехватываемых при передаче. Шеннон представил попытку взломать шифр методом грубой силы, который перебирает все возможные комбинации случайных ключей и ищет на выходе осмысленные слова и фразы. Затем он ввел понятие “интервал однозначности” – количество зашифрованных символов, которые необходимо перехватить, чтобы метод сработал. Этот интервал зависит от того, какие есть варианты при выборе ключа, а также от статистических характеристик языка. Если сообщение на английском передается с помощью простого шифра подстановки, по подсчетам Шеннона, вы сможете расшифровать его, имея около 30 символов.
30 символов – не так уж много, правда? Именно поэтому никто сегодня и не работает с простыми шифрами, которые в своих примерах рассматривал Шеннон. Какой же подход используют вместо этого?
Ответ может вас удивить. Хотя современная криптография дьявольски сложна, новейшие методики основаны на поразительно простой идее, которая возвращает нас в первую главу. Она такова: умножение проще деления.
Если я попрошу вас умножить 3 на 7, вы почти сразу назовете ответ: 21. Но стоит мне попросить вас
