Книга шифров. Тайная история шифров и их расшифровки
Шрифт:
Примерно через шесть недель Паттерсон рассказал Коксу о «совершенно дурацкой идее». Он в общих чертах обрисовал теорию Эллиса относительно криптографии с открытым ключом и пояснил, что до сих пор никто не сумел отыскать требуемую математическую функцию. Паттерсон поделился с Коксом не потому, что ожидал от него, что тот попробует ее решить, а поскольку это была самая щекочущая нервы криптографическая идея. Однако в тот же день, чуть позже, Кокс принялся за эту работу. Как он объясняет: «Ничего особенного не происходило, так что я решил поразмыслить над этой идеей. Поскольку я работал в области теории чисел, было вполне естественно, что и думать я стал об односторонних функциях, с помощью которых вы можете что-то сделать, но вернуться обратно уже не удастся. Явными кандидатурами были простые числа и разложение на множители, и это стало моей отправной точкой».
Рис 67
Кокс начал разрабатывать алгоритм, который позднее стал известен как асимметричный шифр RSA. Ривест, Шамир и Адлеман нашли свой алгоритм для криптографии с открытым ключом в 1977 году, но четырьмя годами раньше юный выпускник Кембриджа шел тем же самым путем. Как вспоминает Кокс: «От начала и до конца это заняло у меня не более получаса. Я был вполне доволен собой. Я думал: «О, это здорово. Мне дали задачу, и я решил ее».
Кокс не мог в полной мере оценить всю значимость своего открытия. Он не знал, что самые светлые умы ШКПС целых три года всеми силами старались отыскать решение проблемы, и не подозревал, что совершил переворот в криптографии, сделав самое выдающееся открытие века. Отчасти причиной успеха Кокса могла быть его неискушенность, позволившая ему самонадеянно взяться за решение проблемы. Кокс рассказал своему наставнику о найденном им решении, а уже тот сообщил об этом руководству.
Кокс был очень застенчив и пока еще оставался слишком «зеленым» новичком, в то время как Паттерсон полностью разбирался в ситуации и в большей мере мог разрешить технические вопросы, которые неизбежно возникнут в дальнейшем. Вскоре к Коксу начали подходить и поздравлять его совершенно незнакомые люди. Одним из них был Джеймс Эллис, страстно желающий встретиться с тем, кто превратил его мечту в реальность. Поскольку Кокс все еще не понимал всей важности своего достижения, эта встреча не произвела на него сильного впечатления, и поэтому сегодня, спустя двадцать лет, он не помнит реакции Эллиса.
Когда в конце концов Кокс понял, что он сделал, его осенило, что это открытие могло бы разочаровать Г.Х. Харди, одного из величайших английских математиков начала века. В своей книге «Апология математика», написанной в 1940 году, Харди с гордостью заявлял: «Истинная математика никак не влияет на войну. Никто еще не обнаружил ни одной, связанной с военной деятельностью цели, для которой понадобилась бы теория чисел». Под истинной математикой подразумевается «чистая» математика, как, например, теория чисел, которая послужила основой для работы Кокса. Кокс доказал, что Харди был неправ. Теперь сложности теории чисел могли помочь генералам планировать свои сражения в абсолютной секретности. Поскольку работа Кокса имела значение для военной связи, ему, как и Эллису, было запрещено говорить кому бы то ни было за пределами ШКПС о том, что он сделал. Работа в совершенно секретном правительственном учреждении означала, что он не мог поделиться этим ни со своими родителями, ни со своими прежними коллегами из Кембриджского университета. Единственным человеком, с кем он мог общаться, была его жена, Джил, так как она тоже работала на ШКПС.
Несмотря на то что идея Кокса была одной из важнейших в ШКПС, она страдала от того, что время для нее еще не пришло. Кокс нашел математическую функцию, которая дала жизнь криптографии с открытым ключом, но по-прежнему оставалась сложность с реализацией данной системы. Для шифрования с использованием криптографии с открытым ключом требуются гораздо большие вычислительные мощности, чем для шифрования с использованием симметричного шифра, как, например, DES. Но в начале 70-х компьютеры были все еще сравнительно примитивными и не могли выполнять процесс шифрования с открытым ключом за приемлемое время. Так что ШКПС была не в состоянии использовать криптографию с открытым ключом. Кокс и Эллис доказали, что, казалось бы, невозможное было возможным, но никто не мог найти способ сделать возможное осуществимым.
В начале следующего, 1974 года Кокс рассказал о своей работе по криптографии с открытым ключом Малькольму Уильямсону, который недавно был принят в ШКПС в качестве криптографа. Так случилось, что оба они были давними друзьями. Оба ходили в манчестерскую среднюю школу, девизом которой был Sapere aude — «Имей мужество пользоваться собственным умом». В 1968, еще учась в школе, оба мальчика представляли Великобританию на математической Олимпиаде, проводившейся в Советском Союзе. Оба поступили в Кембриджский университет, где их дороги на пару лет разошлись, но теперь они вновь воссоединились в ШКПС. Они обменивались математическими идеями уже в одиннадцать лет, но открытие Коксом криптографии с открытым ключом было самым поразительным, о чем когда-либо слышал Уильямсон. «Клиф объяснил мне свою идею, — вспоминает Уильямсон, — но я, вообще-то, не поверил в нее. Я был очень недоверчив, ведь это крайне специфическая вещь, чтобы суметь ее сделать».
Уильямсон ушел, решив попытаться доказать, что Кокс сделал ошибку и что криптографии с открытым ключом в действительности не существует. Он внимательно изучил математические выкладки в поисках изъянов и слабых мест. Криптография с открытым ключом казалась слишком хорошей, чтобы быть правдой, и Уильямсон был настолько полон решимости найти ошибку, что взял задачу домой.
Сотрудникам ШКПС запрещалось брать работу на дом, поскольку все, что они делали, было секретным, а семейная обстановка потенциально уязвима для шпионажа. Однако задача настолько засела в голове Уильямсона, что перестать думать о ней он не мог и, проигнорировав инструкции и предписания, забрал работу к себе домой. Он потратил пять часов, стараясь найти ошибку. «В конце концов я сдался, — говорит Уильямсон. — Вместо этого я предложил другое решение проблемы распределения ключей». Уильямсон нашел алгоритм обмена ключами Диффи-Хеллмана-Меркля, примерно в то же время, когда его открыл Мартин Хеллман. Начальная реакция Уильямсона отражала его циничный характер: «Выглядит это превосходно, — думал я про себя. — Интересно, смогу ли я найти здесь ошибку. Полагаю, что в тот день у меня было дурное настроение».
Рис 68 Малькольм Уильямсон
К 1975 году Джеймс Эллис, Клиффорд Кокс и Малькольм Уильямсон нашли все фундаментальные аспекты криптографии с открытым ключом, но им по-прежнему приходилось молчать. Все три англичанина вынуждены были наблюдать, как в течение трех следующих лет их открытия были заново открыты Диффи, Хеллманом, Мерклем, Ривестом, Шамиром и Адлеманом. Любопытно, что в ШКПС шифр RSA был найден раньше алгоритма обмена ключами Диффи-Хеллмана-Меркля, в то время как во внешнем мире вначале появился алгоритм обмена ключами Диффи-Хеллмана-Меркля. В научной печати сообщалось о выдающихся достижениях в Стэнфорде и Массачусетском технологическом институте, а исследователи, которым было разрешено опубликовать свои работы в научных журналах, стали известны в криптографическом сообществе.
Если провести поиск в Интернете с помощью какой-нибудь из поисковых машин, то окажется, что Клиффорд Кокс упоминается на 15 веб-страницах, а Уитфилд Диффи — на 1382. Кокс относится к этому исключительно сдержанно: «Вы ввязались в это дело не для получения всеобщего признания». Так же спокоен и Уильямсон: «Моей реакцией было: «Ну что ж, так устроен мир». В сущности ведь жизнь продолжается».
Рис. 69 Малькольм Уильямсон (второй слева) и Клиффорд Кокс (крайний справа), прибывшие на математическую Олимпиаду 1968 года.
Единственно, что тревожило Уильямсона, это то, что ШКПС не стала брать патент на криптографию с открытым ключом. Когда Кокс и Уильямсон совершали свои открытия, в руководстве ШКПС существовало мнение, что патентование невозможно по двум причинам. Во-первых, патентование означало бы раскрытие деталей их работы, что противоречило бы целям ШКПС. Во-вторых, в начале 70-х годов было далеко не ясно, могут ли быть запатентованы математические алгоритмы. Однако когда Диффи и Хеллман в 1976 году попробовали подать заявку на патент, оказалось, что патентовать их можно. В этот момент у Уильямсона появилось огромное желание предать гласности свое открытие и заблокировать заявку Диффи и Хеллмана, но ему было отказано руководителями высокого ранга, которые не были достаточно дальновидны, чтобы разглядеть возникновение цифровой революции и возможностей криптографии с открытым ключом. К началу 80-х руководство Уильямсона начало уже раскаиваться в своем решении, поскольку усовершенствования в компьютерах и зарождающийся Интернет убедительно показали, что RSA и алгоритм обмена ключами Диффи-Хеллмана-Меркля оказались бы продуктами, имеющими огромный коммерческий успех. В 1996 году компанией RSA Дата Секьюрити Инк. было продано продуктов RSA на сумму 200 миллионов долларов.