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



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

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

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

Открытый текст = HELLO = 1001000 1000101 1001100 1001100 1001111

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

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

Так, например, если переставить седьмую и восьмую цифры, то поменяются местами последний 0 буквы Н и первая 1 буквы Е. Зашифрованное сообщение представляет собой сплошную строку из 35 двоичных цифр, которую можно передать получателю и из которой затем, путем обратной перестановки, можно воссоздать исходную строку двоичных цифр. После чего получатель преобразует двоичные цифры ASCII-кода и восстановит сообщение HELLO.

Таблица 24. ASCII-код двоичного представления заглавных букв

Допустим, что теперь мы хотим зашифровать это же сообщение, HELLO, только на этот раз с помощью простой компьютерной версии шифра замены. Перед тем как приступить к зашифровыванию, мы вначале опять-таки преобразуем сообщение в ASCII-код. Как обычно, при замене используется ключ, который был согласован между отправителем и получателем. В нашем случае ключом будет слово DAVID, преобразованное в ASCII-код, которое используется следующим образом. Каждый элемент открытого текста «добавляется» к соответствующему элементу ключа. «Добавление» двоичных цифр может выполняться, исходя из двух простых правил. Если элементы в открытом тексте и в ключе одинаковы, то элемент в открытом тексте заменяется на 0 в шифртексте. Если же элементы в сообщении и в ключе различны, то элемент в открытом тексте заменяется на 1 в шифртексте:

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

Компьютерное шифрование ограничивалось только тем кругом лиц, у кого имелись компьютеры; первоначально это означало правительство и военных. Однако ряд научных открытий, и технологических и инженерных достижений сделали компьютеры и компьютерное шифрование гораздо более широко доступными. В 1947 году в компании AT&T Bell Laboratories был создан транзистор — дешевая альтернатива электронной лампе. Использование компьютеров для решения промышленных и коммерческих задач стало реальностью в 1951 году, когда такие компании, как Ферранти, начали изготавливать компьютеры на заказ. В 1953 году IBM выпустила свой первый компьютер, четыре года спустя она же представила Фортран — язык программирования, который позволил «обычным» людям писать компьютерные программы. А создание в 1959 году интегральных схем провозгласило новую эру компьютеризации.

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

Одним из наиболее известных и признанных алгоритмов шифрования и кандидатом в качестве стандарта был продукт компании IBM, известный как Люцифер. Он был создан Хорстом Файстелем, немецким эмигрантом, приехавшим в Америку в 1934 году. Файстель уже вот-вот должен был получить гражданство США, когда Америка вступила в войну, что означало, что он находился под домашним арестом вплоть до 1944 года. После этого он еще несколько лет умалчивал о своем интересе к криптографии, чтобы не возбудить подозрений у американских властей. Когда же он в конце концов начал заниматься изучением шифров в Кембриджском научно-исследовательском центре ВВС США, то вскоре оказался под пристальным вниманием Агентства национальной безопасности (АНБ) — организации, отвечающей за обеспечение безопасности военной и правительственной связи, которая занималась также перехватом и дешифровкой иностранных сообщений. В АНБ работало больше математиков, она приобретала больше компьютерной техники и перехватывала больше сообщений, чем любая другая организация в мире. В общем, что касается совать нос в чужие дела, то тут оно является мировым лидером.

АНБ выдвигало обвинения не против прошлого Файстеля, оно просто хотело обладать монополией в области криптографических исследований, и, по-видимому, именно оно устроило так, что исследовательский проект Файстеля был закрыт. В 60-х годах Файстель перешел в компанию Mitre Corporation, но АНБ продолжало оказывать на него давление и вторично вынудило его бросить работу.

В конце концов Файстель оказался в исследовательской лаборатории Томаса Дж. Уотсона компании IBM неподалеку от Нью-Йорка, где в течение нескольких лет он мог без помех продолжать свои исследования. Там-то в начале 70-х он и создал систему Люцифер.

Люцифер зашифровывает сообщения следующим образом. Вначале сообщение преобразуется в длинную строку двоичных цифр. Далее эта строка разбивается на блоки из 64 цифр, и зашифровывание производится отдельно для каждого блока. Затем берется только один блок, 64 цифры этого блока перетасовываются, после чего его делят на два полублока, состоящих из 32 цифр и обозначаемых как Left0 и Right0. Потом к цифрам в полублоке Right0 применяется «функция обжима», которая сложным образом заменяет цифры. Затем «обжатый» полублок Right0 добавляется к полублоку Left0, образуя новый полу-блок из 32 цифр, который обозначается как Right1. Производится переобозначение исходного полублока Right0 на Left1. Данная последовательность операций называется раундом. Процесс повторяется во втором раунде, но начинается с новых полублоков, Left1 и Right1, и заканчивается полублоками Left2 и Right2, и так продолжается до тех пор, пока не будет выполнено 16 раундов. Процесс зашифровывания немного напоминает замешивание теста. Представьте себе длинный кусок теста в виде бруска с написанным на нем сообщением. Вначале этот длинный кусок делится на блоки длиной 64 см. Затем половинка одного из блоков подцепляется, обжимается, складывается пополам, добавляется к другой половине и растягивается, образуя новый блок. После чего процесс повторяется снова и снова, пока сообщение не станет основательно перемешанным. По завершении 16 циклов «замешивания» шифртекст отсылается; его расшифровка получателем производится точно так же, как и зашифровывание, но в обратном порядке.

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

