1.3. Vigenèreova šifra

Francuski diplomat Blaise de Vigenère je 1586. godine objavio knjigu "Traicte de Chiffres" u kojoj se nalazilo sve što se u to vrijeme znalo o kriptografiji (ali gotovo ništa o kriptoanalizi). U njoj je opisano više originalnih polialfabetskih sustava. Sustav koji se danas naziva Vigenèreova šifra (iako ju je prvi opisao Giovan Battista Bellaso 1553. godine) definiran je na sljedeći način.

Neka je m fiksan prirodan broj. Definiramo P = C = K = (Z26)m. Za ključ K = (k1, k2, ... , km), definiramo eK(x1, x2, ... , xm) = (x1 +26 k1, x2 +26 k2, ... , xm +26 km), dK(y1, y2, ... , ym) = (y1 -26 k1, y2 -26 k2, ... , ym -26 km).

Dakle, slova otvorenog teksta pomičemo za k₁, k₂, ... ili k_m mjesta, u ovisnosti o tome na kojem se mjestu u otvorenom tekstu nalaze (preciznije, pomak ovisi o ostatku koji dobijemo kada poziciju slova podijelimo s duljinom ključa m). Kod ove su šifre osnovni elementi otvorenog teksta i šifrata "blokovi" od po m slova. No, šifriranje se zapravo provodi "slovo po slovo", pa ovdje nije nužno nadopuniti zadnji blok ako broj slova u otvorenom tekstu nije djeljiv s m.

Primjer 1.5: Neka je m = 4 i ključna riječ   BROJ. Njezin numerički ekvivalent je ključ K = (1, 17, 14, 9). Pretpostavimo da je otvoreni tekst   KRIPTOLOGIJA. Šifriranje se provodi na sljedeći način:

        10  17   8  15      19  14  11  14       6   8   9   0 
    
         1  17  14   9       1  17  14   9       1  17  14   9     
  +26  _________________________________________________________

        11   8  22  24      20   5  25  23       7  25  23   9

Primjer 1.5 može se ilustrirati i ovako

    ključ         B R O J B R O J B R O J 
otvoreni tekst    K R I P T O L O G I J A 
    šifrat        L I W Y U F Z X H Z X J

Primjer 1.6: Sve isto kao u Primjeru 1.5, ali s autoključem.

U šifriranju ćemo koristiti tzv. Vigenèreov kvadrat Ako npr. slovo K treba šifrirati ključem B, onda pogledamo stupac koji počinje s K i redak koji počinje s B. U presjeku je šifrat L. Dobivamo:

    ključ         B R O J K R I P T O L O 
otvoreni tekst    K R I P T O L O G I J A 
    šifrat        L I W Y D F T D Z W U O

Vigenèreova šifra je jedan od najpopularnijih kriptosustava u povijesti. Spomenimo da je bila u širokoj uporabi tijekom Američke revolucije, krajem 18. stoljeća, a korištena je i u Američkom građanskom ratu. Čak je 1917. u uglednom časopisu "Scientific American" objavljeno da je ovu šifru "nemoguće razbiti". To naravno nije bilo točno, jer su kriptoanalitičari već pola stoljeća prije toga poznavali metode za napad na Vigenèreovu šifru.

Recimo sada nešto o kriptoanalizi Vigenèreove šifre. Prvi korak je određivanje duljine ključne riječi. Prikazat ćemo dvije metode. Prva metoda se zove Kasiskijev test i uveo ju je Friedrich Kasiski 1863. godine, a koristio ju je otprilike u isto vrijeme i Charles Babbage. Metoda se zasniva na činjenici da će dva identična segmenta otvorenog teksta biti šifrirana na isti način ukoliko se njihove početne pozicije razlikuju za neki višekratnik od m, gdje je m duljina ključa. Obrnuto, ako uočimo dva identična segmenta u šifratu, duljine barem 3, tada je vrlo vjerojatno da oni odgovaraju identičnim segmentima otvorenog teksta (podudarnost odsječaka duljine 2 lako može biti i slučajna, dok je kod odsječaka veće duljine to puno manje vjerojatno).

U Kasiskijevom testu u šifrati tražimo parove identičnih segmenata duljine barem 3, te (ako takvi postoje) zabilježimo udaljenosti između njihovih početnih položaja. Ako na takav način dobijemo udaljenosti d₁, d₂, ... , onda je razumna pretpostavka da m dijeli većinu d_i-ova. Nakon što odredimo m, nalazimo se u sličnoj situaciji kao kod Cezarove šifre. Naime, ako pogledamo samo ona slova koja su šifrirana pomakom za k₁ slova (a ako znamo m, onda znamo i koja su to slova), onda su ona šifrirana običnom Cezarovom šifrom. Situacija je ipak nešto teža nego kod obične Cezarove šifre, zbog toga što to ovdje nisu uzastopna slova u otvorenom tekstu, pa njihovim dešifriranjem nećemo dobiti smisleni tekst. Zato ćemo opisati još jednu metodu za razbijanje Vigenèreove šifre.

