Un tratat despre descifrarea mesajelor criptografice

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 septembrie 2020; verificările necesită 2 modificări .
Un tratat despre descifrarea mesajelor criptografice
مخطوط في فك رسائل التشفير
Un tratat despre descifrarea mesajelor criptografice

Prima pagină a manuscrisului
Autorii Abu Yusuf Yaqub ibn Ishaq ibn Sabbah al-Kindi
data scrierii ~850 [1]
Limba originală arab
Țară
Gen literatura stiintifica
Volum 12 pagini, ~ 6,5 mii de cuvinte [2]
Conţinut criptoanaliză și criptografie
Depozitare Biblioteca Suleymaniye ( Turcia ), documentul nr.4832 [2]
Original necunoscut

„Un tratat despre descifrarea mesajelor criptografice” este o carte scrisă de Abu Yusuf Al-Kindi , cunoscută drept prima mențiune a criptoanalizei în frecvență . Până la mijlocul secolului al IX-lea , cea mai comună metodă de criptare a mesajelor din lume era un cifru monoalfabetic (în care fiecare literă a textului codificat este asociată în mod unic cu un fel de literă criptată). Filosoful și matematicianul arab Al-Kindi în lucrarea sa a descris o metodă eficientă de descifrare a unor astfel de mesaje, împingând astfel dezvoltarea cifrurilor polialfabetice [3] [4] . În țările europene, cifrurile polialfabetice au început să fie folosite abia în secolul al XV-lea .

Istorie

În 750, apariția dinastiei Abbaside a marcat începutul epocii de aur a civilizației islamice . Califatul arab în acel moment se întindea de la Oceanul Atlantic în vest până la granițele cu India în est, ocupând aproximativ jumătate din lumea cunoscută. Califii abasizi erau mai puțin interesați de cucerire decât predecesorii lor și, în schimb, s-au concentrat pe crearea unei societăți organizate și înstărite. Taxele mici au stimulat comerțul și meșteșugurile, în timp ce legile stricte au redus corupția și au protejat cetățenii. Toate acestea s-au bazat pe un sistem de control eficient, care, la rândul său, s-a bazat pe securitatea sistemelor de comunicații. Oficialii au criptat documente guvernamentale confidențiale și dosare fiscale [3] , ceea ce indică utilizarea pe scară largă și regulată a criptografiei . Multe manuale pentru funcționari, cum ar fi „Ghidul pentru secretari” ( arab. أدب الكتـاب ‎), conțineau secțiuni despre criptografie. De obicei, se folosea un cifru monoalfabetic al cărui alfabet de ieșire era o simplă permutare a alfabetului de intrare, dar uneori erau folosite alfabete de ieșire care conțineau alte caractere.

Savanții arabi au căutat să obțină cunoștințe despre civilizațiile anterioare extragând texte egiptene, babiloniene, indiene, chineze, persane, siriace, ebraice, romane și traducându-le în arabă. În 815, califul al-Ma'mun a fondat Casa Înțelepciunii ( arab. بيتالحكمة ‎‎) la Bagdad , o bibliotecă și un centru pentru traducerea manuscriselor. Principalele școli teologice au fost fondate în Basra, Kufa și Bagdad, unde teologii au studiat revelațiile lui Mahomed conținute în Coran [3] . Teologii erau interesați să stabilească cronologia revelațiilor și au făcut acest lucru numărând frecvența cuvintelor conținute în fiecare revelație. Se credea că anumite cuvinte au apărut în limba arabă relativ recent și, prin urmare, dacă o revelație conține un număr mare de aceste cuvinte noi, atunci a apărut mai târziu în cronologie. Teologii au studiat, de asemenea, Hadith -urile , care constau în cuvintele zilnice ale Profetului. Au încercat să demonstreze că fiecare zicală îi aparține cu adevărat lui Mahomed. Aceasta s-a realizat prin studierea etimologiei cuvintelor și a structurii propozițiilor pentru a stabili conformitatea textelor specifice cu stilul de limbaj al Profetului. Ei au analizat, de asemenea, scrisorile individuale și, în special, au descoperit că unele litere erau mai frecvente decât altele. Literele „ﺍ” (/aː/) și „ﻝ” (/l/) sunt cele mai comune în arabă, datorită parțial articolului hotărât „ﺍﻝ” (/aːl/), în timp ce litera „ﺝ” (/ ʤ/ ) este de zece ori mai rar. Această remarcă aparent nesemnificativă a dus la o descoperire uriașă în criptoanaliza. Nu se știe cine a inventat pentru prima dată criptoanaliza în frecvență, dar prima descriere cunoscută a acestei metode este de către Al-Kindi.

