Трактат про дешифрування криптографічних повідомлень

«Трактат про дешифрування криптографічних повідомлень» — книга, написана Абу Юсуфом Аль-Кінді, відома як перша згадка про частотний криптоаналіз. До середини IX століття найбільш поширеним у світі методом шифрування повідомлень моноалфавітний шифр (в якому кожній букві кодованого тексту ставиться у відповідність однозначно якась шифрована літера). Арабський філософ і математик Аль-Кінді в своїй роботі описав ефективний метод розшифровки таких повідомлень, тим самим підштовхнувши розвиток поліалфавітних шифрів[2][3]. В європейських країнах поліалфавітні шифри почали застосовувати лише в XV столітті.

Трактат про дешифрування криптографічних повідомлень
مخطوط في فك رسائل التشفير
Перша сторінка рукопису
Жанр наукова література, криптоаналіз і криптографія
Автор Абу Юсуф Якуб ібн Ісхак ібн Саббах аль-Кінді
Мова арабська
Написано ~ 850[1]

Історія

В 750 році прихід династії Аббасидів ознаменував початок золотого століття ісламської цивілізації. Арабський халіфат до того часу простягався від Атлантичного океану на заході до кордонів з Індією на сході, займаючи приблизно половину відомого світу. Халіфи династії Аббасидів в меншій мірі, ніж їх попередники, були зацікавлені в завоюваннях, і натомість зосередилися на створенні організованого і забезпеченого суспільства. Низькі податки забезпечили підйом торгівлі та ремісництва, в той час як суворі закони призвели до зниження корупції та захищали громадян. Все це спиралося на ефективну систему управління, яка, у свою чергу, спиралися на захищеність систем зв'язку. Чиновники зашифровували конфіденційні державні документи й документи податкового обліку, що свідчить про широке та регулярне застосування криптографії. У багатьох посібниках для чиновників, таких як «Керівництво для секретарів» (араб. أدب الكتـاب‎), містилися розділи, присвячені криптографії. Зазвичай використовувався моноалфавітний шифр, вихідний алфавіт якого був простою перестановкою вхідного алфавіту, але іноді використовували вихідні алфавіти, що містять інші символи.

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

Аль-Кінді народився в місті Куфа приблизно в 801 році. Є нащадком аристократичного роду Кінда. Його батько був еміром (губернатором) Басри. У Басрі Аль-Кінді провів своє дитинство й отримав початкову освіту, пізніше відправився в Багдад, щоб продовжити навчання під патронажем халіфа аль-Мамуна[4]. Після навчання халіф довірив йому керівництво Будинком Мудрості, де він почав роботу над перекладом грецьких рукописів Аристотеля та інших філософів на арабську мову[5]. Під час цієї роботи Аль-Кінді вперше стикається з необхідністю розшифровки текстів, так як деякі з рукописів, які йому доводилося перекладати, були зашифровані[6]. При аль-Мутаваккилі (з 847 р.) Аль-Кінді піддавався гонінням через його релігійно-філософських переконань[7]. Його бібліотека була конфіскована, сам він був побитий. Багато його рукописів були загублені, у тому числі й Трактат про дешифрування криптографічних повідомлень[5]. Проте до нас дійшла копія рукопису, яка була випадково знайдена в Бібліотеці Сулейманіє в Стамбулі. Ця копія містить велику кількість грубих синтаксичних і тематичних помилок і, очевидно, написана писарем, який погано розбирався в лінгвістиці та математичної статистики[8].

Зміст

У вступі Аль-Кінді описує свій трактат як короткий і чіткий посібник, який допоможе читачеві швидко оволодіти основними прийомами криптоаналізу[9]. Іншу частину книги можна умовно розбити на п'ять частин:

  1. Алгоритми криптоаналізу — опис основних методів криптоаналізу, у тому числі частотного криптоаналізу;
  2. Основні типи шифрів — класифікація моноалфавітних і деяких поліалфавітних шифрів;
  3. Алгоритми криптоаналізу деяких типів шифрів — алгоритми злому конкретних шифрів;
  4. Арабські літери: порядок та повторюваність — статистичні дані, які можна використовувати при розшифровці повідомлень на арабській мові;
  5. Комбінації букв в арабській мові — більш глибокий розгляд лінгвістичних особливостей арабської мови.

Алгоритми криптоаналізу

Аль-Кінді починає змістовну частину свого трактату з деяких міркувань математичної статистики. Він порівнює алфавіт з матеріалом з якого можна що-небудь виготовити, надавши йому потрібну форму. Наприклад, золото — матеріал, а зроблені з нього чашки, браслети та інші прикраси — різні форми цього матеріалу. Тому всі вироби зроблені з золота володіють схожими властивостями. Так само кожна мова володіє певними закономірностями, які можна використовувати при розшифровці повідомлень. Наприклад, в алфавітах багатьох мов (в тому числі арабському) більше приголосних букв, ніж голосних. Однак якщо взяти який-небудь текст і порахувати частоту появи кожної букви в ньому, то найбільш частими літерами виявляться голосні[10] (в арабській мові найчастіша буква ﺍ (/aː/), англійською, німецькою, французькою, іспанською — e, російською — о[11]). Метод частотного криптоаналізу автор описує наступним чином[10]:

