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



страница24/32
Дата24.08.2017
Размер4,62 Mb.
1   ...   20   21   22   23   24   25   26   27   ...   32

Единственное предупреждение относительно надежности использования алгоритма 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 Джеймс Эллис

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

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

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

Затраты на распределение ключей уже были огромны, становясь фактором, сдерживающим любое расширение шифрования. Даже снижение затрат на распределение ключей на 10 процентов пробило бы значительную брешь в статье расходов на безопасность бюджета вооруженных сил. Однако Эллис не стал потихоньку подбираться к проблеме, он сразу же принялся за поиск радикального и полного ее решения. «Он обычно всегда приступал к решению задачи с вопроса: «Это действительно то, что мы хотим сделать? — говорит Уолтон. — Джеймс есть Джеймс, и первое, что он делал, это выяснял необходимость совместного пользования секретными данными, я имею в виду — ключом. Теоремы, гласящей, что вам требуется иметь совместно используемые секретные данные, не было. Это было нечто, вызывающее сомнения».

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

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

Шумом называется любой сигнал, который накладывается на сигналы, используемые для связи. Обычно он создается естественными причинами, и больше всего в нем раздражает то, что он носит совершенно случайный характер, что означает, что убрать шум из сообщения крайне сложно. Если радиосистема хорошо спроектирована, то уровень шума низок и сообщение отчетливо слышно, но если уровень шума высок и он забивает сообщение помехами, то разобрать сообщение не удается. Эллис предложил, чтобы получатель, Алиса, намеренно создавала шум, который она может измерять перед тем, как подать его в канал связи, соединяющий ее и Боба. После этого Боб может послать сообщение Алисе; если же Ева подсоединится к каналу связи, она не сможет прочесть сообщение, потому что оно будет «утоплено» в шуме. Ева не сможет выделить сообщение из шума. Так что единственным человеком, который в состоянии устранить шум и прочесть сообщение, будет Алиса, поскольку она единственная знает точную природу шума. Эллис понял, что безопасность достигнута без обмена какими-либо ключами. Ключом здесь послужил шум, и только Алисе требовалось знать все об этом шуме.

В меморандуме Эллис подробно описал ход своих мыслей: «Следующий вопрос был очевиден. Может ли это быть выполнено при обычном зашифровывании? Можем ли создать надежным образом зашифрованное сообщение, которое сможет прочесть законный получатель без какого-то ни было предварительного секретного обмена ключом? Этот вопрос действительно как-то ночью, когда я лежал в кровати, пришел мне в голову, причем на доказательство теоретической возможности мне понадобилось всего несколько минут. Мы получили теорему существования. То, что представлялось немыслимым, на самом деле было возможно». (Теорема существования показывает, что конкретное решение возможно, но не затрагивает подробностей решения). Другими словами, вплоть до того момента поиск решения проблемы распределения ключей напоминал поиск иголки в стоге сена, причем была вероятность, что иголки там может и не быть вовсе. Однако благодаря теореме существования Эллис теперь знал, что иголка где-то там есть.

Идеи Эллиса очень напоминали идеи Диффи, Хеллмана и Мерк-ля, за исключением того, что он на несколько лет опережал их. Однако никто не знал о работе Эллиса, так как он был служащим Британского правительства и потому дал клятву хранить тайну. Похоже, что в конце 1969 года Эллис зашел в тот же тупик, что и стэнфордская троица в 1975 году. Он убедился, что криптография с открытым ключом (или, как он ее назвал, «несекретное шифрование») возможна, и развил концепцию раздельных открытых и секретных ключей. Он также знал, что ему необходимо найти специальную одностороннюю функцию — функцию, которая смогла бы стать обратимой, если получатель имел доступ к некоторому количеству специальной информации. К сожалению, Эллис не был математиком. Он поэкспериментировал с несколькими математическими функциями, но вскоре понял, что самостоятельно добиться большего не сможет.

На этом этапе Эллис представил свое открытие руководству. Какова была их реакция — до сих пор относится к засекреченным материалам, но в интервью Ричард Уолтон был готов изложить мне своими словами содержание различных меморандумов, которые были заменены. Он сидел с портфелем на коленях, так чтобы крышка его закрывала бумаги от моего взора, и бегло просматривал документы:

Я не могу показать вам бумаги, которые у меня сейчас есть, так как на них на всех все еще стоят сомнительные слова вроде «совершенно секретно». По сути, идея Джеймса дошла до самого главного начальника, который, как делают все начальники, перепоручил разобраться с ней, и чтобы на нее смогли взглянуть эксперты. Те заявили, что то, о чем говорит Джеймс, — истинная правда. Другими словами, они не могут отмахнуться от этого человека, посчитав его сумасбродом. В то же время они не могут представить себе, каким образом внедрить его идею на практике. Так что они поражены изобретательностью Джеймса, но им непонятно, как этим воспользоваться.

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

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

Рис 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 миллионов долларов.



Поделитесь с Вашими друзьями:
1   ...   20   21   22   23   24   25   26   27   ...   32


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница