Золотой билет. P, NP и границы возможного - Лэнс Фортноу

Рассмотрим популярную игру «Камень, ножницы, бумага» для двух игроков, в которой нужно выбрать камень, ножницы или бумагу и показать рукой соответствующий знак.

Камень затупляет ножницы, поэтому выбравший камень победит того, кто выбрал ножницы. Ножницы разрезают бумагу, бумага оборачивает камень. Если игроки выбирают один и тот же знак, засчитывается ничья.

Какова оптимальная стратегия в этой игре? Хорошо, если вы можете предсказать выбор противника; но что, если все наоборот, и противник знает ход ваших рассуждений? Неужели вы обречены на вечный проигрыш?

Вовсе нет – при условии, что вы действуете наугад, не размышляя. Когда камень, ножницы и бумага выбираются с одинаковой вероятностью, то независимо от стратегии противника вероятность проигрыша, победы и ничьи тоже будет одинакова – одна треть. Впрочем, человеку на самом деле очень сложно сделать по-настоящему случайный выбор, и знающие люди этим пользуются; вот почему для участия в чемпионатах по игре в «Камень, ножницы, бумагу» необходима не только удача, но и определенное мастерство.

Рис. 8.14. «Камень, ножницы, бумага»

В криптографии дело обстоит аналогичным образом: здесь тоже требуется абсолютная случайность. Во всех криптографических протоколах, обсуждаемых в этой главе, для защиты информации от перехватчиков и нечестных посредников используются случайные величины. Когда числа не являются абсолютно случайными, у злоумышленника появляется шанс, даже если вы используете одноразовые блокноты.

Как получить настоящие случайные числа? Компьютеры пока не научились подбрасывать монетку; впрочем, даже если бы они и умели, то монетки все равно подчинялись бы законам физики, так что случайность эта была бы достаточно условной. Источником случайности могут стать квантовые явления, однако из-за сложности реализации этот способ крайне редко применяется на практике.

Чтобы получить случайность, мы подкидываем монетку, бросаем кости, тасуем карты или крутим колесо рулетки. Все эти процессы подчиняются физическим законам (правда, казино всегда остается в выигрыше). Нетривиальный механизм взаимодействия шарика рулетки с колесом не оставляет шансов вычислить результат очередного запуска, поэтому выпадающие числа кажутся абсолютно случайными.

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

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

Генераторы псевдослучайных чисел спасают нас лишь до тех пор, пока существуют относительно трудные задачи. Если P = NP, то любой вычислительный процесс можно в той или иной степени инвертировать. В совершенном мире будет чрезвычайно трудно – а то и вовсе нереально – программно реализовать полностью случайное подбрасывание монетки. А компьютерный вариант «Камня, ножниц и бумаги» вряд ли сможет называться азартным.

Шифрование с открытым ключом базируется на «неприступности» таких NP-задач, как разложение на множители. Достаточно случайным образом выбрать два больших простых числа и перемножить их – и вы получите число, которое никто, кроме вас, на множители, скорее всего, не разложит.

Является ли задача разложения на множители NP-полной, мы не знаем; на самом деле это очень маловероятно. Впрочем, если бы она даже и была NP-полна, то из неравенства классов P и NP следовало бы лишь то, что некоторые числа трудно разложить на множители, а относительно всех случайных чисел мы не могли бы утверждать то же самое.

В основе современной криптографии лежит предположение о неравенстве классов P и NP и практической неразрешимости NP-полных задач – и в этом-то и состоит ее главная проблема.

Новый этап в развитии криптографии, начало которому в семидесятых годах положили Диффи и Хеллман, привел нас к криптографическим протоколам, базирующимся на практической неразрешимости некоторых задач. Чемпионы по кроссвордам, великие шахматисты и талантливые математики уже не способны были разгадывать шифры силой своего интеллекта.

Впрочем, игра в кошки-мышки по-прежнему продолжается. Современные мошенники уже не взламывают сами шифры, а ищут уязвимые места в системе. В протоколе, которым пользуются Элис и Боб, числа могут оказаться недостаточно случайными. В операционной системе или браузере могут найтись дефекты, позволяющие хакеру проникнуть в компьютер. Злоумышленники могут обмануть Элис и заставить ее сообщить секретный ключ. А придумав ненадежный пароль, Элис сама поставит себя под удар.

Помимо зашифрованного текста, хакеры анализируют самую разнообразную информацию – к примеру, время шифрования, которое для разных сообщений может отличаться. Еще вариант – вывести из строя часть системы, как в случае с расплавленной в микроволновке смарт-картой, и надеяться, что сбои приведут к потере конфиденциальности.

Никакой, пусть даже самый стойкий шифр не гарантирует стойкость всей системы; не исключено, что абсолютно надежный протокол мы так и не создадим.

В 1982 году лауреат Нобелевской премии по физике Ричард Фейнман обратил внимание на тот факт, что простого способа смоделировать работу квантовой системы на цифровом компьютере не существует. Из проблемы родилась идея: а что, если вычислительные устройства, основанные на принципах квантовой механики, будут работать намного эффективнее обычных компьютеров?

В последующие десятилетия в результате совместных усилий физиков и кибернетиков (которые вообще часто работают вместе) было доказано, что некоторые задачи – в частности, разложение на простые множители – квантовые компьютеры способны решать несравненно быстрее. Неизвестно, увидят ли когда-нибудь свет даже самые средненькие квантовые компьютеры, не говоря уже о больших и полноценных; неизвестно также, сумеем ли мы корректно оценить их возможности: все это пока находится под большим вопросом. В данной главе речь пойдет о квантовых вычислениях, об их мощности и таких связанных с ними понятиях, как квантовая криптография и телепортация.

Том живет в Бостоне и, конечно, болеет за «Ред Сокс». Днем его любимая команда принимала Нью-Йоркских «Янкиз»; Том был на работе и специально не читал бейсбольные новости. Вернувшись домой, он заказал пиццу, включил телевизор и начал смотреть игру, которая к тому моменту уже давно закончилась. На исходе девятого иннинга у хозяев были заняты вторая и третья база, два игрока были в ауте и один в рандауне. Отбивающий Брайан Хаммер побежал к «дому». Том напряженно замер в надежде, что его команда получит очко, – и вдруг одернул себя: эфир-то не прямой! Очко уже либо заработано, либо нет, только Тому пока об этом не известно. Для него исход по-прежнему не определен: не победа и не поражение, а что-то между ними. Результат игры он узнает чуть позже.