Русская Википедия:Трактат о дешифровке криптографических сообщений
Шаблон:Произведение средневековой литературы «Трактат о дешифровке криптографических сообщений» — книга, написанная Абу Юсуфом Аль-Кинди, известная как первое упоминание о частотном криптоанализе. До середины IX века самым распространённым в мире методом шифрования сообщений был моноалфавитный шифр (в котором каждой букве кодируемого текста ставится в соответствие однозначно какая-то шифрованная буква). Арабский философ и математик Аль-Кинди в своей работе описал эффективный метод расшифровки таких сообщений, тем самым подтолкнув развитие полиалфавитных шифров[1]Шаблон:Sfn. В европейских странах полиалфавитные шифры начали применять лишь в XV веке.
История
В 750 году приход династии Аббасидов ознаменовал начало золотого века исламской цивилизации. Арабский халифат к тому времени простирался от Атлантического океана на западе до границ с Индией на востоке, занимая примерно половину известного мира. Халифы династии Аббасидов в меньшей степени, чем их предшественники, были заинтересованы в завоеваниях, и вместо этого сосредоточились на создании организованного и обеспеченного общества. Низкие налоги обеспечили подъём торговли и ремесленничества, в то время как строгие законы привели к снижению коррупции и защищали граждан. Всё это опиралось на эффективную систему управления, которая, в свою очередь, опирались на защищённость систем связи. Чиновники зашифровывали конфиденциальные государственные документы и документы налогового учёта[1], что свидетельствует о широком и регулярном применении криптографии. Во многих руководствах для чиновников, таких как «Руководство для секретарей» (Шаблон:Lang-ar), содержались разделы, посвящённые криптографии. Обычно использовался моноалфавитный шифр, выходной алфавит которого был простой перестановкой входного алфавита, но иногда использовали выходные алфавиты, содержащие другие символы.
Арабские учёные стремились получать знания предшествующих цивилизаций, добывая египетские, вавилонские, индийские, китайские, персидские, сирийские, ивритские, римские тексты и переводя их на арабский язык. В 815 году халиф аль-Мамун основал в Багдаде Дом Мудрости (Шаблон:Lang-ar) — библиотеку и центр перевода рукописей. Основные духовные школы были основаны в Басре, Куфе и Багдаде, где теологи изучали откровения Мухаммеда, содержащиеся в Коране[1]. Теологи были заинтересованы в установлении хронологии откровений, и они делали это путём подсчёта частотностей слов, содержащихся в каждом откровении. Считалось, что определённые слова появились в арабском языке сравнительно недавно, и, следовательно, если в откровении содержится большое количество этих новых слов, то оно появилось позже в хронологии. Теологи также изучали Хадисы, которые состоят из ежедневных высказываний Пророка. Они пытались доказать, что каждое высказывание действительно принадлежало Мухаммеду. Это делалось путём изучения этимологии слов и структуры предложений, чтобы установить соответствие конкретных текстов языковому стилю Пророка. Они также проанализировали отдельные буквы, и, в частности, обнаружили, что некоторые буквы встречаются чаще, чем другие. Буквы «ﺍ» (/aː/) и «ﻝ» (/l/) являются наиболее распространёнными в арабском языке, отчасти из-за определенного артикля «ﺍﻝ» (/aːl/), тогда как буква «ﺝ» (/ʤ/) встречается в десять раз реже. Это, казалось бы, незначительное замечание, привело к огромному прорыву в криптоанализе. Неизвестно, кто первый изобрёл частотный криптоанализ, но первое известное описание этого метода принадлежит Аль-Кинди.
Аль-Кинди родился в городе Куфа приблизительно в 801 году. Является потомком аристократического рода Kindah. Его отец был эмиром (губернатором) Басры. В Басре Аль-Кинди провёл своё детство и получил начальное образование, позже отправился в Багдад, чтобы продолжить обучение под патронажем халифа аль-Мамуна[2]. После обучения халиф доверил ему руководство Домом Мудрости, где он начал работу над переводом греческих рукописей Аристотеля и других философов на арабский языкШаблон:Sfn. Во время этой работы Аль-Кинди впервые сталкивается с необходимостью расшифровки текстов, так как некоторые из рукописей, которые ему приходилось переводить, были зашифрованыШаблон:Sfn. При аль-Мутаваккиле (с 847 г.) Аль-Кинди подвергался гонениям из-за его религиозно-философских убеждений[3]. Его библиотека была конфискована, сам он был избит. Многие его рукописи были утеряны, в том числе и Трактат о дешифровке криптографических сообщенийШаблон:Sfn. Однако до нас дошла копия рукописи, которая была случайно найдена в Библиотеке Сулеймание в Стамбуле. Эта копия содержит большое количество грубых синтаксических и тематических ошибок и, очевидно, написана писцом, который плохо разбирался в лингвистике и математической статистикеШаблон:Sfn.
Содержание
Во введении Аль-Кинди описывает свой трактат как краткое и чёткое пособие, которое поможет читателю быстро овладеть основными приёмами криптоанализаШаблон:Sfn. Остальную часть книги можно условно разбить на пять частей:
- Алгоритмы криптоанализа — описание основных методов криптоанализа, в том числе частотного криптоанализа;
- Основные типы шифров — классификация моноалфавитных и некоторых полиалфавитных шифров;
- Алгоритмы криптоанализа некоторых типов шифров — алгоритмы взлома конкретных шифров;
- Арабские буквы: их порядок и повторяемость — статистические данные, которые можно использовать при расшифровке сообщений на арабском языке;
- Комбинации букв в арабском языке — более глубокое рассмотрение лингвистических особенностей арабского языка.
Алгоритмы криптоанализа
Аль-Кинди начинает содержательную часть своего трактата с некоторых соображений математической статистики. Он сравнивает алфавит с материалом из которого можно что-нибудь изготовить, придав ему нужную форму. Например, золото — материал, а сделанные из него чашки, браслеты и прочие украшения — разные формы этого материала. Поэтому все изделия сделанные из золота обладают схожими свойствами. Так же каждый язык обладает определёнными закономерностями, которые можно использовать при расшифровке сообщений. Например, в алфавитах многих языков (в том числе арабского) больше согласных букв, чем гласных. Однако если взять какой-либо текст и посчитать частотность появления каждой буквы в нём, то самыми частыми буквами окажутся гласныеШаблон:Sfn (в арабском языке самая частая буква ﺍ (/aː/), в английском, немецком, французском, испанском — e, в русском — о[4]). Метод частотного криптоанализа автор описывает следующим образомШаблон:Sfn:
|
Шаблон:Начало цитаты Одним из приёмов, используемых при расшифровке криптограмм, если известен язык исходного сообщения, является приобретение достаточно длинного текста на этом языке, и подсчёт количества появлений каждой буквы в нём. Назовём наиболее частую букву «первой», вторую по частотности «второй», следующую «третьей» и так далее, пока не переберём все буквы этого текста. Затем вернемся к криптограмме, которую мы хотим расшифровать, и так же классифицируем её символы: найдём в криптограмме символ встречающийся чаще всех и заменим его на «первую» букву из проанализированного текста, затем перейдём ко второму по частотности символу и заменим его на «вторую» букву, следующий символ на «третью», и так далее, пока не переберём все символы, используемые в криптограмме. Шаблон:Конец цитаты |
Метод, предложенный Аль-Кинди легче объяснить с точки зрения русского алфавита. Прежде всего, необходимо изучить достаточно длинный отрывок текста на русском языке, или несколько отрывков разных текстов, чтобы установить частотность появлений каждой буквы алфавита. В русском языке о — самая частая буква, после неё е, затем а и так далее, как указано в таблице. Потом изучим зашифрованный текст и установим частотность появлений каждого символа в нём. Например, если самый частый символ в зашифрованном тексте Ю, то, вероятнее всего, его следуют заменить на букву о. Если второй по частотности символ зашифрованного текста Э, то его, вероятно, следует заменить на е, и так далее. Благодаря методу Аль-Кинди, известному как частотный криптоанализ, не нужно проверять каждый из миллиардов потенциальных ключей. Вместо этого можно расшифровать сообщение просто проанализировав частотность символов в нём.
| Буква | Частотность % | Буква | Частотность % | Буква | Частотность % | Буква | Частотность % |
|---|---|---|---|---|---|---|---|
| О | 11,08 | Р | 4,45 | Ы | 1,96 | Х | 0,89 |
| Е, Ё | 8,41 | В | 4,33 | Ь | 1,92 | Ш | 0,81 |
| А | 7,92 | К | 3,36 | З | 1,75 | Ю | 0,61 |
| И | 6,83 | М | 3,26 | Г | 1,74 | Э | 0,38 |
| Н | 6,72 | Д | 3,05 | Б | 1,71 | Щ | 0,37 |
| Т | 6,18 | П | 2,81 | Ч | 1,47 | Ц | 0,36 |
| С | 5,33 | У | 2,80 | Й | 1,12 | Ф | 0,19 |
| Л | 5,00 | Я | 2,13 | Ж | 1,05 | Ъ | 0,02 |
Тем не менее частотный криптоанализ не решает полностью задачу взлома моноалфавитных шифров. Его применимость зависит от величины и характера текста. Средние частотности букв какого-либо языка не всегда будут соответствовать частотностям букв конкретного текста. Например, краткое сообщение, в котором обсуждается влияние атмосферы на движение зебр в Африке «Из-за озоновых дыр от Занзибары до Замбии и Заира зебры бегают зигзагами», если будет зашифровано моноалфавитным шифром, не удастся дешифровать с помощью простого частотного криптоанализа. Так как буква з в этом сообщении встречается на порядок чаще, чем в простой речи. В технических текстах редкая буква ф может стать довольно частой в связи с частым использованием таких слов, как функция, дифференциал, диффузия, коэффициент и т. п.[4].
Если не удаётся расшифровать криптограмму с помощью простого частотного криптоанализа (например если сообщение слишком короткое), Аль-Кинди предлагает использовать характерные сочетания букв или, наоборот, несочетаемость определённых букв друг с другомШаблон:Sfn. Например, наиболее распространённые биграммы (группы из двух букв) русского языка: ст, но, ен, то, на, ов, ни, ра, во, ко[4]. Важна статистика сочетаемости гласных и согласных букв. Например перед буквами ь, ы, ъ и после э не могут стоять гласные, а после любой гласной буквы следует согласная с вероятностью 87 %[4]. Так же подсказкой для криптоаналитика могут быть общепринятые вступительные словаШаблон:Sfn, которые используются почти в каждом языке. Например в арабском часто употреблялось «Во имя Бога, милостивого и милосердного» (Шаблон:Lang-ar). При расшифровке стихотворений можно использовать рифмы и стопы.
Арабские буквы: их порядок и повторяемость
Аль-Кинди приводит таблицу с абсолютными частотностями букв арабского алфавита, вычисленными в выборке из семи листов текстаШаблон:Sfn.
По каким-то причинам автор не указал частотности букв Шаблон:Lang-ar2 (/ʃ/), Шаблон:Lang-ar2 (/dˁ/, /ðˤ/) и Шаблон:Lang-ar2 (/x/), указав при этом их место в таблице, упорядоченной по убыванию частотностей.
В арабском алфавите 28 букв. Из них 27 могут обозначать согласные звуки, 3 (Шаблон:Lang-ar2 (/aː/), Шаблон:Lang-ar2 (/uː/), Шаблон:Lang-ar2 (/iː/)) — долгие гласные звуки, букв, обозначающих короткие гласные, — нет (например в слове Муха́ммед пишутся только четыре согласные буквы: Шаблон:Lang-ar2). Таким образом в арабском письме преобладают чисто согласные буквы. Однако этот факт не противоречит указанному в начале трактата утверждению о том что самая частая буква на письме любого языка, как правило, гласная, так как в арабском таковой является Шаблон:Lang-ar2 (/aː/)Шаблон:Sfn.
См. также
Примечания
Литература
- ↑ 1,0 1,1 1,2 Simon Singh — С. 19-24.
- ↑ Шаблон:Source
- ↑ Edward Craig Routledge Encyclopedia of Philosophy // М.:Routledge , 1998. — С. 238. — ISBN 978-0-415-07310-3.
- ↑ 4,0 4,1 4,2 4,3 Шаблон:Cite web
- ↑ Пилиди В. С. Криптография. Вводные главы. // Ростов-на-Дону, 2009. — C. 34. (текстШаблон:Недоступная ссылка)
