Читать «Золотой билет. P, NP и границы возможного» онлайн - страница 84

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

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

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

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

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

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

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

Проблемы разрастаются

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

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