Параллельные миры

(Ноябрь 2000)

Мистические и просто любопытные страницы из истории создания криптографии с открытым ключом.

parallel-worlds

Поскольку материалистическое мировоззрение является строго детерминистским и не принимает возможности существования «многозначительных совпадений», то любые намеки на необычные синхронности автоматически толкуются как бред…

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

Станислав Гроф, «Космическая игра»
(тексты трансперсональной психологии)

В последние дни октября (2000 г) по Четвертому каналу британского телевидения прошла заключительная передача из серии «Наука тайны», включавшая в себя интервью с Клиффордом Коксом, сотрудником Штаб-квартиры правительственной связи (GCHQ) Великобритании и «тайным» изобретателем криптосхемы RSA.

Примерно с конца 1997 года миру стало известно, что группа криптографов из спецслужбы GCHQ, базирующейся в Челтнеме, открыла основные принципы криптографии с открытым ключом на несколько лет раньше, чем их коллеги из академического и индустриального сообщества.

За прошедшие 3 года в Интернете опубликованы несколько основополагающих работ английских правительственных криптографов в этой области, однако лишь ныне одному из них впервые было разрешено дать интервью средствам массовой информации.

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

* *

GCHQ является наследницей знаменитой криптослужбы, работавшей в Блечли-Парк и вскрывавшей вражеские шифры в годы Второй мировой войны (см. «Колосс британский»). В некотором смысле GCHQ является аналогом американской спецслужбы АНБ или российской ФАПСИ.

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

В конце 1960-х годов британские военные уже вполне реально ощущали вступление в эру высоких технологий, сулившую обеспечить каждого бойца собственным входом в тактическую радиосеть. Перспективы разворачивания таких сетей обещали грандиозные перемены и упрощение задач по руководству военными операциями, однако ставили и очень серьезные проблемы перед службой, отвечающей за безопасность и засекречивание подобной связи.

Настоящей головной болью становилась необходимость распределения и управления гигантскими количествами криптоключей, причем передавать каждый из ключей надо было в строжайшем секрете от неприятеля. Поэтому в 1969 году одному из выдающихся творческих умов GCHQ по имени Джеймс Эллис (James Ellis) было поручено поразмышлять как следует над возможным выходом из столь безнадежной ситуации.

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

Но тут, как это часто случается накануне открытия, внимание Эллиса привлекла давнишняя, времен войны техническая статья неизвестного автора из компании Bell-Telephone, в которой описывалась остроумная, но так и не реализованная идея засекречивания телефонной связи.

Там предлагалось, чтобы получатель маскировал речь отправителя путем добавления в линию шума. Сам получатель впоследствии мог вычитать шум, поскольку он же его и добавлял и, следовательно, знал, что тот собой представляет. Принципиально же важным моментом было то, что получателю уже не было нужды находиться в особом положении или иметь секретную информацию для того, чтобы получать засекреченную речь…

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

Далее перед Эллисом встал достаточно очевидный вопрос: «А можно ли нечто подобное проделать не с каналом электрической связи, а с обычным шифрованием»?

Как известно, главное — правильно сформулировать вопрос, поэтому как только однажды (среди ночи в постели) вопрос уложился у Эллиса в нужную форму, то доказательство теоретической возможности этого заняло всего несколько минут. Так родилась «теорема существования».

То, что было немыслимо, на самом деле оказалось вполне возможным.

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

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

* *

А вот что происходило точно в то же самое время по другую сторону океана, в Стэнфордском университете. Здесь на рубеже 1969-1970 гг. молодой профессор Мартин Хеллман начал заниматься вопросами проектирования электронных коммуникационных систем, активно привлекая математический аппарат криптографии и кодирования.

Этими вещами он увлекся с тех пор, как прочитал военного периода статьи Клода Шеннона по теории информации и криптографии, подготовленные в годы секретной работы ученого в Bell Labs и опубликованные в 1948-1949 годах. По рассказам Хеллмана, до этого он «и представить себе не мог, насколько тесно связаны шифрование и теория информации».

В статьях Шеннона вопросы кодирования рассматривались в связи с задачей снижения шумов электростатических помех, мешающих передаче радиосигналов. Хеллману стало ясно, что «шифрование решает диаметрально противоположную задачу. Вы вносите искажения при помощи ключа. Для того, кто слышит сигнал и не знает ключа, он будет выглядеть максимально искаженным. Но легитимный получатель, которому известен секретный ключ, может удалить эти помехи»…