Al-Kindi s-a născut în orașul Kufa în jurul anului 801. Este un descendent al familiei aristocratice Kindah . Tatăl său a fost emirul (guvernatorul) din Basra . În Basra, Al-Kindi și-a petrecut copilăria și a primit studiile primare, mai târziu a plecat la Bagdad pentru a-și continua studiile sub patronajul califului al-Ma'mun [5] . După pregătire, califul i-a încredințat conducerea Casei Înțelepciunii , unde a început să lucreze la traducerea manuscriselor grecești ale lui Aristotel și ale altor filozofi în arabă [6] . În timpul acestei lucrări, Al-Kindi a întâlnit pentru prima dată nevoia de a descifra textele, deoarece unele dintre manuscrisele pe care trebuia să le traducă erau criptate [7] . Sub al-Mutawakkil (din 847), Al-Kindi a fost persecutat din cauza convingerilor sale religioase și filozofice [8] . Biblioteca i-a fost confiscată și el însuși a fost bătut. Multe dintre manuscrisele sale s-au pierdut, inclusiv Tratatul de decriptare a mesajelor criptografice [6] . Cu toate acestea, o copie a manuscrisului a ajuns la noi, care a fost găsită accidental în Biblioteca Suleymaniye din Istanbul . Această copie conține un număr mare de erori sintactice și tematice grosolane și se pare că a fost scrisă de un scrib care nu cunoștea lingvistică și statistica matematică [2] .

Cuprins

În introducere, Al-Kindi descrie tratatul său ca pe un manual scurt și concis care va ajuta cititorul să stăpânească rapid tehnicile de bază ale criptoanalizei [9] . Restul cărții poate fi împărțit aproximativ în cinci părți:

  1. Algoritmi de criptoanaliza - descrierea principalelor metode de criptoanaliză, inclusiv criptoanaliza în frecvență ;
  2. Principalele tipuri de cifruri sunt clasificarea cifrurilor monoalfabetice și a unor cifruri polialfabetice ;
  3. Algoritmi de criptoanaliza pentru unele tipuri de cifruri - algoritmi de spargere a unor cifruri specifice;
  4. Litere arabe: ordinea și frecvența lor - date statistice care pot fi folosite la descifrarea mesajelor în arabă;
  5. Combinații de litere în arabă - o examinare mai profundă a caracteristicilor lingvistice ale limbii arabe.

Algoritmi de criptoanaliza

Al-Kindi începe partea substanțială a tratatului său cu câteva considerații de statistică matematică. El compară alfabetul cu materialul din care se poate face ceva, dându-i forma dorită. De exemplu, aurul este un material, iar cupele, brățările și alte bijuterii realizate din acesta sunt diferite forme ale acestui material. Prin urmare, toate produsele din aur au proprietăți similare. De asemenea, fiecare limbă are anumite modele care pot fi folosite la descifrarea mesajelor. De exemplu, alfabetele multor limbi (inclusiv arabă) au mai multe consoane decât vocale. Totuși, dacă luăm orice text și calculăm frecvența de apariție a fiecărei litere din el, atunci cele mai frecvente litere vor fi vocalele [10] (în arabă, cea mai frecventă literă este ﺍ (/aː/), în engleză, germană , franceză, spaniolă - e , în rusă - aproximativ [11] ). Metoda criptoanalizei frecvenței este descrisă de autor după cum urmează [10] :

Unul dintre trucurile folosite la descifrarea criptogramelor, dacă se cunoaște limba mesajului original, este de a obține un text suficient de lung în acea limbă și de a număra numărul de apariții ale fiecărei litere din acesta. Să numim cea mai frecventă literă „prima”, a doua cea mai frecventă „a doua”, următoarea „a treia” și așa mai departe, până când sortăm toate literele acestui text.

Apoi revenim la criptograma pe care dorim să o decriptăm și clasificăm simbolurile acesteia în același mod: găsim cel mai comun simbol în criptogramă și îl înlocuim cu „prima” literă din textul analizat, apoi trecem la a doua. cel mai frecvent simbol și înlocuiți-l cu „a doua” literă, următorul caracter la „al treilea” și așa mai departe, până când trecem prin toate caracterele utilizate în criptogramă.

Metoda propusă de Al-Kindi este mai ușor de explicat din punct de vedere al alfabetului rus . În primul rând, este necesar să se studieze un pasaj suficient de lung de text în limba rusă sau mai multe pasaje din texte diferite, pentru a stabili frecvența de apariție a fiecărei litere a alfabetului. În rusă, o este cea mai comună literă, după ea , apoi a și așa mai departe, așa cum este indicat în tabel. Apoi studiem textul cifrat și determinăm frecvența de apariție a fiecărui caracter din el. De exemplu, dacă cel mai frecvent caracter din textul cifrat este Yu , atunci cel mai probabil ar trebui înlocuit cu litera o . Dacă al doilea cel mai frecvent caracter din textul cifrat este E , atunci probabil ar trebui înlocuit cu e și așa mai departe. Datorită metodei lui Al-Kindi, cunoscută sub numele de criptoanaliza de frecvență, nu este necesar să se verifice fiecare dintre miliardele de chei potențiale . În schimb, puteți decripta mesajul pur și simplu analizând frecvența caracterelor din el.

