(или
асимметричное шифрование) решает эту проблему. Оно позволяет вам посылать секретное сообщение людям, которых вы никогда раньше не встречали и с которыми вы не договаривались о секретном ключе. Оно допускает возможность двум людям обмениваться данными у всех на виду и в результате этого обмена получить секретные данные, которые не сможет получить кто-то, подслушивавший переговоры. Говоря в терминах физического мира, такое шифрование позволяет вам и вашему приятелю прокричать друг другу числа в кафе, битком набитом математиками, – так что, когда вы закончите, вы и ваш приятель получите одно и то же число, и никто, кроме вас двоих, совсем ничего не поймет.
Звучит нелепо? Это кажется невозможным. Если бы вы спросили шифровальщиков со всего света в 1975 году, все они сказали бы, что это невозможно. Так что можете себе представить всеобщее изумление, когда в 1976 году Витфилд Диффи и Мартин Хеллман объяснили, как это сделать. Или удивление британской разведки, когда Джеймс Эллис, Клиффорд Кок и М. Д. Уильямсон осуществили то же самое на несколько лет раньше.
Основная идея в том, чтобы использовать математическую функцию, которую просто вычислять в одном направлении и тяжело – в другом. Одна из таких функций – разложение целых чисел на множители. Если даны два числа, их легко перемножить и найти произведение. Но если дано только произведение, практически невозможно разложить число на множители и определить исходные числа. Как раз такого плана математику можно применять для создания шифрования с открытым ключом: в нее входят арифметические операции над абсолютными значениями чисел, возведение в степень и большие многоразрядные (до нескольких тысяч битов) исходные числа. Сегодня существует добрые полдюжины алгоритмов с названиями вроде RSA, Эль-Гамаль и алгоритм эллиптических кривых. (Алгоритмы, в основе которых лежит так называемая «задача о ранце», конкурировали с ними на ранних стадиях, но по прошествии 20 лет их так или иначе взломали.) Математика для каждого алгоритма своя, но концептуально они все одинаковы.
Вместо единственного ключа совместного пользования у Алисы и Боба есть два ключа: один для шифрования, а другой для расшифровки. Ключи различны, и невозможно, зная один ключ, вычислить другой. То есть если у вас есть ключ для шифрования, вы не сумеете найти ключ для расшифровки.
Вот в этом-то и есть самое интересное. Боб может создать пару таких ключей. Он может взять и обнародовать ключ для шифрования. Он может послать его друзьям, опубликовать на своем веб-сайте или поместить в телефонной книге. Алиса может найти этот ключ. Она может с его помощью зашифровать сообщение для Боба. Затем она может послать ему сообщение. Боб, используя свой ключ расшифровки (который он предусмотрительно не размещал на веб-сайте), сможет расшифровать и прочитать послание Алисы. Заметим, что Алисе не приходится встречаться с Бобом в какой-нибудь темной аллее и договариваться об общем секрете. Бобу даже не обязательно знать Алису. И, как ни странно, даже Алисе не обязательно знать Боба. Если Алиса сможет найти ключ, который Боб обнародовал, она сможет послать ему тайное сообщение, которое никто, кроме Боба, не сможет прочитать. Такое постоянно происходит с пользователями PGP; один из их ключей находится на каком-либо сервере, и тогда совершенно посторонний человек может отправить им зашифрованные сообщения. Даже если вы что-то смыслите в математике, это не менее удивительно.