Дэвид Кан
Взломщики кодов

Предисловие

   Дешифрование является одним из наиболее важных способов добывания разведывательных данных в современном мире. Оно дает намного больше достоверной информации, чем традиционная агентурная разведка, оказывая значительное влияние на политику правительств. Тем не менее у дешифровальных спецслужб нет своего летописца.
   А они остро нуждаются в таком летописце. Хотя официально было признано, что американские дешифровальщики сократили сроки окончания войны на Тихом океане примерно на год, в научных трудах по истории это отражено лишь мимоходом, что приводит к неправильному взгляду на ход исторических событий в мире. Более того, криптоанализ сам может только выиграть, как и другие области человеческой деятельности, зная своих гениев и основные направления развития, свои ошибки и извлеченные из них уроки.
   Я сделал попытку написать серьезную историю криптоанализа, и в первую очередь – разъяснить обществу ту важную роль, которую дешифрование сыграло в жизни человечества. Для любознательных читателей эта книга может послужить надежным проводником в прошлое криптоанализа. А для историков она будет полезна тем, что обратит их внимание на скрытое влияние дешифрования на историю.
   Начиная эту книгу, я, подобно другим, хорошо осведомленным криптологам-любителям, считал, будто знаю обо всем, что напечатано по криптоанализу. Но как же мало нам было известно! Ни мы, любители, ни даже профессионалы не имели представления о том, какое большое количество ценной информации содержится в научных журналах. Мы не обращались к дешифровальщикам с просьбой поделиться своими воспоминаниями. Мы не пытались воспользоваться огромным богатством архивов. Мы не пробовали изучать вопросы, которые в настоящее время представляются нам главными. Я думаю, что не ошибусь, если заявлю, что по сравнению с ранее опубликованными материалами в моем труде содержится от 85 до 90% совершенно нового.
   И это далеко не все. Из-за необоснованной секретности недоступна большая часть документов, относящихся к недавнему прошлому. Чтобы рассказать о криптоаналитических разработках этого периода полностью, потребуется еще одна такая же книга. Даже, к примеру, в XVIII веке можно обнаружить массу неизученных рукописей.
   В моей книге я старался придерживаться двух принципов. Первый – по возможности использовать первоисточники. Часто я не мог поступить иначе, так как по некоторым вопросам еще ничего не было опубликовано. Второй – при оценке роли криптоанализа, будь то на поле брани или на дипломатическом поприще, я пытался никогда не забывать об иных важных факторах, сыгравших свою роль. Если книга создает впечатление, что все события в истории зависели от тех, о ком написана эта книга, то это не история, а ее искажение. Такой подход особенно широко распространен в литературе о шпионах, но от него не застрахован и криптоанализ. Я считаю, что хотя и пытаюсь уравновесить рассказ об истории дешифрования упоминанием других факторов, тем самым я не уменьшаю интереса к книге. Просто мое повествование становится от этого достовернее и поэтому заслуживает более серьезного внимания.
   У каждой профессии есть свой словарь. Словарь криптоаналитика достаточно сложен, поэтому небольшое по объему введение в общепринятую криптоаналитическую терминологию значительно облегчит понимание изложенного в этой книге. Определения в нем являются нестрогими и преследуют лишь цель пояснения того или иного термина. Исключения игнорируются, а множество редко употребляемых терминов и вовсе не определены – в процессе чтения книги их значение становится ясным из контекста.
   Открытый текст – сообщение, подлежащее засекречиванию. В результате применения методов шифрования сообщение делают непонятным для посторонних, используя два основных способа преобразования открытого текста.
   В случае перестановки знаки открытого текста перемешиваются, нарушается их нормальный порядок следования. Перетасовать буквы слова «секрет» так, чтобы получить «еткрсе», и означает сделать перестановку.
   При замене знаки открытого текста замещаются другими знаками. Так, слово «секрет» может быть заменено на 19 5 3 18520.
   Системы замены основаны на идее шифралфавита – перечня эквивалентов, используемых для преобразования открытого текста в шифрованный.
   Иногда шифралфавит предусматривает несколько замен одного знака. Например, знак открытого текста «с» не всегда замещается числом 16, а может быть заменен одним из чисел 16, 21, 35, 74. Этот выбор называется гомофоном. Время от времени в шифралфавит включаются символы, которые ничего не означают. Такие символы зовут пустышками.
   В том случае, когда используется только один шифралфавит, система замены называется одноалфавитной. Но когда применяются два или большее число шифралфавитов по какому-то заранее определенному правилу, система замены становится многоалфавитной.
   Среди систем замены следует делать различия между кодами и шифрами. Код состоит из тысяч слов, фраз, букв и слогов и соответствующих им кодовых слов или кодовых обозначений, которые заменяют эти элементы открытого текста. По существу, код является огромным шифром замены, в котором основными единицами открытого текста служат слова и фразы. В шифрах же основная единица – это знак, иногда пара знаков.
   В течение 450 лет, начиная примерно с 1400 г. и до 1850 г., в шифровальной практике доминировали системы, которые являлись наполовину кодом и наполовину шифром. В них обычно был отдельный шифралфавит, включавший гомофоны и кодоподобный перечень имен, слов и слогов. От этого перечня, первоначально состоявшего только из имен, и произошло название для таких систем – номенклатор.
   Во многих шифрах используется ключ, который определяет порядок следования знаков в шифралфавите, или порядок перемешивания знаков в перестановке, или начальные установки в шифрмашинах. Когда слово, или фраза, или число служат ключом, они, естественно, называются ключевым словом, ключевой фразой или ключевым числом.
   Проведение соответствующих преобразований открытого текста в шифрованный называется шифрованием или кодированием открытого текста. То, что получается в результате, носит название шифртекста или кодтекста.
   Окончательно обработанное и отосланное секретное сообщение называется криптограммой. Термин «шифртекст» обращает внимание на результат зашифрования, в то время как термин «криптограмма» подчеркивает сам факт передачи сообщения и является аналогом слова «телеграмма».
   Расшифрование (раскодирование) означает проведение обратных преобразований шифртекста (кодтекста) лицами, владеющими на законном основании ключом и системой шифрования (кодирования), для получения открытого текста. Этот процесс следует отличать от криптоанализа, который ставит своей целью прочтение открытого текста (или, другими словами, дешифрование) криптограммы людьми, не имеющими в своем распоряжении ни ключа, ни системы, то есть лицами, являющимися третьей стороной, «противником». Разница между ними, безусловно, огромная, хотя начиная с того времени, когда возникло слово «криптоанализ», термины «расшифровать» или «раскодировать» часто использовались и в смысле «дешифровать».
   Успешный криптоанализ шифра или кода часто именуют его вскрытием или взломом.
   Сообщения, посылаемые без предварительного зашифрования, называются незашифрованными или отправляемыми клером. Иногда говорят еще, что они передаются открытым текстом.
   Наконец, криптология – это наука, охватывающая составление шифров (криптографию) и криптоанализ.

