[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]

1.3. Vigenèreova šifra

Kod supstitucijske šifre svakom slovu otvorenog teksta odgovara jedinstveno slovo šifrata. Takve šifre se zovu monoalfabetske. Prikazat ćemo sada Vigenèreovu šifru koja spada u polialfabetske kriptosustave. Naime, kod nje svako slovo otvorenog teksta može se preslikati u jedno od m mogućih slova (gdje je m duljina ključa), u ovisnosti o svom položaju unutar otvorenog teksta.

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 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 k1, k2, ... ili km 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

Dakle, šifrat je   LIWYUFZXHZXJ. Rezultat se može provjeriti i OVDJE. Uočimo da se prvo slovo O preslikalo u F, a drugo u X.

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
Vidimo da se ovdje ključ ponavlja u nedogled pa prema podjeli šifara, s obzirom na način na koji se obrađuje otvoreni tekst, ovu šifru možemo shvatiti kao primjer blokovne šifre. Postoje i druge varijante Vigenèreove šifre. Jedna takva (sigurnija od originalne) je ona s autoključem (engl. autokey), u kojoj otvoreni tekst generira ključ. naime, originalni ključ se koristi samo za šifriranje prvog bloka od m slova, dok se za šifriranje daljnjih blokova koristi prethodni blok otvorenog teksta. Time ova varijanta spada u protočne šifre.

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 d1, d2, ... , onda je razumna pretpostavka da m dijeli većinu di-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 k1 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 p0, p1, ... , p25 (vidi ranije navedene frekvencije slova u promilima). Ako je n dovoljno velik, za očekivati je da će vrijediti

Ic(x) ≈ ∑i  pi2 ≈ 0.064

(vjerojatnost da su oba slova A je p02 ≈ 0.1152, da su oba B je p12 ≈ 0.0152, itd.). Isti zaključak vrijedi i ukoliko je x šifrat dobiven iz otvorenog teksta na hrvatskom jeziku pomoću neke monoalfabetske šifre. Tu će se pojedinačne vjerojatnosti ispremještati, ali će veličina i  pi2 ostati nepromijenjena.

Pretpostavimo sada da imamo šifrat y = y1y2 ... yn koji je dobiven Vigenèreovom šifrom. Rastavimo y na m podnizova z1, z2, ... , zm 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 z1, z2, ... , zm. 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 k1. Zato bi svi indeksi koincidencije Ic(zi) trebali biti približno jednaki 0.064. S druge strane, ako m nije duljina ključne riječi, onda će zi-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

Ic ≈ 26 · (1/26)2 = 1/26 ≈ 0.038.

Ove dvije vrijednosti κp = 0.064 i κr = 0.038 (p = plaintext, r = random) su dovoljno daleko jedna od druge, tako da ćemo najčešće na ovaj način moći odrediti točnu duljinu ključne riječi (ili potvrditi pretpostavku dobivenu pomoću Kasiskijeve metode). Spomenimo da je u engleskom jeziku κp = 0.065, u njemačkom 0.076, u francuskom 0.078, u talijanskom 0.074, a u španjolskom 0.078. Odavde zaključujemo da za primjenu ove metode nije nužno znati na kojem je jeziku pisan otvoreni tekst. Jedina bitna pretpostavka jest da se za jezik na kojem je pisan otvoreni tekst veličina κp značajno razlikuje od 0.038.

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


      GSIQITUKQIEAOHRVUGLTAZGHXUHLPJMRTTNQRBZIAVBTG
      QTBYMYAIVOMZTAIXJBTEDEWVQWADVWGOOKNQNTCIPEGPY
      BOKUSECNWELLCPZUMIVWFUIJMYATUEXISLMZTNPGUJHTM
      ERXJSYSIVWABGVWFDTZILNTIEDEFJMFAMPNQZBRSDIZPR
      MLGVKFEDZXMVXVQMJXWSLEEQRMAEPRUJXIMFNT