Druga metoda za određivanje duljine ključa koristi tzv. indeks koincidencije. Taj je pojam uveo 1920. godine William Friedman u knjizi "Indeks koincidencije i njegove primjene u kriptografiji", koja se smatra jednom od najvažnijih publikacija u povijesti kriptologije.

Definicija 1.2: Neka je x = x1x2 ... xn niz od n slova. Indeks koincidencije od x, u oznaci Ic(x), se definira kao vjerojatnost da su dva slučajna elementa iz x jednaka. Neka su f0, f1, ... , f25 redom (apsolutne) frekvencije od A, B, C, ... , Z u x. Dva elementa iz x možemo odabrati na n(n-1)/2 načina, a za svaki i = 0, 1, ... , 25 postoji fi (fi-1)/2 načina odabira dvaput i-tog slova. Stoga vrijedi formula Ic(x) = ∑i  fi(fi-1) / n(n-1).

Pretpostavimo sada da x predstavlja neki tekst na hrvatskom jeziku. Označimo očekivane vjerojatnosti pojavljivanja slova A, B, ... , Z u hrvatskom jeziku redom s p₀, p₁, ... , p₂₅ (vidi ranije navedene frekvencije slova u promilima). Ako je n dovoljno velik, za očekivati je da će vrijediti

I_c(x) ≈ ∑_i  p_i² ≈ 0.064

Pretpostavimo sada da imamo šifrat y = y₁y₂ ... y_n koji je dobiven Vigenèreovom šifrom. Rastavimo y na m podnizova z₁, z₂, ... , z_m tako da y napišemo, po stupcima, u matricu dimenzija m × (n/m). (Ako m ne dijeli n, možemo nadopuniti y na prozvoljan način ili promatrati "krnju matricu" s nepotpunim zadnjim stupcem.) Redci ove matrice su upravo traženi podnizovi z₁, z₂, ... , z_m. Ako je m jednak duljini ključne riječi, onda su elementi istog retka matrice šifrirani pomoću istog slova ključa. Na primjer, prvi redak sadrži prvo, (m+1)-vo, (2m+1)-vo, ... slovo šifrata, a sva su ta slova šifrirana pomoću k₁. Zato bi svi indeksi koincidencije I_c(z_i) trebali biti približno jednaki 0.064. S druge strane, ako m nije duljina ključne riječi, onda će z_i-ovi izgledati više-manje slučajni nizovi slova, budući su dobiveni pomacima pomoću različitih slova ključa. Primijetimo da za potpuno slučajni niz imamo

I_c ≈ 26 · (1/26)² = 1/26 ≈ 0.038.

Primjer 1.7: Dekriptirati šifrat dobiven Vigenèreovom šifrom:

      GSIQITUKQIEAOHRVUGLTAZGHXUHLPJMRTTNQRBZIAVBTG
      QTBYMYAIVOMZTAIXJBTEDEWVQWADVWGOOKNQNTCIPEGPY
      BOKUSECNWELLCPZUMIVWFUIJMYATUEXISLMZTNPGUJHTM
      ERXJSYSIVWABGVWFDTZILNTIEDEFJMFAMPNQZBRSDIZPR
      MLGVKFEDZXMVXVQMJXWSLEEQRMAEPRUJXIMFNT

Pogledajmo hoćemo li pomoću indeksa koincidencije doći do istog zaključka. Za m = 1 je I_c = 0.040; za m = 2 su indeksi 0.037 i 0.040; za m = 3 su 0.038, 0.048 i 0.038; za m = 4 su 0.036, 0.038, 0.044 i 0.036, dok za m = 5 dobivamo indekse 0.057, 0.052, 0.066, 0.076 i 0.066. Sada već s prilično velikom sigurnošću možemo zaključiti da je duljina ključne riječi jednaka 5.

Sljedeće je pitanje kako odrediti ključnu riječ ukoliko znamo njezinu duljinu. Tu nam može pomoći međusobni indeks koincidencije dvaju nizova.

Definicija 1.3: Neka su x = x1x2 ... xn i y = y1y2 ... yn' dva niza od n, odnosno n' slova. Međusobni indeks koincidencije od x i y, u oznaci MIc(x,y), se definira kao vjerojatnost da je slučajni element od x jednak slučajnom elementu od y. Ako frekvencije od A, B, C, ... , Z u x i y označimo sa f0, f1, ... , f25, odnosno f'0, f'1, ... , f'25, onda je MIc = ∑i  fif'i / nn'.

Neka je sada m duljina ključne riječi, te neka su podnizovi z₁, z₂, ... , z_m dobiveni kao prije.

