Арабские криптоаналитики

В возрасте около сорока лет Мухаммад (Магомет) начал регулярно приходить в пещеру на горе Хира неподалеку от Мекки — уединенное место, самой природой предназначенное для молитв и размышлений. В момент глубоких раздумий, примерно в 610 году н. э., его посетил ангел Джебраил, провозгласивший Мухаммада пророком, посланником Аллаха. Это было первое из ряда откровений, которые продолжались до самой смерти Мухаммада двадцатью годами позже. На протяжении всей жизни пророка писцы записывали эти откровения, но только в виде отрывков; и на Абу Бакра (Абу Бекра), первого халифа ислама, была возложена задача собрать их в единый текст. Работа была продолжена Омаром, вторым халифом, и его дочерью Хафсой и завершена Османом, третьим халифом. Каждое из откровений стало одной из 114 сур Корана.

Правящий халиф был обязан продолжать дело Пророка, поддерживая его учение и распространяя его Слово. Между провозглашением Абу Бакра халифом в 632 году и до смерти четвертого халифа, Али, в 661 году, шло неудержимое распространение ислама, и в конце концов мусульманское государство охватило половину всего мира. В 750 году, после столетия укрепления господства, начало халифата (или династии) Аббасидов предвещало золотой век исламской цивилизации. В равной мере расцвели искусства и науки. От исламских мастеров дошли до нас великолепные картины, изысканные резные украшения и ткани исключительной отделки, а от исламских ученых мы унаследовали целый ряд арабских слов, которыми усеян язык современной науки: алгебра, щелочь, зенит и другие.

Процветание исламской культуры было в значительной степени обусловлено тем, что общество было богатым и мирным. В отличии от своих предшественников, халифы династии Аббасидов не так уж стремились завоевывать новые территории и покорять другие народы; вместо этого они приступили к созданию организованного и процветающего общества. Низкие налоги поощряли развитие коммерческой деятельности и вели к росту торговли и предпринимательства, а строгие законы сократили взяточничество и обеспечили защиту населения. Все это опиралось на эффективно действующую систему управления, чиновники же, в свою очередь, полагались на систему передачи сообщений, безопасность которой обеспечивалась за счет использования зашифровывания. Документально подтверждено, что, помимо информации государственной важности, чиновники зашифровывали также сведения о налогах, то есть уже в то время криптография широко применялась и ее использование было достаточно обыденным делом. Во многие руководства для чиновников, к примеру, в «Adab аl-Kuttab» («Руководство для секретарей») десятого века, вошли разделы, посвященные криптографии.

Чиновники обычно пользовались шифралфавитом, который представлял собой просто перестановку букв алфавита открытого текста, как было описано выше, но они также применяли и шифралфавиты, в которых содержались другие типы символов. Например, a в алфавите открытого текста может быть заменена на # в шифралфавите, b может быть заменена на + и так далее. Одноалфавитный шифр замены является обобщенным названием, которое присваивается любому шифру замены, шифралфавит которого состоит из любых букв или символов или из тех и других. Все шифры замены, которые нам уже встречались, входят в эту общую категорию.

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

Криптоанализ не смог бы появиться до тех пор, пока цивилизация не достигла бы достаточно высокого уровня в ряде дисциплин, включая математику, статистику и лингвистику. Мусульманская цивилизация являлась идеальной колыбелью для криптоанализа, поскольку ислам требовал соблюдения законов во всех областях человеческой деятельности, а для этого нужны знания, или ilm. Каждый мусульманин был обязан приобретать знания во всех его видах, и экономический расцвет халифата Аббасидов означал, что у ученых было время, деньги и материалы, необходимые для выполнения ими своих обязанностей. Они старались овладеть знаниями предшествующих цивилизаций, приобретая египетсткие, вавилонские, индийские, китайские, персидские, сирийские, армянские, еврейские и латинские тексты и переводя их на арабский язык. В 815 г. халиф Аль-Мамун основал в Багдаде Bait al-Hikmah (Дом мудрости) — библиотеку и центр переводов.

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

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

Важно, что религиозные ученые не остановились в своем исследовании на уровне слов. Они также проанализировали отдельные буквы; в частности, они выяснили, что некоторые буквы встречаются чаще других.

