Pojednání o dešifrování kryptografických zpráv

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 3. září 2020; kontroly vyžadují 2 úpravy .
Pojednání o dešifrování kryptografických zpráv
مخطوط في فك رسائل التشفير
Pojednání o dešifrování kryptografických zpráv

První strana rukopisu
Autoři Abu Yusuf Yaqub ibn Ishaq ibn Sabbah al-Kindi
datum psaní ~850 [1]
Původní jazyk Arab
Země
Žánr vědecká literatura
Hlasitost 12 stran, ~ 6,5 tisíce slov [2]
Obsah kryptoanalýza a kryptografie
Úložný prostor Knihovna Suleymaniye ( Turecko ), dokument č. 4832 [2]
Originál neznámý

„Pojednání o dešifrování kryptografických zpráv“ je kniha napsaná Abu Yusuf Al-Kindi , známá jako první zmínka o frekvenční kryptoanalýze . Až do poloviny 9. století byla nejběžnější metodou šifrování zpráv na světě monoalfabetická šifra (ve které je každé písmeno zakódovaného textu jednoznačně spojeno s nějakým druhem zašifrovaného písmene). Arabský filozof a matematik Al-Kindi ve své práci popsal účinnou metodu dešifrování takových zpráv, čímž posunul vývoj polyalfabetických šifer [3] [4] . V evropských zemích se polyalfabetické šifry začaly používat až v 15. století .

Historie

V roce 750 nástup dynastie Abbásovců znamenal začátek zlatého věku islámské civilizace . Arabský chalífát se v té době rozkládal od Atlantského oceánu na západě k hranicím s Indií na východě a zabíral asi polovinu známého světa. Abbásovští chalífové se méně zajímali o dobývání než jejich předchůdci a místo toho se soustředili na vytvoření organizované a dobře situované společnosti. Nízké daně podpořily obchod a řemeslo, zatímco přísné zákony omezily korupci a chránily občany. To vše se opíralo o účinný kontrolní systém, který se zase opíral o bezpečnost komunikačních systémů. Úředníci zašifrovali důvěrné vládní dokumenty a daňové záznamy [3] , což ukazuje na rozšířené a pravidelné používání kryptografie . Mnoho příruček pro úředníky, jako například „Průvodce pro sekretářky“ ( arab. أدب الكتـاب ‎), obsahovalo části o kryptografii. Obvykle se používala monoalfabetická šifra, jejíž výstupní abeceda byla jednoduchou permutací vstupní abecedy, ale někdy se používaly výstupní abecedy obsahující jiné znaky.

Arabští učenci se snažili získat znalosti o předchozích civilizacích extrahováním egyptských, babylonských, indických, čínských, perských, syrských, hebrejských, římských textů a jejich překladem do arabštiny. V roce 815 založil chalífa al-Ma'mun v Bagdádu Dům moudrosti ( arab. بيتالحكمة ‎‎), knihovnu a centrum pro překládání rukopisů. Hlavní teologické školy byly založeny v Basře, Kufě a Bagdádu, kde teologové studovali zjevení Mohameda obsažená v Koránu [3] . Teologové se zajímali o stanovení chronologie zjevení a dělali to tak, že počítali četnost slov obsažených v každém zjevení. Věřilo se, že určitá slova se objevila v arabském jazyce relativně nedávno, a proto, pokud zjevení obsahuje velké množství těchto nových slov, objevilo se později v chronologii. Teologové také studovali hadísy , které se skládají z každodenních výroků Proroka. Snažili se dokázat, že každý výrok skutečně patřil Mohamedovi. To bylo provedeno studiem etymologie slov a struktury vět, aby se zjistila shoda konkrétních textů s jazykovým stylem Proroka. Analyzovali také jednotlivá písmena a zejména zjistili, že některá písmena jsou běžnější než jiná. Písmena „ﺍ“ (/aː/) a „ﻝ“ (/l/) jsou v arabštině nejběžnější, částečně kvůli určitému členu „ﺍﻝ“ (/aːl/), zatímco písmeno „ﺝ“ (/ ʤ/ ) je desetkrát vzácnější. Tato zdánlivě bezvýznamná poznámka vedla k obrovskému průlomu v kryptoanalýze. Není známo, kdo jako první vynalezl frekvenční kryptoanalýzu, ale první známý popis této metody je od Al-Kindiho.

