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

ПОЛНАЯ ПОБЕДА

Разумеется, шифр хорош лишь настолько, насколько добросовестны использующие его люди. К примеру, вы, вероятно, знаете, что Конфедерация (отколовшиеся южные штаты) вела войну против Соединенных Штатов в отчаянном стремлении сохранить чудовищную систему рабства; но знаете ли вы, что южане совершенно безобразно пользовались криптографией? Конфедераты использовали шифр Виженера с коротким ключом, повторяющимся во всем сообщении, и заботились только о кодировании слов, которые считали стратегически важными. Например, депеша, отправленная 30 сентября 1864 года Джефферсоном Дэвисом[228] генералу Эдмунду Кирби Смиту, гласила:

By which you may[229] effect O – TPQGEXYK – above that part HJ – OPG – KWMCT – patrolled by the ZMGRIK – GGIUL–CW – EWBNDLXL.

Шифровальщики конфедератов не только не зашифровали большую часть текста, но и сохранили длину зашифрованных слов. Поэтому неудивительно, что северяне, перехватив сообщение, догадались, что после слов above that part («выше той части») должно следовать выражение of the river («реки»). А имея фрагмент дешифрованного текста, определить ключ не проблема[230]. Вернитесь к алфавитному квадрату. Если слову OF соответствует слово HJ, то можно узнать буквы ключа. Буква O перешла в H, поэтому соответствующая буква в ключе будет T. Буква F перешла в J, поэтому должна быть E. На языке арифметики мы можем записать это так: H – O = T, а J – F = E. Действуя аналогичным образом и далее, получаем:

Из этой короткой фразы дешифровщик северян извлек уже больше половины использованного ключа конфедератов complete victory («Полная победа»), что выглядело несколько иронично, если учесть то, что вот-вот должно было случиться с южанами. А как только ключ известен, расшифровать оставшуюся часть сообщения – дело нескольких минут.

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

Подросток Берни Вебер[234] – математический гений. Вашингтон, ЦРУ и Йельский университет внедряются в Милуоки, чтобы похитить его. Они хотят узнать его секрет разложения простых чисел.

(Если вы не засмеялись над последним предложением, остановитесь и хорошенько подумайте над математической задачей, с которой, как предполагается, справился Берни.)