Трактат о дешифровке криптографических сообщений



«Трактат о дешифровке криптографических сообщений» — книга, написанная Абу Юсуфом Аль-Кинди, известная как первое упоминание о частотном криптоанализе. До середины IX века самым распространённым в мире методом шифрования сообщений был моноалфавитный шифр (в котором каждой букве кодируемого текста ставится в соответствие однозначно какая-то шифрованная буква). Арабский философ и математик Аль-Кинди в своей работе описал эффективный метод расшифровки таких сообщений, тем самым подтолкнув развитие полиалфавитных шифров. В европейских странах полиалфавитные шифры начали применять лишь в XV веке.

История

В 750 году приход династии Аббасидов ознаменовал начало золотого века исламской цивилизации. Арабский халифат к тому времени простирался от Атлантического океана на западе до границ с Индией на востоке, занимая примерно половину известного мира. Халифы династии Аббасидов в меньшей степени, чем их предшественники, были заинтересованы в завоеваниях, и вместо этого сосредоточились на создании организованного и обеспеченного общества. Низкие налоги обеспечили подъём торговли и ремесленничества, в то время как строгие законы привели к снижению коррупции и защищали граждан. Всё это опиралось на эффективную систему управления, которая, в свою очередь, опирались на защищённость систем связи. Чиновники зашифровывали конфиденциальные государственные документы и документы налогового учёта, что свидетельствует о широком и регулярном применении криптографии. Во многих руководствах для чиновников, таких как «Руководство для секретарей» (араб. أدب الكتـاب‎), содержались разделы, посвящённые криптографии. Обычно использовался моноалфавитный шифр, выходной алфавит которого был простой перестановкой входного алфавита, но иногда использовали выходные алфавиты, содержащие другие символы.

Арабские учёные стремились получать знания предшествующих цивилизаций, добывая египетские, вавилонские, индийские, китайские, персидские, сирийские, ивритские, римские тексты и переводя их на арабский язык. В 815 году халиф аль-Мамун основал в Багдаде Дом Мудрости (араб. بيتالحكمة‎) — библиотеку и центр перевода рукописей. Основные духовные школы были основаны в Басре, Куфе и Багдаде, где теологи изучали откровения Мухаммеда, содержащиеся в Коране. Теологи были заинтересованы в установлении хронологии откровений, и они делали это путём подсчёта частотностей слов, содержащихся в каждом откровении. Считалось, что определённые слова появились в арабском языке сравнительно недавно, и, следовательно, если в откровении содержится большое количество этих новых слов, то оно появилось позже в хронологии. Теологи также изучали Хадисы, которые состоят из ежедневных высказываний Пророка. Они пытались доказать, что каждое высказывание действительно принадлежало Мухаммеду. Это делалось путём изучения этимологии слов и структуры предложений, чтобы установить соответствие конкретных текстов языковому стилю Пророка. Они также проанализировали отдельные буквы, и, в частности, обнаружили, что некоторые буквы встречаются чаще, чем другие. Буквы «ﺍ» (/aː/) и «ﻝ» (/l/) являются наиболее распространёнными в арабском языке, отчасти из-за определенного артикля «ﺍﻝ» (/aːl/), тогда как буква «ﺝ» (/ʤ/) встречается в десять раз реже. Это, казалось бы, незначительное замечание, привело к огромному прорыву в криптоанализе. Неизвестно, кто первый изобрёл частотный криптоанализ, но первое известное описание этого метода принадлежит Аль-Кинди.

Аль-Кинди родился в городе Куфа приблизительно в 801 году. Является потомком аристократического рода Kindah. Его отец был эмиром (губернатором) Басры. В Басре Аль-Кинди провёл своё детство и получил начальное образование, позже отправился в Багдад, чтобы продолжить обучение под патронажем халифа аль-Мамуна. После обучения халиф доверил ему руководство Домом Мудрости, где он начал работу над переводом греческих рукописей Аристотеля и других философов на арабский язык. Во время этой работы Аль-Кинди впервые сталкивается с необходимостью расшифровки текстов, так как некоторые из рукописей, которые ему приходилось переводить, были зашифрованы. При аль-Мутаваккиле (с 847 г.) Аль-Кинди подвергался гонениям из-за его религиозно-философских убеждений. Его библиотека была конфискована, сам он был избит. Многие его рукописи были утеряны, в том числе и Трактат о дешифровке криптографических сообщений. Однако до нас дошла копия рукописи, которая была случайно найдена в Библиотеке Сулеймание в Стамбуле. Эта копия содержит большое количество грубых синтаксических и тематических ошибок и, очевидно, написана писцом, который плохо разбирался в лингвистике и математической статистике.

Содержание

Во введении Аль-Кинди описывает свой трактат как краткое и чёткое пособие, которое поможет читателю быстро овладеть основными приёмами криптоанализа. Остальную часть книги можно условно разбить на пять частей:

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

    • Алгоритмы криптоанализа

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

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

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

    Если не удаётся расшифровать криптограмму с помощью простого частотного криптоанализа (например если сообщение слишком короткое), Аль-Кинди предлагает использовать характерные сочетания букв или, наоборот, несочетаемость определённых букв друг с другом. Например, наиболее распространённые биграммы (группы из двух букв) русского языка: ст, но, ен, то, на, ов, ни, ра, во, ко. Важна статистика сочетаемости гласных и согласных букв. Например перед буквами ь, ы, ъ и после э не могут стоять гласные, а после любой гласной буквы следует согласная с вероятностью 87 %. Так же подсказкой для криптоаналитика могут быть общепринятые вступительные слова, которые используются почти в каждом языке. Например в арабском часто употреблялось «Во имя Бога, милостивого и милосердного» (араб. بسم الله الرحمن الرحيم‎). При расшифровке стихотворений можно использовать рифмы и стопы.

    Арабские буквы: их порядок и повторяемость

    Аль-Кинди приводит таблицу с абсолютными частотностями букв арабского алфавита, вычисленными в выборке из семи листов текста.

    По каким-то причинам автор не указал частотности букв ﺵ‎ (/ʃ/), ﺽ‎ (/dˁ/, /ðˤ/) и ﺥ‎ (/x/), указав при этом их место в таблице, упорядоченной по убыванию частотностей.

    В арабском алфавите 28 букв. Из них 27 могут обозначать согласные звуки, 3 (ﺍ‎ (/aː/), ﻭ‎ (/uː/), ﻱ‎ (/iː/)) — долгие гласные звуки, букв, обозначающих короткие гласные, — нет (например в слове Мухаммед пишутся только четыре согласные буквы: محمد‎). Таким образом в арабском письме преобладают чисто согласные буквы. Однако этот факт не противоречит указанному в начале трактата утверждению о том что самая частая буква на письме любого языка, как правило, гласная, так как в арабском таковой является ﺍ‎ (/aː/).