По всеобщему мнению Люцифер являлся одним из наиболее стойких, коммерчески доступных программных продуктов шифрования, вследствие чего он использовался рядом организаций. Казалось само собой разумеющимся, что эта система шифрования будет принята в качестве американского стандарта, но в работу Файстеля опять вмешалось АНБ. Люцифер оказался настолько стойким, что, будучи принятым в качестве стандарта шифрования, мог оказаться за пределами криптоаналитических возможностей АНБ; поэтому не удивительно, что АНБ не хотело видеть стандартом шифрования такой продукт, который они не смогут взломать. Ходили слухи, что АНБ, перед тем как разрешить принять Люцифер в качестве стандарта, пыталось ослабить один из его аспектов — сократить число возможных ключей.

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

АНБ настаивало на том, чтобы число ключей составляло примерно 100 000 000 000 000 000 (или, иначе, 56 бит[26], поскольку это число состоит из 56 цифр, если записать его в двоичном представлении). Видимо, АНБ полагало, что такой ключ обеспечит безопасность для гражданских организаций и лиц, так как ни в одной гражданской организации нет достаточно мощного компьютера, способного проверить все возможные ключи за приемлемое время. Однако само АНБ, имеющее доступ к самым мощным в мире вычислительным ресурсам, сможет раскрыть такие сообщения. 56-битовый вариант шифра Люцифер Файстеля, получивший название DES (стандарт шифрования данных), был официально принят 23 ноября 1976 года. Четверть века спустя DES по-прежнему остается официальным американским стандартом шифрования.

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

Представьте, что банк хочет передать определенную конфиденциальную информацию клиенту по телефонной линии, но обеспокоен тем, что кто-нибудь может подключиться к линии и перехватить сообщение. Банк выбирает ключ и использует DES, чтобы зашифровать информационное сообщение. Чтобы расшифровать сообщение, клиенту нужно не только иметь копию DES на своем компьютере, но также знать, какой ключ использовался для зашифровывания сообщения. Каким же образом банк может сообщить о ключе своему клиенту? Он не может выслать ключ по телефонной линии, поскольку подозревает, что на линии имеется подслушивающее устройство. Единственный, действительно безопасный способ передать ключ, — это вручить его лично, что, несомненно, требует времени. Менее безопасное, но более практичное решение — это передать ключ через курьера. В 70-х годах банки пытались передавать ключи, используя для этого специальных связных из числа наиболее доверенных служащих. Эти связные мчались через весь мир с запертыми на замок портфелями, лично доставляя ключи тем, кто должен будет получить сообщения от банка в течение следующей недели. По мере роста масштабов коммерческих сетей, передачи все большего числа сообщений и необходимости доставки все большего количества ключей, банки пришли к заключению, что процесс распределения превратился в ужасающий кошмар, а накладные расходы стали непомерно высоки.

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

Правительство и вооруженные силы способны до известной степени справиться с проблемой распределения ключей, вкладывая в ее решение средства и ресурсы. Их сообщения настолько важны, что они не остановятся ни перед чем, чтобы обеспечить безопасность распределение ключей. Контролем и распределением ключей правительства США ведает COMSEC — сокращенное название подразделения, обеспечивающего безопасность передачи данных. В 70-х годах СОМ Б ЕС отвечала за перевозку огромного количества ключей текущего дня. Когда корабли, перевозящие материалы СОМ8ЕС, швартовались у причала, сотрудники, ответственные за хранение криптоключей, поднимались на борт и забирали кипы перфокарт, бумажные перфоленты, дискеты и любые другие носители, на которых могли храниться ключи, доставляя их затем адресатам.

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

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

Бог вознаграждает дураков

Уитфилд Диффи — один из криптографов-энтузиастов своего поколения. Внешний вид его поражает и создает отчасти противоречивый образ. Его безупречный костюм отражает тот факт, что большую часть 90-х годов он трудился в одной из американских компьютерных корпораций — ныне официально его должность звучит как «Заслуженный инженер компании Сан Микросистеме». В то же время его длинные, до плеч, волосы и белая бородка говорят о том, что сердце его принадлежит 60-м. Он проводит массу времени за компьютером, но выглядит так, словно столь же комфортно он чувствовал бы себя и в ашраме Бомбея. Диффи понимает, что его одежда и внешность вполне могут оказать влияние на других, и так комментирует это: «Люди всегда думают, что я выше, чем я есть на самом деле, но я говорю, что это — «эффект тигра»: неважно, сколько он весит фунтов и унций; из-за своих прыжков он всегда кажется крупнее».

