Китаб аль-Муамма

Китаб аль-Муамма
Китаб аль-Муамма
Авторы Халиль ибн Ахмад аль-Фарахиди
Дата написания VIII век
Язык оригинала арабский
Страна
Содержание о криптографическом методе шифрования
Оригинал не сохранился

«Кита́б аль-Муамма́» (араб. كتاب المُعَمَّى‎ — «Книга тайного языка») — арабская книга, составленная в VIII веке Халилем ибн Ахмадом аль-Фарахиди на основе его собственного метода шифрования.

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

На основе открытого им метода дешифрования он написал книгу «Китаб аль-Муамма».

Предыстория

Однажды Халилю ибн Ахмаду потребовалось дешифровать криптограмму на греческом языке, которую переслал ему византийский император. Он объяснил свой метод расшифровки так:

Я сказал себе, что письмо должно начинаться со слов «Во имя Аллаха» или как-нибудь в этом роде. Итак, я составил на основе этого первые буквы, и всё оказалось правильным.

Другими словами, его решение было основано на известной (верно угаданной) части текста всего сообщения, которая началась: «Во имя Аллаха перед всем …» (англ. His solution was based on known (correctly guessed) plaintext at the message which began: “In the name of Allah before all things…”.).

Этот метод атаки был использован в Великой Отечественной войне[уточнить], чтобы взломать немецкие коммуникации.[1]

Строение книги

Метод шифрования, придуманный аль-Фарахиди, представляет собой звуковую часть уже известного языка (в оригинале — арабского). Словарь включает в себя некоторые составляющие исходного языка. Применяется правило отбора слов и букв, согласно которому вышеперечисленное не должно подчиняться правилам фонологических исследований, которое аль-Фарахиди получил ранее в своих трудах. Для этого он использовал свои знания о музыке.

Проведя различие между знаками и значениями, он был в состоянии создать язык знаков в одиночку. Эта дифференциация позволила предложить следующее: существуют регулярные звуки (музыкальные) и нерегулярные звуки (апериодические), то есть другими словами — гласные и согласные звуки. Согласные звуки затем были классифицированы в соответствии с их точки артикуляции: начиная с ларингальных звуков и заканчивая губными, гласные же остались в одной группе звуков. В дальнейшем такое разделение значительно облегчило процесс шифрования.[2]

Позже арабские криптографы прибегают к частотному анализу текста, предложенномуаль-Фарахиди, для расчета частоты слов в своих работах.[3]

Другие труды на основе предложенного метода

К сожалению, «Китаб аль-Муамма» не сохранилась, мы знаем о ней по упоминаниям в работах других учёных. Самый известный труд на основе метода дешифровки Халиля ибн Ахмада — это труд Абу Юсуф Якуб ибн Исхак ибн Сабба аль-Кинди, известного философа, математика и астронома, который называется «Трактат о дешифровке криптографических сообщений».

Первая страница рукописи «Трактат о дешифровке криптографических сообщений»

Метод, предложенный Халилем ибн Ахмадом, содержит много новшеств, в том числе использование перестановок и комбинаций различных слов (для того, чтобы перечислить все возможные арабские слова без использования гласных букв в них).[4]

Но вся революционная и доработанная система криптоанализа, предложенная аль-Кинди, вмещается в два коротких абзаца:

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

[5]

Помимо трактата Аль-Кинди есть не менее известная работа — это энциклопедия из 14-и томов «Шауба аль-Аша» («Светоч для незрячего в ремесле писаря»), которая была написана ученым Шихабом ад-Дин Абу-л-Аббас Ахмад ибн Али ал-Калкашанди в 1412 году. Все последующие работы по криптоанализу в арабских странах до X века были на основе одного из этих двух трактатов — «Трактат о дешифровке криптографических сообщений» или «Шауба аль-Аша», поскольку работа Халиля ибн Ахмада не сохранилась. Автор изложил все известные ему на то время криптосистемы. В работе предлагалось семь систем шифрования, которые повторяли неопубликованные идеи его предшественника Ибн ад-Дурайхима, который впервые использовал частотный анализ букв. Вот эти системы шифрования:

  • замена одной буквы на другую;
  • написание слова в обратном порядке;
  • написание в обратном порядке некоторые буквы слов;
  • замена букв на цифры согласно принятой замене арабских букв числами;
  • замена каждой буквы открытого текста на две арабские буквы, которые могут использоваться в роли чисел и сумма которых равна цифровой величине шифруемой буквы открытого текста;
  • замена каждой буквы на имя какого-либо человека;
  • использование словаря замены, описывающего положение Луны, названия стран (в определённом порядке), названия фруктов, деревьев и т. д.

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

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

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

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

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

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

[6]

Другими словами, Калкашанди начинает изложение с того, что криптоаналитик должен знать язык, на котором написана криптограмма. Далее составляется подробное описание его лингвистических характеристик (Калкашанди использует арабский язык, как «самый благородный и самый прекрасный из всех языков»). После этого приводятся перечень букв, которые никогда не могут стоять вместе в одном слове, и букв, которые редко появляются по соседству. Рассматриваются также буквенные комбинации, которые в словах встретить невозможно. Последним идет список букв в порядке «частоты их использования в арабском языке в свете результатов изучения священного Корана». Автор даже отмечает, что «в произведениях, не связанных с Кораном, частота использования может быть иной».[7]

Калкашанди привёл пример раскрытия шифра: дешифрованная криптограмма состоит из двух стихотворных строк, зашифрованных с помощью условных символов. В заключение Калкашанди отметил, что восемь букв не было использовано и что это именно те буквы, которые находятся в конце перечня, составленного по частоте появления. Он подчеркнул: «Однако это простая случайность: буква может быть поставлена не на то место, которое она должна занимать в вышеупомянутом перечне». Так Калкашанди привёл наглядный пример использования статистического анализа текста в шифровании сообщений. Метод успешно применяется в расшифровке сообщений, зашифрованных методом использования одного алфавита (моноалфавитный метод), по сей день, но он не является криптостойким[8].

Примечания

  1. ↑ Bengt Beckman, 2002.
  2. ↑ R.Rashed, 1994.
  3. ↑ R.Rashed, 1996, p. 378.
  4. ↑ Lyle D.Broemeling, 2011, p. 255–257.
  5. ↑ В.В.Гребенников, 2012.
  6. ↑ И.Ю.Крачковский, 1957.
  7. ↑ Kahn D., 1967.
  8. ↑ «Новые Грани», 2012.

Литература