M. Joldoş SSA. Îndrumător pentru laborator Criptografie

Algoritmii de cifrare şi descifrare Vigenere (polialfabetic) explicaŃi Cifrul Cezar Cifrul Vigenere este o variaŃie a cifrului Cezar, cunsocut şi sub numele de cifru de deplasarel. Un cifru Cezar ia literele din alfabet şi le deplasează cu numărul de poziŃii indicat de cheie. Alfabetul este numerotat de la 0 la 25. Tabelul 1 prezintă alfabetul şi numerele corespunzătoare.

a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25

Tabelul 1: Alfabetul şi numerele corespunzătoare pentru cifrul Cezar. Apoi se alege o cheie/. Cheia este un întreg, k, unde 0 ≤ k ≤ 25. Cheia poate şi corespunde unei litere. Textul cifrat, c, este produs din textul clar, p, prin c = p + k (mod 26). Dacă litera din textul clar a fost c, iar cheia a fost 3, atunci textul cifrat este 2 + 3 = 5 = f. Spre exemplu, să presupunem că am dori să trimitem cuiva un mesaj cifrat. Am putea hotărî să deplasăm toate literele din alfabet cu trei poziŃii. Mesajul şi textul calr sunt arătate mai jos:

Text clar: This is an example of the Caesar cipher Text cifrat: wklvlvdqhadpsohriwkhfdhvduflskhu

Toate literele au fost schimbate şi nu se pot deduce cu uşurinŃă. Cifrarea Cezar este o metodă de cifrare uşoară, dar produce un cod uşor de spart. Se poate afla mesajul încercând toate cele 26 de combinaŃii posibile. Cifrul Vigenere La fel ca cifrul Cezar, cifrul Vigenere deplasează literele, dar, spre deosebire de acesta nu se poate sparge uşor în 26 combinaŃii. Cifrul Vigenere foloseşte o deplasare multiplă. Cheia nu este constituită de o singură deplasare, ci de mai multe. Cheia este constituită din câŃiva întregi ki, unde 0 ≤ ki ≤ 25. Aceşti întregi pot fi, de exemplu, , k = (21, 4, 2 19, 14, 17). Această cheie ar provoca deplasare primei litere cu 21, c1 = p1 + 21 (mod 26), a celei de a doua cu 4, c2 = p2 + 4 (mod 26), ş.a.m.d. până la sfârşitul cheii şi apoi de la început, din nou. Cheia este de obicei un cvuvânt, pentru a fi mia uşor de memorat – cheia de mai sus corespunde cuvântului "vector". Metoda cu deplasare multiplă oferă protecŃie suplimentară din două motive. Primul motiv este că ceilalŃi nu cunosc lungimea cheii. Cel de al doilea este că numărul de soluŃii posibile creşte. De exemplu, pentru lungimea cheii = 5, numărul de combinaŃii care ar fi necesare la căutare exhaustivă ar fi 265 = 11,881,376. Cifrul Vigenere a fost spart folosind altceva decât forŃa brută (vezi mai jos). Un exemplu de cifru Vigenere:

Textul clar: This is an example of the Vigenere Cipher Cheia: vector Textul cifrat: olklwjvrgqodkpghtkcixbuviitxqzklgk

Decriptarea

Metoda de descifrare folosită pentru cifrul Vigenere este asemănătoare metodei de cifrare. DiferenŃa constă în faptul că se scade cheia din textul cifrat, pi = ci - ki (mod 26). Mai jos este dat un exemplu:

Textul cifrat: olklwjvrgqodkpghtkcixbuviitxqzklgk Cheia: vector Textul clar: thisisanexampleoftheVigenerecifrul

Tot ce rămâne de făcut este să se insereze spaŃiile la locul potrivit..

M. Joldoş SSA. Îndrumător pentru laborator Criptografie

EquaŃii

Cifrare: Cheia este constituită din câŃiva întregi, ki, unde 0 ≤ ki ≤ 25. K = (k1, k2, k3, … , ki) Lungimea cheii este la alegere.

ci = pi + ki (mod 26) Descifrare:

Trebuie cunsocută cheia. pi = ci - ki (mod 26)

Cum se sparge cifrul Vigenere Cifrul Vigenere codeză un bloc sau o mulŃime de litere deodată. Lungimea cheii determină lungimea blocului. Cum cifrul Vigenere este o variaŃie a cifrului de deplasare, putem folosi o variaŃie a atacului bazat pe contorizarea frecvenŃelor de apariŃie pentru a găsi cheia şi algoritmul.. Folosind acest atac, applet-ul Vigenere Cipher generează o lista de chei posibile pe care utilizatorul să le folosească pentru descifratea textului codat. În medie, cheia corectă se găseşte între primele 25-30 de chei afişate. Totuşi, pot fi situaŃii în care cheia corectă să nu fie între primele 30 sau chiar de loc în listă. Pentru explicaŃie vezi "Puncte slabe". Atacul bazat pe frecvenŃă Un atac bazat pe frecvenŃa de apariŃie a literelor într-o limbă exploatează faptul că unele dintre literele limbii engleze (la fel pentru limba română) apar mai des decât altele (frecvenŃele nu sunt egale). Spre exemplu, litera 'e' apare mult mai des decât litera 'z'. Tabelul de mai jos arată frecvenŃele literelor din limba engleză (reprodus după Trappe, Wade şi Washington, Lawrence; Introduction to Cryptography with Coding Theory; 2002, Prentice Hall, Upper Saddle River, NJ).

