Cifrul lui Cezar

Istoric și aplicație

Cifrul Caesar este numit după Iulius Caesar, care, conform vieții celor doisprezece Cezari din Suetonius , l-a folosit cu tura 3 pentru a proteja mesajele militare. Deși Cezar a fost prima persoană înregistrată care a folosit această schemă, se știe că au mai fost folosite alte cifruri de substituție.

Dacă avea ceva confidențial de transmis, atunci l-a notat în cifr, adică a schimbat ordinea literelor alfabetului, astfel încât să fie imposibil să deslușești un singur cuvânt. Dacă cineva dorea să-l descifreze și să-i înțeleagă semnificația, atunci trebuia să înlocuiască a patra literă a alfabetului, și anume, D, cu A și așa mai departe, cu alte litere.
Gaius Suetonius Tranquill Viața celor doisprezece Cezari , cartea întâi, cap. 56 [3]

Nepotul său, Augustus , a folosit și el acest cifr, dar s-a deplasat la dreapta cu unul și nu s-a repetat până la începutul alfabetului:

Ori de câte ori a scris în cifr, a scris B pentru A, C pentru B și restul literelor pe același principiu, folosind AA pentru X.
Gaius Suetonius Tranquill Viața celor doisprezece Cezari , cartea a doua, cap. 88 [3]

Există dovezi că Iulius Caesar a folosit și scheme mai complexe [4] .

Nu se știe cât de eficient era cifrul lui Caesar la acea vreme, dar probabil că era rezonabil de sigur, nu în ultimul rând pentru că majoritatea dușmanilor lui Cezar erau analfabeți și mulți presupuneau că mesajele erau scrise într-o limbă străină necunoscută [5] . Nu există dovezi de atunci cu privire la metodele de spargere a cifrurilor simple de substituție. Cea mai veche înregistrare de analiză a frecvenței care a supraviețuit este lucrarea lui Al-Kindi din secolul al IX-lea privind descoperirea analizei frecvenței [6] .

Cifrul Caesar, schimbat cu unul, este folosit pe spatele mezuzei pentru a cripta numele lui Dumnezeu . Acest lucru poate fi o rămășiță dintr-o perioadă timpurie când poporului evreu nu avea voie să aibă mezuzah [7] .

În secolul al XIX-lea, secțiunea personală a reclamelor din ziare a fost uneori folosită pentru a face schimb de mesaje criptate folosind cifruri simple. Kahn (1967) descrie cazuri în care amatorii s-au angajat în comunicații secrete criptate folosind cifrul Caesar în The Times [8 ] . Chiar mai târziu, în 1915, cifrul Caesar și-a găsit întrebuințare: armata rusă l-a folosit ca înlocuitor pentru cifruri mai complexe care s-au dovedit prea dificile pentru trupe; criptoanalistii germani si austrieci au avut putine dificultati in a descifra aceste mesaje [9] .

Cifrul Caesar cu 13 trepte este folosit și în algoritmul ROT13 , o metodă simplă de înfundare a textului utilizată pe scară largă pe Usenet și este folosit mai mult ca o modalitate de a ascunde spoilere decât ca metodă de criptare [10] . Cifrul Vigenère folosește un cifru Caesar cu diferite schimbări la fiecare poziție din text; valoarea deplasării este definită folosind un cuvânt cheie care se repetă. Dacă cuvântul cheie este atât de lung cât mesajul, este generat aleatoriu, păstrat secret și folosit o singură dată - o astfel de schemă se numește o schemă de blocare unică  - și acesta este singurul sistem de criptare pentru care s-a dovedit puterea criptografică absolută [11]. ] .

Cuvintele cheie mai scurte decât mesajul (cum ar fi „Victoria completă” utilizate de Confederație în timpul războiului civil american ) introduc un model ciclic care ar putea fi detectat cu o versiune îmbunătățită a analizei de frecvență [12] .

