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), |
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 9Dakle, š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 JVidimo 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 (čiji je autor zaista Vigenère i koja je 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
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
Pretpostavimo sada da imamo šifrat
Ic ≈ 26 · (1/26)2 = 1/26 ≈ 0.038.
Ove dvije vrijednostiPrimjer 1.7: Dekriptirati šifrat dobiven Vigenèreovom šifrom:
GSIQITUKQIEAOHRVUGLTAZGHXUHLPJMRTTNQRBZIAVBTG QTBYMYAIVOMZTAIXJBTEDEWVQWADVWGOOKNQNTCIPEGPY BOKUSECNWELLCPZUMIVWFUIJMYATUEXISLMZTNPGUJHTM ERXJSYSIVWABGVWFDTZILNTIEDEFJMFAMPNQZBRSDIZPR MLGVKFEDZXMVXVQMJXWSLEEQRMAEPRUJXIMFNTPrimijenimo 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 MIc = ∑i fif'i / nn'. |
Neka je sada m duljina ključne riječi, te neka su podnizovi
Pretpostavimo da je
p |
|
p |
| , |
p |
|
p |
| , |
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________________________________________________________ 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
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
MIc(x, yg) = ∑i fif'i-g / nn'.
Za g ≡ q (mod 26), MIc bi trebao biti blizu 0.064, a zaNa 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) ≈ ∑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
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:
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 TNAili, 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.
Web stranica kolegija Kriptografija | Andrej Dujella - osobna stranica |