29 октября 2000 г. по Четвертому каналу британского телевидения прошла заключительная передача из серии «Наука тайны», включавшая в себя интервью с Клиффордом Коксом, сотрудником Штаб-квартиры правительственной связи (ШКПС) Великобритании и «тайным» изобретателем знаменитой криптосхемы RSA.
Примерно с конца 1997 года миру стало известно, что группа криптографов из спецслужбы ШКПС, базирующейся в Челтнеме, открыла основные принципы криптографии с открытым ключом на несколько лет раньше, чем их коллеги из академического и индустриального сообщества. За последующие 3 года в Интернете было опубликовано несколько основополагающих работ английских правительственных криптографов в этой области, и лишь потом одному из них власти впервые разрешили дать интервью средствам массовой информации. Постепенно всплывавшие факты продемонстрировали, что история параллельного изобретения нового направления в криптографии секретным и открытым сообществами содержит целый ряд удивительно синхронных совпадений.
ШКПС является наследницей знаменитой криптослужбы, работавшей в Блечли Парк и вскрывавшей вражеские шифры в годы второй мировой войны. В некотором смысле можно говорить, что ШКПС является аналогом американской спецслужбы АНБ или российского ФАПСИ. Однако есть и существенное отличие: ШКПС – это сугубо гражданское ведомство, формально входящее в структуру министерства иностранных дел (вероятно, по той причине, что основным объектом дешифровальных усилий спецслужбы является дипломатическая переписка зарубежных стран). Впрочем, для другого основного направления деятельности криптослужбы, сводящегося к заботе о надежных средствах засекречивания государственных коммуникаций, главным потребителем являются, естественно, военные.
В конце 1960-х годов британские вооруженные силы уже вполне реально ощущали наступление эры высоких технологий, сулившей обеспечить каждого бойца собственным входом в тактическую радиосеть. Перспективы разворачивания таких сетей обещали грандиозные перемены в упрощении руководства военными операциями, однако ставили и очень серьезные проблемы перед службой, отвечающей за безопасность и засекречивание подобной связи. Настоящей головной болью становилась необходимость распределения и управления гигантскими количествами криптоключей, причем передавать каждый из ключей надо было в строжайшем секрете от неприятеля.
Поэтому в 1969 году одному из выдающихся творческих умов ШКПС по имени Джеймс Эллис было поручено поразмышлять как следует над возможным выходом из столь безнадежной ситуации. Эллис слыл в спецслужбе одним из тех эксцентричных и гениальных чудаков, которые время от времени рождают блестящие идеи, украшают своим даром всякий творческий коллектив, и которых, однако, опасаются назначать на сколь-нибудь ответственные руководящие посты.
Поначалу для Эллиса, как и для всех, было очевидно, что не может быть никакой засекреченной связи без секретного ключа, какой-то другой секретной информации, или по крайней мере какого-то способа, с помощью которого законный получатель находился бы в позиции, отличающей его от того, кто перехватывает передачи. В конце концов, если бы они были в одинаковом положении, то как один имел бы возможность получать то, что другой не может?
Но тут, как это часто случается накануне открытия, внимание Эллиса привлекла давнишняя, времен войны техническая статья неизвестного автора из компании Bell-Telephone, в которой описывалась остроумная, но так и не реализованная идея засекречивания телефонной связи. Там предлагалось, чтобы получатель маскировал речь отправителя путем добавления в линию шума. Сам получатель впоследствии мог вычитать шум, поскольку он же его и добавлял и, следовательно, знал, что тот собой представляет.
Принципиально же важным моментом было то, что получателю уже не было нужды находиться в особом положении или иметь секретную информацию для того, чтобы получать засекреченную речь… Первичный идейный толчок оказался достаточным: различие между описанным и общепринятым методом шифрования заключалось в том, что здесь получатель сам принимает участие в процессе засекречивания.
Далее перед Эллисом встал достаточно очевидный вопрос: «А можно ли нечто подобное проделать не с каналом электрической связи, а с обычным шифрованием переписки?» Как известно, для решения задачи главное – правильно сформулировать вопрос, поэтому как только однажды (ночью в постели) вопрос уложился у Эллиса в нужную форму, то доказательство теоретической возможности этого заняло всего несколько минут. Родилась «теорема существования». То, что было немыслимо, на самом деле оказалось вполне возможным.
Так Эллис пришел к схеме, позже получившей название «криптография с открытым ключом», сам же он назвал свою концепцию «несекретное шифрование». Суть концепции, сформулированной и формально подтвержденной к началу 1970 года, сводилась к схеме из открытого и секретного ключа, управляющих однонаправленной математической операцией. Правда, поскольку Эллис был прежде всего экспертом в системах коммуникаций, а не в математике, то его революционная концепция не была доведена до конкретных математических формул. На начальство доклад Эллиса произвел большое впечатление, однако никто не смог решить, что с этими экзотическими идеями делать… и на несколько лет дело полностью встало.
А вот что происходило точно в то же самое время по другую сторону океана, в Стэнфордском университете. Здесь на рубеже 1969-1970 гг. молодой профессор Мартин Хеллман начал заниматься вопросами проектирования электронных коммуникационных систем, активно привлекая математический аппарат криптографии и теории кодирования. Этими вещами он увлекся с тех пор, как прочитал военного периода статьи Клода Шеннона по теории информации и криптографии, опубликованные в 1948 и 1949 годах. По рассказам Хеллмана, до этого он «и представить себе не мог, насколько тесно связаны шифрование и теория информации».
В статьях Шеннона вопросы кодирования рассматривались в связи с задачей снижения шумов электростатических помех, мешающих передаче радиосигналов. Хеллману стало ясно, что «шифрование решает диаметрально противоположную задачу. Вы вносите искажения при помощи ключа. Для того, кто слышит сигнал и не знает ключа, он будет выглядеть максимально искаженным. Но легитимный получатель, которому известен секретный ключ, может удалить эти помехи»… Нетрудно заметить, что траектория выхода на изобретение у Хеллмана обозначилась по сути дела та же самая, что и у Эллиса.
Но в те времена ни информативных книг, ни справочников по криптографии у академических ученых практически не было, поскольку эта наука считалась строго засекреченным делом военных и спецслужб. Пытаясь объединить разрозненные идеи по шифрованию данных, Хеллман одновременно искал единомышленников. Но случилось так, что главный единомышленник вышел на него сам.
В сентябре 1973 года Хеллмана нашел Уитфилд Диффи, выпускник МТИ и молодой сотрудник Стэнфорда, страстно увлеченный криптографией. Их получасовая встреча плавно перешла в обед у Хеллмана, после чего разговоры затянулись далеко за полночь. С этого момента Хеллман и Диффи начали совместно работать над созданием криптосхемы для защиты транзакций покупок и продаж, выполняемых с домашних терминалов. Главная проблема, которую с подачи Диффи поставили перед собой ученые, сводилась к следующему: «Как (не пересылая секретный ключ) получать сообщение и преобразовать его таким образом, чтобы его воспринимали только те, кому оно предназначено, а посторонним информация была бы недоступна»…
В том же самом сентябре того же 1973 года, но уже в Великобритании на работу в ШКПС пришел молодой талантливый математик Клиффорд Кокс, только что закончивший Кембридж и весьма продвинутый в теории чисел (которую в те времена обычно расценивали как один из наиболее красивых и самых бесполезных разделов математики). Уже на начальном этапе его вхождения в курс работы кто-то из наставников поведал Коксу о «воистину кучерявой» концепции несекретного шифрования. Идея крайне заинтересовала молодого человека, и он начал играть с ней в контексте простых чисел и проблем факторизации (разложения чисел на множители).
Буквально через полчаса Кокс пришел к той схеме, которой будет суждено через несколько лет стать знаменитой под именем RSA, или алгоритм Ривеста-Шамира-Адлемана. Сам же Кокс в тот момент воспринимал свое открытие просто как решение достаточно тривиальной математической головоломки. Он был весьма удивлен тем, в какое волнение и даже возбуждение пришли его коллеги. Но руководство ШКПС вновь не стало предпринимать каких-либо шагов к практической реализации идеи, поскольку для широкого внедрения целочисленных операций над огромной длины числами требовались вычислительные мощности,
