6 Появляются Алиса и Боб

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

Шифр Лоренца использовался для связи между Гитлером и его генералами. Шифрование выполнялось с помощью машины Lorenz SZ40, которая действовала подобно «Энигме», но была намного сложнее, и из-за этого у дешифровальщиков в Блечли возникали огромные проблемы. Но все же двум дешифровальщикам, Джону Тилтману и Биллу Тьютте, удалось отыскать изъян в способе использования шифра Лоренца — то слабое место, которым сумели воспользоваться в Блечли и, благодаря этому, прочитать сообщения Гитлера.

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

В значительной степени позаимствовав концепцию универсальной машины Алана Тьюринга, Ньюмен спроектировал машину, которая была способна сама настраиваться на решение различных задач — то, что сегодня мы назвали бы программируемым компьютером.

Реализация конструкции Ньюмена считалась технически невозможной, так что руководство Блечли даже не стало рассматривать проект. По счастью, Томми Флауэрс, инженер, принимавший участие в обсуждении проекта Ньюмена, решил проигнорировать скептицизм Блечли и приступил к созданию такой машины. В исследовательском центре Управления почт и телеграфа в Доллис Хилл, в Северном Лондоне, Флауэрс взял чертежи Ньюмена и потратил десять месяцев, чтобы создать на его основе машину «Колосс», которую 8 декабря 1943 года передал в Блечли-Парк. Машина состояла из 1500 электронных ламп, которые действовали значительно быстрее медлительных электромеханических релейных переключателей, используемых в «бомбах». Но гораздо важнее скорости «Колосса» являлось то, что эту машину можно было программировать. Благодаря этому-то «Колосс» и стал предшественником современных цифровых ЭВМ.

После войны «Колосс», как и все остальное в Блечли-Парке, был демонтирован, а всем, кто так или иначе был связан с работой над «Колоссом», было запрещено даже упоминать о нем. Когда Томми Флауэрсу приказали уничтожить чертежи «Колосса», он послушно отнес их в котельную и сжег. Так были навсегда утрачены чертежи первого в мире компьютера. Такая секретность означала, что признание за изобретение компьютера получили другие ученые. В 1945 году Джон Преспер Эккерт и Джон Уильям Мочли в Пенсильванском университете завершили создание ЭНИАКа (электронного числового интегратора и компьютера), состоящего из 18 000 электронных ламп и способного выполнять 5000 вычислений в секунду. И в течение десятилетий именно вычислительная машина ЭНИАК, а не «Колосс», считалась прародительницей всех компьютеров.

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

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

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

Третье, и, пожалуй, наиболее существенное отличие — это то, что компьютер выполняет зашифровывание чисел, а не букв алфавита. Компьютеры работают только с двоичными числами — последовательностями единиц и нулей, которые называются двоичными знаками, или, для краткости, битами. Поэтому любое сообщение перед зашифровыванием должно быть преобразовано в двоичные знаки. Такое преобразование может выполняться в соответствии с различными протоколами, например, американским стандартным кодом для обмена информацией, широко известным как ASCII. В ASCII каждой букве алфавита сопоставляется число длиной 7 бит. Будем пока рассматривать двоичное число просто как последовательность единиц и нулей, которая однозначно определяет каждую букву (таблица 24), подобно тому, как в коде Морзе каждая буква обозначается своей последовательностью точек и тире. Существует 128 (2⁷) способов расположения 7 двоичных знаков, поэтому в ASCII можно определить до 128 различных символов. Этого вполне достаточно, чтобы задать все строчные буквы (например, а = 1100001), все необходимые знаки пунктуации (например, ! = 0100001), а также другие символы (например, & = 0100110). После того как сообщение будет переведено в двоичный вид, можно приступать к его зашифровыванию.

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

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

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

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

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

Так, например, если переставить седьмую и восьмую цифры, то поменяются местами последний 0 буквы H и первая 1 буквы E. Зашифрованное сообщение представляет собой сплошную строку из 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 цифр и обозначаемых как Left⁰ и Right⁰. Потом к цифрам в полублоке Right⁰ применяется «функция обжима», которая сложным образом заменяет цифры. Затем «обжатый» полублок Right⁰ добавляется к полублоку Left⁰, образуя новый полу-блок из 32 цифр, который обозначается как Right¹. Производится переобозначение исходного полублока Right⁰ на Left¹. Данная последовательность операций называется раундом. Процесс повторяется во втором раунде, но начинается с новых полублоков, Left¹ и Right¹, и заканчивается полублоками Left² и Right², и так продолжается до тех пор, пока не будет выполнено 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-х годах COMSEC отвечала за перевозку огромного количества ключей текущего дня. Когда корабли, перевозящие материалы COMSEC, швартовались у причала, сотрудники, ответственные за хранение криптоключей, поднимались на борт и забирали кипы перфокарт, бумажные перфоленты, дискеты и любые другие носители, на которых могли храниться ключи, доставляя их затем адресатам.

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

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