Al-Kindi se narodil ve městě Kufa kolem roku 801. Je potomkem aristokratické rodiny Kindah . Jeho otec byl emír (guvernér) Basry . V Basře strávil Al-Kindi dětství a získal základní vzdělání, později odešel do Bagdádu , aby pokračoval ve studiu pod patronací chalífy al-Ma'muna [5] . Po výcviku mu chalífa svěřil vedení Domu moudrosti , kde začal pracovat na překladu řeckých rukopisů Aristotela a dalších filozofů do arabštiny [6] . Během této práce Al-Kindi poprvé narazil na potřebu dešifrovat texty, protože některé rukopisy, které musel přeložit, byly zašifrovány [7] . Za al-Mutawakkila (od roku 847) byl Al-Kindi pronásledován kvůli svému náboženskému a filozofickému přesvědčení [8] . Jeho knihovna byla zabavena a on sám byl zbit. Mnoho z jeho rukopisů bylo ztraceno, včetně Pojednání o dešifrování kryptografických zpráv [6] . Kopie rukopisu se k nám však dostala, která byla náhodně nalezena v knihovně Suleymaniye v Istanbulu . Tento výtisk obsahuje velké množství hrubých syntaktických a tematických chyb a byl zřejmě napsán písařem, který se špatně orientoval v lingvistice a matematické statistice [2] .

Obsah

V úvodu popisuje Al-Kindi své pojednání jako krátký a stručný manuál, který čtenáři pomůže rychle si osvojit základní techniky kryptoanalýzy [9] . Zbytek knihy lze zhruba rozdělit do pěti částí:

  1. Algoritmy kryptoanalýzy - popis hlavních metod kryptoanalýzy, včetně frekvenční kryptoanalýzy ;
  2. Hlavní typy šifer jsou klasifikace monoalfabetických a některých polyalfabetických šifer;
  3. Algoritmy kryptoanalýzy pro některé typy šifer - algoritmy pro prolomení konkrétních šifer;
  4. Arabská písmena: jejich pořadí a frekvence – statistické údaje, které lze použít při dešifrování zpráv v arabštině;
  5. Kombinace písmen v arabštině - hlubší zkoumání jazykových rysů arabského jazyka.

Algoritmy kryptoanalýzy

Al-Kindi začíná podstatnou část svého pojednání některými úvahami o matematické statistice. Porovnává abecedu s materiálem, ze kterého lze něco vyrobit, a dává tomu požadovaný tvar. Například zlato je materiál a poháry, náramky a další šperky z něj jsou různé formy tohoto materiálu. Proto všechny výrobky ze zlata mají podobné vlastnosti. Každý jazyk má také určité vzory, které lze použít při dešifrování zpráv. Například abecedy mnoha jazyků (včetně arabštiny) mají více souhlásek než samohlásek. Pokud však vezmeme libovolný text a spočítáme četnost výskytu každého písmena v něm, pak nejčastějšími písmeny budou samohlásky [10] (v arabštině je nejčastější písmeno ﺍ (/aː/), v angličtině, němčině , francouzsky, španělsky - e , v ruštině - asi [11] ). Metodu frekvenční kryptoanalýzy autor popisuje takto [10] :

Jedním z triků používaných při dešifrování kryptogramů, pokud je znám jazyk původní zprávy, je získat dostatečně dlouhý text v tomto jazyce a spočítat počet výskytů každého písmena v něm. Nazývejme nejčastější písmeno „první“, druhé nejčastější „druhé“, další „třetí“ a tak dále, dokud neprotřídíme všechna písmena tohoto textu.

Poté se vrátíme ke kryptogramu, který chceme dešifrovat, a klasifikujeme jeho symboly stejným způsobem: najdeme nejběžnější symbol v kryptogramu a nahradíme ho „prvním“ písmenem z analyzovaného textu, poté přejdeme k druhému. nejčastější symbol a nahraďte jej „druhým“ písmenem, dalším znakem „třetím“ a tak dále, dokud neprojdeme všechny znaky použité v kryptogramu.

Metoda navržená Al-Kindim je snadněji vysvětlitelná v podmínkách ruské abecedy . Nejprve je nutné nastudovat dostatečně dlouhou pasáž textu v ruštině nebo několik pasáží různých textů, aby bylo možné určit frekvenci výskytu každého písmena abecedy. V ruštině je nejběžnějším písmenem o , po něm e , pak a atd., jak je uvedeno v tabulce. Poté prostudujeme šifrový text a určíme frekvenci výskytu každého znaku v něm. Pokud je například nejčastějším znakem v šifrovém textu Yu , pak by měl být s největší pravděpodobností nahrazen písmenem o . Pokud je druhým nejběžnějším znakem v šifrovém textu E , pak by měl být pravděpodobně nahrazen znakem e a tak dále. Díky Al-Kindiho metodě, známé jako frekvenční kryptoanalýza, není nutné kontrolovat každý z miliard potenciálních klíčů . Místo toho můžete zprávu dešifrovat jednoduše analýzou četnosti znaků v ní.

Tabulka relativních četností písmen ruské abecedy [12] .
Dopis % frekvence Dopis % frekvence Dopis % frekvence Dopis % frekvence
Ó 11.08 R 4.45 S 1,96 X 0,89
JEJÍ 8.41 V 4.33 b 1,92 W 0,81
ALE 7,92 Na 3.36 Z 1,75 YU 0,61
A 6,83 M 3.26 G 1,74 E 0,38
H 6.72 D 3.05 B 1,71 SCH 0,37
T 6.18 P 2,81 H 1.47 C 0,36
Z 5.33 V 2,80 Y 1.12 F 0,19
L 5,00 já 2.13 A 1.05 Kommersant 0,02

