Анатомия криптоанализа
Криптографию и криптоанализ иногда называют науками-двойниками. И действительно, на практике они взаимно дополняют друг друга: то, что одна наука создает, другая разрушает, и наоборот. Однако но своей природе криптография и криптоанализ различаются весьма существенно. Шифровальное дело абстрактно и до предела теоретизировано. Взлом же шифров эмпиричен и конкретен.
Голландский криптограф Моуриц Фрис так написал о теории шифрования: «Вообще криптографические преобразования имеют чисто математический характер. Например, перестановки набора первичных элементов (букв алфавита), преобразования координат узлов решеток, сложение и вычитание в конечных кольцах, линейные алгебраические преобразования. Простым примером таких математических преобразований, используемых для засекречивания, служит равенство: у = ах+b, где x — буква сообщения, у — буква шифртекста, полученная в результате операции шифрования, а и b являются постоянными величинами, определяющими данное преобразование. Таким образом, вычисления над буквами легко выполняются после определения для них соответствующего алгебраического закона».
Операции шифрования и их результаты настолько же универсальны и справедливы, насколько это свойственно законам математики. Отрицать, что при применении классического шифра Виженера* буква «d» открытого текста дает знак «F» шифрованного, невозможно точно так же, как и заявлять, что 4 + 2
* Для засекречивания сообщений в этом шифре используется математическое преобразование вида у = х + 2, в котором, как и у Фриса, х — это буква открытого текста сообщения, a y — соответствующий ей знак шифртекста.
В криптоанализе положение несколько иное. Эта наука пользуется методологией других наук, изучающих материальный мир.
Ее методы основаны не на неизменных законах математической логики, а на подмеченных фактах реального мира. Криптоаналитик получает эти факты с помощью экспериментов и измерений. В противоположность криптографу, который может вывести уравнение шифрования для классического шифра Виженера, не прибегая к дополнительным опытам, криптоаналитик, имея любое число высказываний об английском языке, априори не может сказать, какая буква встречается в нем наиболее часто. Он должен сперва подсчитать частоту встречаемости всех букв. В криптоанализе факты могут быть постоянными в каждом конкретном случае, но они логически не обусловлены и зависят от обстоятельств, от реальной действительности.
Эмпирический характер криптоанализа наиболее отчетливо проявляется в его операциях. Последние проделываются в четыре этапа, которые можно найти в других науках, занимающихся материальным миром. Эти этапы включают. 1) анализ (подсчет букв); 2) выдвижение гипотезы (знак х в шифртексте, возможно, заменяет букву «е» открытого текста); 3) предсказание (если х означает «е», то появляются некоторые возможности для нахождения открытого текста); 4) проверку (такие возможности существуют) или опровержение (таких возможностей нет, так что х вовсе не означает «е»). Данный научный метод, общий для криптоанализа и для других естественных наук, оправдывает употребление метафор вроде: «Он пытался дешифровать историю Земли, изучая отложения пород».
В криптоанализе применяются два метода — дедуктивный и индуктивный. Дедуктивные решения основываются на анализе частот встречаемости и используются при вскрытии любого шифра. Индуктивные решения основываются на вероятных словах или на благоприятном стечении обстоятельств, например наличии двух шифртелеграмм с одним и тем же открытым текстом.
Типичный силлогизм при анализе частот встречаемости букв в телеграмме на английском языке, засекреченной шифром простой однобуквенной замены, имеет в качестве универсальной посылки утверждение о том, что самым частым знаком в шифртелеграмме, вероятно, является замена для буквы «е», а в качестве частной — заявление о том, что знак х встречается в шифртелеграмме наиболее часто.
Вывод: знак х шифртекста, вероятно, заменяет букву «е» открытого текста. Поскольку всем языкам присущи строго определенные характеристики частот встречаемости букв, этот дедуктивный метод, как известно, применим к любой шифрованной телеграмме еще до ее изучения.
По своему характеру такой подход к дешифрованию является априорным. При наличии достаточного объема шифртекста он всегда дает правильный ответ и поэтому представляет собой общее решение.
С другой стороны, вскрытие шифра индуктивными методами может быть успешным лишь при выполнении определенных условий. Поскольку криптоаналитик не может сказать, действительно ли выполнены определенные условия, пока он не получит шифртелеграмму и не познакомится с ее особенностями, индуктивные методы вскрытия шифров по своему характеру являются апостериорными.
Если противник посылает шифрованное сообщение сразу же после того, как он был подвергнут массированному артиллерийскому обстрелу, за которым последовала танковая атака, криптоаналитик вполне может предположить, что в открытом тексте посланной шифровки содержатся слова: «артиллерийский обстрел» или «атака». Он может использовать эти вероятные слова для того, чтобы прочесть шифровку*. Рассуждения криптоаналитика основываются на множестве конкретных фактов, связанных с перехваченным шифрованным сообщением, и кристаллизуются всего в один вывод относительно открытого текста этого шифрсообщения. Такие рассуждения чисто индуктивны.
* Распространенные слова «что», «и» и определенный артикль, которые очень часто можно найти во всех текстах на английском языке, в этом смысле но являются вероятными.
То же можно сказать и о криптоаналитических рассуждениях, используемых при вскрытии шифров в других особых случаях.
Так как наличие вероятных слов и особые случаи позволяют криптоаналитику добыть дополнительную информацию, такое вскрытие шифров является весьма эффективным и плодотворным. Поэтому криптоанализ новых шифрсистем чаще всего начинают именно с них. К сожалению, этот подход ограничен конкретными ситуациями, и от него криптоаналитики, как правило, затем переходят к поиску общего дедуктивного решения, основанного на частоте встречаемости букв.
Представление о криптографии как о математической науке, которое впервые сформулировали в своих работах Бэббидж* и Фрис, позволило глубоко изучить ее. Осознание этого факта породило также новые способы аналитического вскрытия шифров.
* Бэббидж Ч. — английский математик, в XIX в. разработавший идею вычислительной машины, осуществленную лишь в середине XX в.
Применение принципа частот встречаемости букв в криптоанализе постепенно ширилось. В результате были вскрыты шифры, которые вначале казались ему неподвластными. Затем этот принцип столкнулся с явлением, на котором основывается современный криптоанализ, — с постоянством частотных характеристик текстов. Только после Первой мировой войны в криптоанализе возникла новая замечательная теория, которая дала объяснение этому явлению и всему процессу самого криптоанализа. Она позволила, наконец, ясно и четко понять, почему вообще возможно аналитическое вскрытие шифров.
Часто не учитывают поразительной стабильности и универсальности частот букв. Кроме криптоанализа есть и другие виды человеческой деятельности, в которых постоянство частот букв всегда принимается во внимание, поскольку пренебрежение этим явлением может причинить большие материальные убытки. Для иллюстрации этого положения обратимся к некоторым забавным фактам, прямо не связанным с криптоанализом.
В 1939 г. в США был напечатан 267-страничныи роман со скромными литературными достоинствами, но настолько оригинальный, что в своем роде у него нет равных во всей многовековой истории английского языка.
Само название романа указывает на его уникальность: «Гэдсби — роман, содержащий более 50 тысяч слов без буквы «е». Это — поразительное творение. Пусть скептически настроенный читатель убедится сам, как долго приходится подбирать хотя бы одно предложение на английском языке без использования буквы «е». Автор «Гэдсби», Эрнст Райт, перечислил некоторые трудности, с которыми он столкнулся при написании «Гэдсби». Ему приходилось избегать употребления большинства правильных глаголов в прошедшем времени, так как они оканчиваются на «ed».
Он не мог использовать определенный артикль «the» или местоимения «he», «she», «they», «we», «me» и «them»*. В «Гэдсби» надо было отказаться от просто незаменимых глаголов «are», «have», «were» и «be»** и крайне необходимых слов, как «there», «these», «those», «when», «then», «more», «after» и «very»***.
* «Он», «она», «они», «мы», «мне» и «им».
** «Являются», «иметь», «являлись» и «быть».
*** «Там», «эти», «те», «когда», «затем», «больше», «после» и «очень».
Строго придерживаясь избранного им принципа, Райт отказался от использования числительных между 6 и 30 даже в цифровом написании, так как буква «е» используется при их написании прописью. Райт жаловался: «Почти непреодолимая трудность возникла при введении в повествование молодых женщин: ведь про них не напишешь, что им за тридцать». Были изъяты также сокращения «Mr.»* и «Mrs.»** из-за присутствия «е» в полном написании этих слов. Сложную задачу приходилось решать в конце почти каждого длинного абзаца: будучи не в состоянии найти слово, не содержащее «е», которым можно было бы закончить мысль, автор возвращался назад и переписывал весь абзац.
* «Г-н».
** «Г-жа».
Райт так часто испытывал искушение использовать запрещенное слово, что ему пришлось заклинить рычаг буквы «е» на пишущей машинке, чтобы исключить ее попадание в текст. В предисловии к своей книге автор сообщает: «Часто буква «е» пыталась-таки проскользнуть незамеченной. Когда я писал, первоначально от руки, вокруг моего стола столпилась целая армия крохотных «е», нетерпеливо ожидавших, когда их позовут. Но постепенно, наблюдая, как я пишу, не замечая их, они забеспокоились и, возбужденно перешептываясь, стали вскакивать верхом на мое перо, постоянно посматривая вниз в надежде улучить момент и прыгнуть в какое-нибудь слово. Они вели себя, как морские птицы, удобно рассевшиеся для охоты за проплывающей рыбой. Но когда они увидели, что я уже отмахал 138 страниц на бумаге машинописного формата, они соскользнули на пол и, взявшись за руки, удалились с поникшими головами, а потом, обернувшись, прокричали: «Представляем, какую тарабарщину ты там нацарапал без нас.
Вот уж, право, человек! В любом рассказе нас всегда пишут сотни тысяч раз! А сейчас нас гонят прочь! Впервые за всю нашу жизнь!»
Райт говорил, что для написания романа ему потребовалось «пять с половиной месяцев упорного труда, причем в тексте пришлось сделать столько подчисток и поправок, что при воспоминании о них меня до сих пор бросает в дрожь». Эти эмоции Райта наглядно свидетельствуют о всепроникающей распространенности одной только буквы английского языка. Остальные буквы тоже держатся цепко.
Не только Райт, но и другие авторы написали, в качестве литературных курьезов, липограммы, то есть сочинения, из которых намеренно исключается одна или несколько букв. Древнегреческий писатель Трифиодор сочинил «Одиссею», в первой книге которой не встречалась буква «?», во второй «?» и т. д.
Несмотря на постоянство частот встречаемости букв и на большое различие частот отдельных букв во всех языках, они не настолько заметны, чтобы об их существовании знали все. Одним из людей, которые, очевидно, и не подозревали об этом, был Латам Шоулс, изобретатель пишущей машинки, увековечивший ее ужасную клавиатуру.
Такая клавиатура с неудобным размещением букв впервые появилась в опытном образце, изготовленном в 1872 г. Остатки алфавитного порядка сохранились в расположении букв «d», «f», «g», «h», «j», «k», «1» во втором ряду, а в верхний ряд были включены буквы слова «typewriter»*, чтобы торговцы могли их легко найти при демонстрации работы.
* «Пишмашинка».
Клавиатура с неудачным подбором букв первого ряда «q», «w», «е», «г», «t», «у», «u», «i», «о», «р» оборачивается для предпринимателей потерями времени и денег. Несмотря на то, что основная рабочая нагрузка у большинства людей приходится на правую руку, при такой клавиатуре левая рука делает более половины всех ударов. Получается, что для печатания слов вроде «federated»* и «addressed»** левая рука лихорадочно мечется по клавишам, а правая тем временем пребывает в абсолютном покое. Кроме того, получается, что два самых «работящих» пальца правой руки приходятся на клавиши с наиболее редкими буквами английского алфавита — «j» и «k».
* «Объединенный в федерацию».
** «Адресованный».
Ввиду этих вопиющих недостатков было разработано множество других, более удачных клавиатур. Однако все нововведения были отвергнуты машинистками, не захотевшими переучиваться для работы на новой клавиатуре, и фирмами, не желающими платить за переделку печатающих машинок, имеющих стандартную клавиатуру Шоулса.
В тех случаях, когда изобретатели и предприниматели учитывают явления, связанные с частотами встречаемости букв, они могут получить значительную дополнительную прибыль. Наиболее ярким примером является Ф. Морзе. В 1838 г. он решил использовать алфавитную систему сигналов для своего только что изобретенного электромагнитного телеграфа. Морзе сосчитал буквы в наборной кассе типографии одной филадельфийской газеты и присвоил наиболее короткие сочетания из точек и тире самым частым буквам.
За небольшими исключениями Морзе придерживался этого правила и при создании своего знаменитого кода, поставив в соответствие самый короткий знак (точку) самой распространенной букве («е»), другой короткий знак (тире) — следующей часто встречающейся букве («t») и т. д. При использовании современного кода Морзе, слегка отличающегося от его первоначального варианта, на передачу телеграммы из 100 букв на английском языке требуется около 940 знаков. Если бы код Морзе был составлен произвольным образом, то на такую же телеграмму потребовалось бы около 1160 знаков, или примерно на 23% больше. Благодаря проницательности изобретателя, принесшей, кстати, значительные денежные выгоды его потомкам, стало возможно передавать за один сеанс почти на 25% больше телеграмм, чем в случае, если бы Морзе составлял свой код наугад.
Из этих примеров видно, что частоты букв действительно довольно постоянны. Неоднократно проведенные опыты по их подсчету подтверждают этот факт. Например, восемь немецких криптоаналитиков независимо друг от друга подсчитали частоту буквы «е» в различных текстах на родном языке объемом примерно в тысячу букв.
Полученные ими результаты колеблются от 16 до 19,2%. Эти цифры можно сравнить с подсчетом частот встречаемости букв, проведенным в лингвистических целях немецким филологом Ф. Кёдингом в 1898 г. Его подсчет можно принять за эталон: Кёдинг обработал 59298274 буквы, извлеченные из 20 миллионов слогов немецкого языка. Среди них он насчитал 10598015 букв «е», или 17,9%. Интересно, что средняя цифра от восьми результатов аналогичных подсчетов на текстах меньшего объема составляет 18%, то есть отклонение от нормы, полученной Кёдингом, составляет лишь одно «е» на тысячу букв. Получается, что любой человеческий язык укладывается в строгие статистические нормы!
В чем причина этого поразительного явления? Ответ можно найти с помощью разработанной после Второй мировой войны теории, которая называется «теория информации». Предметом ее изучения являются математические законы, которым подчиняются системы передачи данных. Созданная для решения проблем телефонии и телеграфии, она оказалась применима практически ко всем устройствам, передающим информацию, включая компьютеры и нервную систему животных. Ее идеи оказались настолько плодотворными, что были взяты на вооружение другими науками — психологией, лингвистикой, молекулярной генетикой, историей, статистикой и нейрофизиологией. Создатель этой теории стал также родоначальником ее применения в криптографии.
Клод Шеннон родился в городе Петоски в штате Мичиган 30 апреля 1916 г. Поступив в Мичиганский университет, Шеннон занялся серьезным изучением электротехники и математики. Именно там у него впервые проявился интерес к теории связи и криптографии.
В Массачусетском технологическом институте Шеннон написал диссертацию, в которой содержалось множество новаторских идей, связанных с разработкой телефонных систем. Получив степень доктора математических наук, Шеннон поступил на службу в лабораторию компании «Белл», которая была заинтересована в реализаций этих идей на практике.
«Во время Второй мировой войны, — рассказывал Шеннон, — компания «Белл» работала над засекречиванием информации.
Я тогда занимался системами связи и был назначен в несколько комиссий, изучавших криптоаналитические методы. Начиная примерно с 1941 г., исследования в области математической теории связи и теории шифров велись мной одновременно. Я трудился в обеих областях сразу, и кое-какие идеи в одной из них возникали у меня, когда я работал в другой. Я не хочу сказать, что одна из этих областей доминирует над другой. Просто они настолько тесно связаны, что их невозможно разделить». Хотя разработка обеих теорий была в основном завершена примерно к 1944 г., Шеннон продолжал уточнять полученные результаты до 1948-1949 гг., когда они были опубликованы в виде двух отдельных статей в солидном теоретическом журнале «Белл систем текникал джорнэл».
В обеих статьях Шеннона — «Математическая теория связи» и «Теория связи в секретных системах» — идеи излагаются в краткой, математической форме. Обе они изобилуют выражениями вроде «должно существовать единственное обратное преобразование» и формулами вида «TjRj(TkRl)-1TmRn». Тем не менее точный и выразительный стиль изложения Шеннона вдохнул в них жизнь. В результате его первая статья породила теорию информации, а вторая — теорию шифров.
Главной в работах Шеннона является концепция избыточной информации. В его интерпретации слово «избыточность» сохраняет свое основное значение ненужного избытка, но оно уточняется и расширяется. Избыточность, по Шеннону, означает, что в сообщении содержится больше символов, чем в действительности требуется для передачи информации. В простом примере, который привел сам Шеннон, входящая в сочетание «qu» буква «u» — лишняя, поскольку в английских словах «u» всегда стоит после «q». По его мнению, также не обязателен и определенный артикль, употребляемый перед существительными во множественном числе. Ведь, посылая телеграммы, англичане прекрасно обходятся без него.
Насколько велика избыточность английского языка, наглядно демонстрируют некоторые из военных сообщений, которые спрессовываются в «черную магию» сокращенных слов и выражений вроде: «off pres on AD for an indef per».
Человек посвященный без особых затруднений прочтет: «officer present on active duty for an indefinite period»*. Эта избыточность связана с излишком правил, обременяющих все языки.
*«Офицер, находящийся на действительной службе без ограничения срока».
Одни правила, приводящие к избыточности, можно найти в грамматике («I am», а не «I is»), другие — в фонетике (ни одно из английских слов не может начинаться на «ng»), третьи — в идиомах (после глагола «believe» не может стоять глагол в инфинитиве). Четвертые основаны на различного рода ограничениях, налагаемых на словарь. Пользуясь языком, гораздо более избыточным и ограниченным, чем речь взрослых, подросток говорит «swell»* для выражения одобрительного отношения, передать которое старший по возрасту может с помощью доброго десятка других слов. Как писал Шеннон: «Две крайности избыточности в английском языке представлены словарным запасом «бэйсик инглиш»** и книгой Джеймса Джойса*** «Поминки по Финнегану». Словарь первого ограничен 850 словами, его избыточность очень велика. Это отражается в расширении, происходящем при переводе какого-нибудь отрывка из «Поминок по Финнегану» на «бэйсик инглиш». Со своей стороны, Джойс увеличивает словарь и этим самым, как утверждают, достигает сжатости семантического содержания».
* «Замечательный, превосходный».
** Упрошенный английский язык.
*** Джойс Джеймс — английский писатель-модернист, ирландец.
Еще два источника избыточности имеют особое значение, учитывая их влияние на таблицу частот встречаемости букв. Один из них берет свое начало от различных связей, к которым так часто обращаются люди и которые, естественно, отражаются в языке. Это связи одного лица или предмета с другим («the son of John»* или «the book on the table»**) и какого-то предмета с действием («put it down»***). Английский язык выражает такие связи отдельными словарными единицами, называемыми «словами-функциями». Местоимения, предлоги, артикли и союзы — все это слова-функции.
Некоторые из них служат для задания чисто грамматических связей, являясь своего рода лингвистической стенографией: говорят «я» вместо того, чтобы все время повторять свое имя. Слова-функции самостоятельного значения не имеют. Но они входят в число наиболее распространенных слов английского языка, так как передаваемые ими связи встречаются чаще других. Всего лишь десяток английских слов («the», «of», «and», «to», «a», «in», «that», «it», «is» и «I») занимает более '/4 любого текста. Преобладание этих слов неизбежно влияет на таблицу частот встречаемости. Например, своим появлением в ней буква «h» в большинстве случаев бывает обязана только определенному артиклю «the».
* «Сын Джона».
** «Книга на столе».
*** «Положи это».
Второй источник языковой избыточности проистекает из человеческой лености, которая заставляет людей выбирать легко выговариваемые и узнаваемые звуки. На произнесение глухих согласных «р», «t», «k» тратится меньше энергии, чем на соответствующие звонкие согласные «b», «d», «g». Поэтому частота первых в среднем вдвое превосходит частоту вторых в 16 различных языках. Равным образом и краткие гласные звуки используются заметно чаще, чем долгие гласные или дифтонги*.
* Дифтонги — гласные, состоящие из двух элементов, произносимых в пределах одного слога.
Всякий, кто желает овладеть каким-то языком, предварительно должен узнать лингвистические правила, которые, собственно, и порождают присущую вожделенному языку избыточность. Знание этих правил позволяет находить и исправлять ошибки, появляющиеся при передаче сообщений. Если, например, в телеграмме на английском языке будет пропущена одна точка и буква «i» («..») в слове «individual»* превратится в «е» («.»), получатель телеграммы сообразит, что сделана ошибка, так как в английском языке слова «endividual» нет. Когда в языке нет избыточности, как в случае с телефонными номерами, где одна неправильно набранная цифра приводит к вызову другого абонента, люди сами привносят ее.
Они повторяют номер, сообщая его кому-либо, а при передаче фамилий они обычно говорят: «б — Борис, о — Ольга...» Объясняется это просто: чем больше избыточность, тем легче обнаружить ошибки. Если в деловом письме получатель встретится с последовательностью «rhe company», он выделит «rhe» как несуществующее слово, вспомнит, что правила английского языка позволяют поставить перед словом «company»** определенный артикль, учтет, что на клавиатуре пишущей машинки «г» соседствует с «t», и придет к выводу, что вместо «rhe» должно стоять «the».
* «Индивидуальный».
** «Компания».
Этот процесс корректорской правки сродни криптоанализу, ибо при вскрытии шифров криптоаналитики также используют свое знание правил фонетики, грамматики, идиом, слов-функций и фонетических склонностей, которые в совокупности и придают языку избыточность. Способы, применяемые людьми в обыденной жизни для обнаружения опечаток, криптоаналитики употребляют для отыскания деформаций открытого текста. Разумеется, криптограмма несравненно более сложна и запутанна, но в ней заложена скрытая закономерность, какой нет в изолированной, случайной описке. Именно такое построение криптограммы помогает во многих ее «исправлениях», составляющих сущность криптоанализа, и подтверждает их правильность.
С чего начинается криптоанализ? При исправлении ошибки все избыточные элементы, используемые для правки, лежат в готовом виде на поверхности. В криптограмме все наоборот — они незаметны. Криптоаналитик начинает с того, что дробит эти элементы до тех пор, пока не получит их простейшей формы — буквенной. Затем он сравнивает буквы с избыточными элементами языка, приведенными к общему знаменателю. Иными словами, криптоаналитик производит подсчет частот букв криптограммы и соотносит полученные результаты с известными частотами букв предполагаемого языка, на котором записан открытый текст. Методику подсчета иногда приходится менять в зависимости от построения шифра. Для многоалфавитного шифра подсчет необходимо сделать для каждого алфавита, а если перехвачено кодированное сообщение, то простейшей формой избыточных элементов являются слова, и считать надо их.
Откуда у криптоаналитика уверенность в том, что частоты букв открытого текста данной криптограммы примерно совпадают с частотами эталонного открытого текста? Разве не может это соответствие нарушиться из-за различий в словарном запасе корреспондентов и в темах их переписки? Нет, не может, ибо избыточные элементы языка превалируют над остальными: 75-процентная избыточность английского языка подавляет влияние его «свободной» части, хотя не настолько, чтобы она не могла воспрепятствовать точному совпадению частот встречаемости букв в различных текстах.
Именно избыточные элементы в совокупности обеспечивают стабильность таблицы частот встречаемости для любого текста. Действительно, из-за постоянного употребления артикля «the» нередко случается, что буква «h» оказывается среди часто встречающихся букв английского языка. Склонность англичан к использованию альвеолярных согласных приводит к тому, что буквы «n», «t», «г», «s», «d», «1» имеют высокую или среднюю частоту встречаемости. А поскольку в Англии не жалуют буквы «р» и «k», они незаслуженно попали в разряд редко встречающихся. Однако такие избыточные элементы постоянны, заранее известны и поэтому дают стабильные данные для таблиц частот встречаемости. В немецком языке доминирующее влияние избыточности наглядно проявилось в весьма близких пропорциях буквы «е» при подсчетах частот встречаемости букв, произведенных Кёдингом и К°. И конечно же оно проявляется в повседневных успехах криптоаналитиков.
Сила ума Шеннона, его огромный вклад в теорию шифровального дела выразились в открытии избыточности как основы криптоанализа: «Вскрытие большинства шифров становится возможным только благодаря существованию избыточности в открытых текстах». Шеннон первым сумел объяснить постоянство частот встречаемости букв, а тем самым и такое зависящее от него явление, как криптоанализ, дав возможность глубоко понять процесс аналитического вскрытия шифров.
Понимание этого процесса позволяет сделать ряд выводов. Получается, что чем меньше избыточность, тем труднее аналитическим путем прочесть криптограмму.
Это видно из двух примеров, иллюстрирующих две крайности в избыточности и приведенных самим Шенноном. Книга «Поминки по Финнегану» заканчивается словами:
«End here. Us then, Finn, again! Take. Bussoftlee, mememor mee! Till thousends thee. Lps. The keys to. Given! A way a lone a last a loved a long the».
Криптоаналитику прочтение такого открытого текста доставит значительно больше хлопот, чем получение отрывка из Нового Завета на «бэйсик инглиш»:
«And the disciples were full of wonder at his words. But Jesus said to them again: Children, how hard it is for those who put faith in wealth to come into the kingdom of God!»*
* «И изумились ученики словам Его. Но Иисус сказал им: Как трудно, дети мои, войти в царство Божье верующим в богатство!»
Криптограммы, помещаемые для занимательности в журналах для широкой публики, достигают поставленной цели — в максимальной степени затруднить их отгадывание — за счет того, что для них подбирают архаические и редкие слова, соединяемые в почти бессмысленные тексты. Избыточность в таких криптограммах сравнительно низкая. Вот образец открытого текста одной такой криптограммы: «Tough cryptos contain traps snaring unwary solvers abnormal frequencies, consonantal combinations unthinkable, terminals freakish, quaint twisters like «myrrth»*.
* «В стойких криптограммах есть ловушки, в которые попадаются неосторожные люди, пытающиеся раскрыть их ненормальные частоты, немыслимые сочетания согласных, странные окончания, необычные головоломки вроде «мирра».
Но даже в этом случае избыточные элементы берут верх. Хотя от некоторых из них отделываются, другие все-таки остаются. Они-то и дают искомое решение задачи. Правда, никогда не проверялся интересный вопрос о том, создают ли отмечаемые среди естественных языков различия в избыточности дополнительные трудности при вскрытии криптограмм аналитическими способами.
Проблема низкой избыточности особенно актуальна, когда криптоаналитик работает над вскрытием кода с перешифровкой.
Для того чтобы снять перешифровку и выделить кодированный текст, требуется прочесть криптограмму, открытый текст которой состоит из кодовых обозначений и может выглядеть как бессмысленный набор букв «I X К D Y W U K J T P L K J E...». Здесь избыточность очень низка из-за более равномерного использования букв, большей свободы их сочетания, нивелировки частот путем употребления омофонов и т. д. Но при неизбежном наличии в переписке повторяющихся фраз давление избыточности языка, внутренне присущей коду, а также необходимость подбора структуры кодовых обозначений с учетом возможности их исправления в случае искажения при передаче — все это превращает скрытый кодированный текст в достаточно прочный материал, из которого криптоаналитик делает опору для всего здания успешного вскрытия кода с перешифровкой.
Из сказанного выше следует, что сокращение избыточности значительно затрудняет криптоанализ. Перед зашифрованием Шеннон рекомендует обязательно проделывать над открытым текстом операцию, «которая убирает все излишества... То обстоятельство, что из текста можно без особого вреда убрать гласные буквы, дает простейший способ существенного усовершенствования почти любой шифрсистемы. Сначала уберите все гласные буквы или ту максимально большую часть сообщения, без которой не будет риска разночтения при восстановлении его слов, а затем зашифровывайте то, что осталось». Криптоаналитики, пытавшиеся прочесть шифртелеграммы, из открытых текстов которых изымалась одна только буква «е», подтвердили, что трудность решения задачи вскрытия после этого заметно возрастала. Понижение избыточности действует весьма эффективно, так как оно притупляет одно из главных орудий криптоаналитика. К этому приему прибегали еще итальянские составители шифров эпохи Возрождения, приказывавшие шифровальщикам опускать вторую букву в удвоениях, например «1» в слове «sigillo»*. Прием этот основан на знании криптографами своего языка, которое позволяет им без всякого ущерба убирать из него элементы избыточности.
* «Тайна».
Низкую избыточность могут иметь и сокращения: для их прочтения иногда требуется настолько большое приращение информации (например, как в случае с сокращением «bn» для слова «battalion»*), что они не только затрудняют получение открытого текста при аналитическом вскрытии шифра, но и сами пригодны для использования в быту в качестве простейшего средства шифрования. Например, две болтающие кумушки могут упомянуть в разговоре между собой о третьей, назвав лишь ее инициалы, чтобы никто из лиц, находящихся рядом, не понял, о ком, собственно, идет речь.
* «Батальон».
Следующий вывод состоит в том, что для прочтения криптограммы, открытый текст которой обладает низкой избыточностью, требуется, чтобы она была более длинной, чем в случае криптограммы с высокой избыточностью. Шеннону удалось определить количество шифртекста, необходимого для получения единственного правильного решения задачи вскрытия шифра при условии, что соответствующий открытый текст имеет известную степень избыточности. Необходимое для этого количество букв он назвал «расстоянием единственности» и описал, как вычислить его с помощью довольно сложной формулы. Эта формула, естественно, видоизменяется для различных шифров, но непременным ее членом всегда остается избыточность.
В одной из своих ранних работ, в которой Шеннон исходил из 50-процентной избыточности английского языка, он установил, что расстояние единственности для шифра однобуквенной замены составляет 27 букв, для многоалфавитных шифров с известными алфавитами — двойную длину периода, а с неизвестными алфавитами — 53 длины периода. Наиболее интересное применение шенноновской формулы расчета расстояния единственности связано с определением правильности решения задачи аналитического вскрытия шифра. Шеннон писал: «Вообще можно утверждать, что если ключ и предложенный метод позволяют прочитать криптограмму при наличии шифртекста, длина которого значительно превосходит расстояние единственности, то решение надежно.
Если же длина шифртекста имеет тот же порядок, что и расстояние единственности, или короче его, значит, решение весьма сомнительно».
Вскоре появилась возможность проверить это утверждение Шеннона на практике. Иб Мельхиор, сын известной оперной звезды Лорис Мельхиор, решил, что дешифрование эпитафии, найденной им на надгробии Шекспира, может помочь найти первое издание «Гамлета». Мельхиор преобразовал эпитафию в цифровой шифртекст, прочитал его и отредактировал полученный в результате открытый текст, убрав служебные символы и модернизировав написание слов, принятое в эпоху английской королевы Елизаветы. В конечном итоге Мельхиор стал обладателем загадочной фразы: «Elsinore laid wedge first Hamlet edition». Эти слова, по мнению Мельхиора, означали, что первое издание «Гамлета» было замуровано в клинообразной нише в толще стен замка Эльсинор. О своей находке Мельхиор сообщил в интервью журналу «Лайф».
Один из читателей журнала в своем письме в редакцию обратил внимание Мельхиора на то, что даже при заведомо заниженной 50-процентной оценке избыточности английского языка основная часть этой зашифрованной надписи совершенно не укладывается в найденную Шенноном формулу расстояния единственности. Несмотря на это математическое предсказание неудачи, Мельхиор все-таки отправился в Эльсинор в составе поисковой экспедиции, снаряженной «Лайфом». Вскоре ее участники возвратились из Эльсинора с отличным фоторепортажем для журнала, но без первого издания «Гамлета».
Таким образом, шенноновская концепция избыточности вновь и вновь демонстрирует свою силу, объясняя многие явления криптоанализа, каждое из которых прежде приходилось толковать в отдельности. Почему занимательные криптограммы из газет и журналов труднее поддаются дешифрованию, чем обычные шифртелеграммы? Раньше криптоаналитики могли лишь сказать, что это происходит потому, что для «газетно-журнальных» криптограмм подбираются более редкие и необычные слова. Теперь они могут опереться на принцип избыточности Шеннона и указать, что такие криптограммы обладают более низкой избыточностью.
Почему криптоаналитиков так часто выручают стандартные выражения вроде: «В ответ на вашу телеграмму от...»? Да потому, что они повышают избыточность до весьма значительных величин. Чтобы ее понизить, можно разделить текст пополам и переместить его первую половину в конец, а вторую — в начало. При этом стандартное начало телеграммы оказывается упрятанным в середину, что значительно затрудняет криптоанализ.
Шеннон также рассмотрел криптоанализ с двух других точек зрения, которые существенно расширили горизонты возможного в этой области. Первая из них является следствием преломления криптоанализа через призму теории связи.
Шеннон писал: «С криптографической точки зрения секретная система почти тождественна системе связи при наличии шума». В теории связи термин «шум» имеет особое значение. Под шумом подразумевается любая помеха, создающая ошибки при передаче по каналу связи. В качестве примеров шума можно указать плохое соединение по телефону и иностранный акцент собеседника. Шеннон исходит из того, что шум схож с шифрованием. Он утверждает: «Основное различие между ними заключается, во-первых, в том, что преобразование при помощи шифра имеет обычно более сложный характер, чем возникающее за счет шума в канале; во-вторых, в том, что ключ в секретной системе выбирается из конечного множества, тогда как шум обычно вносится в канал постоянно и выбирается из бесконечного множества».
Когда автора статистической теории детектирования сигнала Карла Хелстрома спросили, имеет ли техника отделения полезных сигналов от помех какое-либо сходство с криптоанализом, он ответил: «Я полагаю, что аналогия между правилом шифрования по ключу и беспорядочной помехой вряд ли полезна. Со значительно большим основанием можно рассматривать зашифрование как «фильтрацию» открытого текста для получения его в преобразованном виде. Здесь «фильтр» представляет собой определенное правило преобразования, но оно неизвестно криптоаналитику. Поэтому его задача состоит в отыскании характера «фильтра», когда известны статистические данные текста, вводимого в «фильтр», и текста уже «профильтрованного».
Это вроде нахождения структуры электрического фильтра путем пропускания через него произвольной помехи и замера статистических распределений на входе и напряжений на выходе».
Другая точка зрения, с которой Шеннон рассмотрел криптоанализ, касается соревнования между криптографом и криптоаналитиком. Он первым предложил отождествить это соревнование с конфликтом — понятием из математической теории игр. Шеннон отмечает: «Действия составителя шифра и криптоаналитика можно представить как игру с очень простой структурой ходов... Ход криптографа состоит в выборе им шифра. Криптоаналитик, осведомленный об этом выборе, разрабатывает метод вскрытия. «Ценой» в игре является средний объем работы, требуемый для прочтения криптограммы, засекреченной выбранным шифром, при помощи разработанного метода».
Как и в любой игре, взаимодействие криптографа и криптоаналитика всегда связано со временем, ибо любые практические дела человека в конце концов неотделимы от этого неотвратимого, необратимого и невозместимого фактора.
У криптографа отношение к фактору времени сложное. Один из самых общих принципов его работы основан на соблюдении баланса между скоростью и секретностью. Когда необходимость в ускоренной связи возрастает, соответственно уменьшается потребность в секретности. На ранних стадиях разработки крупной военной операции нужна повышенная секретность связи, так как, если противник сможет прочитать шифрпереписку, он успеет выработать эффективные контрмеры. В разгар же самого сражения командиры могут обмениваться и открытыми сообщениями, поскольку, даже если противник их перехватит, времени для осуществления полноценных ответных действий у него все равно не будет.
В отличие от криптографа, криптоаналитик постоянно испытывает гнет времени и стремится как можно быстрее довести до конца свои разработки. Вероятно, справедлива истина, что содержание любой шифртелеграммы будет представлять какую-то ценность всегда (хотя бы для историков). Но это слабое утешение для командующего, который мог бы заранее узнать из нее о сроках наступления противника, но так и не узнал, поскольку криптоаналитики не прочли ее вовремя.
В числе факторов, определяющих время, необходимое для дешифрования, помимо таких внешних факторов, как скорость доставки криптографу перехваченных шифрсообщений, следует назвать стойкость шифра, разумность правил его использования, точность их соблюдения шифровальщиками, объем перехвата, а также количество и качество вспомогательной информации.
Если говорить о профессиональном уровне криптоаналитика, то встает вопрос: является криптоанализ наукой или искусством? С одной стороны, как было продемонстрировано выше, криптоанализ — это стройная наука. А с другой — успехи во вскрытии шифров явно зависят от личных способностей. Одни криптоаналитики работают лучше других. В этом смысле криптоанализ — искусство. Как сказал Ярдли, выдающиеся криптоаналитики наделены «шифрмозгом», то есть особыми способностями, однако при рассмотрении вопроса о том, кто и почему обладает «шифрмозгом», приходится сталкиваться с загадками.
Никому не ведомы побудительные мотивы к занятию криптоанализом. Фрейд* считает, что ребенок стремится к учебе, к приобретению знаний, поскольку прежде всего желает увидеть скрытые от него половые органы взрослых и детей. Тогда криптоанализ можно рассматривать как одно из проявлений вуайеризма**.
* Фрейд Зигмунд — австрийский врач, разработавший психоанализ — метод исследования подсознательных процессов человека.
** Вуайеризм — половое извращение, характеризующееся тем, что источником сексуального наслаждения является тайное подглядывание за действиями, совершаемыми другими лицами.
Эта гипотеза получила поддержку у некоторых известных специалистов. Например, Теодор Райк, авторитетный психоаналитик, так ответил на вопрос о взаимосвязи криптоанализа и вуайеризма: «Я склонен считать, что в основе стремления вскрыть шифр аналитическим путем заложено продолжение детского желания узнать, в чем заключается секрет сексуальности, который родители или взрослые скрывают от мальчика». Высказывание Райка созвучно с точкой зрения Фрейда, который считает, что ученые и вообще все специалисты, труд которых связан с математическим или умозрительным видением мира, руководствуются в своей работе именно такими побудительными мотивами.
Знаменитый психолог Эрих Фромм особо подчеркивал, что вуайеристическое толкование склонности к криптоанализу «иногда оказывается правильным, но ни в коем случае не настолько универсальным, как думают фрейдисты».
Попытался внести ясность в гипотезу о вуайеристическом происхождении криптоанализа и английский писатель Олдос Хаксли. В его книге «Опавшие листья» есть такие строки: «Любила ли она меня? Во всяком случае, она часто говорила и даже писала, что любит. У меня сохранились все ее письма — два десятка наспех набросанных записок, передававшихся с рассыльным из одного крыла отеля «Сесиль» в другое, и несколько писем, присланных ею, когда она уезжала от меня на праздники или одна проводила где-нибудь уик-энд. Эти листки передо мной. Почерк грамотного, интеллигентного человека. Перо, едва отрываясь от бумаги, торопится от буквы к букве, от слова к слову. Письмо быстрое, но аккуратное, четкое и понятное. Лишь кое-где, обычно в концовках ее записок, четкость почерка нарушается и появляются слова-каракули, составленные из бесформенных букв. Я склоняюсь над ними, пытаясь разобрать. «Я обожаю тебя, любимый мой... тысячу раз целую тебя... тоскую в ожидании вечера... люблю тебя безумно». В ее каракулях мне удается прочитать лишь эти слова. Мы пишем о таких вещах неразборчиво по той же причине, по какой мы прикрываем наготу наших тел. Стыд не позволяет нам ходить обнаженными, и, даже если мы сделаем над собой усилие, доверив мысли бумаге, мы не можем допустить, чтобы наши самые сокровенные думы, страстные желания и тайные воспоминания слишком легко читались и понимались. Записывая наиболее скабрезные детали своих любовных похождений, Пипс не довольствовался их зашифрованием; он прятался еще и за плохой французский. И, вспоминая о Пипсе, я думаю о том, что и сам я проделывал такие фокусы в моих письмах к Барбаре, которые я заканчивал фразами вроде: «Bellissima, ti voglio un bene enorme» или «Je t'embrasse en peu partout»*.
* Обе фразы содержат ошибки. Видимо, герои хотел сказать по-итальянски: «Красавица, люблю тебя безумно» и по-французски: «Целую тебя тысячу раз».
У вуайеристической гипотезы нашлись оппоненты. Психиатр-фрейдист Джепта Макфарлейн считает, что криптоанализ выражает только стремление к власти: «Криптоаналитик не интересуется содержанием шифртелеграмм. Для него имеет значение лишь аналитическое вскрытие шифра. Его обуревает не подленькое любопытство и не желание прочесть чужую шифрованную переписку, а гордость за победу над шифром. Криптоаналитик не подсматривает сквозь замочную скважину. Он сокрушает саму дверь».
Гипотеза Макфарлейна подкрепляется и высказываниями самих криптоаналитиков. Вернер Кюнзе из отделения «Z», объясняя недостаточное знание им конечных результатов своей работы, говорил, что не обращает особого внимания на содержание телеграмм и что у него пропадает всякий интерес к шифру, как только он этот шифр вскрывает. С Кюнзе солидарны и любители отгадывать занимательные криптограммы в газетах и журналах: ответ их совершенно не интересует, они просто хотят разгадать саму криптограмму.
Хотя факты скорее подтверждают гипотезу о стремлении криптоаналитика к власти, ни эта гипотеза, ни вуайеристическая не были научно проверены. Частичное объяснение этому дает третья гипотеза, согласно которой вуайеристические побуждения вызывают у человека общий интерес к криптоанализу, а стремление к власти обеспечивает ему успех при работе над вскрытием конкретных шифров.
Какое отношение указанные гипотезы имеют к людям, избравшим своей профессией разработку стойких шифров? Райк полагает, что в основе такого профессионального интереса, «возможно, лежит подозрительность и опасение, что посторонние могут подсмотреть за нами и узнать что-то не только о нашей половой жизни, но и о нашей враждебности, агрессивности и т. д., а также желание не допустить этого». В отличие от Райка, Фромм считает, что «интерес к дешифрованию и составлению секретных кодов в большой мере связан с отношением человека к окружающему миру, а конкретнее говоря, с чувством одиночества и с надеждой, что он отыщет родственную душу, с которой мог бы связаться...
Мир закрыт для него, и поэтому он вынужден дешифровывать то, что пишется не для него». Психолог Гарольд Гринвальд, интересовавшийся одно время криптологией, пишет: «Лечившиеся у меня пациенты, которые работали в данной области, имели побудительный мотив, отличный от вуайеризма. Преимущественно это были люди стремившиеся испытывать превосходство в силе, скрывая свои действия и мысли (путем их зашифрования) или разгадывая то, что другие хотят держать в секрете (занимаясь криптоанализом)».
Это объяснение проливает некоторый свет на исследуемый вопрос, но и оно ненамного убедительнее других гипотез. Однако, если психологические корни криптографии и криптоанализа не разгаданы, их биологические корни ясны. Эти корми уходят в глубь геологических эпох, к простейшим одноклеточным организмам, боровшимся за жизнь в теплых морях первобытной Земли.
Шифры — это защита. Для современного человека это то же, что панцирь для черепахи, чернильный мешок для осьминога, маскировка для хамелеона. А криптоанализ собирает информацию о внешнем мире наподобие уха летучей мыши, чувствительности амебы к химическим раздражителям, глаза орла. Защита нужна для самосохранения. Это закон жизни, одинаково непреложный и для государства, и для отдельного организма. В условиях соперничества знания существуют в двух формах — у меня и у моего врага. Все организмы пытаются первую форму довести до максимума, а вторую — до минимума. Криптография и криптоанализ являют собой примеры этих двух форм. Составители шифров стремятся сохранить в тайне запас знаний своей страны, а криптоаналитики — увеличить этот запас за счет окружающих.
Но знания сами по себе — это еще не сила. Для придания им веса их нужно соединить с физической силой. Оба направления криптологии, подобно службам снабжения и транспорта, помогают вооруженным силам, составляющим главный элемент мощи страны. Правительство использует эту мощь для достижения своих политических, социальных и военных целей. И криптология в целом — одно из средств их достижения.
Но даже если цели, достижению которых служит криптология, являются чисто оборонительными по отношению к другим государствам, между криптоанализом и вооруженными силами существует огромное различие морального порядка. Последние представляют собой честные, открытые средства устрашения агрессора. Криптоанализ же агрессивен сам по себе. И хотя эта агрессия часто носит превентивный характер, она все-таки остается агрессией, правонарушением. Криптоаналитики действуют исподтишка, подглядывают за чужими делами, норовят стащить то, что им не принадлежит.
В таком случае существует ли моральное оправдание для криптоанализа? Конечно же существует. Один и тот же поступок, в зависимости от обстоятельств, может быть моральным или аморальным. При самообороне убийство допустимо. Так и с криптоанализом. Во время войны он определенно выглядит как благо, особенно если сохраняет людям жизнь. Но и в мирное время криптоанализ может выступать в качестве формы самозащиты. Криптоаналитик способен предупредить о враждебных намерениях и предоставить правительству возможность сохранить своим гражданам жизнь и свободу. Если же государству никто не угрожает, то оно будет не право, если станет попирать достоинство другой страны, тайно подсматривая за ее перепиской.
Человечество доказало, что оно вполне способно познать высшую истину. Вся история развития человечества со времен варварства неопровержимо подтверждает это. Накопление мудрости и моральных ценностей, управляемое в наше время таким императивом, как реальная угроза полного уничтожения, может когда-нибудь привести человечество к тому, что оно перекует мечи на орала, а после этого откажется от услуг криптоаналитиков. И да будет таким венец их славных дел!
