Что, если бы я попросил вас разложить на множители число 302 041? Здесь вам остается лишь прибегнуть к методу грубой силы и перебирать варианты. Можно начать с выражения 3 умножить на 100 тысяч с чем-то, пока не найдется верная комбинация. Я говорю “комбинация”, а не “комбинации”, потому что в этом примере лишь один ответ (не считая варианта с умножением самого числа на 1): 302 041 – это произведение 367 и 823. Эти множители нельзя разложить дальше, потому что они принадлежат к бесконечности простых чисел, которые делятся только на самих себя и на 1. Как и в случае с π и
Шифрование с помощью простых чисел впервые применили в Лабораториях Белла – где же еще? В октябре 1944 года инженер Уолтер Кёниг-младший закончил работу над секретным документом под названием “Итоговый отчет по проекту C-43”[235]. Работа над этим проектом велась параллельно с созданием системы X, над которой трудился Шеннон, и он представлял собой трехгодичное исследование технологий шифрования речи.
“Насущная необходимость этих исследований объяснялась, разумеется, войной”, – отмечает Кёниг во введении. Армия, флот и Национальный исследовательский комитет по вопросам обороны хотели знать, как обеспечить безопасность телефонной связи, а также выяснить, в какой степени поддаются расшифровке переговоры противника. Кёниг понимал, что, хотя отчет и был итоговым, работы предстояло еще много. Он рекомендовал “в мирное время продолжить настоящее исследование под эгидой правительства, чтобы оставаться в курсе последних изменений в искусстве связи”.
Его желание сбылось. В 1969 году инженер Джеймс Эллис наткнулся на отчет в ходе собственных исследований. Эллис работал в британском Центре правительственной связи (GCHQ) и искал способы сделать технологию шифрования более практичной. Он выяснил, что в рамках проекта C-43 среди прочего изучалось, насколько безопасной становится телефонная связь, когда лишь одна сторона добавляет в сигнал шумы. Если отправить получателю по телефонной линии гигантский объем случайных электрических помех и записать по отдельности сам звонок и созданный шум, то позже он сможет удалить помехи из разговора. Перехватчик не будет знать форму помех и потому не сможет выделить из сигнала интересующий его голос. Это “односторонняя” функция: ее легко создать, но невозможно обратить, если только у вас нет ключа.
Эллис заинтересовался возможностью обеспечивать безопасность переговоров силами лишь одной из сторон и предположил, что можно найти способ разработать подобную технологию для передачи данных. Одним летним вечером он лег спать, и, как он сказал позже, “к утру все само сложилось у меня в голове”[236]. Как истинный шпион, он решил не делать никаких записей дома и просто понадеялся, что ничего не забудет.
И не забыл. В июле 1969 года отчет Эллиса лег на стол старшего математика GCHQ Шона Уайли. Ответ Уайли позволяет понять, как работает пессимистически настроенный мозг начальника разведки: “Увы, – сказал он, – мне здесь не к чему придраться”.
Возможно, Уайли вздохнул с облегчением, поняв, что идею Эллиса не получится внедрить с использованием технологий, доступных в то время. Путь к этому методу открылся лишь в 1973 году, когда в GCHQ пришел кембриджский математик Клиффорд Кокс. Кокс проводил постдипломное исследование больших простых чисел. Когда ему объяснили, в чем состоит идея Эллиса, он сразу подумал, что с помощью простых чисел можно воссоздать “односторонний” эффект добавления помех на телефонную линию.
Он рассчитал все за один вечер. Находясь дома, он ничего не записывал, но схема запечатлелась у него в голове. В (весьма) упрощенном варианте она такова: Кокс производит математическую операцию, в ходе которой два больших простых числа создают “открытый ключ”. Он может опубликовать его, чтобы тот, кто хочет передать ему секретное сообщение, мог математически смешать свой секрет с открытым ключом. Получившуюся последовательность данных следует отправить Коксу. Поскольку математика создания открытого ключа с помощью двух простых чисел известна только Коксу, только он и может расшифровать сообщение и открыть секрет.
Эллис и Кокс описали свою идею “шифрования с открытым ключом”, но только для сотрудников британских и американских спецслужб. Через несколько лет гражданские математики тоже совершили это открытие, которое в итоге легло в основу коммерческого продукта: системы шифрования Ривеста – Шамира – Адлемана (RSA), созданной в 1977 году. Двадцать лет спустя GCHQ объявил, что на самом деле освоил шифрование с открытым ключом несколькими десятилетиями раньше.
После Эллиса и Кокса творческие математики разработали целый ряд новых способов хранить секреты. Сегодня внедрять надежные криптографические методы так просто, что подобные схемы повсеместно защищают наши персональные данные, данные наших кредитных карт, наши разговоры и все, что мы предпочитаем не разглашать. В онлайн-шопинге, как правило, используется шифрование с открытым ключом, но компания
Мы упоминали о “квантовом” мире молекул, атомов и субатомных частиц, когда изучали странные миры, которые нам открывают комплексные числа. Законы, по которым они работают, сильно отличаются от законов обычной жизни. Когда теория информации применяется на стандартном, или “классическом”, компьютере, двоичные символы – это вполне определенные нули и единицы. Однако, если вы решите зашифровать свои биты на квантовом компьютере, может возникнуть неопределенность. И это, как выясняется, меняет все.
На классических компьютерах нули и единицы закодированы как определенные состояния электрической схемы. Это может быть наличие/отсутствие напряжения, включенное/выключенное состояние транзистора или заряженное/незаряженное состояние конденсатора. На квантовых компьютерах все не так конкретно. Здесь мы кодируем нули и единицы в сущности, которые можем описать лишь математически. Как мы выяснили в главе о комплексных числах, в математике квантового мира применяются комплексные числа и волновые уравнения, а его физические проявления выходят за рамки обыденного. Это значит, что с информацией могут происходить странные вещи.
В 1994 году математик, работающий в дочерней компании – вы угадали – Лабораторий Белла, показал, насколько странными они бывают. Питер Шор изучал математику разложения на множители: поиска двух чисел, которые при перемножении дают большее известное число. Как мы уже видели, в традиционной математике нет быстрого способа раскладывать числа на множители: приходится пользоваться методом проб и ошибок. Но в квантовой математике такая хитрость есть.
Будет сложно, но лучше всего представить, что квантовые сущности кодируют информацию в виде волн. Эти волны, как рябь на воде, могут “интерферировать” друг с другом: когда небольшие волны встречаются, их структура меняется предсказуемым образом. Волны обладают и другим свойством: некоторые их атрибуты, например местоположение, не имеют точного, определенного значения. Шор продемонстрировал, что неизвестные факторы можно находить, манипулируя интерференцией неопределенных свойств волны. В более полном объяснении задействуются преобразования Фурье, но главное, что достаточно большой квантовый компьютер, который одновременно кодирует большое число квантовых битов (кубитов), может применять алгоритм Шора, чтобы с непревзойденной легкостью раскладывать большие числа на простые множители.
Это открытие сильно всколыхнуло органы государственной безопасности разных стран. В последующие годы правительства вложили немалые деньги в исследование квантовых компьютеров. Они хотели выяснить, насколько просто собрать такую машину и правда ли она будет представлять такую опасность, как указывает алгоритм Шора. Но правда в том, что прогресс в сфере квантовых компьютеров идет медленно, и лишь через двадцать лет, в 2016 году, Агентство национальной безопасности США сделало заявление по этому вопросу. “АНБ неизвестно, будет ли однажды создан квантовый компьютер достаточно большого размера, подходящий для работы с шифрованием с открытым ключом, и если да, то когда это произойдет”, – говорилось в нем. Но завершалось заявление предостережением: “Объем исследований в сфере квантовых компьютеров растет, и наблюдается достаточно серьезный прогресс, в связи с чем АНБ необходимо переходить к активным действиям”. Агентство посоветовало всем американским компаниям отказаться от шифрования на базе разложения больших чисел на простые множители. Стало ясно, что вскоре и RSA, и эллиптические кривые, и другие системы могут оказаться совершенно бесполезными[237].
Возможно, вас обнадежит, что работу Шеннона в сфере шифрования продолжают и сегодня: некоторые из лучших современных математиков разрабатывают на смену старым новые алгоритмы, способные выдержать даже квантовую атаку. Другие математики приспособили работу Шеннона по криптографии 1949 года к веку квантовой информации. Вернувшись к не имеющему равных и не поддающемуся взлому одноразовому блокноту, они подчинили себе силы квантового мира и дали нам новый способ безопасно распространять ключи шифрования. В результате возникла так называемая квантовая криптография – метод абсолютно безопасной передачи битов криптографических ключей по оптоволоконному кабелю или по спутниковой связи в любую точку мира. Если перехватчик получит эти данные или попытается завладеть хотя бы фрагментом ключа, отправитель и получатель узнают об этом, поскольку так работают математические законы квантового мира. Далее им останется лишь снова передать ключ с новым набором чисел.
В заключение разговора об этом ужасающе конструктивном и утилитарном исследовании стоит отметить, что у него возник и неожиданный побочный эффект. Совмещение бинарной логики с законами квантовой физики стимулировало новые, квантово-ориентированные исследования Вселенной, мышления и моделей поведения человека. Мы словно создаем квантовую версию “И цзин” – Лейбниц был бы доволен.
В основе этих изысканий лежит любопытная фраза “всё из бита” (
Уилер объяснил, что фраза “всё из бита” – это “наиболее емкая” формулировка идеи, что “всё – каждая частица, каждое силовое поле, даже сам пространственно-временной континуум – своей функцией, своим смыслом, даже своим существованием всецело – хотя в некоторых контекстах и опосредованно – обязано аппаратно извлеченным ответам на вопросы, предполагающие ответ «да» или «нет», двоичным вариантам, битам”. По мнению Уилера, вполне логично свести все во Вселенной к информации, которая поступает к нам в форме двоичной единицы. Если правильно совместить квантовую теорию с этими простыми кирпичиками информации, получатся пространство и время, звезды и планеты, вы и я.
Поиски продолжаются: сегодня физики, стремящиеся постичь вселенную во всей ее сложности, полагают, что теория информации может открыть им новые двери. Они мыслят категориями информационной “энтропии” – изучают пути передачи информации и проводят ее количественную оценку – и вычислительных процессов, поскольку каждый закон физики и химии можно представить как процесс, обрабатывающий биты физической Вселенной с помощью квантовых версий логических вентилей. Мы – результат этих вычислительных процессов, и наши мысли и поступки определяют их ход. Как выразился физик Сет Ллойд, “каждый атом, каждая элементарная частица участвуют в масштабном вычислительном процессе, который и есть Вселенная”, а “каждый человек на Земле – часть общего вычислительного процесса”[239]. На переднем крае физики всё во Вселенной, включая нас, можно свести к обработке битов Шеннона, Буля и Лейбница: истина и ложь, да и нет, 1 и 0.
ebooksa