Cifrul Vigenère
Cifrul Vigenère este cel mai simplu dintre cifrele polialfabetice . Se bazează pe utilizarea unui vers pentru a controla alternanța alfabetelor de substituție, concept introdus pentru prima dată de Giovan Battista Bellaso în Figura Domnului Giovan Battista Belaso din 1553.
Istorie
Publicat în 1586, cifrul lui Blaise de Vigenère a fost considerat inatacabil de secole, bucurându-se de o reputație în mare parte nemeritată, fiind mult mai slabă decât alte cifre polialfabetice anterioare, cum ar fi discul cifrat al lui Alberti sau cifrele lui Bellaso . [ citație necesară ] O faimă care a durat mulți ani chiar și după descoperirea primei metode de criptanaliză de către Charles Babbage și formalizarea ulterioară de către maiorul Friedrich Kasiski : Metoda Kasiski din 1863.
Metoda
Metoda poate fi considerată o generalizare a cifrului lui Cezar ; în loc să deplaseze întotdeauna litera pentru a fi criptată de același număr de locuri, este mutată de un număr variabil, dar repetat de locuri, determinat pe baza unui cuvânt cheie, care să fie convenit între expeditor și destinatar și să fie scris în mod repetat sub mesajul, caracter cu caracter; cheia a fost numită și vierme, pentru că, fiind în general mult mai scurtă decât mesajul, trebuie repetată de mai multe ori sub aceasta, ca în exemplul următor:
Text simplu - RAPORT IMEDIAT Vierme - VERMEVERMEVERMEVE Ciphertext - MEGBSMXFUQHIUUEOS
Textul cifrat se obține prin deplasarea literei clare cu un număr fix de caractere, egal cu numărul ordinal al literei corespunzătoare a viermelui. De fapt, se realizează o sumă aritmetică între ordinalul clarului (A = 0, B = 1, C = 2 ...) și cel al viermelui; dacă treci ultima literă, Z, o iei de la A, conform logicii aritmeticii finite.
Avantajul față de cifrele mono-alfabetice (cum ar fi cifrul lui Caesar sau cele pentru înlocuirea literelor cu simboluri / alte litere) este evident: textul este cifrat cu n alfabete cifrate. În acest fel, aceeași literă este criptată (dacă se repetă consecutiv) de n ori; prin urmare, aceasta face criptanaliza textului cifrat mai complexă.
Evident, o funcție matematică poate fi utilizată pentru criptare și decriptare; în ambele vom folosi întotdeauna aceleași litere:
Număr prima literă a cifrului (A) = 0
Numărul ultimei litere a cifrului (Z) = 25
L = Lungimea cifrului = Numărul de elemente ale setului (26)
a = Numărul literei cuvântului în Clear (0-25)
b = Cuvânt cheie / număr de literă vierme (0-25)
c = Numărul literei cuvântului criptat (0-25)
Pentru a cripta : n = a + b (mod 26)
Pentru a decripta : n = c - b + 26
r [parte întreagă a numărului] = n / L
F (x) = n - (L * r) = Numărul literei cuvântului în Clear / Encrypted (0-25)
Funcția se bazează pur și simplu pe adăugarea / scăderea numerelor literelor și împărțirea la lungimea cifrului pentru a obține numărul de literă dorit. Pentru a obține ÎNTOTDEAUNA un număr pozitiv n și pentru decriptare, ca o scădere, folosiți doar aritimul simplu pentru a adăuga 26, deoarece va fi apoi eliminat datorită lui r .
Exemplu de criptare cu primele două litere din textul / exemplul cheie anterior.
L = 26
a [R] = 17
b [V] = 21
n = 17 + 21 = 38
r = 38/26 = 1,461 ... = 1
F (x) = 38 - (26 * 1) = 38 - 26 = 12
F (12) = M
-------------------------------------------------- -------
L = 26
a [A] = 0
b [E] = 4
n = 0 + 4 = 4
r = 4/26 = 0,153 ... = 0
F (x) = 4 - (26 * 0) = 4 - 0 = 4
F (4) = E
Exemplu de decriptare cu primele două litere ale textului / exemplului cheie anterior.
L = 26
b [V] = 21
c [M] = 12
n = 12 - 21 + 26 = 17
r = 17/26 = 0,653 ... = 0
F (x) = 17 - (26 * 0) = 17 - 0 = 17
F (17) = R.
-------------------------------------------------- -------
L = 26
b [E] = 4
c [E] = 4
n = 4 - 4 + 26 = 26
r = 26/26 = 1 = 1
F (x) = 26 - (26 * 1) = 26 - 26 = 0
F (0) = A
Masa Vigenère
Pentru a simplifica cifrarea, Vigenère a propus utilizarea următoarei „matrice” pătrate, compusă din alfabete sortate și deplasate. Dacă doriți să criptați, cu cheia exemplului anterior, litera „R” a cuvântului relație, găsiți doar litera „R” în primul rând, identificând coloana relativă. Apoi, găsiți „V”-ul „viermelui” în prima coloană pentru a găsi rândul, identificând, prin intersecție, litera corectă de utilizat.
ABCDEFGHIJKLMNOPQ R STUVWXYZ BCDEFGHIJKLMNOPQR S TUVWXYZA CDEFGHIJKLMNOPQRS T UVWXYZAB DEFGHIJKLMNOPQRST U VWXYZABC EFGHIJKLMNOPQRSTU V WXYZABCD FGHIJKLMNOPQRSTUV W XYZABCDE GHIJKLMNOPQRSTUVW X YZABCDEF HIJKLMNOPQRSTUVWX Y ZABCDEFG IJKLMNOPQRSTUVWXY Z ABCDEFGH JKLMNOPQRSTUVWXYZ TO BCDEFGHI KLMNOPQRSTUVWXYZA B CDEFGHIJ LMNOPQRSTUVWXYZAB C DEFGHIJK MNOPQRSTUVWXYZABC D EFGHIJKL NOPQRSTUVWXYZABCD ȘI FGHIJKLM OPQRSTUVWXYZABCDE F GHIJKLMN PQRSTUVWXYZABCDEF G HIJKLMNO QRSTUVWXYZABCDEFG H IJKLMNOP RSTUVWXYZABCDEFGH I JKLMNOPQ STUVWXYZABCDEFGHI J KLMNOPQR TUVWXYZABCDEFGHIJ K LMNOPQRS UVWXYZABCDEFGHIJK L MNOPQRST VWXYZABCDEFGHIJKL M NOPQRSTU WXYZABCDEFGHIJKLM N OPQRSTUV XYZABCDEFGHIJKLMN SAU PQRSTUVW YZABCDEFGHIJKLMNO P QRSTUVWX ZABCDEFGHIJKLMNOP Q RSTUVWXY
Cum să decriptați mesajul
Pentru a decripta mesajul, destinatarul trebuie pur și simplu să utilizeze metoda inversă (mai degrabă scade decât adaugă); referindu-vă la exemplul de mai sus, veți avea:
Ciphertext - MEGBSMXFUQHIUUEOS Vierme - VERMEVERMEVERMEVE Text clar - RAPORT IMEDIAT
Folosind tabelul pătrat va fi posibil să se descifreze primul „M” căutându-l în rândul literei corespunzătoare a viermelui, V; coloana unde se găsește M are, prin urmare, în partea de sus litera clară, R.
Criptanaliza Vigenère
După cum am menționat, acest cifru s-a bucurat de reputația de a fi un cifru inatacabil de trei secole; în 1863 colonelul prusac Friedrich Kasiski a publicat o primă metodă de decriptare; mai târziu, au fost găsite alte câteva metode eficiente de cracare a acestui cifru. În realitate, cifrul Vigenère a fost deja forțat de Charles Babbage, dar rezultatele cercetărilor sale nu au fost niciodată publicate.
Slăbiciunea Vigenère constă în a fi, de fapt, un set de n cifrări Cezar, unde n este lungimea cheii; dacă criptanalistul poate determina lungimea cheii (în cazul nostru, n ) decriptarea devine foarte simplă.
Pentru a face acest lucru, metodele statistice pot fi folosite pentru a găsi n , și ulterior se aplică analiza de frecvență pentru fiecare alfabet cifrat. Adică, dacă avem cheia WORM, este suficient să analizăm frecvențele pentru toate literele criptate de V, apoi pentru cele criptate de E etc. Prin urmare, primul, al șaselea, al unsprezecelea etc. litera va avea același alfabet cifrat. Cea mai complicată parte este, prin urmare, să aflați lungimea cheii de criptare, chiar dacă nu este imposibil. De fapt, în textul cifrat, dacă cheia utilizată este scurtă, vor exista probabil serii de litere repetate. Aceste serii de litere, dacă sunt suficient de lungi (5-6 caractere), vor fi generate probabil din același cuvânt simplu. Apoi va fi suficient să calculați distanța dintre un cuvânt și altul și lungimea repetării pentru a reveni la lungimea n a tastei. Făcând acest lucru, este posibil să înțelegeți care litere utilizează primul alfabet cifrat, care al doilea și așa mai departe, continuând apoi cu analiza frecvențelor pentru fiecare alfabet.
Pentru a depăși această problemă, am încercat să alegem taste foarte lungi (și, prin urmare, nu repetate sau doar minim). Procedând astfel, există mult mai multe alfabete cifrate și probabilitatea repetărilor este mai mică.
Dacă utilizați o cheie de lungime comparabilă cu textul, criptanaliza devine dificilă, dar nu imposibilă, deoarece se poate baza pe natura textului folosit ca cheie.
În limbile naturale, de fapt, fiecare caracter conține doar o cantitate limitată de entropie și diferitele caractere, grupuri de caractere și cuvinte au, prin urmare, probabilități diferite de apariție, ceea ce face ca cifrarea să fie nesigură, fiind posibilă, în consecință, o analiză statistică a textului cifrat care permite pentru a elimina progresiv, caracter cu caracter sau grup cu grup, cele mai puțin probabile soluții de perechi (text simplu plus cheie) în favoarea celor mai probabile care conduc la recuperarea unei părți de text simplu, sau cheie, cu semnificație completă.
Dezvoltarea calculelor automate începând din a doua jumătate a secolului al XIX-lea a făcut ca o astfel de analiză statistică să fie extrem de eficientă și practicabilă, făcând cifrele bazate pe chei în limbaje naturale definitiv învechite (au existat numeroase exemple de cifre încălcate de Charles Babbage ).
Mai mult, dacă pentru comoditate este folosit un text cunoscut ca cheie, recuperarea unor porțiuni din acesta face posibilă identificarea textului-cheie cu compromisul definitiv al figurii; acest factor devine extrem de important dacă o parte a textului simplu este cunoscută ( atac cu text simplu ) sau poate fi aleasă de atacator ( atac cu text simplu ales ) și, în consecință, devine banală recuperarea porțiunii cheii asociate acestuia.
Următorul pas logic a fost de a dota fluxul de date al cheii cu astfel de caracteristici încât să reziste analizei statistice a textului cifrat și recuperării cheii din porțiuni ale acestuia; în secolul următor, această idee a condus la dezvoltarea unor funcții matematice din ce în ce mai avansate, care acopereau complet caracteristicile statistice ale textului simplu, dacă sunt combinate cu acesta chiar și cu o funcție foarte simplă (de exemplu, xor între fiecare element de intrare și fiecare element al tastei), fiind ieșirile distribuite într-o manieră pseudoaleatorie (și fără a prezenta periodicitate pentru o lungime cel puțin egală cu cea a textului simplu) și care au împiedicat, cunoscută o cantitate arbitrară de ieșire, să prezică ieșirile ulterioare sau anterioare (o caracteristică evident incompatibilă cu un text în natură precum cheile folosite în cifrul Vigenère).
Aceste funcții se numesc PRNG, generatoare de numere pseudorandom, atunci când prima prepoziție este verificată și când este verificată și a doua prepoziție, acestea sunt numite criptografice puternice și este posibil să se utilizeze aceste funcții ca flux de cifrare.
Dacă fluxul de date al cheii nu este pseudo-aleator, ci strict aleatoriu, generat de exemplu de un detector (care nu este accesibil atacatorului) al fenomenelor aleatorii (precum dezintegrări radioactive, zgomot electric sau termic etc.), toate sunt verificate condițiile anterioare de rezistență la atacuri:
- nu există periodicitate;
- nu există caracteristici statistice utile nici în cheie, nici în textul cifrat rezultat;
- nu este posibil să se extindă cunoașterea cheii pornind de la o cantitate arbitrară de cheie cunoscută.
Limita PRNG-urilor este dată de faptul că aceste proprietăți statistice (perioada, uniformitatea statistică a ieșirii, corelația care nu poate fi exploatată din punct de vedere computerizat al ieșirilor) trebuie demonstrate, în plus, fiecare funcție nu poate genera toate cheile posibile, ci doar un număr (extrem de mare , astfel încât practic să nu permită precomputarea de către atacator) determinată de natura funcției în sine, prin urmare aceste funcții pot fi întotdeauna forțate cu un număr de încercări care nu depășesc numărul de taste care pot fi generate.
Dimpotrivă, pentru un RNG aceste proprietăți statistice sunt adevărate prin definiție și, în plus, întrucât un RNG poate genera toate ieșirile posibile ale lungimii dorite într-un mod echiprobabil, rezultă că fiecare ieșire de această lungime este, la fel de probabilă, textul clar corespunzător. , nepermițând atacatorului nicio verificare a acurateței decriptării.
Vernam, pornind de la o altă reinvenție a cifrului Vigenère, a venit apoi în anii '20 pentru a încorpora aceste noțiuni în cifrul său și Claude Shannon a adus în 1949 o demonstrație matematică a modului în care un cifru cu aceste caracteristici (cheie generată de un RNG, cel puțin ca atâta timp cât textul, niciodată reutilizat: One Time Pad) este teoretic inatacabil ( cifru perfect ).
Cunoscutul cifru Vernam este de acest tip, folosit ca bază a unor mașini de cifrat și, de asemenea, pe faimoasa linie roșie dintre Moscova și Washington .
Bibliografie
- Luigi Sacco , Manual de criptografie , Roma 1947
- Andrea Sgarro , Criptografie , Padova 1993, ISBN 88-7021-640-3
- Caterina Marrone, Semnele înșelăciunii. Semiotica criptografiei , Alternative Press & Graffiti, Viterbo, 2010, pp. 199, ISBN 978-88-6222-132-0
- Simon Singh , Codes & Secrets , Milano 2011, ISBN 978-88-17-12539-0
- Cine se teme de Vigenere? ( JPG ), în MCmicrocomputer , n. 101, Roma, Technimedia, noiembrie 1990, pp. 179-183, ISSN 1123-2714 .
linkuri externe
- Implementarea Java a unora dintre cele mai faimoase cifre din istorie, inclusiv cea a Vigenère. , la angelusworld.com . Adus la 19 august 2007 (arhivat din original la 30 septembrie 2007) .
- Implementarea Visual Basic a unor cifre monoalfabetice și polialfabetice, inclusiv cea a Vigenère ( ZIP ), pe furo.altervista.org . Adus la 8 aprilie 2014 (arhivat din original la 9 aprilie 2014) .