Tabelul 2 – FrecvenŃa literelor în limba engleză

Presupunând că textul clar este în engleză, cineva care foloseşte atacul bazat pe frecvenŃă va lua textul cifrat şi va număra apariŃiile tuturor literelor. Apoi, folosind cunoştinŃele despre frecvenŃa de apariŃie a literelor în limba engleză, persoana respectivă ar putea concluziona că cea mai frecventă literă din textul cifrat corespunde literei 'e' în limba engleză ş.a.m.d., descifrând astfel mesajul. Cu toate acestea, acest lucru e mai uşor de spus decât de făcut. Dacă numărul de apariŃii are valori apropiate pentru litere diferite, nu există text cifra suficient pentru a obŃine cu acurateŃe contoare de frecvenŃă. În această situaŃie, potrivirea literelor din textul cifrat are o şansă mai mare să fie incorectă. Ca rezultat, acest atac este util doar în cazul cifrurilor de deplasare şi unele variaŃii ale acestora, unde diferenŃele de frecvenŃe între litere sunt mari. Pasul 1 – aflarea lungimii cheii Pentru a determina lungimea cheii, numărăm apariŃiile literelor care se potrivesc la compararea textului cifrat cu sine însuşi deplasat cu un număr de poziŃii (lungimea potenŃiala a cheii). Spre exemplu, dacă texul cifrat a fost obŃinut prin apăsare butonului “Sample Ciphertext #1” şi efectuăm comparaŃia pentru o deplasare de 3, avem:

ocwyikoooniwugpmxwktzdwgtssayjzwy ocwyikoooniwugpmxwktzdwgtssayjzwyemd emdlbnqaaavsuwdvbrflauplooubfgqhg lbnqaaavsuwdvbrflauplooubfgqhgcsc *

M. Joldoş SSA. Îndrumător pentru laborator Criptografie

cscmgzlatoedcsdeidpbhtmuovpiekifp mgzlatoedcsdeidpbhtmuovpiekifpimf * * * * imfnoamvlpqfxejsmxmpgkccaykwfzpyu noamvlpqfxejsmxmpgkccaykwfzpyuavt avtelwhrhmwkbbvgtguvtefjlodfefkvp elwhrhmwkbbvgtguvtefjlodfefkvpxsg xsgrsorvgtajbsauhzrzalkwuowhgedef rsorvgtajbsauhzrzalkwuowhgedefnsw * * nswmrciwcpaaavogpdnfpktdbalsisurl mrciwcpaaavogpdnfpktdbalsisurlnps * npsjyeatcuceesohhdarkhwotikbroqrd jyeatcuceesohhdarkhwotikbroqrdfmz fmzghgucebvgwcdqxgpbgqwlpbdaylooq ghgucebvgwcdqxgpbgqwlpbdaylooqdmu * dmuhbdqgmyweuik

hbdqgmyweuik Avem nouă coincidenŃe. Dacă continuăm pentru toate deplasările posibile (de la 1 la 311), aflăm că cel mai mare număr de coincidenŃe apare pentru o deplasare cu 6. Aceasta ar fi estimarea noastră pentru lungimea cheii. Pasul 2 – aflarea cheii După aflarea lungimii cheii, avem nevoie de frecvenŃele literelor în textul cifrat. Trebuie să creăm un tabel asemănător Tabelului 2. Facem acest lucru numărând frecvenŃa fiecărei a n-a literă (n este determinat de lungimea cheii) şi împărŃirea contoarelor respectivi prin numărul total de litere. Continuând cu exemplu nostru, cum avem lungimea cheii 6, vom face 6 tabele. Pentru primul tabel, începem cu prima literă din textul cifrat şi numărăm frecvenŃele fiecărei a 6-a litere (numărăm apariŃiile primei litere, apoi a celei de a 7-a, apoi a celei de a 13-a etc.). Pentru cel de al doilea tabel începem cu a 2-a literă din textul cifrat numărăm frecvenŃele fiecărei a 6-a litere (numărăm apariŃiile celei de a 2-a litere, apoi a celei de a 8-a, apoi a celei de a 14-a etc.). repetăm până avem şase tabele (W1-W6). Ultima tabelă este după cum urmează:

Tabelul 3 – Cea de a 6-a tabelă