Одним із прийомів, що використовуються при розшифровці криптограми, якщо відома мова вихідного повідомлення, є придбання досить довгого тексту цією мовою, і підрахунок кількості появ кожної букви в ньому. Назвемо найбільш часту букву «перша», другу за частотою «друга», наступну «третя» і так далі, поки не переберемо всі букви цього тексту. Потім повернемося до криптограми, яку ми хочемо розшифрувати, й так само класифікуємо її символи: знайдемо в криптограмі символ, який зустрічається частіше за всіх і замінимо його на «першу» букву з проаналізованого тексту, потім перейдемо до другого по частоті символу й замінимо його на «другу» букву, наступний символ на «третю», і так далі, поки не переберемо все символи, які використані в криптограмі.

Метод, запропонований Аль-Кінді легше пояснити з точки зору російського алфавіту. Насамперед, необхідно вивчити досить довгий уривок тексту російською мовою, або кілька уривків різних текстів, щоб встановити частоту появи кожної букви алфавіту. В російській мові о — найчастіша літера, після неї е, потім а і так далі, як вказано в таблиці. Потім вивчимо зашифрований текст і встановимо частоту появи кожного символу в ньому. Наприклад, якщо самий частий символ в зашифрованому тексті Ю, то, найімовірніше, його слід замінити на літеру о. Якщо другий по частоті символ зашифрованого тексту е, то його, ймовірно, слід замінити на є, і так далі. Завдяки методу Аль-Кінді, відомому як частотний криптоаналіз, не потрібно перевіряти кожен з мільярдів потенційних ключів. Замість цього можна розшифрувати повідомлення, просто проаналізувавши частоту символів в ньому.

Таблиця відносних частот букв російського алфавіту[12].
Літера Частота % Літера Частота % Літера Частота % Літера Частота %
Про 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

Тим не менш, частотний криптоаналіз не вирішує повністю завдання злому моноалфавітных шифрів. Його застосування залежить від величини й характеру тексту. Середні частоти літер будь-якої мови не завжди будуть відповідати частоті букв конкретного тексту. Наприклад, коротке повідомлення, в якому обговорюється вплив атмосфери на рух зебр в Африці «Через озонові дірки від Занзибара до Замбії і Заїру зебри бігають зигзагами», якщо буде зашифрованно моноалфавітным шифром, не вдасться дешифрувати з допомогою простого частотного криптоаналізу. Так як буква з в цьому повідомленні зустрічається на порядок частіше, ніж в простій мові. У технічних текстах рідкісна літера ф може стати досить частою у зв'язку з частим використанням таких слів, як функція, диференціал, дифузія, коефіцієнт і т. ін..

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

Арабські літери: порядок та повторюваність

Аль-Кінді наводить таблицю з частотами букв арабського алфавіту, обчисленими у вибірці з семи аркушів тексту[13].

Буква Частота Буква Частота Буква Частота Буква Частота
ا‎ 600‎ ﺭ‎ 155‎ ﺱ‎ 91‎ ﺵ‎ —‎
ﻝ‎ 437‎ ﻉ‎ 131‎ ﻕ‎ 63‎ ﺽ‎ —‎
ﻡ‎ 320‎ ﻑ‎ 122‎ ﺡ‎ 57‎ ﺥ‎ —‎
ﻩ‎ 273‎ ﺕ‎ 120‎ ﺝ‎ 46‎ ﺙ‎ 17‎
ﻭ‎ 262‎ ﺏ‎ 112‎ ﺫ‎ 35‎ ﻁ‎ 15‎
ﻱ‎ 252‎ ﻙ‎ 112‎ ﺹ‎ 32‎ ﻍ‎ 15‎
ﻥ‎ 221‎ ﺩ‎ 92‎ ﺥ‎ 20‎ ﻅ‎ 8‎

З якихось причин автор не вказав частоти літер ﺵ‎ (/ʃ/), ﺽ‎ (/dˁ/, /ðˤ/) і ﺥ‎ (/x/), вказавши при цьому їх місце в таблиці, впорядкованої за спаданням частот.

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

Див. також

Примітки
  1. Simon Singh. Arab Code Breakers. Архів оригіналу за 7 січня 2012. Процитовано 7 січня 2012.
  2. Simon Singh — С. 19-24.
  3. Габидулин, Кшевецкий, Колыбельников, 2011.
  4. Henry Corbin (1993). History Of Islamic Philosophy (англ.). London, New York City: Kegan Paul International Ltd. с. 154. ISBN 978-0-7103-0416-2.
  5. Mrayati, Alam, At-Tayyan, 2003, с. 77.
  6. Mrayati, Alam, At-Tayyan, 2003, с. 86-95.
  7. Edward Craig, ред. (1998). Routledge Encyclopedia of Philosophy (рос.). Routledge. с. 238. ISBN 978-0-415-07310-3.
  8. Mrayati, Alam, At-Tayyan, 2003, с. 111.
  9. Mrayati, Alam, At-Tayyan, 2003, с. 81.
  10. Mrayati, Alam, At-Tayyan, 2003, с. 122—130.
  11. Анализ текстов. StatSoft. Архів оригіналу за 7 січня 2012. Процитовано 4 січня 2012.
  12. Пилиди В. С. Криптография. Вводные главы. // Ростов-на-Дону, 2009. — C. 34. (текст[недоступне посилання з липня 2019])
  13. Mrayati, Alam, At-Tayyan, 2003, с. 166—170.


Література
  • Singh S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography — New York City: Doubleday, 1999. — P. 19–24. — 416 p. — ISBN 978-1-85702-879-9, 978-0-385-49531-8
  • Mrayati M., Alam Y. M., At-Tayyan M. H. Al-Kindi's Treatise on Cryptanalysis — Riyadh: KFCRIS and KACST, 2003. — (Arabic Origins of Cryptology; Vol. 1) — ISBN 978-9960-890-08-1
  • Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.