Книга шифров .Тайная история шифров и их расшифровки - Саймон Сингх

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

Большинство математиков полагает,' что разложение на множители по своей природе является трудной задачей и что существует некий математический закон, который запрещает любые ускоренные вычисления. Если, допустим, они правы, то RSA останется надежной в течение обозримого будущего.

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

Об RSA впервые было объявлено в августе 1977 года, когда Мартин Гарднер написал статью, озаглавленную «Новый вид шифра, для взлома которого потребуются миллионы лет», для колонки «Математические игры» в «Сайентифик Америкен». Объяснив, как происходит шифрование с открытым ключом, Гарднер задал задачу своим читателям. Он напечатал зашифрованное сообщение и дал открытый ключ, который использовал для его зашифровывания:

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541.

Задача заключалась в том, чтобы разложить на сомножители р и q, а затем использовать эти числа, чтобы расшифровать сообщение. Призом были 100 долларов. У Гарднера не было места, чтобы объяснить все подробности алгоритма RSA; вместо этого он попросил читателей написать в лабораторию вычислительной техники Массачусетского технологического института, откуда им пришлют технический меморандум, который был как раз к тому времени подготовлен. Ривест, Шамир и Адлеман были поражены, получив три тысячи запросов. Однако ответили они не сразу, так как были обеспокоены, что открытое распространение их идеи могло бы поставить под угрозу получение патента. Когда же вопросы по выдаче патента были в конце концов разрешены, троица устроила праздничную вечеринку, на которой преподаватели и студенты уплетали пиццу, запивая ее пивом, и одновременно раскладывали по конвертам технические меморандумы для читателей «Сайентифик Америкен».

Что касается задачи Гарднера, то для ее решения потребовалось 17 лет. 26 апреля 1994 года команда из шестисот добровольцев сообщила о том, какие сомножители были у N:

q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577

р = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533.

Используя эти значения в качестве секретного ключа, они смогли расшифровать сообщение. Сообщение состояло из ряда чисел, но, преобразованное в буквы, гласило: «Волшебные слова: брезгливая скопа». Задача разложения на множители была распределена между добровольцами, проживающими в Австралии, Англии, США и Венесуэле. Они использовали свободное время своих рабочих станций, больших ЭВМ и суперкомпьютеров; при этом каждый занимался только частью задачи. По сути, чтобы решить задачу Гарднера, компьютеры, разбросанные по всему миру, объединялись в сеть и работали одновременно. Даже принимая во внимание огромную работу, которая велась параллельно, некоторые читатели могут удивиться, что RSA была взломана за такое короткое время, но следует заметить, что в задаче Гарднера использовалось относительно малое значение N; оно составляло порядка 10129. Сегодня, чтобы обеспечить безопасность жизненно важной информации, пользователи RSA могут брать гораздо большие значения. Ныне вполне обычное дело зашифровывать сообщение с использованием такого большого N, что всем компьютерам в мире, чтобы взломать шифр, потребуется время, превышающее возраст Вселенной.

За последние двадцать лет Диффи, Хеллман и Меркль приобрели мировую известность как криптографы, которые придумали способ шифрования с открытым ключом, а Ривесту, Шамиру и Адлеману приписывается слава создания RSA — самой превосходной реализации криптографии с открытым ключом. Однако появившаяся недавно информация означает, что учебники истории необходимо переписать.

Как заявило правительство Великобритании, шифрование с открытым ключом было первоначально разработано в Штаб-квартире правительственной связи (ШКПС) в Челтенхеме, сверхсекретном учреждении, которое было сформировано из остатков Блечли-Парка после Второй мировой войны. Это — рассказ о поразительной изобретательности, безвестных героях и о правительственном комплексе мер по обеспечению скрытности, что длилось несколько десятилетий.

История началась в конце 60-х годов, когда перед Вооруженными силами Великобритании встала проблема распределения ключей. Заглядывая в 70-е годы, высшие армейские чины представили себе ситуацию, когда миниатюризация и снижение стоимости радио приведет к тому, что у каждого солдата будет постоянная связь со своим офицером. Преимущества такого широкого распространения средств связи были бы неоспоримы, но информация при этом должна передаваться в зашифрованном виде, и проблема распределения ключей оказалась бы непреодолимой. То была эпоха, когда существовала единственно симметричная форма криптографии, так что каждому участнику коммуникационной сети следовало надежным образом передать отдельный ключ. Любое расширение линий коммуникации вело к тому, что они стали бы просто задыхаться под бременем проблемы распределения ключей. Поэтому в начале 1969 гот да представители вооруженных сил попросили Джеймса Эллиса, одного из ведущих правительственных криптографов Великобритании, изучить, каким образом можно было бы справиться с проблемой распределения ключей.

Эллис был любознательным и слегка эксцентричным человеком. Он с гордостью похвалялся, что объехал пол мира еще до рождения: зачат он был в Британии, а родился в Австралии. Затем, еще будучи ребенком, он вернулся в Лондон и в 20-е годы рос в Ист-Энде. В школе его прежде всего интересовала наука. После школы он продолжил изучение физики в Имперском колледже, а затем поступил на службу в исследовательский центр Управления почт и телеграфа в Доллис Хилл, где Томми Флауэрс построил «Колосс», первый компьютер для взлома шифров. Криптографическое отделение в Доллис Хилл было в итоге присоединено к ШКПС, и поэтому 1 апреля 1965 года Эллис был переведен в Челтенхем для работы во вновь созданном Отделении обеспечения скрытности работы средств связи и электронного оборудования, специальное подразделение в ШКПС, предназначенное для обеспечения безопасности британских средств коммуникации. В связи с тем, что его работа была связана с вопросами национальной безопасности, Эллис обязался хранить тайну в течение всего срока службы. Хотя его жена и семья знали, что он работал на ШКПС, им ничего не было известно о его открытиях, и они и не подозревали, что он являлся одним из самых выдающихся криптографов страны.

Рис 66 Джеймс Эллис

Но несмотря на его высокую квалификацию как криптографа, Эллиса никогда не назначали руководителем любой мало-мальски важной исследовательской группы ШКПС. Он был гениален, но непредсказуем, интроверт, и его никак нельзя было назвать настоящим членом команды. Его коллега Ричард Уолтон вспоминал:

Он был довольно своеобразным работником и, по правде говоря, не годился для повседневной деятельности ШКПС. Но если надо предложить новые идеи, тут ему не было равных. Время от времени вам приходится разгребать груду макулатуры, он же был исключительно творческой личностью и всегда желал бросить вызов ортодоксальности и общепринятому порядку. Нас бы всерьез тревожило, если бы все в ШКПС были как он, но мы, в отличие от большинства организаций, можем вытерпеть большее число таких людей. Мы миримся с некоторым количеством похожих на него людей.

Что больше всего поражало в Эллисе, так это его широта знаний. Он прочитывал все научные журналы, которые попадали ему в руки, и никогда ничего не выбрасывал. В целях безопасности сотрудники ШКПС должны были каждый вечер освобождать свои столы и все складывать в запирающиеся шкафы, и поэтому шкафы Эллиса были набиты под завязку самыми непонятными изданиями. Он приобрел репутацию «криптогуру», и если кто-то из исследователей сталкивался с исключительно сложной задачей, он стучался к нему в дверь в надежде, что его обширные знания и оригинальность мышления позволят решить ее. Возможно, что именно благодаря такой своей репутации его и попросили исследовать проблему распределения ключей.