Primijenimo najprije Kasiskijev test. Uočavamo pojavu nekoliko trigrama koji se dvaput pojavljuju u šifratu. To su MYA s početkom na pozicijama 50 i 115 (115 - 50 = 65 = 5 · 13), MZT s početkom na pozicijama 56 i 125 (125 - 56 = 69 = 3 · 23), EDE (160 - 65 = 95 = 5 · 19), IVW (143 - 108 = 35 = 5 · 7), i VWF (149 - 109 = 40 = 5 · 8). Odavde se kao najvjerojatnija duljina ključne riječi nameće broj m = 5, koji dijeli sve osim jedne od razlika početnih pozicija ponovljenih trigrama.

Pogledajmo hoćemo li pomoću indeksa koincidencije doći do istog zaključka. Za m = 1 je Ic = 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 z1, z2, ... , zm dobiveni kao prije.

Pretpostavimo da je K = (k1, k2, ... , km) ključna riječ, te pokušajmo ocijeniti indeks MIc(zi,zj). Promotrimo proizvoljno slovo u zi i proizvoljno slovo u zj. Procijenimo vjerojatnost da su oba slova jednaka A. Vjerojatnost da pomakom za ki dobijemo slovo A približno je jednaka vjerojatnosti s kojom se u hrvatskom jeziku pojavljuje slovo čiji je numerički ekvivalent -ki 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

MIc(zi, zj) ≈ ∑h  ph-ki ph-kj = ∑h  ph ph+ki-kj

(pomakom indeksa suma se ne mijenja). Uočimo da ova ocjena ovisi samo o razlici (ki - kj) mod 26, koju ćemo zvati relativni pomak od zi i zj. Također, vrijedi h  ph ph+q = ∑h  ph ph-q, što znači da za pomak q dobivamo istu ocjenu kao i za pomak 26 - q. Stoga je dovoljno promatrati pomake između 0 i 13. To je i napravljeno u sljedećoj tablici

________________________________________________________

 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 
________________________________________________________

Važno je uočiti da ako je pomak jednak 0, onda je ocjena 0.064, a ako je pomak različit od 0, onda su ocjene između 0.031 i 0.044, dakle, bitno manje. Ovo zapažanje se može iskoristiti za određivanje vrijednosti q = ki - kj.

Pretpostavimo da smo fiksirali zi i promotrimo efekt šifriranja zj sa slovima A, B, C, ... , Z (tj. pomakom za 0, 1, 2, ... , 25 mjesta). Tako dobivene nizove označimo sa zj0, zj1, ... . Za g = 0,1,...,25 izračunamo indeks MIc(zi, zjg) po formuli

MIc(x, yg) = ∑i  fif'i-g / nn'.

Za gq (mod 26), MIc bi trebao biti blizu 0.064, a za gq (mod 26) bi trebao uglavnom varirati između 0.031 i 0.044.

Na ovaj način, možemo utvrditi relativne pomake bilo koja dva podniza zi i zj. 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 zi i zjg, računat ćemo MIc(x, zjg), 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 fi / n približno jednake pi, pa je

MIc(x, zjg) ≈ ∑i  pi f'i-g / n'.

Očekujemo da je MIc(x, zjg) ≈ 0.064 ako je g ≡ -kj (mod 26), a u protivnom da je MIc(x, zjg) < 0.045.

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

Mg = ∑i  pi f'i-g / n'.

Odredimo h takav da je Mh = max { Mg : 0 ≤ g ≤ 25 }, te stavimo kj ≡ -h (mod 26).

Nastavak primjera 1.7: Već smo zaključili da je m = 5. Za j = 1,2,3,4,5 izračunajmo vrijednosti M0, M1, ... , M25. Npr. za j = 1 je

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

Sve tražene vrijednosti nalaze se u sljedećoj tablici.

Iz tablice iščitavamo redom:

Stoga je ključna riječ   MATHE, a traženi otvoreni tekst glasi:

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
ili, s umetnutim "kvačicama", razmacima i interpunkcijom:

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.


[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]
Web stranica kolegija Kriptografija Andrej Dujella - osobna stranica