Искусство большего. Как математика создала цивилизацию - Майкл Брукс
Что, если бы я попросил вас разложить на множители число 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, который представляет собой комбинацию нескольких техник шифрования. Единственная проблема в том, что сегодня все перечисленные алгоритмы под угрозой, поскольку появилась революционная, квантовая версия криптоанализа.
Информация и квантовое будущее
Мы упоминали о “квантовом” мире молекул, атомов и субатомных частиц, когда изучали странные миры, которые нам открывают комплексные числа. Законы, по которым они работают, сильно отличаются от законов обычной жизни. Когда теория информации применяется на стандартном, или “классическом”, компьютере, двоичные символы – это вполне определенные нули и единицы. Однако, если вы решите зашифровать свои биты на квантовом компьютере, может возникнуть неопределенность. И это, как выясняется, меняет все.
На классических компьютерах нули и единицы закодированы как определенные состояния электрической схемы. Это может быть наличие/отсутствие напряжения, включенное/выключенное состояние транзистора или заряженное/незаряженное состояние конденсатора. На квантовых компьютерах все не так конкретно. Здесь мы кодируем нули и единицы в сущности, которые можем описать лишь математически. Как мы выяснили в главе о комплексных числах, в математике квантового мира применяются комплексные числа и волновые уравнения, а его физические проявления выходят за рамки обыденного. Это значит, что с
