Искусство большего. Как математика создала цивилизацию

Возникает любопытный вопрос: в какой степени ухищрения, необходимые для практичного шифрования с помощью одноразового блокнота, умаляют его надежность? Для ответа на него нужно учитывать диапазон вариантов доступных символов, размер ключа, с помощью которого осуществляется шифрование, а также число зашифрованных сообщений, перехватываемых при передаче. Шеннон представил попытку взломать шифр методом грубой силы, который перебирает все возможные комбинации случайных ключей и ищет на выходе осмысленные слова и фразы. Затем он ввел понятие “интервал однозначности” – количество зашифрованных символов, которые необходимо перехватить, чтобы метод сработал. Этот интервал зависит от того, какие есть варианты при выборе ключа, а также от статистических характеристик языка. Если сообщение на английском передается с помощью простого шифра подстановки, по подсчетам Шеннона, вы сможете расшифровать его, имея около 30 символов.

30 символов – не так уж много, правда? Именно поэтому никто сегодня и не работает с простыми шифрами, которые в своих примерах рассматривал Шеннон. Какой же подход используют вместо этого?

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

Если я попрошу вас умножить 3 на 7, вы почти сразу назовете ответ: 21. Но стоит мне попросить вас разложить 21 на множители – целые числа, которые при перемножении дают 21, – и вам уже придется подумать подольше.

Что, если бы я попросил вас разложить на множители число 302 041? Здесь вам остается лишь прибегнуть к методу грубой силы и перебирать варианты. Можно начать с выражения 3 умножить на 100 тысяч с чем-то, пока не найдется верная комбинация. Я говорю “комбинация”, а не “комбинации”, потому что в этом примере лишь один ответ (не считая варианта с умножением самого числа на 1): 302 041 – это произведение 367 и 823. Эти множители нельзя разложить дальше, потому что они принадлежат к бесконечности простых чисел, которые делятся только на самих себя и на 1. Как и в случае с π и e, люди приписывают простым числам мистические свойства и наделяют их метафизической значимостью. Но в процессе они порой забывают, что простые числа обладают огромной практической ценностью – особенно если вам нужно хранить секреты.

Шифрование с помощью простых чисел впервые применили в Лабораториях Белла – где же еще? В октябре 1944 года инженер Уолтер Кёниг-младший закончил работу над секретным документом под названием “Итоговый отчет по проекту C-43”[235]

. Работа над этим проектом велась параллельно с созданием системы X, над которой трудился Шеннон, и он представлял собой трехгодичное исследование технологий шифрования речи.

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

Его желание сбылось. В 1969 году инженер Джеймс Эллис наткнулся на отчет в ходе собственных исследований. Эллис работал в британском Центре правительственной связи (GCHQ) и искал способы сделать технологию шифрования более практичной. Он выяснил, что в рамках проекта C-43 среди прочего изучалось, насколько безопасной становится телефонная связь, когда лишь одна сторона добавляет в сигнал шумы. Если отправить получателю по телефонной линии гигантский объем случайных электрических помех и записать по отдельности сам звонок и созданный шум, то позже он сможет удалить помехи из разговора. Перехватчик не будет знать форму помех и потому не сможет выделить из сигнала интересующий его голос. Это “односторонняя” функция: ее легко создать, но невозможно обратить, если только у вас нет ключа.

Эллис заинтересовался возможностью обеспечивать безопасность переговоров силами лишь одной из сторон и предположил, что можно найти способ разработать подобную технологию для передачи данных. Одним летним вечером он лег спать, и, как он сказал позже, “к утру все само сложилось у меня в голове”[236]. Как истинный шпион, он решил не делать никаких записей дома и просто понадеялся, что ничего не забудет.

И не забыл. В июле 1969 года отчет Эллиса лег на стол старшего математика GCHQ Шона Уайли. Ответ Уайли позволяет понять, как работает пессимистически настроенный мозг начальника разведки: “Увы, – сказал он, – мне здесь не к чему придраться”.