Nicméně frekvenční kryptoanalýza neřeší zcela problém prolamování monoalfabetických šifer. Jeho použitelnost závisí na velikosti a povaze textu. Průměrné frekvence písmen jakéhokoli jazyka nebudou vždy odpovídat frekvencím písmen konkrétního textu. Například krátká zpráva pojednávající o vlivu atmosféry na pohyb zeber v Africe „Kvůli ozónovým dírám ze Zanzibaru do Zambie a Zairu se zebry klikatí“, pokud je zašifrována v monoalfabetické šifře, nelze dešifrovat pomocí jednoduché frekvence. kryptoanalýza. Protože se písmeno z v této zprávě vyskytuje o řád častěji než v jednoduché řeči. V odborných textech se vzácné písmeno f může stát poměrně běžným kvůli častému používání slov jako funkce, diferenciál, difúze, koeficient atd. [11] .

Pokud není možné kryptogram dešifrovat pomocí jednoduché frekvenční kryptoanalýzy (např. pokud je zpráva příliš krátká), Al-Kindi navrhuje použít charakteristické kombinace písmen nebo naopak nekompatibilitu určitých písmen mezi sebou [10] . Například nejběžnější bigramy (skupiny dvou písmen) ruského jazyka: st , but , en , to , na , ov , ni , ra , vo , ko [11] . Důležitá je statistika kompatibility samohlásek a souhlásek. Například před písmeny ь , ы , ъ a za e nemohou být samohlásky a za jakoukoli samohláskou následuje souhláska s pravděpodobností 87 % [11] . Nápovědou pro kryptoanalytika mohou být také běžná úvodní slova [10] , která se používají téměř v každém jazyce. Například v arabštině se často používalo „ve jménu Boha, milosrdného a milosrdného“ ( arab. بسم الله الرحمن الرحيم ‎). Při přepisu básní lze použít říkadla a zastavení .

Arabská písmena: jejich pořadí a frekvence

Al-Kindi uvádí tabulku s absolutními četnostmi písmen arabské abecedy , vypočítanou na vzorku sedmi listů textu [13] .

Dopis Frekvence Dopis Frekvence Dopis Frekvence Dopis Frekvence
ا 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

Z nějakého důvodu autor neuvedl četnost písmen ﺵ ‎ (/ʃ/), ﺽ ‎ (/dˁ/, /ðˤ/) a ﺥ ‎ (/x/), přičemž uvedl jejich místo v tabulce, seřazené v sestupném pořadí podle frekvence.

V arabské abecedě je 28 písmen. Z nich 27 může představovat souhlásky, 3 ( ﺍ ‎ (/aː/), ﻭ ‎ (/uː/), ﻱ ‎ (/iː/)) - dlouhé samohlásky, neexistují žádná písmena označující krátké samohlásky (např. Slovo Mohamed má pouze čtyři souhlásky: محمد ). V arabském písmu tedy převládají čisté souhlásky. Tato skutečnost však není v rozporu s tvrzením uvedeným na začátku pojednání, že nejčastějším písmenem při psaní jakéhokoli jazyka je obvykle samohláska, protože v arabštině je to ﺍ ‎ (/aː/) [13] .

Viz také

Poznámky

  1. ↑ Simon Singh. Arabští prolomitelé kódu . Datum přístupu: 7. ledna 2012. Archivováno z originálu 7. ledna 2012.
  2. ↑ 1 2 3 Mrayati, Alam, At-Tayyan, 2003 , str. 111.
  3. ↑ 1 2 3 Simon Singh - str. 19-24.
  4. ↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , str. 11, 12.
  5. ↑ Corbin H. History Of Islamic Philosophy  (Angl.) - Londýn , NYC : Kegan Paul International Ltd. , 1993. - S. 154. - 445 s. — ISBN 978-0-7103-0416-2
  6. ↑ 1 2 Mrayati, Alam, At-Tayyan, 2003 , str. 77.
  7. ↑ Mrayati, Alam, At-Tayyan, 2003 , str. 86-95.
  8. ↑ Edward Craig Routledge Encyclopedia of Philosophy // M.: Routledge, 1998. - S. 238. - ISBN 978-0-415-07310-3 .
  9. ↑ Mrayati, Alam, At-Tayyan, 2003 , str. 81.
  10. ↑ 1 2 3 4 Mrayati, Alam, At-Tayyan, 2003 , str. 122-130.
  11. ↑ 1 2 3 4 Analýza textu . statsoft. Staženo: 4. ledna 2012.
  12. ↑ Pilidi V. S. Kryptografie. Úvodní kapitoly. // Rostov-on-Don, 2009. - C. 34. ( text  (nepřístupný odkaz) )
  13. ↑ 1 2 Mrayati, Alam, At-Tayyan, 2003 , str. 166-170.

Literatura