В арабском языке наиболее распространенными буквами являются a и l, отчасти из-за определенного артикля аl-, в то время как буква j занимает только десятое место по частоте появления. Это на первый взгляд безобидное наблюдение привело к первому значительному прорыву в криптоанализе.

Кто первым догадался, что изменение частоты появления букв может быть использовано в целях взлома шифров, неизвестно, но наиболее раннее из известных описаний этого метода датировано IX веком и принадлежит перу одного из крупнейших ученых Абу Юсуф Якуб ибн Исхак ибн ас-Сабах ибн Умран ибн Исмаил аль-Кинди. Известный как «философ арабского мира», аль-Кинди был автором 290 книг по медицине, астрономии, математике, лингвистике и музыке. Его самый знаменитый трактат, который был обнаружен заново лишь в 1987 году в оттоманском архиве Сулайманийа в Стамбуле, озаглавлен «Рукопись по дешифрованию криптографических сообщений», первая страница которой показана на рисунке 6. Хотя в нем содержится подробный анализ статистики, фонетики и синтаксиса арабского языка, революционная система криптоанализа аль-Кинди умещается в два коротких абзаца:

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

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

Объяснение аль-Кинди гораздо проще показать на примере английского алфавита. Прежде всего необходимо взять достаточно большой кусок обычного английского текста, может быть, несколько текстов, чтобы установить частоту появления каждой буквы алфавита. Наиболее часто встречающейся буквой в английском алфавите является буква e, затем идут буквы t, а и т. д. (см. таблицу 1). Затем возьмите интересующий вас зашифрованный текст и подсчитайте частоту появления каждой буквы в нем.

_{Рис. 6 Первая страница «Рукописи по дешифрованию криптографических сообщений аль-Кинди», в которой содержится самое первое из дошедших до нас описаний криптоанализа с помощью частотного анализа. Если, например, в зашифрованном тексте самой часто встречающейся буквой будет J, то, по всей видимости, она заменяет букву e. Если второй по частоте появления буквой в зашифрованном тексте будет P, то вполне вероятно, что она заменяет букву t, и так далее. Способ аль-Кинди, известный как частотный анализ, показывает, что нет никакой необходимости проверять каждый из биллионов возможных ключей. Вместо этого можно прочесть зашифрованное сообщение просто путем анализа частоты появления букв в зашифрованном тексте.}

Однако не следует безоговорочно применять принцип аль-Кинди для криптоанализа, поскольку в таблице 1 указаны только усредненные частоты появления букв, а они не будут в точности совпадать с частотами появления этих же букв в любом другом тексте. К примеру, краткое сообщение, в котором обсуждается влияние состояния атмосферы на передвижение полосатых четвероногих животных в Африке, «From Zanzibar to Zambia and Zaire, ozone zones make zebras run zany zigzags» не поддалось бы непосредственному применению частотного анализа. Вообще говоря, частота появления букв в коротком тексте значительно отклоняется от стандартной, и если в сообщении меньше ста букв, то его дешифрование окажется очень затруднительным. В то же время в более длинных текстах частота появления букв будет приближаться к стандартной, хотя это происходит и не всегда.

_{Таблица 1 Таблица относительной частоты появления букв на основе отрывков, взятых из газет и романов; общее количество знаков в отрывках составляло 100 362 буквы. Таблица была составлена X. Бекером и Ф. Пайпером и впервые опубликована в «Системах шифрования: защита связи»}

В 1969 году французский автор Жорж Перек написал 200-страничный роман «Исчезновение» («La Disparition»), в котором не было слов с буквой e. Вдвойне примечательно то, что английскому писателю-романисту и критику Гилберту Адэру удалось перевести «La Disparition» на английский язык, где по-прежнему, как и у Перека, буква e отсутствовала. Как ни удивительно, но перевод Адэра, под названием «А Void», является удобочитаемым (см. Приложение А). Если бы весь этот роман был зашифрован с помощью одноалфавитного шифра замены, то попытка дешифровать его оказалась бы безуспешной из-за полного отсутствия наиболее часто встречающейся буквы в английском алфавите.

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