În aprilie 2006, șeful mafiei fugar Bernardo Provenzano a fost prins în Sicilia în parte din cauza criptoanalizei mesajelor sale, scrise folosind o variantă a cifrului Caesar. În cifrul Provenzano, literele au fost mai întâi înlocuite cu numere - numerele de serie ale literelor din alfabet, iar cifrul Caesar a fost deja aplicat secvenței de numere rezultate - astfel încât atunci când a fost deplasat cu 3, „A” a fost scris ca „4”, „B” - ca „5” și așa mai departe [13] .

Adesea, pentru confortul utilizării cifrului Caesar, se folosesc două discuri de diametre diferite montate pe o axă comună cu alfabete desenate de-a lungul marginilor discurilor. Inițial, discurile sunt rotite astfel încât fiecare literă a alfabetului discului exterior să fie vizavi de aceeași literă a alfabetului discului mic. Dacă acum rotim discul interior cu mai multe caractere, atunci vom obține o corespondență între simbolurile discului exterior și cel interior - cifrul Caesar. Discul rezultat poate fi folosit atât pentru criptare, cât și pentru decriptare [14] .

De exemplu, dacă roata interioară este rotită astfel încât simbolul A al discului exterior să corespundă simbolului D al discului interior, atunci obținem un cifr cu o deplasare de 3 la stânga.

Ruperea cifrului

Cifrul Caesar poate fi spart cu ușurință chiar dacă crackerul cunoaște doar textul cifrat. Pot fi luate în considerare două situații:

1. Crackerul știe (sau presupune) că a fost folosit un simplu cifr de substituție, dar nu știe că este o schemă Caesar.
2. Crackerul știe că a fost folosit un cifru Caesar, dar nu cunoaște valoarea deplasării.

În primul caz, cifrul poate fi spart folosind aceleași metode ca și pentru cifrul de substituție simplu, cum ar fi analiza de frecvență , etc. Folosind aceste metode, crackerul este probabil să observe rapid regularitatea în soluție și să realizeze că cifrul fiind folosit este cifrul lui Cezar.

În al doilea caz, spargerea cifrului este și mai ușoară. Nu există multe opțiuni pentru valorile de schimbare (26 pentru engleză), toate pot fi verificate prin forță brută [15] . O modalitate de a face acest lucru este să scrieți o bucată de text cifrat într-o coloană cu toate schimbările posibile, o tehnică denumită uneori „completarea unei componente simple” [16] . Luați în considerare un exemplu pentru textul cifrat „EXXEGOEXSRGI”; textul simplu este recunoscut imediat de ochi în a patra linie.

O altă modalitate de a aplica această metodă este să scrieți alfabetul sub fiecare literă a textului cifrat, începând cu acea literă. Metoda poate fi accelerată prin utilizarea benzilor alfabetice pregătite în prealabil. Pentru a face acest lucru, trebuie să pliați benzile astfel încât textul cifrat să fie format pe o linie, apoi pe altă linie vom vedea textul simplu.

O altă abordare a cracking-ului prin forță brută este verificarea frecvențelor literelor . Prin trasarea frecvenței literelor în textul cifrat și cunoașterea distribuției așteptate a literelor pentru textul simplu în limba în cauză, se poate determina cu ușurință deplasarea uitându-se la deplasarea unor caracteristici din diagramă. Această metodă este cunoscută sub denumirea de analiză a frecvenței . De exemplu, într-un text în limba engleză, frecvențele literelor E , T , (de obicei cele mai frecvente) și Q , Z (de obicei mai rare) sunt deosebit de diferite [17] . Acest proces poate fi automatizat dacă programul de calculator evaluează cât de bine se potrivește distribuția reală a frecvenței cu distribuția așteptată. De exemplu, poate fi folosit un test chi-pătrat [18] .

Pentru textul în limbaj natural simplu, cel mai probabil va exista o singură opțiune de decodare. Dar, dacă utilizați mesaje foarte scurte, atunci există cazuri în care sunt posibile mai multe opțiuni de decriptare cu diferite ture. De exemplu, textul cifrat „MPQY” poate fi decodificat fie ca „aden” fie „know” (presupunând că textul simplu este scris în engleză). În mod similar, „ALIIP” poate fi descifrat ca „păpuși” sau ca „roată”; „AFCCP” ca „vesel” sau ca „vesel” (vezi și distanța de unicitate ).