Первые 3000 лет

   Почти четыре тысячи лет тому назад в древнеегипетском городе Менет-Хуфу на берегу Нила один опытный писец нарисовал иероглифы, рассказавшие историю жизни его господина. Сделав это, он стал родоначальником документально зафиксированной истории криптографии.
   Его система не является тайнописью в том виде, в каком она известна современному миру. Для засекречивания своей надписи он не использовал никакого полноценного шифра. Эта надпись, вырезанная им примерно в 1900 г. до нашей эры на гробнице знатного человека по имени Хнумхотеп, лишь в отдельных местах состоит из необычных иероглифических символов вместо более привычных иероглифов. Большинство их встречается в ее последних двадцати столбцах, в которых перечисляются монументы, созданные Хнумхотепом на службе у египетского фараона Аменемхета II. Неизвестный писец старался не затруднить чтение текста, а придать ему важность, подобно тому, как это делается в каком-нибудь заявлении по торжественному поводу, в котором пишут «в год одна тысяча восемьсот шестьдесят третий от Рождества Христова», вместо того чтобы просто и без затей написать «в 1863 году». Таким образом, хотя писец применил не тайнопись, он, бесспорно, воспользовался одним из существенных элементов шифрования – умышленным преобразованием письменных символов. Это самый древний известный нам текст, который претерпел такие изменения.
   По мере расцвета древнеегипетской цивилизации и совершенствования ее письменности росло количество усыпальниц почитаемых умерших и все более изощренными становились преобразования текстов, которые вырезались на камнях гробниц. Со временем писцы стали заменять обычную иероглифическую форму буквы, например, рот, изображенный анфас, иной формой, например, ртом, изображенным в профиль. Они вводили в употребление новые иероглифы, первый звук произношения которых выражал желательную букву, как, например, изображение свиньи. Иногда произношение двух иероглифов различалось, но их изображение напоминало друг друга. Время от времени писцы использовали иероглиф по принципу ребуса, подобно тому, как, например, в английском языке изображение пчелы может означать букву «В». Эти преобразования были изначально свойственны обычному египетскому письму: именно с их помощью иероглифы приобрели свои звуковые значения. В дальнейшем они лишь усложнялись и делались все более искусственными.
   Такие преобразования были обнаружены во многих местах – в надгробных надписях, восхвалявших пройденный путь умерших, в гимне в честь Тота1 и на саркофагах фараона Сети I. В них нет ничего такого, что преследовало бы цель скрыть смысл текста. И действительно, большинство надписей повторяются в обычной форме рядом с измененной. Для чего же тогда делать преобразования? Часто с той же целью, что и в гробнице Хнумхотепа, а именно – чтобы произвести впечатление на читателя. Иногда – чтобы показать хорошую каллиграфию или ради украшения. Реже – чтобы отразить соответствующее тому времени произношение.
   Но постепенно многие надписи начинают преследовать другую, важную для криптографии цель – секретность. В некоторых случаях секретность была нужна для усиления тайны и, следовательно, колдовской силы поминальных текстов. Гораздо чаще секретность проистекала из понятного желания древних египтян заставить прохожего прочитать их эпитафии и тем самым выразить умершим благословения, которые содержались в надгробных надписях. В Древнем Египте, с характерной для него непоколебимой верой в загробную жизнь, количество надписей быстро выросло до такой степени, что внимание к ним прохожих пошатнулось. Чтобы возродить их интерес, писцы нарочно делали надписи несколько туманными. Они ввели криптографические знаки, дабы привлечь внимание читателя, заставить его задуматься и вызвать у него желание разгадать их смысл. Но эти приемы совершенно не удались. Вместо того чтобы заинтересовать читателя, они губили даже малейшее желание прочитать набившие всем оскомину эпитафии. А посему вскоре после появления «надгробной» криптографии от нее отказались.
   Итак, добавление элемента секретности в преобразование иероглифов породило криптографию. Правда, это напоминало скорее игру, поскольку преследовалась цель задержать разгадку только на самое короткое время. Поэтому криптоанализ также заключался всего лишь в раскрытии головоломки. Таким образом, древнеегипетский криптоанализ был квазинаукой, в отличие от этой современной, чрезвычайно серьезной области научных знаний. Однако всем великим делам свойственны скромные начинания. Иероглифы Древнего Египта действительно включали, хотя и в несовершенной форме, два элемента – секретность и преобразование письма, которые составляют основные атрибуты криптографии.
   Так родилась криптология. В течение первых 3000 лет ее развитие не было неуклонным. В одних местах криптология появилась самостоятельно и потом умерла вместе с породившими ее цивилизациями. В других она выжила, проникнув в литературу. Опираясь на ее литературную основу, следующее поколение могло карабкаться к новым высотам криптологии. Но продвижение к ним было медленным и прерывистым. Больше было потеряно, чем сохранено. Значительная часть древней истории криптологии представляет собой плохо подобранный букет, составленный из расцветающих, распустившихся и увядающих цветов. Накопленные знания получили простор только в начале эпохи европейского Возрождения.
   В Индии, стране с древней высокоразвитой цивилизацией, люди с незапамятных времен пользовались несколькими разновидностями тайнописи. В классическом древнеиндийском трактате об искусстве управлять государством, написанном между 321-м и 300 гг. до нашей эры, рекомендуется, чтобы глава шпионской спецслужбы давал своим агентам задания с помощью тайнописи. Там же дипломатам дается совет прибегать к криптоанализу для получения разведывательных данных: «При невозможности беседовать с людьми пусть посол осведомится о происходящем у врага из речей нищих, пьяных, сумасшедших, спящих или из условных знаков, надписей, рисунков в храмах и местах паломничества». И хотя автор трактата не дает никакого намека, как именно нужно читать тайнопись, тот факт, что он знает о возможности ее дешифрования, свидетельствует о некоторой искушенности в области криптоанализа. Более того, впервые в истории человечества здесь упоминается о криптоанализе в политических целях.
   Не избежала соприкосновения с шифрами (или, если говорить точнее, с предшественниками шифров, так как в ней нет элемента секретности) и Библия. Как в случае с иероглифами на гробнице Хнумхотепа, преобразования письма сделаны в Библии без какого-либо явного желания скрыть содержание текста. Главной причиной, очевидно, было стремление переписчика обессмертить себя путем изменения текста, который позднее будет снова тщательно переписан и позволит пронести частицу его личности через века.
   Самая знаменитая «криптограмма» в Библии связана с историей о том, как в разгар пира у вавилонского царя Валтасара человеческая рука стала писать на стене зловещие слова: «мене, текел, упарсин». Однако тайна заключается не в том, что означают эти слова. Непонятно, почему мудрецы царя не смогли разгадать их смысл.
   Сами слова «мене», «текел» и «упарсин» взяты из арамейского языка, родственного древнееврейскому, и означают «исчислил», «взвешен» и «разделено». Когда Валтасар вызвал к себе пророка Даниила, последний без труда прочитал надпись и дал толкование этих трех слов: «мене – исчислил Бог царство твое и положил конец ему; текел – ты взвешен и найден очень легким; фарес – разделено царство твое и отдано мидянам и персам». При этом было обыграно значение слова «фарес», которое в арамейском языке идентично слову «упарсин».
   «Надпись „мене, текел, упарсин“ может также означать названия денежных единиц – мина, текел (1/60 мины) и фарес (1/2 мины). Их перечисление именно в такой последовательности символизирует крушение Вавилонской империи.
   Учитывая возможность всех этих интерпретаций, кажется странным, что вавилонские священники не сумели прочитать зловещую надпись на стене. Возможно, они боялись сообщить Валтасару плохую новость, или, может быть, Господь открыл глаза только Даниилу. Как бы там ни было, одному Даниилу удалось разгадать эту загадку, и в результате он стал первым известным криптоаналитиком. А поскольку это библейское сказание, то и награда за успешный криптоанализ, согласно Библии, намного превзошла какие-либо более поздние вознаграждения за аналогичные успехи в дешифровании: «Тогда… облекли Даниила в багряницу, и возложили золотую цепь на шею его, и провозгласили его третьим властелином в царстве».
   В Европе криптография находилась в состоянии застоя вплоть до наступления эпохи Возрождения. Применявшиеся шифрсистемы были предельно просты – фразы писались по вертикали или в обратном порядке, гласные заменялись точками, использовались иностранные алфавиты (например, древнееврейский и армянский), каждая буква открытого текста заменялась следовавшей за ней буквой. Кроме того, в течение всех этих лет криптология была поражена болезнью, которая сохранилась до более позднего времени, а именно – убежденностью многих людей в том, что криптография и криптоанализ являются разновидностями черной магии.
   С первых дней своего существования криптография преследовала цель спрятать содержание важных разделов письменных документов, имевших отношение к таким сферам магии, как гадание и заклинание. В одной из рукописей о магии, датируемой III веком, используется шифр, чтобы скрыть важные части колдовских рецептов. Криптография часто была на службе магии во времена средневековья, и даже в эпоху Возрождения с помощью шифров алхимики засекречивали важные части формул получения философского камня.
   Сходство между магией и криптографией подчеркивалось и другими факторами. Помимо криптографии, таинственные символы использовались в таких понятных лишь посвященным областях магических знаний, как астрология и алхимия, где, подобно знакам открытого текста, каждая планета и каждое химическое вещество имели специальный знак. Как и зашифрованные слова, заклинания и магические формулы, вроде «абракадабры», походили на чепуху, но в действительности были сильны скрытым значением.
   Вдобавок многие люди, которые хвастались своей способностью разгадывать шифры, одновременно похвалялись и умением слышать человеческие голоса, будучи глубоко под землей, или даром телепатии. Естественно, что впоследствии эти две области стали обсуждаться вместе – поскольку, мол, они всегда развивались бок о бок.
   Мнение о том, что криптоанализ является по своей природе черной магией, происходит и от поверхностного сходства между криптоанализом и гаданием. Извлечение смысла из шифртекста казалось точно таким же делом, что и получение знаний путем изучения расположения звезд и планет, длины линий и мест их пересечения на ладони, внутренностей овец, положения кофейного осадка в чашке. Видимость брала верх над реальностью. Простодушные усматривали магию даже в обычном процессе расшифрования. Другие, более искушенные, видели ее в криптоанализе, так как вскрытие чего-то глубоко спрятанного казалось им непостижимым и сверхъестественным.
   Ни в одном из упомянутых выше случаев применения тайнописи нет подтверждения существованию криптоанализа как науки. Время от времени факт дешифрования текста имел место. Подтверждением тому служат истории с пророком Даниилом или с какими-нибудь египтянами, которые разгадали отдельные иероглифические надписи на могильных памятниках. Но научного криптоанализа не существовало ни в Египте с Индией, ни в Европе в период до 1400 г. Была только криптография.
   Первыми открыли и описали методы криптоанализа арабы. Этот народ создал одну из самых развитых цивилизаций, которую когда-либо знала история. Арабская наука процветала. Медицина и математика у арабов стали самыми лучшими в мире. Распространились ремесла. Мощная созидательная энергия арабской культуры, которую ислам лишил живописи и скульптуры, дала плоды на ниве литературы. Получило широкое распространение составление словесных загадок, ребусов и каламбуров. Грамматика стала главным учебным предметом и включала в себя тайнопись.
   Интерес к криптографии у арабов проявился рано. В 855 г. арабский ученый по имени Абу Бакр тамед бен-Али бен-Вахшия ан-Набати включил несколько классических шифралфавитов в свою «Книгу о большом стремлении человека разгадать загадки древней письменности». Один такой шифралфавит, называвшийся «дауди» (по имени израильского царя Давида), использовался для зашифрования трактатов по черной магии. Он был составлен из видоизмененных букв древнееврейского алфавита. Другой – сохранился до более позднего времени: в 1775 г. он был использован в письме шпиона, направленном регенту Алжира.
   Познания арабов в области криптологии были подробно изложены в произведении Шехаба Калкашанди, которое представляет собой громадную 14-томную энциклопедию, написанную в 1412 г. для того, чтобы дать систематический обзор всех важных областей знания. Раздел под общим заголовком «Относительно сокрытия в буквах тайных сообщений» содержал две части: одна касалась символических действий и намеков, а другая была посвящена симпатическим чернилам и криптологии. Первый раз за всю историю шифров в энциклопедии приводился список как систем перестановки, так и систем замены. Более того, в пятом пункте списка впервые упоминался шифр, для которого была характерна более чем одна замена букв открытого текста. Однако каким бы замечательным и важным этот факт ни был, он затмевается первым в истории описанием криптоаналитического исследования шифртекста.
   Его истоки, очевидно, следует искать в интенсивном и скрупулезном изучении Корана многочисленными школами арабских грамматиков. Наряду с другими исследованиями, они занимались подсчетом частоты встречаемости слов, пытаясь составить хронологию глав Корана, изучали фонетику слов, чтобы установить, являлись ли они подлинно арабскими или были заимствованы из других языков. Большую роль в обнаружении лингвистических закономерностей, приведших к возникновению криптоанализа у арабов, сыграло также развитие лексикографии. Ведь при составлении словаря автору фактически приходилось учитывать частоту встречаемости букв, а также то, какие буквы могут стоять рядом, а какие – никогда не встречаются по соседству.
   Калкашанди начинает изложение криптоаналитических методов с главного: криптоаналитик должен знать язык, на котором написана криптограмма. Поскольку арабский язык, «самый благородный и самый прекрасный из всех языков», является «одним из наиболее распространенных», далее дается пространное описание его лингвистических характеристик. Приводятся перечни букв, которые никогда не стоят вместе в одном слове, и букв, которые редко появляются по соседству, а также буквенные комбинации, которые в словах встретить невозможно. Последним идет список букв в порядке «частоты их использования в арабском языке в свете результатов изучения священного Корана». Автор даже отмечает, что «в произведениях, не связанных с Кораном, частота использования может быть иной».
   Калкашанди продолжает:
   «Если вы хотите прочесть сообщение, которое вы получили в зашифрованном виде, то прежде всего начните подсчет букв, а затем сосчитайте, сколько раз повторяется каждый знак, и подведите итог в каждом отдельном случае. Если изобретатель шифра был очень внимателен и скрыл в сообщении все границы между словами, то первая задача, которая должна быть решена, заключается в нахождении знака, разделяющего слова. Это делается так: вы берете букву и работаете, исходя из предположения, что следующая буква является знаком, делящим слова. И таким образом вы изучаете все сообщение с учетом различных комбинаций букв, из которых могут быть составлены слова… Если получается, тогда все в порядке; если нет, то вы берете следующую по счету букву и т. д., пока вы не сможете установить знак раздела между словами. Затем нужно найти, какие буквы чаще всего встречаются в сообщении, и сравнить их с образцом частоты встречаемости букв, о котором упоминалось прежде. Когда вы увидите, что одна буква попадается чаще других в данном сообщении, вы предполагаете, что это буква „Алиф“. Затем вы предполагаете, что следующая по частоте встречаемости будет буквой „Лам“. Точность вашего предположения должна подтверждаться тем фактом, что в большинстве контекстов буква „Лам“ следует за буквой „Алиф“… Затем первые слова, которые вы попытаетесь разгадать в сообщении, должны состоять из двух букв. Это делается путем оценки наиболее вероятных комбинаций букв до тех пор, пока вы не убедитесь в том, что вы стоите на правильном пути. Тогда вы глядите на их знаки и выписываете их эквиваленты всякий раз, когда они попадаются в сообщении. Нужно применять точно такой же принцип по отношению к трехбуквенным словам этого сообщения, пока вы не убедитесь, что вы на что-то напали. Вы выписываете эквиваленты из всего сообщения. Этот же принцип применяется по отношению к словам, состоящим из четырех и пяти букв, причем метод работы прежний. Всякий раз, когда возникает какое-либо сомнение, нужно высказать два, три предположения или еще больше и выписать каждое из них, пока оно не подтвердится на основании другого слова».
   Дав это четкое разъяснение, Калкашанди приводит пример вскрытия шифра. Дешифруемая криптограмма состоит из двух стихотворных строк, зашифрованных с помощью условных символов. В заключение Калкашанди отмечает, что восемь букв не было использовано и что это как раз те самые буквы, которые стоят в конце перечня, составленного по частоте встречаемости. Он отмечает: