Лэнс Фотноу - Золотой билет

В этом случае помогут системы, называемые полностью гомоморфными. Протокол RSA устроен таким образом, что, умножив шифр одного числа (к примеру, числа 28) на шифр другого (к примеру, 45), мы в итоге получим шифр их произведения (т. е. числа 1260). Умножение чисел можно проводить без расшифровки, и исходные данные при этом знать не обязательно. Для сложения, однако, это правило не действует, и по кодам чисел 28 и 45 код числа 73 в системе RSA не получишь.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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