Pretpostavimo da je K = (k₁, k₂, ... , k_m) ključna riječ, te pokušajmo ocijeniti indeks MI_c(z_i,z_j). Promotrimo proizvoljno slovo u z_i i proizvoljno slovo u z_j. Procijenimo vjerojatnost da su oba slova jednaka A. Vjerojatnost da pomakom za k_i dobijemo slovo A približno je jednaka vjerojatnosti s kojom se u hrvatskom jeziku pojavljuje slovo čiji je numerički ekvivalent -k_i mod 26. Dakle, vjerojatnost, da su oba ova slova jednaka A, približno je jednaka

p

-ki

p

-kj

,

da su oba slova B, približno je jednaka

p

1-ki

p

1-kj

,

itd. (operacije u indeksima su modulo 26). Dakle, imamo ocjenu

MI_c(z_i, z_j) ≈ ∑_h  p_h-ki p_h-kj = ∑_h  p_h p_h+ki-kj

________________________________________________________

 relativni pomak            očekivana vrijednost od MIc 
________________________________________________________

        0                             0.064  
        1                             0.039 
        2                             0.031 
        3                             0.031  
        4                             0.044
        5                             0.040
        6                             0.039  
        7                             0.033 
        8                             0.040
        9                             0.042
       10                             0.036  
       11                             0.036  
       12                             0.036 
       13                             0.039 
________________________________________________________

Pretpostavimo da smo fiksirali z_i i promotrimo efekt šifriranja z_j sa slovima A, B, C, ... , Z (tj. pomakom za 0, 1, 2, ... , 25 mjesta). Tako dobivene nizove označimo sa z_j⁰, z_j¹, ... . Za g = 0,1,...,25 izračunamo indeks MI_c(z_i, z_j^g) po formuli

MI_c(x, y^g) = ∑_i  f_if'_i-g / nn'.

Na ovaj način, možemo utvrditi relativne pomake bilo koja dva podniza z_i i z_j. Nakon što to učinimo, ostaje nam samo 26 mogućih ključnih riječi koje onda možemo ispitati jednu po jednu.

No, malom modifikacijom ove metode, do ključne riječi možemo doći efikasnije, ukoliko nam je poznato na kojem je jeziku pisan otvoreni tekst. Umjesto međusobnog indeksa koincidencije nizova z_i i z_j^g, računat ćemo MI_c(x, z_j^g), gdje je x niz koji odgovara tipičnom tekstu na jeziku otvorenog teksta. Pretpostavimo da nam je poznato (ili da to barem naslućujemo) da je otvoreni tekst pisan na hrvatskom jeziku. To znači da su relativne frekvencije f_i / n približno jednake p_i, pa je

MI_c(x, z_j^g) ≈ ∑_i  p_i f'_i-g / n'.

Prema tome, da bismo odredili j-to slovo k_j ključne riječi, postupamo da sljedeći način. Za 0 ≤ g ≤ 25 izračunamo

M_g = ∑_i  p_i f'_i-g / n'.

Nastavak primjera 1.7: Već smo zaključili da je m = 5. Za j = 1,2,3,4,5 izračunajmo vrijednosti M₀, M₁, ... , M₂₅. Npr. za j = 1 je

M₀ = (0.115 · 3 + 0.015 · 1 + 0.028 · 0 + ... + 0.023 · 1)/44 ≈ 0.0310.

Iz tablice iščitavamo redom:

• Za j = 1 imamo h = 14, M₁₄ = 0.0636, pa je k₁ = -14 mod 26 = 26- 14 = 12;
• Za j = 2 imamo h = 0, M₀ = 0.0616, pa je k₂ = 0;
• Za j = 3 imamo h = 7, M₇ = 0.0650, pa je k₃ = 19;
• Za j = 4 imamo h = 19, M₁₉ = 0.0643, pa je k₄ = 7;
• Za j = 5 imamo h = 22, M₂₂ = 0.0681, pa je k₅ = 4.

USPJE HURJE SAVAN JUNEP OZNAT IHSIF ARAMJ ERISE OVIMC ETIRI
MAPOK AZATE LJIMA REDOM KAKOS UOVDJ ENAVE DENIU PORNO SCUPA
ZSILJ IMPOS TUPCI MAANA LIZEI NTUIC IJOMI SRECO MSPOS OBNOS
TDASE ZNABA REMCI TATIJ EZIKO RIGIN ALNOG TEKST AVEOM AJEPO 
ZELJN AALIN IJEBI TNA

Uspjeh u rješavanju nepoznatih šifara mjeri se ovim četirima pokazateljima, redom kako su ovdje navedeni: upornošću, pažljivim postupcima analize, intuicijom i srećom. Sposobnost da se zna barem čitati jezik originalnog teksta veoma je poželjna, ali nije bitna.

Tako glase prve dvije rečenice "Udžbenika za rješavanje vojnih šifara" autora Parkera Hitta, jednog od najpoznatijih američkih kriptografa iz vremena Prvog svjetskog rata.