Нетрудно заметить, что траектория выхода на изобретение у Хеллмана обозначилась по сути дела та же самая, что и у Эллиса.

В те времена, однако, ни информативных книг, ни справочников по криптографии у академических ученых по сути дела не было, поскольку эта наука считалась строго засекреченным делом военных и спецслужб.

Пытаясь собрать и объединить разрозненные идеи по шифрованию данных, Хеллман продолжал искать единомышленников. Но случилось так, что главный единомышленник вышел на него сам.

В сентябре 1973 года Хеллмана нашел Уитфилд Диффи, выпускник МТИ и молодой сотрудник Стэнфорда, страстно увлеченный криптографией. Их получасовая встреча плавно перешла в обед у Хеллмана, а разговоры затянулись далеко за полночь.

merkle_hellman_diffie
Слева направо: Ральф Меркль, Мартин Хеллман, Уитфилд Диффи

Вскоре началось и практическое сотрудничество. Хеллман и Диффи стали совместно работать над созданием криптосхемы для защиты транзакций покупок и продаж, выполняемых с домашних терминалов. Главная проблема, которую с подачи Диффи поставили перед собой ученые, сводилась к следующему «Как (не пересылая секретный ключ) получать сообщение и преобразовать его таким образом, чтобы его воспринимали только те, кому оно предназначено, а посторонним информация была бы недоступна»…

* *

В том же самом сентябре того же 1973 года, но уже в Великобритании на работу в GCHQ пришел молодой талантливый математик Клиффорд Кокс (Clifford Cocks), только что закончивший Кембридж и весьма продвинутый в теории чисел (которую в те времена обычно расценивали как один из наиболее красивых и самых бесполезных разделов математики).

Уже на начальном этапе вхождения новичка в курс работы, кто-то из наставников поведал Коксу о «воистину кучерявой» концепции несекретного шифрования. Идея крайне заинтересовала молодого человека, и он начал играть с ней в контексте простых чисел и проблем факторизации.

Rivest-Shamir-Adleman
Слева направо: Рональд Райвест, Ади Шамир, Леонард Адлеман

Буквально через полчаса Кокс пришел по сути дела к той схеме, которой будет суждено через несколько лет стать знаменитой под именем RSA, или алгоритм Райвеста-Шамира-Адлемана. Сам же изобретатель в тот момент воспринимал свое открытие просто как решение достаточно тривиальной математической головоломки.

Кокс был весьма удивлен тем, в какое волнение и возбуждение пришли его коллеги. Но при этом руководство GCHQ вновь не стало предпринимать каких-либо шагов к практической реализации идеи, поскольку для широкого внедрения целочисленных операций над огромной длины числами требовались вычислительные мощности, чересчур по тем временам дороговатые.

Несколько месяцев спустя на работу в GCHQ поступил другой даровитый математик по имени Мэлколм Уильямсон (Malcolm Williamson), приятель Кокса еще со школьных лет. Когда Кокс рассказал другу о любопытной криптосхеме, то недоверчивый Уильямсон решил, что она чересчур красива, чтобы быть правдой, и поэтому ринулся отыскивать в ней скрытые дефекты.

ellis-cocks-williams
Слева направо: Джеймс Эллис, Клиффорд Кокс, Мэлколм Уильямсон

Слабостей ему найти так и не удалось, но зато в процессе поисков он пришел к еще одному элегантному алгоритму формирования общего ключа шифрования. Другими словами, в 1974 году Уильямсон открыл то, что уже, считай, почти родилось в Америке и совсем скоро станет известно как схема распределения ключей Диффи-Хеллмана-Меркля.

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

Когда в 1976 году Диффи и Хеллман объявили о своих открытиях, то Уильямсон попытался было, как мог, склонить руководство GCHQ к публикации результатов, полученных засекреченными английскими криптографами.  Однако молодому человеку абсолютно не удалось пробить железобетонный консерватизм начальства, которое предпочло не нарушать традиций и не высовываться со своими приоритетами.

Через несколько лет, благодаря личным знакомствам в АНБ США, любопытный Уитфилд Диффи все же прослышал о работах в GCHQ и даже самолично ездил в Челтнем со своей женой, чтобы встретиться и пообщаться с Джеймсом Эллисом.

