бедиться, что хранилище надежно и что им известно, какой именно ключ применять при получении нового сообщения.
Из-за этих трудностей практического характера единственный математически надежный метод шифрования используется редко. Вместо него все прибегают к несовершенным шифрам. Это не так уж плохо, учитывая, что более серьезные проблемы обычно возникают из-за несовершенства задействованных в процессе людей. Как и при работе с шифром “Лоренц”, польским математикам удалось взломать немецкий код “Энигма” (после чего они сообщили о своем прорыве британским разведчикам) главным образом не потому, что шифровальные машины “Энигма” были несовершенны, а потому, что связисты повторялись в своих действиях и становились предсказуемыми – например, завершали многие сообщения фразой “Хайль Гитлер”.
Возникает любопытный вопрос: в какой степени ухищрения, необходимые для практичного шифрования с помощью одноразового блокнота, умаляют его надежность? Для ответа на него нужно учитывать диапазон вариантов доступных символов, размер ключа, с помощью которого осуществляется шифрование, а также число зашифрованных сообщений, перехватываемых при передаче. Шеннон представил попытку взломать шифр методом грубой силы, который перебирает все возможные комбинации случайных ключей и ищет на выходе осмысленные слова и фразы. Затем он ввел понятие “интервал однозначности” – количество зашифрованных символов, которые необходимо перехватить, чтобы метод сработал. Этот интервал зависит от того, какие есть варианты при выборе ключа, а также от статистических характеристик языка. Если сообщение на английском передается с помощью простого шифра подстановки, по подсчетам Шеннона, вы сможете расшифровать его, имея около 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 Шона Уайли. Ответ Уайли позволяет понять, как работает пессимистически настроенный мозг начальника разведки: “Увы, – сказал он, – мне здесь не к чему придраться”.
Возможно, Уайли вздохнул с облегчением, поняв, что идею Эллиса не получится внедрить с использованием технологий, доступных в то время. Путь к этому методу открылся лишь в 1973 году, когда в GCHQ пришел кембриджский математик Клиффорд Кокс. Кокс проводил постдипломное исследование больших простых чисел. Когда ему объяснили, в чем состоит идея Эллиса, он сразу подумал, что с помощью простых чисел можно воссоздать “односторонний” эффект добавления помех на телефонную линию.
Он рассчитал все за один вечер. Находясь дома, он ничего не записывал, но схема запечатлелась у него в голове. В (весьма) упрощенном варианте она такова: Кокс производит математическую операцию, в ходе которой два больших простых числа создают “открытый ключ”. Он может опубликовать его, чтобы тот, кто хочет передать ему секретное сообщение, мог математически смешать свой секрет с открытым ключом. Получившуюся последовательность данных следует отправить Коксу. Поскольку математика создания открытого ключа с помощью двух простых чисел известна только Коксу, только он и может расшифровать сообщение и открыть секрет.
Эллис и Кокс описали свою идею “шифрования с открытым ключом”, но только для сотрудников британских и американских спецслужб. Через несколько лет гражданские математики тоже совершили это открытие, которое в итоге легло в основу коммерческого продукта: системы шифрования Ривеста – Шамира – Адлемана (RSA), созданной в 1977 году. Двадцать лет спустя GCHQ объявил, что на самом деле освоил шифрование с открытым ключом несколькими десятилетиями раньше.
После Эллиса и Кокса творческие математики разработали целый ряд новых способов хранить секреты. Сегодня внедрять надежные криптографические методы так просто, что подобные схемы повсеместно защищают наши персональные данные, данные наших кредитных карт, наши разговоры и все, что мы предпочитаем не разглашать. В онлайн-шопинге, как правило, используется шифрование с открытым ключом, но компания Apple для блокировки своих мобильных устройств применяет алгоритм шифрования, основанный на математике “эллиптической кривой”. При шифровании с помощью эллиптической кривой данные скрывают не простые числа, а точки на графике. Этот алгоритм определяет последовательность простых операций, которые позволяют вам перемещаться по кривой, а перехватчик знает только начальную и конечную точки, но никак не может определить, какие точки между ними скрывают данные. Другой подход у WhatsApp: для шифрования сообщений применяется протокол Signal, который представляет собой комбинацию нескольких техник шифрования. Единственная проблема в том, что сегодня все перечисленные алгоритмы под угрозой, поскольку появилась революционная, квантовая версия криптоанализа.
Мы упоминали о “квантовом” мире молекул, атомов и субатомных частиц, когда изучали странные миры, которые нам открывают комплексные числа. Законы, по которым они работают, сильно отличаются от законов обычной жизни. Когда теория информации применяется на стандартном, или “классическом”, компьютере, двоичные символы – это вполне определенные нули и единицы. Однако, если вы решите зашифровать свои биты на квантовом компьютере, может возникнуть неопределенность. И это, как выясняется, меняет все.
На классических компьютерах нули и единицы закодированы как определенные состояния электрической схемы. Это может быть наличие/отсутствие напряжения, включенное/выключенное состояние транзистора или заряженное/незаряженное состояние конденсатора. На квантовых компьютерах все не так конкретно. Здесь мы кодируем нули и единицы в сущности, которые можем описать лишь математически. Как мы выяснили в главе о комплексных числах, в математике квантового мира применяются комплексные числа и волновые уравнения, а его физические проявления выходят за рамки обыденного. Это значит, что с информацией могут происходить странные вещи.
В 1994 году математик, работающий в дочерней компании – вы угадали – Лабораторий Белла, показал, насколько странными они бывают. Питер Шор изучал математику разложения на множители: поиска двух чисел, которые при перемножении дают большее известное число. Как мы уже видели, в традиционной математике нет быстрого способа раскладывать числа на множители: приходится пользоваться методом проб и ошибок. Но в квантовой математике такая хитрость есть.