Tabel cu frecvențele relative ale literelor alfabetului rus [12] .
Scrisoare Frecvență % Scrisoare Frecvență % Scrisoare Frecvență % Scrisoare Frecvență %
O 11.08 R 4.45 S 1,96 X 0,89
A EI 8.41 LA 4.33 b 1,92 W 0,81
DAR 7,92 La 3.36 Z 1,75 YU 0,61
Și 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
DIN 5.33 La 2,80 Y 1.12 F 0,19
L 5.00 eu 2.13 ȘI 1.05 Kommersant 0,02

Cu toate acestea, criptoanaliza frecvenței nu rezolvă complet problema ruperii cifrurilor monoalfabetice. Aplicabilitatea sa depinde de dimensiunea și natura textului. Frecvențele medii ale literelor oricărei limbi nu vor corespunde întotdeauna cu frecvențele literelor unui anumit text. De exemplu, un scurt mesaj care discută influența atmosferei asupra mișcării zebrelor în Africa, „Din cauza găurilor de ozon din Zanzibar în Zambia și Zaire, zebrele zigzag”, dacă este criptat într-un cifr monoalfabetic, nu poate fi decriptat folosind o frecvență simplă. criptoanaliza. Deoarece litera z din acest mesaj apare un ordin de mărime mai des decât în ​​vorbirea simplă. În textele tehnice, litera rară f poate deveni destul de comună datorită utilizării frecvente a unor cuvinte precum funcție, diferențială, difuzie, coeficient etc. [11] .

Dacă nu este posibilă descifrarea criptogramei folosind criptoanaliza simplă a frecvenței (de exemplu, dacă mesajul este prea scurt), Al-Kindi sugerează utilizarea combinațiilor de litere caracteristice sau, dimpotrivă, incompatibilitatea anumitor litere între ele [10] . De exemplu, cele mai comune bigrame (grupuri de două litere) ale limbii ruse: st , but , en , to , na , ov , ni , ra , vo , ko [11] . Statistica compatibilității vocalelor și consoanelor este importantă. De exemplu, înaintea literelor ь , ы , ъ și după e nu pot exista vocale, iar după orice vocală urmează o consoană cu o probabilitate de 87% [11] . De asemenea, un indiciu pentru un criptoanalist poate fi cuvintele introductive comune [10] care sunt folosite în aproape fiecare limbă. De exemplu, în arabă a fost adesea folosit „În numele lui Dumnezeu, milostiv și milostiv” ( arab. بسم الله الرحمن الرحيم ‎). Când transcrieți poezii, pot fi folosite rime și opriri .

Literele arabe: ordinea și frecvența lor

Al-Kindi oferă un tabel cu frecvențele absolute ale literelor alfabetului arab , calculate într-un eșantion de șapte foi de text [13] .

Scrisoare Frecvență Scrisoare Frecvență Scrisoare Frecvență Scrisoare Frecvență
ا 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

Din anumite motive, autorul nu a indicat frecvența literelor ﺵ ‎ (/ʃ/), ﺽ ‎ (/dˁ/, /ðˤ/) și ﺥ ‎ (/x/), în timp ce a indicat locul lor în tabel, sortate în ordine descrescătoare a frecvenței .

Există 28 de litere în alfabetul arab. Dintre acestea, 27 pot reprezenta consoane, 3 ( ﺍ ‎ (/aː/), ﻭ ‎ (/uː/), ﻱ ‎ (/iː/)) - vocale lungi, nu există litere care să desemneze vocale scurte (de exemplu, în Cuvântul Mohammed are doar patru consoane: محمد ‎). Astfel, în scrierea arabă predomină consoanele pure. Cu toate acestea, acest fapt nu contrazice afirmația indicată la începutul tratatului că cea mai frecventă literă în scrierea oricărei limbi este de obicei o vocală, deoarece în arabă este ﺍ ‎ (/aː/) [13] .

Vezi și

Note

  1. ↑ Simon Singh. Spărgătoare de coduri arabe . Data accesului: 7 ianuarie 2012. Arhivat din original pe 7 ianuarie 2012.
  2. ↑ 1 2 3 Mrayati, Alam, At-Tayyan, 2003 , p. 111.
  3. ↑ 1 2 3 Simon Singh - pp. 19-24.
  4. ↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , p. 11, 12.
  5. ↑ Corbin H. History Of Islamic Philosophy  (Eng.) - Londra , NYC : Kegan Paul International Ltd. , 1993. - P. 154. - 445 p. — ISBN 978-0-7103-0416-2
  6. ↑ 1 2 Mrayati, Alam, At-Tayyan, 2003 , p. 77.
  7. ↑ Mrayati, Alam, At-Tayyan, 2003 , p. 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 , p. 81.
  10. ↑ 1 2 3 4 Mrayati, Alam, At-Tayyan, 2003 , p. 122-130.
  11. ↑ 1 2 3 4 Analiza textului . statsoft. Preluat: 4 ianuarie 2012.
  12. ↑ Pilidi V. S. Criptografie. Capitole introductive. // Rostov-pe-Don, 2009. - C. 34. ( text  (link inaccesibil) )
  13. ↑ 1 2 Mrayati, Alam, At-Tayyan, 2003 , p. 166-170.

Literatură