Диффи родился в 1944 году и большую часть детства жил в Куинсе, одном из районов Нью-Йорка. Еще ребенком он увлекся математикой, читая все подряд от «Сборника математических таблиц для компаний по производству синтетического каучука» до «Курса чистой математики» Г.Х. Харди. Он продолжил ее изучение в Массачусетском технологическом институте, который окончил в 1965 году. И к началу 70-х годов, поработав в нескольких местах, стал одним из нескольких полностью независимых экспертов по безопасности, свободным криптографом, не состоящим на службе у правительства или каких-либо крупных корпораций. Оглядываясь назад, можно сказать, что он был первым шифрпанком[27].

Рис. 62. Уитфилд Диффи

Диффи особенно интересовался проблемой распределения ключей, и он понял, что тот, кому удастся найти решение, войдет в историю как один из самых величайших криптографов. Диффи настолько захватила проблема распределения ключей, что в его специальной записной книжке появилась даже запись «Задачи для величественной теории криптографии». Отчасти Диффи занялся этой проблемой еще и потому, что в воображении ему виделся мир, весь опутанный проводами. Еще в 60-е годы министерство обороны США стало финансировать организацию, занимающуюся самыми современными и перспективными исследованиями — Управление перспективных исследований[28] (ARPA), и одна из задач, стоящих перед Управлением, заключалась в том, чтобы найти способ объединить компьютеры военного назначения, находящиеся на значительных расстояниях друг от друга. Это позволило бы в случае повреждения или выхода из строя какого-либо компьютера передать решаемые им задачи другому компьютеру в сети. Основной целью являлось создание более надежной и стойкой к ядерному удару инфраструктуры имеющихся в Пентагоне компьютеров, но эта сеть также позволила бы ученым пересылать друг другу сообщения и выполнять вычисления, используя резервные мощности удаленных компьютеров. Сеть ARPANet была создана в 1969 году, а к концу этого же года четыре рабочих места уже стали объединены. ARPANet постоянно расширялся, и в 1982 году на ее основе появился Интернет. В конце 80-х доступ к Интернету получили пользователи, не являющиеся сотрудниками учебных заведений и правительственными служащими; с этого момента число пользователей стало быстро возрастать. Сегодня более сотни миллионов людей используют Интернет для обмена информацией и отправки сообщений по электронной почте.

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

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

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

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

Мартин Хеллман родился в 1945 году в еврейском квартале Бронкса, но, когда ему исполнилось четыре года, его семья переехала в другой район, где жили преимущественно ирландцы-католики. Как говорил Хеллман, это навсегда изменило его отношение к жизни: «Другие дети ходили в церковь, и там они узнали, что евреи убили Христа; из-за этого меня звали «Христоубийцей» и нередко били. Сначала мне хотелось быть таким же, как и другие дети: хотелось, чтобы у меня была рождественская елка и рождественские подарки. Но потом я понял, что таким же я быть не смогу, и тогда, в целях самозащиты, я занял позицию «а кому хочется быть похожим на других?» Свой интерес к шифрам Хеллман относит на счет стремления быть не похожим на других. Его коллеги говорили ему, что он сошел с ума, решив заняться исследованиями по криптографии, потому что его конкурентом будет АНБ с его многомиллиардным бюджетом. Как мог он надеяться найти что-то, чего им еще не было известно? А если даже он что-нибудь и обнаружит, АНБ тут же это засекретит.

Когда Хеллман приступил к исследованиям, он наткнулся на книгу «Взломщики кодов» историка Дэвида Кана. В этой книге впервые подробно рассказывается о развитии шифров, и в этом качестве она являлась прекрасным учебником для начинающих криптографов. «Взломщики кодов» была единственным помощником Хеллмана вплоть до сентября 1974 года, когда ему неожиданно позвонил Уитфилд Диффи, только что пересекший весь контитент, чтобы встретиться с ним. Хеллман никогда прежде не слышал о Диффи и с неохотой согласился уделить ему полчаса попозже днем. Но к концу встречи Хеллман понял, что Диффи был самым знающим человеком, которого он когда-либо встречал. И это чувство было обоюдным. Как вспоминает Хеллман: «Я пообещал своей жене, что буду дома, чтобы присмотреть за детьми, поэтому он пошел со мной, и мы вместе пообедали. Он уехал где-то за полночь. Мы совершенно разные, он гораздо больше нигилист, чем я, но в конечном счете наше несходство пошло нам обоим только на пользу. Для меня это оказалось словно глоток свежего воздуха. Работать «в вакууме» было поистине тяжело».



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


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

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