Саймон Сингх - Книга шифров .Тайная история шифров и их расшифровки
Рис 66 Джеймс Эллис
Но несмотря на его высокую квалификацию как криптографа, Эллиса никогда не назначали руководителем любой мало-мальски важной исследовательской группы ШКПС. Он был гениален, но непредсказуем, интроверт, и его никак нельзя было назвать настоящим членом команды. Его коллега Ричард Уолтон вспоминал:
Он был довольно своеобразным работником и, по правде говоря, не годился для повседневной деятельности ШКПС. Но если надо предложить новые идеи, тут ему не было равных. Время от времени вам приходится разгребать груду макулатуры, он же был исключительно творческой личностью и всегда желал бросить вызов ортодоксальности и общепринятому порядку. Нас бы всерьез тревожило, если бы все в ШКПС были как он, но мы, в отличие от большинства организаций, можем вытерпеть большее число таких людей. Мы миримся с некоторым количеством похожих на него людей.
Что больше всего поражало в Эллисе, так это его широта знаний. Он прочитывал все научные журналы, которые попадали ему в руки, и никогда ничего не выбрасывал. В целях безопасности сотрудники ШКПС должны были каждый вечер освобождать свои столы и все складывать в запирающиеся шкафы, и поэтому шкафы Эллиса были набиты под завязку самыми непонятными изданиями. Он приобрел репутацию «криптогуру», и если кто-то из исследователей сталкивался с исключительно сложной задачей, он стучался к нему в дверь в надежде, что его обширные знания и оригинальность мышления позволят решить ее. Возможно, что именно благодаря такой своей репутации его и попросили исследовать проблему распределения ключей.
Затраты на распределение ключей уже были огромны, становясь фактором, сдерживающим любое расширение шифрования. Даже снижение затрат на распределение ключей на 10 процентов пробило бы значительную брешь в статье расходов на безопасность бюджета вооруженных сил. Однако Эллис не стал потихоньку подбираться к проблеме, он сразу же принялся за поиск радикального и полного ее решения. «Он обычно всегда приступал к решению задачи с вопроса: «Это действительно то, что мы хотим сделать? — говорит Уолтон. — Джеймс есть Джеймс, и первое, что он делал, это выяснял необходимость совместного пользования секретными данными, я имею в виду — ключом. Теоремы, гласящей, что вам требуется иметь совместно используемые секретные данные, не было. Это было нечто, вызывающее сомнения».
Эллис приступил к решению проблемы с того, что перерыл всю свою сокровищницу научных статей. Много лет спустя он записал тот миг, когда обнаружил, что распределение ключей не является обязательной частью криптографии:
Случаем, который изменил мою точку зрения, послужило то, что я нашел подготовленный в военное время отчет неизвестного автора из компании Белл Телефон, в котором описывалась остроумная идея, как обезопасить телефонные разговоры. Предлагалось, чтобы тот, кто слушает, маскировал речь говорящего, создавая шум в линии. Потом он смог бы отсечь шум, так как это он создал его и потому знает, каков он. Использовать такую систему не позволили ее очевидные практические недостатки, но в ней было несколько интересных моментов. Разница между этой системой и обычным шифрованием заключалась в том, что в данном случае тот, кто слушает, участвует в процессе шифрования… Так родилась идея.
Шумом называется любой сигнал, который накладывается на сигналы, используемые для связи. Обычно он создается естественными причинами, и больше всего в нем раздражает то, что он носит совершенно случайный характер, что означает, что убрать шум из сообщения крайне сложно. Если радиосистема хорошо спроектирована, то уровень шума низок и сообщение отчетливо слышно, но если уровень шума высок и он забивает сообщение помехами, то разобрать сообщение не удается. Эллис предложил, чтобы получатель, Алиса, намеренно создавала шум, который она может измерять перед тем, как подать его в канал связи, соединяющий ее и Боба. После этого Боб может послать сообщение Алисе; если же Ева подсоединится к каналу связи, она не сможет прочесть сообщение, потому что оно будет «утоплено» в шуме. Ева не сможет выделить сообщение из шума. Так что единственным человеком, который в состоянии устранить шум и прочесть сообщение, будет Алиса, поскольку она единственная знает точную природу шума. Эллис понял, что безопасность достигнута без обмена какими-либо ключами. Ключом здесь послужил шум, и только Алисе требовалось знать все об этом шуме.
В меморандуме Эллис подробно описал ход своих мыслей: «Следующий вопрос был очевиден. Может ли это быть выполнено при обычном зашифровывании? Можем ли создать надежным образом зашифрованное сообщение, которое сможет прочесть законный получатель без какого-то ни было предварительного секретного обмена ключом? Этот вопрос действительно как-то ночью, когда я лежал в кровати, пришел мне в голову, причем на доказательство теоретической возможности мне понадобилось всего несколько минут. Мы получили теорему существования. То, что представлялось немыслимым, на самом деле было возможно». (Теорема существования показывает, что конкретное решение возможно, но не затрагивает подробностей решения). Другими словами, вплоть до того момента поиск решения проблемы распределения ключей напоминал поиск иголки в стоге сена, причем была вероятность, что иголки там может и не быть вовсе. Однако благодаря теореме существования Эллис теперь знал, что иголка где-то там есть.
Идеи Эллиса очень напоминали идеи Диффи, Хеллмана и Мерк-ля, за исключением того, что он на несколько лет опережал их. Однако никто не знал о работе Эллиса, так как он был служащим Британского правительства и потому дал клятву хранить тайну. Похоже, что в конце 1969 года Эллис зашел в тот же тупик, что и стэнфордская троица в 1975 году. Он убедился, что криптография с открытым ключом (или, как он ее назвал, «несекретное шифрование») возможна, и развил концепцию раздельных открытых и секретных ключей. Он также знал, что ему необходимо найти специальную одностороннюю функцию — функцию, которая смогла бы стать обратимой, если получатель имел доступ к некоторому количеству специальной информации. К сожалению, Эллис не был математиком. Он поэкспериментировал с несколькими математическими функциями, но вскоре понял, что самостоятельно добиться большего не сможет.
На этом этапе Эллис представил свое открытие руководству. Какова была их реакция — до сих пор относится к засекреченным материалам, но в интервью Ричард Уолтон был готов изложить мне своими словами содержание различных меморандумов, которые были заменены. Он сидел с портфелем на коленях, так чтобы крышка его закрывала бумаги от моего взора, и бегло просматривал документы:
Я не могу показать вам бумаги, которые у меня сейчас есть, так как на них на всех все еще стоят сомнительные слова вроде «совершенно секретно». По сути, идея Джеймса дошла до самого главного начальника, который, как делают все начальники, перепоручил разобраться с ней, и чтобы на нее смогли взглянуть эксперты. Те заявили, что то, о чем говорит Джеймс, — истинная правда. Другими словами, они не могут отмахнуться от этого человека, посчитав его сумасбродом. В то же время они не могут представить себе, каким образом внедрить его идею на практике. Так что они поражены изобретательностью Джеймса, но им непонятно, как этим воспользоваться.
Следующие три года самые светлые умы ШКПС изо всех сил старались отыскать одностороннюю функцию, которая удовлетворила бы требованиям Эллиса, но ничего не вышло. В сентябре 1973 года к команде присоединился новый математик. Клиффорд Кокс недавно окончил Кембриджский университет, где он специализировался в теории чисел, разделе, который относится к чистой математике. Когда он пришел в ШКПС, он почти ничего не знал ни о шифровании, ни о призрачном мире военных и дипломатических средств связи, так что ему был выделен наставник, Ник Паттерсон, который инструктировал и направлял его первые несколько недель в ШКПС.
Примерно через шесть недель Паттерсон рассказал Коксу о «совершенно дурацкой идее». Он в общих чертах обрисовал теорию Эллиса относительно криптографии с открытым ключом и пояснил, что до сих пор никто не сумел отыскать требуемую математическую функцию. Паттерсон поделился с Коксом не потому, что ожидал от него, что тот попробует ее решить, а поскольку это была самая щекочущая нервы криптографическая идея. Однако в тот же день, чуть позже, Кокс принялся за эту работу. Как он объясняет: «Ничего особенного не происходило, так что я решил поразмыслить над этой идеей. Поскольку я работал в области теории чисел, было вполне естественно, что и думать я стал об односторонних функциях, с помощью которых вы можете что-то сделать, но вернуться обратно уже не удастся. Явными кандидатурами были простые числа и разложение на множители, и это стало моей отправной точкой».