Aceste 6 tabele ne vor ajuta să găsim fiecare dintre cele 6 litere ale cheii. Dar, înainte de a face acest lucru, trebuie să creăm şi un table cu frecvenŃele fiecărora dintre cele 26 litere ale limbii engleze (în total 26: A1-A26). Tabelul 2 este pentru litera 'a'. Pentru a obŃine tabelele pentru celelalte litere, deplasăm pur şi simplu valorile din tabelul 1 cu valoarea corespunzătoare. De exemplu, pentru tabelul literei 'c', deplasăm valorile din Tabelul 2 cu doi. Tabelul literei 'c' ar fi:

Tabelul 4 – Tabel de frecvenŃe pentru litera 'c'

Dupa obŃinerea celor 26 tabele, scriem tabelele ca vectori şi luăm produsul fiecăruia dintre W-uri cu A-urile. Exemplul de mai jos ia W1 în produs cu toate A-urile.

W1 • A1 = WA1 W1 • A2 = WA2

M. Joldoş SSA. Îndrumător pentru laborator Criptografie

.

.

. W1 • A26 = WA26

Cea mai mare valoare a produsului • va fi litera pentru acel loc din cheie. Folosindu-ne exemplul, W6 • toate A-urile rezultă în:

W6 • A1 = 0.0313 (Tabelul pentru “a”) W6 • A2 = 0.0329 (Tabelul pentru “b”) W6 • A3 = 0.0523 (Tabelul pentru “c”) W6 • A4 = 0.0472 (Tabelul pentru “d”) W6 • A5 = 0.0258 (Tabelul pentru “e”) W6 • A6 = 0.0329 (Tabelul pentru “f”) W6 • A7 = 0.0491 (Tabelul pentru “g”) W6 • A8 = 0.0392 (Tabelul pentru “h”) W6 • A9 = 0.0310 (Tabelul pentru “i”) W6 • A10 = 0.0325 (Tabelul pentru “j”) W6 • A11 = 0.0398 (Tabelul pentru “k”) W6 • A12 = 0.0301 (Tabelul pentru “l”) W6 • A13 = 0.0384 (Tabelul pentru “m”) W6 • A14 = 0.0358 (Tabelul pentru “n”) W6 • A15 = 0.0404 (Tabelul pentru “o”) W6 • A16 = 0.0395 (Tabelul pentru “p”) W6 • A17 = 0.0348 (Tabelul pentru “q”) W6 • A18 = 0.0372 (Tabelul pentru “r”) W6 • A19 = 0.0637 (Table for “s”) W6 • A20 = 0.0386 (Tabelul pentru “t”) W6 • A21 = 0.0274 (Tabelul pentru “u”) W6 • A22 = 0.0348 (Tabelul pentru “v”) W6 • A23 = 0.0485 (Tabelul pentru “w”) W6 • A24 = 0.0294 (Tabelul pentru “x”) W6 • A25 = 0.0417 (Tabelul pentru “y”) W6 • A26 = 0.0467 (Tabelul pentru “z”)

Cea mia mare valoare este 0.0637, adică W6 • A19 sau tabelul pentru “s”. Aşa că, cea de a 6-a literă din cheie este “s”. Folosind acest proces pentru a afla celelalte litere din cheie va da cheia “holmes”. Folosind o variaŃie a atacului pe baza frecvenŃei putem afla cheia pentru “Sample Cipher Text#1.” Puncte slabe Problemele acestei variante de atac bazat pe frecvenŃă sunt similare atacului bazat pe frecvenŃă original. Raportul text cifrat / cheie trebuie să fie suficient de mare. Cu late cuvinte, e nevoie de suficient text pentru a determina frecvenŃele. Altfel nu se poate afla cheia corectă. Acest lucru se poate testa folosind “Sample Plaintext #3” cifrat cu cheia “vector”. Applet0ul nu va putea afla cheia din cauza lipsei de text cifrat suficient. Acelaşi test poate fi efectuat pe orice alt exemplu de text clar. Doar luaŃi o cheie lungă. Acest punct slab apare la pasul al 2-lea al algoritmului de spargere a cifrului. Algoritmul are un punct slab şi la pasul 1. Cel mai mare contor de coincidenŃe ar trebui să dea lungimea cheii. Dar nu întotdeauna se întâmplă astfel. Eroarea este legată de supoziŃia pe care am făcut-o relativ la limba engleză. Am presupus că cea mai mare frecvenŃă va fi în mod natural aceea a literei “e” fiindcă “e” apare cel mai frecvent în engleză. Dar aceasta nu este adevărat întotdeauna. Sunt ocazii în care un bloc de text nu are “e” ca literă cea mai frecventă. Aceeaşi excepŃie există şi pentru supoziŃia că cel mai mare contor de coincidenŃe ne va da lungimea cheii. Sunt situaŃii când nu este aşa. Applet-ul rezolvă slăbiciunea de la pasul 1 prin oferirea unei liste de chei posibile. Cheile sunt listate în ordinea probabilităŃii lor. Applet-ul, nu rezolvă însă slăbiciunea de la pasul 2. Fără suficient text cifrat pentru a obŃine un contor de frecvenŃe corect, literele din cheie nu vor fi aflate, chiar dacă lungimea cheii este aflată şi e corectă. În general, cheia corectă se va afla între primele 25-30 chei din listă.