Встреча была крайне теплой и приветливой, однако Эллис, по рукам и ногам повязанный обязательством хранить служебные тайны, самым вежливым образом уклонялся от всех попыток Диффи перевести разговор в русло криптографии.

В конце концов, когда потерявший терпение и менее склонный к политесу Уит Диффи уже прямо в лоб спросил Эллиса о его роли в создании криптографии с открытым ключом, тот на некоторое время замолк, а потом тихо-тихо прошептал: «Ну не знаю я, сколько здесь можно рассказывать. Позвольте я лишь скажу, что вы, ребята, сделали со всем этим гораздо больше, чем мы»…

В последующие годы руководство GCHQ несколько раз намеревалось поведать правду. В 1987 году, в частности, Джеймсу Эллису, в связи с уходом ветерана на пенсию, даже заказали обзорную статью – для возможного широкого опубликования. Однако на главный шаг опять так и не решились, засунув ее в секретный архив.

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

* *

Когда вдруг обнаружилось, что у схем с открытым ключом объявились новые «авторы невидимого фронта», то поначалу многие испытали нечто вроде шока. Ведь это направление всегда было предметом особой гордости открытого криптосообщества.

Понемногу, впрочем, страсти и недоверчивые споры улеглись, поскольку стало ясно, что никто не собирается посягать на приоритеты традиционных авторов, а просто отчасти восстановлена историческая справедливость.

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

Или, скажем так, не связанными с материалистической точки зрения… 🙂

The END

Послесловие из 2007 г:

Секреты криптографии

(Март 2007)

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

Речь идет об известном сюжете из первой половины 1970-х годов, когда базовые принципы и конкретные алгоритмы криптографии с открытым ключом были открыты одновременно и независимо в «параллельных мирах»: коллективом засекреченных математиков из разведслужб и учеными открытого академического сообщества.

О работах  криптографов из английской спецслужбы GCHQ (Штаб-квартира правительственной связи), чуть-чуть опередивших общепризнанных в мире первооткрывателей Диффи, Хелмана, Райвеста, Шамира и Адлемана, известно уже около 10 лет.

Но в этой истории до последнего времени оставался один неясный и довольно существенный нюанс — о роли Агентства национальной безопасности США.

Ибо еще четверть века назад, на рубеже 1970-1980-х годов тогдашний директор АНБ адмирал Бобби Инман в одном из своих публичных выступлений мимоходом отметил, что принципы криптографии с открытым ключом были изобретены в стенах его спецслужбы на несколько лет раньше, чем появилась в печати новаторская работа Уитфилда Диффи и Мартина Хелмана.

И поскольку в дальнейшем от выдачи каких-либо уточняющих комментариев АНБ упорно уклонялось, то после подтвержденного документами признания английской спецслужбы в 1997 получалось, что одна и та же важная криптотехнология была изобретена независимо и одновременно сразу в трех местах…

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

Неизвестно, сделал он это преднамеренно или будучи неверно информирован своими подчиненными, но наверняка можно говорить, что речь у него шла явно об изобретении математиков из GCHQ, с которыми криптографы АНБ давно и весьма тесно связаны по линиям сотрудничества дружественных спецслужб.

Достоверно известно это стало отнюдь не по добровольному признанию АНБ, а благодаря подвижнической деятельности нью-йоркского архитектора и правозащитника Джона Янга, более всего знаменитого в интернете благодаря своему «разоблачительному» сайту Cryptome.

Еще в 1999 году Янг направил в АНБ соответствующий FOIA-запрос (т.е. официальный запрос документов на основании закона о праве граждан на доступ к государственной информации) относительно материалов, касающихся разработки методов крипто с открытым ключом.

И вот теперь, по прошествии 7 с лишним лет, из АНБ прислали Янгу пакет из десятка, примерно, документов по этой теме (cryptome.org/nsa-nse/nsa-nse-01.htm). В основном, правда, это уже известные и опубликованные в других местах работы, включая статьи англичан из GCHQ, но есть и несколько американских, со снятыми серьезными грифами вплоть до Top Secret.

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

(2000)_Shamir_Rivest_Adleman_Merkle_Hellman_Diffie
Год 2000-й. Слева направо: Шамир, Райвест, Адлеман, Меркль, Хеллман, Диффи.