Un cifr de substituție este o metodă de criptare în care elementele textului simplu original sunt înlocuite cu text cifrat conform unei anumite reguli. Elementele de text pot fi caractere simple (cel mai frecvent caz), perechi de litere, triple de litere, o combinație a acestor cazuri și așa mai departe. În criptografia clasică , există patru tipuri de cifruri de substituție [1] :
Ca alternativă la cifrurile de substituție, se pot lua în considerare cifrurile de permutare . În ele, elementele textului sunt rearanjate într-o ordine diferită de originalul, iar elementele în sine rămân neschimbate. În schimb, în cifrurile de substituție, elementele textului nu își schimbă succesiunea, ci se schimbă singure.
Utilizarea cifrurilor de substituție își are originile în Mesopotamia . Pentru a ascunde informații despre rețeta de producere a glazurii pentru ceramică, autorul a înlocuit unele dintre cuvinte cu numere și semne cuneiforme . Împăratul roman Gaius Julius Caesar , când a scris mesaje secrete, a mutat fiecare literă a alfabetului cu 3 poziții. Acest tip de cifr de substituție a fost numit ulterior după el, cifrul Caesar . Un alt cifr nu mai puțin faimos al antichității , Atbash , a fost folosit în Biblie pentru a crea mesaje ascunse. Fiecare literă a cuvântului a fost înlocuită cu imaginea sa în oglindă în alfabet [2] [3] .
Unul dintre primele dispozitive de criptare este considerat a fi rigla Aeneas , atunci când se folosea un fir lung printr-o fantă și apoi prin găurile făcute în riglă. Literele corespunzatoare acestora erau situate langa gauri. Pe fir s-a legat un nod în locul în care a trecut prin gaură. Astfel, textul mesajului a fost înlocuit cu o succesiune de distanțe între noduri. Acest dispozitiv a fost inventat de vechiul comandant grec Aeneas Tacticus în secolul al IV-lea î.Hr. e. [4] [5]
Odată cu utilizarea analizei de frecvență pentru a sparge cifrurile monoalfabetice în secolul al IX-lea , a devenit necesară schimbarea frecvenței de apariție a caracterelor în textul simplu. În acest scop, a început să fie folosit un cifr de substituție monosonic , a cărui esență a fost compararea mai multor caractere de înlocuire cu o literă proporțional cu frecvența apariției acestei litere în diferite texte. Secretarul antipapului Clementius al VII-lea, Gabriel de Lavinda, în secolul al XV- lea , a fost primul care a folosit omofone pentru a asigura aproximativ aceeași frecvență a vocalelor. După 65 de ani, Leon Battista Alberti descrie în detaliu cifrul de substituție cu un singur sunet în cartea sa Tratat despre Cifre . Principala problemă cu răspândirea substituției homofonice a fost necesitatea de a folosi un alfabet extins pentru a cripta mesajele. [6] [7] [8] [9]
Acest neajuns a fost înlăturat prin cifrurile polialfabetice , dintre care primul a fost descris de călugărul german Johann Trithemius . Conform metodei descrise în tratatul său „Tipărire”, următoarea literă a fost înlocuită cu un caracter din propriul alfabet cifrat, în timp ce fiecare alfabet următor a fost obținut din precedentul prin deplasarea cu o literă. Cifrul polialfabetic descris de Blaise de Vigenère în 1585 a câștigat o popularitate deosebită . Un cuvânt arbitrar a fost folosit ca o cheie a cifrului. Setul de alfabete cifrate corespunzătoare unui cuvânt dat a fost determinat din tabelul Vigenère. [zece]
În 1854, fizicianul englez Charles Wheatstone a publicat un cifru poligramă , numit mai târziu după Lord Lyon Playfair. Acest cifru înlocuiește perechi de litere (bigrame) cu caractere unice, ceea ce crește semnificativ rezistența criptografică la analiza frecvenței. [unsprezece]
Odată cu apariția computerelor , cifrurile polialfabetice și poligrame au dispărut în fundal și au fost înlocuite cu cifruri bloc noi, mai sigure . [12]
În cifrurile de substituție simplă , substituția este efectuată doar pe un singur caracter. Pentru o demonstrație vizuală a unui cifr de substituție simplu, este suficient să scrieți același alfabet sub un anumit alfabet , dar într-o ordine diferită sau, de exemplu, cu un offset. Alfabetul scris în acest fel se numește alfabet de substituție.
Un simplu cifr de substituție folosit pentru alfabetul ebraic și de la care își ia numele. Criptarea are loc prin înlocuirea primei litere a alfabetului cu ultima, a doua cu penultima ( alef (prima literă) este înlocuită cu tav (ultima), bet (a doua) este înlocuită cu shin (penultima); din aceste combinații cifrul și-a primit numele). [13] Cifrul Atbash pentru alfabetul englez:
Alfabetul sursă: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Alfabetul de înlocuire: | ZYXWVUTSRQPONMLKJIHGF EDCBA |
Cifrul Caesar este unul dintre cele mai vechi cifruri. În timpul criptării, fiecare literă este înlocuită cu alta, care este separată de aceasta în alfabet printr-un număr fix de poziții. Cifrul este numit după împăratul roman Gaius Iulius Caesar , care l-a folosit pentru corespondența secretă. O dezvoltare naturală a cifrului Caesar a fost cifrul Vigenère . Criptare folosind o cheie :
Alfabetul sursă: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Alfabetul de înlocuire: | EFGHIJKLMNOPQRSTUVWXY ZABCD |
Un exemplu modern de cifru Caesar este ROT13 . Schimbă fiecare caracter al alfabetului englez cu 13 poziții. Folosit în forumurile de pe Internet , ca mijloc de a ascunde spoilere , puncte principale, soluții puzzle și material ofensator din perspectiva obișnuită. [paisprezece]
Cifrează folosind un cuvânt codUn cifru care utilizează un cuvânt cod este unul dintre cele mai ușor de implementat și de decriptat. Ideea este că se alege un cuvânt cod , care este scris în față, apoi restul literelor alfabetului sunt scrise în ordinea lor. Cifrează folosind cuvântul cod WORD.
Alfabetul sursă: | ABCDEFGHIJKLMNOPQRSTU VWXYZ |
Alfabetul de înlocuire: | WORDABCEFGHIJKLMNPQST UVXYZ |
După cum putem vedea, atunci când folosim un cuvânt cu cod scurt, obținem o înlocuire foarte, foarte simplă. Putem folosi un cuvânt cu litere repetate ca cuvânt cod, dar numai dacă eliminăm literele suplimentare din cuvântul cod, altfel acest lucru va duce la ambiguitate de decriptare, adică aceeași literă a textului cifrat va corespunde la două litere diferite de alfabetul original. [cincisprezece]
Prin tradiție, textul cifrat este scris în blocuri (un alt nume pentru „grupuri”) de 5 caractere, fără a ține cont de punctuația și spațiile. Acest lucru ajută la evitarea erorilor la transmiterea unui mesaj criptat și vă permite să ascundeți limitele cuvintelor în textul original. Blocul conține 6 caractere, deoarece înainte era convenabil să le trimiteți prin telegraf .
Principalul dezavantaj al acestei metode de criptare este că ultimele litere ale alfabetului (care au coeficienți de analiză de frecvență joasă ) tind să rămână la sfârșit. O modalitate mai sigură de a construi un alfabet de înlocuire este să faci o mutare a coloanei (mutarea coloanei) în alfabet folosind un cuvânt cheie, dar acest lucru nu se face adesea.
Deși numărul de chei posibile este foarte mare (26! = 288,4 ), acest tip de cifră poate fi spart cu ușurință. Cu condiția ca mesajul să aibă o lungime suficientă (vezi mai jos), criptoanalistul poate ghici semnificațiile unora dintre cele mai comune litere pe baza unei analize a distribuției de frecvență a caracterelor din textul cifrat. Acest lucru vă permite să formați cuvinte separate care pot fi folosite în avans pentru a obține o soluție mai completă mai târziu (vezi analiza frecvenței). Conform distanței de unicitate a limbii engleze, 27,6 litere din textul cifrat ar trebui să fie suficiente pentru a sparge cifrul de substituție simplu. În practică, aproximativ 50 de caractere sunt de obicei suficiente pentru a se sparge, deși unele texte cifrate pot fi sparte cu mai puține caractere dacă sunt găsite structuri nestandard. Dar cu o distribuție uniformă a caracterelor în text, ar putea fi necesare texte cifrate mult mai lungi pentru a sparge.
O încercare timpurie de a crește complexitatea analizei de frecvență a textelor cifrate a fost de a masca frecvențele reale ale caracterelor de text simplu folosind omofonie. În aceste cifruri, literele alfabetului original corespund mai mult de un caracter din alfabetul de înlocuire. De obicei, caracterelor de text sursă cu cea mai mare frecvență li se acordă mai multe echivalente decât caracterele mai rare. Astfel, distribuția frecvențelor devine mai uniformă, complicând foarte mult analiza frecvenței [17] .
Deoarece alfabetul de înlocuire necesita mai mult de 26 de caractere, a fost nevoie de alfabete extinse. Una dintre cele mai simple soluții este înlocuirea alfabetului cu numere . O altă metodă constă în modificări simple ale unui alfabet existent: litere mari , litere mici , caractere inversate etc. Mai artistice, deși nu neapărat mai fiabile, ar fi cifrurile homofonice care folosesc alfabete complet inventate (ficțiune) (cum ar fi cifrul într-un cartea „Gold Bug” al lui E. Poe sau „ Manuscrisul Voynich ”. Cu toate acestea, aceste cifruri nu sunt exemple de substituție homofonică).
Un cifr emis de un oficial medieval, care este o carte mică cu tabele mari de substituție homofonică. Cifrul a fost inițial limitat la numele unor oameni importanți ai vremii, de unde a urmat și numele cifrului; în edițiile ulterioare, acest cifru a fost completat de un număr mare de cuvinte comune și nume de locuri. Pe baza acestui „nomenclator”, a fost alcătuit Marele Cifr de Rossignol, folosit de regele Ludovic al XIV-lea al Franței . Într-adevăr, după ce acest cifr a încetat să fie folosit, arhivele franceze au fost închise timp de câteva sute de ani.
„Nomenclatorii” au fost standardul pentru corespondența diplomatică, mesajele de spionaj și au fost principalele mijloace de conspirație antipolitică de la începutul secolului al XV-lea până la sfârșitul secolului al XVIII-lea. Deși criptoanalistii guvernamentali au spart sistematic „nomenclatorii” până la mijlocul secolului al XVI-lea. Modul obișnuit de ieșire din această situație a fost creșterea volumului meselor. Dar până la sfârșitul secolului al XVIII-lea, când sistemul a început să cadă în neutilizare, unii „nomenclatori” aveau până la 50.000 de caractere. Cu toate acestea, nu toate „nomenclatoarele” au fost rupte.
Marele Cifr al lui RossignolAntoine Rossignol și fiul său Bonaventure Rossignol au inventat Marele Cifr , care a folosit 587 de numere diferite. [18] Cifrul a fost atât de puternic încât timp de multe secole nimeni nu l-a putut rupe, până când a fost făcut de ofițerul armatei franceze, criptograful Etienne Bazery în 1893, folosind exemplul unei scrisori a ministrului de război Louvois către regele Ludovic al XIV-lea . . Și-a dat seama că fiecare număr codifica nu o literă, ci o întreagă silabă . Baseri a presupus că secvența 124-22-125-46-345 codifică cuvântul „les ennemis” (dușmani) și, pornind de la aceste informații, a reușit să descifreze întregul text.
Cifrarea cărțiiUn cifr de carte este un cifr în care cheia este o carte sau o mică bucată de text . Principala cerință va fi ca ambii corespondenți să aibă nu numai aceeași carte, ci și aceeași ediție și număr. În mod tradițional, cifrurile cărților funcționează prin înlocuirea cuvintelor din textul original cu locația acelorași cuvinte în carte. Acest lucru va funcționa până când se întâlnește un cuvânt care nu este în carte, moment în care mesajul nu poate fi codificat. [19] O abordare alternativă care ocolește această problemă este înlocuirea caracterelor individuale, mai degrabă decât a cuvintelor. Cu toate acestea, această metodă are un efect secundar: textul cifrat devine foarte mare (de obicei, 4 până la 6 cifre sunt folosite pentru a cripta fiecare caracter sau silabă).
O continuare suplimentară a cifrurilor de substituție simple este cifrurile polialfabetice. Abu Al-Kindi în lucrările sale a arătat că cifrurile monoalfabetice obișnuite sunt destul de ușor de frecventat criptoanaliza și a fost primul care a propus utilizarea cifrurilor polialfabetice. În Europa, astfel de cifruri au fost descrise pentru prima dată în 1467 de către arhitectul italian Leon Battista Alberti . În secolul al XVI-lea, starețul german Johann Trithemius , în cartea sa Shorthand, a prezentat o schemă de criptare polialfabetică sub forma unui tabel. O versiune mai complexă folosind alfabete mixte a fost descrisă în 1563 de Giambattista della Porta în cartea sa De Furtivis Literarum Notis (în latină: „Despre semnificația ascunsă a literelor individuale”). Esența cifrurilor polialfabetice constă în aplicarea repetată a diferitelor cifruri simple de substituție la un anumit număr de litere ale textului criptat. Adică, unul dintre cifrurile simple de substituție este aplicat fiecărei litere individual.
Cifrul Vigenère constă dintr-o secvență de mai multe cifruri Caesar cu valori diferite de schimbare. Pentru criptare, se poate folosi un tabel de alfabet numit tabula recta sau pătratul (tabelul) al lui Vigenère. În ceea ce privește alfabetul latin, tabelul Vigenère este alcătuit din rânduri a câte 26 de caractere fiecare, fiecare rând următoare fiind deplasată cu mai multe poziții. Astfel, există 26 de cifruri Caesar diferite în tabel. În diferite etape de codificare, cifrul Vigenère utilizează alfabete diferite din acest tabel. Fiecare etapă de criptare folosește alfabete diferite, selectate în funcție de caracterul cuvântului cheie. [20] De exemplu, dacă cuvântul cheie este „CAT”, atunci prima literă a textului simplu este criptată folosind alfabetul „C”, a doua „A”, a treia „T”, a patra din nou „C” și curând.
Blocnotes de unică folosințăAcest tip de cifr de substituție este destul de specific. A fost inventat la sfârșitul Primului Război Mondial de Gilbert Vernam . Claude Shannon și-a demonstrat matematic puterea criptografică absolută în lucrarea sa din 1945. Pentru a crea un text cifrat, textul simplu este XORed cu o cheie (numită un bloc unic sau cipherpad). În acest caz, utilizarea unui pad unic, în cele mai multe cazuri, este nepractică, deoarece este necesar ca cheia să aibă aceeași dimensiune ca textul simplu. De asemenea, necesită ca cheia să fie complet aleatorie, folosită o singură dată și păstrată secretă pentru toată lumea, cu excepția destinatarului și expeditorului. În acest sens, utilizarea comercială a cifrului Vernam nu este la fel de comună ca schemele cu chei publice și este folosită în principal pentru transmiterea de mesaje de importanță deosebită de către agențiile guvernamentale. [21]
În cifrurile de substituție poligramă, literele de text simplu sunt înlocuite nu pe rând, ci în grupuri. Primul avantaj al acestei metode este că distribuția de frecvență a grupurilor de litere este mult mai uniformă decât caracterele individuale. În al doilea rând, analiza productivă a frecvenței necesită o dimensiune mai mare a textului cifrat, deoarece numărul diferitelor grupuri de litere este mult mai mare decât doar alfabetul.
Cifrul Playfair este o tehnică manuală de criptare simetrică care a fost pionier în utilizarea înlocuirii bigramelor . Inventat în 1854 de Charles Wheatstone , dar numit după Lord Lyon Playfair, care a introdus acest cifr în serviciile guvernamentale din Regatul Unit. Cifrul prevede criptarea perechilor de caractere (bigrame) în loc de caractere unice, ca în cifrul de substituție și în sistemele de criptare Vigenère mai complexe. [22] [23] Cifrul Playfair folosește o matrice 5x5 (pentru alfabetul latin, pentru alfabetul chirilic este necesar să se mărească dimensiunea matricei la 4x8), ale cărei celule sunt umplute cu un alfabet mixt (în engleză). texte, caracterul „Q” este de obicei omis pentru a reduce alfabetul, în alte versiuni „I” și „J” sunt combinate într-o singură celulă). Înlocuirea se face apoi prin reprezentarea bigramelor ca două colțuri ale unui dreptunghi. Celelalte două colțuri din diagramă sunt folosite pentru criptare (a se vedea articolul principal pentru mai multe detalii). Cifrul Playfair a fost folosit tactic de armata britanică în cel de -al Doilea Război Boer și Primul Război Mondial și de australieni și germani în timpul celui de-al Doilea Război Mondial . Motivul utilizării cifrului Playfair a fost că este destul de rapid de utilizat și nu necesită echipament special.
Hill CipherCifrul Hill, inventat în 1929 de Lester S. Hill, este un cifr poligramă care poate folosi grupuri mari folosind algebra liniară . Fiecărei litere i se atribuie mai întâi un număr. Pentru alfabetul latin se folosește adesea cea mai simplă schemă: A = 0, B =1, ..., Z=25. Blocul de n litere este tratat ca un vector n-dimensional și înmulțit cu o matrice n × n modulo 26. Componentele matricei sunt cheia și trebuie să fie aleatoare, cu condiția ca matricea să fie inversabilă pentru decriptare. operațiunea să fie posibilă. [24] Cifrul Hill este vulnerabil la atacurile de text simplu, deoarece folosește operații liniare. Prin urmare, pentru a crește puterea criptografică, trebuie adăugate unele operații neliniare. Combinația de operații liniare, ca în cifrul Hill, și pași neliniari a condus la crearea unei rețele de permutare-permutare (cum ar fi rețeaua Feistel ). Prin urmare, dintr-un anumit punct de vedere, cifrurile bloc moderne pot fi considerate ca un tip de cifruri poligrame. [25]
Celebrul criptograf american Bruce Schneier identifică patru 4 metode principale de criptoanaliza: [26]
Să descriem puterea criptografică a cifrurilor de substituție în raport cu aceste metode.
Cifrurile monoalfabetice sunt ușor de spart folosind metode de analiză a frecvenței [6] .
Criptanaliza cifrurilor de substituție monosonică se realizează prin numărarea frecvențelor de apariție a perechilor și triplelor de caractere [27] .
Pentru a decripta cifrurile polialfabetice , se folosește metoda Kasiski [28] .
Cifrul poligramei lui Hill poate fi spart prin calcularea frecvențelor secvențelor de caractere [29] .
Având în vedere un text simplu de lungime suficientă, ruperea cifrurilor monoalfabetice și monosunete este trivială [30] .
Pentru a sparge rapid cifrurile polialfabetice , lungimea textului simplu trebuie să depășească lungimea cheii [31] .
Toate cifrurile de substituție sunt vulnerabile la atacuri alese cu text simplu, cu excepția pad-ului unic [32] .
Cifrul Hill standard , compus din n ecuații liniare, poate fi spart în textul simplu ales prin interceptarea n² de perechi de caractere de mesaj și text cifrat de către un criptoanalist. [25]
Unul dintre primele dispozitive de criptare a fost inventat în secolul al XV-lea și a înlocuit cifrul Caesar . Autorul său a fost arhitectul italian Leon Battista Alberti , care a adus o contribuție semnificativă la dezvoltarea cifrurilor de substituție. Acest dispozitiv era format din două discuri de cupru de dimensiuni diferite, fixate cu un ac. De-a lungul marginilor fiecărui disc a fost aplicat un alfabet. Ambele discuri s-ar putea roti independent unul de celălalt, potrivindu-se astfel literele textului simplu și ale textului cifrat. Discul Alberti a fost utilizat pe scară largă timp de cinci secole, inclusiv în timpul războiului civil american [33] .
La începutul secolului XX, după invenția radioului, a devenit necesară dezvoltarea mașinilor de criptare pentru uz militar și comercial. Ca bază pentru aceste dispozitive s-au folosit cifruri de substituție polialfabetică, precum și principiul de funcționare al discului de criptare [34] .
Pentru a obține un semnal criptat, a fost folosit un disc gol cu contacte aplicate pe ambele părți. Textul obținut ca urmare a criptării depindea de comutația discului și de poziția unghiulară a acestuia. Acest tip de dispozitive de criptare a fost numit ulterior mașini rotative [34] [35] .
Mașinile rotative au fost folosite de diferite țări în timpul celui de-al Doilea Război Mondial . Cele mai cunoscute dintre ele au fost: mașina americană SIGABA , germanul ENIGMA , englezul TYPEX și japonezul PURPLE. [36]
Sistemele de criptare rotativă aveau două tipuri de chei. Lipirea între contactele rotorului stabilește o cheie permanentă. Pentru a înlocui cheile permanente, a fost necesar să se actualizeze toate mașinile de criptare lansate ale acestui model, care este dificil de implementat în practică. Cheile variabile se schimbau adesea în fiecare zi și erau determinate de un set de rotoare și de poziția lor inițială. [37]
În ciuda înlocuirii cifrurilor de substituție cu cifrurile bloc, pad- urile unice sunt încă folosite la nivel de stat în timpul nostru. Sunt folosite pentru a oferi canale de comunicare top secret. Potrivit zvonurilor, linia telefonică dintre șefii URSS și Statele Unite a fost criptată folosind un tampon unic și, foarte probabil, încă mai există. Blocnotesele de unică folosință sunt folosite de spioni din diferite state pentru a ascunde informații deosebit de importante. Astfel de mesaje nu pot fi decriptate în absența unei chei scrise într-un notebook, indiferent de puterea de calcul a computerului. [38] [12]