Золотой билет

В 1976 году большинство ученых уже склонялись к тому, что P ≠ NP, а потому системы с открытым ключом имеют право на жизнь. Диффи и Хеллман такую систему предложили, однако более широкое распространение получила криптосистема RSA, которую в 1978 году разработали Рональд Ривест, Ади Шамир и Леонард Адлеман. Система была названа по первым буквам фамилий ее создателей – Rivest, Shamir, Adleman.

В основе алгоритма RSA лежит тот факт, что умножать легко, а раскладывать на множители – очень трудно. Возьмем, к примеру, два достаточно больших простых числа, 5754853343 и 2860486313. Найти их произведение легко: это 16461679220973794359. А вот с обратным процессом все обстоит гораздо сложнее – попробуйте-ка по числу 16461679220973794359 восстановить сомножители 5754853343 и 2860486313! В системе RSA используются громадные простые числа, состоящие, как правило, из нескольких сот цифр. Нельзя утверждать, что разложение на простые множители практически неразрешимо, пока неравенство классов P и NP остается недоказанным; однако по мнению ученых задача эта представляет огромную вычислительную трудность.

За свое изобретение Ривест, Шамир и Адлеман в 2002 году получили премию Тьюринга.

Удивительный факт: позднее выяснилось, что впервые подобную криптосистему описал в 1973 году Клиффорд Кокс, работавший в то время в Центре правительственной связи Великобритании. Эта информация была обнародована лишь в 1997 году.

С системой RSA вы наверняка неоднократно сталкиваетесь каждый день. Возьмем для примера какой-нибудь часто посещаемый веб-сайт (в вашем браузере он может отображаться немного по-другому).

Рис. 8.4. Верхняя часть страницы Facebook

Обратите внимание на букву s в адресной строке и на замочек.

Рис. 8.5. Верхняя часть страницы Facebook с отметками

Буква s указывает на безопасное соединение (от англ. secure). Facebook опубликовал свой открытый ключ; этим ключом браузер шифрует ваш пароль. Злоумышленник с ноутбуком, расположившийся в другом углу кофейни, не сможет взломать пароль, даже если будет перехватывать все передаваемые по Wi-Fi данные, а вот Facebook легко восстановит его с помощью закрытого ключа. Аналогичным образом ваш браузер при необходимости создаст пару ключей и сообщит открытый ключ Facebook, а тот в ответ пришлет вам зашифрованную информацию об обновленных статусах ваших друзей, которую больше никто, кроме вас, не увидит.

Криптография в совершенном мире

Что станет с криптографией в совершенном мире? В мире из второй главы, где P = NP? Определить, что число 16461679220973794359 представляется в виде 5754853343 × 2860486313, а числа 5754853343 и 2860486313 – простые, не составит особого труда; подобные вычисления можно будет проделывать с числами из тысяч и даже миллионов цифр! Задача разложения на множители лежит в классе NP, поскольку потенциальное решение можно проверить очень быстро; если классы P и NP совпадают, то для этой задачи существует эффективный алгоритм, а значит, мы легко отыщем все делители любого, сколь угодно большого числа. Протокол RSA, как и любая другая система шифрования с открытым ключом, станет абсолютно бесполезен, поскольку закрытый ключ будет быстро восстанавливаться по открытому ключу. Равенство P и NP приведет к тому, что мы больше не сможем обмениваться секретной информацией, не условившись предварительно о способе ее передачи.

Так, значит, в совершенном мире о криптографии придется забыть? Вообще-то есть один шифр, надежность которого не зависит от отношений между P и NP: это так называемый одноразовый шифровальный блокнот. Предположим, Элис придумала пароль из 12 символов: FIDDLESTICKS. Шифровальный ключ – он же блокнот – представляет собой случайную последовательность символов той же длины: JXORMQNAMRHC. Возьмем первые символы пароля и ключа, F и J. Это шестая и десятая буквы алфавита, соответственно. В сумме их номера дают число 16, поэтому первым символом шифрованного текста будет шестнадцатая буква алфавита – P. Теперь возьмем вторые символы пароля и ключа, I и X. Это девятая и двадцать шестая буквы алфавита. В сумме их номера дают 33, однако тридцать третьей буквы алфавита в английском языке не существует, поэтому мы вычитаем из числа 33 количество букв в алфавите, т. е. 26. Получается 7, а значит, вторым символом шифровки будет седьмая буква алфавита – G. Действуя аналогичным образом, мы в итоге получим PGSVYVGUVUSV. Эту криптограмму Элис отошлет на Facebook, а он расшифрует ее с помощью точно такого же блокнота, выполняя вычитание вместо сложения.