Форма реальности. Скрытая геометрия стратегии, информации, общества, биологии и всего остального

Если ключ длинный, то шифр Виженера более или менее сохраняет свой неразгадываемый статус. Однако тут есть проблема, причем серьезная. У кого-то еще, кроме Акбара и Джеффа, может быть экземпляр книги Гертруды Стайн «Нежные кнопки», и, соответственно, тогда этот кто-то с легкостью расшифрует их сообщения. Если Акбар или Джефф хотят включить в число доверенных собеседников Шебу[231], они должны послать ей экземпляр книги. При намерении отправить кому-то свой ключ вы не можете его зашифровать, поскольку у вашего адресата еще нет ключа для расшифровки; но если вы отправите его в незашифрованном виде и его перехватят, то тогда можно уже вообще не шифровать.

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

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

Потайной вход – это дверь, в которую легко войти, но очень сложно выйти. Умножение двух чисел из тысячи цифр – действие, которое ваш смартфон выполнит так быстро, что вы и глазом не успеете моргнуть. Разложить это произведение на два исходных сомножителя – задача, которую ни один известный алгоритм не сможет решить за миллион миллионов человеческих жизней. И эту асимметрию вы можете использовать для передачи ключа Шебе так, чтобы противник ничего не мог с этим поделать. А поможет в этом замечательный алгоритм RSA, названный так в честь Рональда Ривеста, Ади Шамира и Леонарда Адлемана (Rivest, Shamir, Adleman), которые изобрели его в 1977 году. По крайней мере они были теми, кто его изобрел и рассказал всем об этом. Реальная история несколько интереснее. В полном соответствии с законом Стиглера система RSA носит имя не тех, кто ее создал. На самом деле она была изобретена в начале 1970-х Клиффордом Коксом и Джеймсом Эллисом. Но на этот раз для изменения авторства была крайне веская причина: Кокс и Эллис работали в Центре правительственной связи – сверхсекретной спецслужбе Великобритании. До 1990-х никто[232], кроме узкого круга лиц, не должен был знать, что алгоритм RSA был раньше, чем работа R, S и A.

Детали алгоритма RSA содержат несколько больше теории чисел, чем я хотел бы здесь поместить, но вот ключевая вещь. Шеба знает два очень больших простых числа, p и q. Никто, кроме нее, их не знает – ни Акбар, ни Джефф, ни кто-либо еще. Эти числа – ключи. Алгоритм RSA для декодирования сообщения может быть использован любым, кто знает эти два больших простых числа.

Однако для шифрования сообщений вам нужно знать не числа p

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

Это большое число N называется открытым ключом, поскольку Шеба может сообщить его всем, а при желании даже прилепить его на входную дверь своего дома. Акбару, чтобы отправить Шебе сообщение, нужно знать только произведение N

; с его помощью он может зашифровать свое сообщение, а Шеба с помощью чисел p и q превратит его обратно в исходный текст. Любой человек может с помощью числа N присылать Шебе сообщения, их можно даже открыто публиковать. Увидеть их смогут все, а вот прочитать – только Шеба, обладательница тайных ключей.

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

на составляющие простые множители p и q, то мгновенно получил бы доступ ко всем ранее отправленным личным сообщениям, зашифрованным с помощью числа N.

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