Criptarea de mai multe ori nu îmbunătățește în niciun fel securitatea, deoarece utilizarea cifrurilor cu schimbare a și b este echivalentă cu utilizarea cifrului cu schimbare a + b. În termeni matematici, criptarea cu chei diferite formează un grup [19] .

Note

1. ↑ Luciano D. , Prichett G. Cryptology: From Caesar Ciphers to Public-Key Cryptosystems  // The College Mathematics Journal - Mathematical Association of America , Taylor & Francis , 1987. - Vol. 18, Iss. 1. - P. 2-17. — ISSN 0746-8342 ; 1931-1346 - doi:10.2307/2686311
2. ↑ Wobst, 2007 , pp. 19.
3. ↑ 1 2 Viața celor doisprezece Cezari, 1964 .
4. ↑ Reinke E. C. Criptografie clasică  // Clasa . j. (Class. Assoc. Middle West South) - Asociația clasică a Vestului Mijlociu și Sudului , 1962. - Vol. 58, Iss. 3. - P. 113-121. — ISSN 0009-8353 ; 2327-5812
5. ↑ Pieprzyk J. , Hardjono T. , Seberry J. Fundamentals of Computer Security  (engleză) - Springer Science + Business Media , 2003. - P. 6. - 677 p. — ISBN 978-3-540-43101-5
6. ↑ Singh, 1999 , pp. 14–20.
7. ↑ Alexander Poltorak. Mezuza și astrologia . chabad.org . Preluat la 13 iunie 2008. (nedefinit)
8. ↑ Kahn, 1967 , pp. 775–6.
9. ↑ Kahn, 1967 , pp. 631–2.
10. ↑ Wobst, 2007 , pp. douăzeci.
11. ↑ Fomichev, 2003 , p. 239-246.
12. ↑ Kahn, 1967 .
13. ↑ Leyden, John . Mafia boss undone by clusy crypto , The Register  (19 aprilie 2006). Preluat la 13 iunie 2008.
14. ↑ Reynard, Robert. Secret Code Breaker: Manualul  unui criptoanalist . - 1996. - P. 92-51. - ISBN 1-889668-00-1 ).
15. ↑ Beutelspacher, Albrecht Criptologie  (neopr.) . - Mathematical Association of America , 1994. - S.  8 -9. - ISBN 0-88385-504-6 .
16. ↑ Sinkov A. Criptanaliză elementară  (engleză) : A Mathematical Approach - Mathematical Association of America , 1998. - P. 13-15. — 232p. — ISBN 978-0-88385-622-2
17. ↑ Singh, 1999 , pp. 72–77.
18. ↑ Savarese, Chris; Brian Hart. The Caesar Cipher (15 iulie 2002). Preluat: 16 iulie 2008. (nedefinit)
19. ↑ Wobst, 2007 , pp. 31.

Literatură

• Gaius Suetonius Tranquill . Viața celor Doisprezece Cezari = De vita XII caesarvm. - M . : Editura „Nauka”, 1964. - 374 p. - (Monumente literare).
• Kahn D. The Codebreakers  (engleză) : The Story of Secret Writing - Macmillan , 1967. - 1164 p. — ISBN 978-0-684-83130-5
• Singh S. The Code Book , Histoire des codes secrets  (engleză) : The Science of Secrecy from Ancient Egypt to Quantum Cryptography, De l'Égypte des pharaons à l'ordinateur quantique - NYC : Doubleday , Knopf Doubleday Publishing Group , 1999. — 416 p.
• Fomichev V. M. Matematică discretă și criptologie : Curs de cursuri / ed. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - 397 p. — ISBN 978-5-86404-185-7
• Wobst R. Cryptology Unlocked  (engleză) / A. Shafir - Chichester : John Wiley & Sons Ltd , 2007. - 554 p. — ISBN 978-0-470-06064-3

Link -uri

• Cifrul Caesar  - implementarea cifrului Caesar în diferite limbi la Rosetta Code .
• Cifrare Caesar - criptare și decriptare

Dicționare și enciclopedii	Britannica (online)