Broj 1 

Andrej Dujella

Vigenèreova šifra

Supstitucijske šifre | Vigenèreova šifra | Dno stranice | Verzija za printanje

Andrej Dujella: Vigenèreova šifra

1. Uvod

Neki elementi kriptografije naziru se već kod starih Grka. Naime, Spartanci su već u 5. stoljeću prije Krista u vojne svrhe upotrebljavali napravu za šifriranje zvanu skital. To je bio drveni štap oko kojega se namotavala vrpca od pergamenta na koju se uzdužno pisala poruka. Nakon upisivanja poruke vrpca bi se odmotala, a na njoj bi ostali izmiješani znakovi koje je mogao pročitati samo onaj tko je imao štap jednake debljine.

Osnovni zadatak kriptografije je omogućavanje dvjema osobama (zvat ćemo ih pošiljalac i primalac) da komuniciraju preko nesigurnog komunikacijskog kanala na način da treća osoba (njihov protivnik) ne može razumjeti njihove poruke. Poruku koju pošiljalac želi poslati primaocu zovemo otvoreni tekst. To može biti tekst na njihovom materinjem jeziku, numerički podatci ili bilo što drugo. Pošiljalac transformira otvoreni tekst koristeći unaprijed dogovoreni ključ. Taj postupak zove se šifriranje, a dobiveni rezultat šifrat ili kriptogram. Nakon toga pošiljalac pošalje šifrat preko nekog komunikacijskog kanala. Protivnik prisluškujući može doznati sadržaj šifrata, ali ne može odrediti otvoreni tekst. Za razliku od njega, primalac koji zna ključ kojim je šifrirana poruka može dešifrirati šifrat i odrediti otvoreni tekst.

Kriptografski algoritam ili šifra je matematička funkcija koja se koristi za šifriranje i dešifriranje. Općenito, radi se o dvjema funkcijama, jednoj za šifriranje (njezini argumenti su ključ i otvoreni tekst), a drugoj za dešifriranje (njezini argumenti su ključ i šifrat). Skup svih mogućih vrijednosti ključeva zovemo prostor ključeva. Kriptosustav se sastoji od kriptografskog algoritma, te svih mogućih otvorenih tekstova, šifrata i ključeva.

Funkcije šifriranja i dešifriranja koje odgovaraju ključu K označavat ćemo s e_K, odnosno d_K. One su jedna drugoj inverzne. Kriptosustave kod kojih je iz poznavanja funkcije e_K lako izračunati funkciju d_K nazivamo simetrični kriptosustavi. Njihova sigurnosti leži u tajnosti ključa. Dakle, pošiljalac i primalac moraju prije same komunikacije tajno razmijeniti ključ. Kako im nije dostupan "sigurni komunikacijski kanal" (jer inače ne bi ni imali potrebu za šifriranjem poruka), ovo može biti veliki problem.

Postoje i asimetrični kriptosustavi ili kriptosustavi s javnim ključem. Kod njih se za šifriranje koriste funkcije e_K koje su "jednosmjerne" (one se računaju lako, ali njihov inverz vrlo teško). To znači da funkcija za šifriranje e_K može biti javna, dok samo funkcija za dešifriranje d_K mora biti tajna. Kako su ovakvi kriptosustavi mnogo sporiji od najboljih simetričnih kriptosustava, u praksi se kriptosustavi s javnim ključem koriste za sigurnu razmjenu ključeva koji se potom koriste u šifriranju poruke nekim simetričnim kriposustavom. U ovom članku nećemo se baviti kriptosustavima s javnim ključem. Recimo ipak da se svi oni zasnivaju na teškim matematičkim problemima. Jedan od njih je faktorizacija velikih prirodnih brojeva. Naime, mnogo je lakše pomnožiti dva broja nego njihov umnožak rastaviti na faktore. Uvjerite se u to i sami rješavajući sljedeća dva zadatka:

• pomnožite (na ruke) brojeve 1987 i 2741;
• rastavite na faktore (bez uporabe računala) broj 4505143.

Home | Vrh stranice | Uvod | Vigenèreova šifra | Dno stranice | Verzija za printanje

2. Supstitucijske šifre

            VENI VIDI VICI

            YHQL YLGL YLFL.

otvoreni tekst    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

    šifrat        D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

A B C D E F G H I J K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Na skupu možemo definirati zbrajanje modulo 26 na sljedeći način: a + b mod 26 je ostatak pri dijeljenju broja a + b s 26.

Danas se Cezarovom šifrom nazivaju i šifre istog oblika s pomakom različitim od 3. Dakle, Cezarovu šifru možemo definirati na sljedeći način:

Za  x, y, K definiramo eK(x) = x + K mod 26,   dK(y) = y K mod 26.

Očito je d_K(e_K(x)) = x, kao što se i zahtjeva u definiciji kriptosustava. Za K = 3 dobiva se originalna Cezarova šifra.

Primjer 1: Dekriptirajte šifrat  NXBGZYQG  dobiven Cezarovom šifrom.

Budući da je prostor ključeva vrlo malen (ima ih 26), zadatak možemo riješiti "grubom silom", tj. tako da ispitamo sve moguće ključeve dok ne dođemo do nekog smislenog teksta. Za d₀, d₁, ... dobivamo redom:

              N X B G Z Y Q G
              M W A F Y X P F
              L V Z E X W O E
              K U Y D W V N D
              J T X C V U M C
              I S W B U T L B
              H R V A T S K A

Cezarova šifra je poseban slučaj supstitucijske šifre koja je definirana s:

Neka su  x, y . Za svaku permutaciju skupa {0, 1, 2, ... , 25} definiramo e(x) = (x),   d(y) = -1(y), gdje je -1 inverzna permutacija od .

Ovdje imamo 26! 4 10²⁶ mogućih ključeva, tako da je napad ispitivanjem svih mogućih ključeva praktički nemoguć čak i uz pomoć računala. Međutim, supstitucijsku šifru lako je moguće dekriptirati koristeći neka statistička svojstva jezika na kojemu je pisan otvoreni tekst. Osnovna metoda je analiza frekvencije slova; broji se pojavljivanje svakog slova u šifratu, te se distribucija slova u šifratu uspoređuje s poznatim podatcima o distribuciji slova u jeziku otvorenog teksta. Vrlo je vjerojatno da najfrekventnija slova šifrata odgovaraju najfrekventnijim slovima jezika. Ta vjerojatnost raste s duljinom šifrata. Također mogu biti korisni i podatci o najčešćim bigramima (parovima slova) i trigramima (nizovima od tri slova) u jeziku.

Začetci analize frekvencija mogu se naći u 14. stoljeću u djelu arapskog autora Ibn ad-Duraihima, a čini se da su tu metodu u isto vrijeme poznavali i talijanski kriptografi.

Navest ćemo osnovne podatke za hrvatski jezik. Pritom smatramo da u tekstu nema interpunkcijskih znakova ni razmaka između riječi (u protivnom bi kriptoanaliza bila mnogo lakša), te da su slova Č, Ć, Đ, Dž, Lj, Nj, Š, Ž iz hrvatske abecede zamijenjena na ranije opisani način slovima iz međunarodnog alfabeta.

Spomenimo da su najfrekventnija slova u engleskom jeziku E, T, A, O, I, N, S, R, H, L.
U njemačkom jeziku to su E, N, I, R, S, A, T, D, H, U,  a u francuskom E, A, I, S, T, N, R, U, L, O.

Najfrekventniji bigrami u hrvatskom jeziku su:

JE (2.7 %), NA (1.5 %), RA (1.5 %), ST, AN, NI, KO, OS, TI, IJ, NO, EN, PR (1.0 %).

Daleko najfrekventniji trigram u hrvatskom jeziku je IJE (0.6 %). Slijede (s frekvencijama između 0.3 % i 0.4 %): STA, OST, JED, KOJ, OJE, JEN.

U engleskom jeziku najfrekventniji bigrami su

TH, HE, AN, IN, ER, RE, ON, ES, TI, AT,

Primjer 2: Treba dekriptirati šifrat

TQCWT QCKIQ RWNOQ OBCEW OQVKB UKAPK

OQOQB CQPQA JGDUQ EQORW TSJGR WEQKY

WGTWC JKRBI KZGVO GBQ

Analizu frekvencija slova i bigrama možemo izvršiti pomoću tablice u kojoj pokraj svakog slova zapisujemo sve njegove sljedbenike u šifratu. Iz tablice iščitavamo da su najfrekventnija slova u šifratu:

Q (13), K (7), O (7), W (7), B, C, G, R, T, E, J,

OQ (4), QO (3), RW (3), BC, EQ, JG, QC, TQ, WT.

otvoreni tekst   A B C D E F G H I J K L M N O P Q R S T U W X Y Z
    šifrat       q       w       k r       o g       b c

TQCWT QCKIQ RWNOQ OBCEW OQVKB UKAPK
 ate  ati a je na nst e na is  i  i

OQOQB CQPQA JGDUQ EQORW TSJGR WEQKY
nanas ta a   o  a  anje    oj e ai 

WGTWC JKRBI KZGVO GBQ
eo et  ijs  i o n osa

Matematika je znanstvena disciplina nastala
proučavanjem brojeva i geometrijskih odnosa

q s u v w x y z k r i p t o g a f j b c d e h l m n

Prema tome, usprkos velikom prostoru ključeva, supstitucijska šifra je vrlo laka za kriptoanalizu. To je bilo poznato već početkom 15. stoljeća, kada je u Italiji počela uporaba tzv. homofona, tj. šifriranje najfrekventnijih slova s više različitih simbola. To svakako povećava sigurnost šifre, ali i dalje se analizom frekvencija bigrama i trigrama može doći do rješenja.

Home | Vrh stranice | Uvod | Supstitucijske šifre | Dno stranice | Verzija za printanje

3. Vigenèreova šifra

Kod supstitucijske šifre svakom slovu otvorenog teksta odgovara jedinstveno slovo šifrata. Takvi kriptosustavi zovu se monoalfabetski. Sada ćemo prikazat Vigenèreovu šifru koja pripada polialfabetskim kriptosustavima. Naime, kod nje se svako slovo otvorenog teksta može preslikati u jedno od m mogućih slova (gdje je m duljina ključa).

Blaise de Vigenère je 1586. godine objavio knjigu u kojoj se nalazilo sve što se u to vrijeme znalo o kriptografiji. U njoj je opisano više originalnih polialfabetskih sustava. Sustav koji se danas naziva Vigenèreova šifra definiran je s:

Neka je m fiksan prirodni broj. Za ključ K = (k1, k2, ... , km) definiramo eK(x1, x2, ... , xm) = (x1 + k1, x2 + k2, ... , xm + km), dK(y1, y2, ... , ym) = (y1 k1, y2 k2, ... , ym km), gdje su sve operacije u .

Primjer 3: Neka je m = 4, a 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 3 može se ilustrirati 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 4: Sve isto kao u Primjeru 3, ali s autoključem.

U šifriranju ćemo koristiti tzv. Vigenèreov kvadrat. (Ako 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.)

    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 jedan je od najpopularnijih kriptosustava u povijesti. Spomenimo da je korištena tijekom američke revolucije, krajem 18. stoljeća. Godine 1917. u uglednom časopisu "Scientific American" objavljeno je 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 zove se Kasiskijev test i uveo ju je Friedrich Kasiski 1863. godine. Metoda se zasniva na činjenici da će dva identična odsječka otvorenog teksta biti šifrirana na isti način ukoliko se njihove početne pozicije razlikuju za neki višekratnik od m. Obrnuto, ako uočimo dva identična odsječka u šifratu, duljine barem 3, tada je vrlo vjerojatno da oni odgovaraju identičnim odsječcima otvorenog teksta.

U Kasiskijevom testu u šifratu tražimo parove identičnih odsječaka duljine barem 3, te 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.

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.

Neka je x = x₁x₂ ... x_n niz od n slova. Indeks koincidencije od x, u oznaci I_c(x), definira se kao vjerojatnost da su dva slučajna elementa iz x jednaka.

Neka su f₀, f₁, ... , f₂₅ 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  f_i(f_i-1)/2 načina odabira dvaput i-tog slova. Stoga vrijedi formula

I_c(x) = _i  f_i(f_i-1) / n(n-1).

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). 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, pa bi svi 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 kao više-manje slučajni nizovi slova, budući da 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 5: Vigenereovom šifrom dobiven je šifrat

      GSIQITUKQIEAOHRVUGLTAZGHXUHLPJ
      MRTTNQRBZIAVBTGQTBYMYAIVOMZTAI
      XJBTEDEWVQWADVWGOOKNQNTCIPEGPY
      BOKUSECNWELSBSNUVBTTASMBTOIFHE
      ZAEPDQIGAYUCBQSYILYIOOFZTASHIR
      ASMKEEESUENAKLQOIMHXUJXGMWOKPK
      UNTSRAGMLOETTCIAMTQIBOSLPVNTHP
      UNBQINIMU

Pogledajmo hoćemo li pomoću indeksa koincidencije doći do istog zaključka. Za m = 1 je I_c = 0.044; za m = 2 su indeksi 0.048 i 0.042; za m = 3 su 0.049, 0.046 i 0.039; za m = 4 su 0.040, 0.039, 0.047 i 0.042, dok za m = 5 dobivamo indekse 0.061, 0.059, 0.080, 0.053 i 0.074. 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: 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), definira se 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 s 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, a neka su podnizovi z₁, z₂, ... , z_m dobiveni kao prije.

Pretpostavimo da je K = (k₁, k₂, ... , k_m) ključna riječ i pokušajmo ocijeniti MI_c(z_i,z_j). Promotrimo proizvoljno slovo u z_i i proizvoljno slovo u z_j. Vjerojatnost da su oba ova slova jednaka A je

________________________________________________________

 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 pa promotrimo efekt šifriranja z_j s A, B, C, ... . 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 ustvrditi 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 učinkovitije. 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 hrvatskom jeziku. To znači da su njegove 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 na sljedeći način. Za 0 g 25 izračunamo

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

Nastavak primjera 5: Već smo zaključili da je m = 5. Za j = 1,2,3,4,5 izračunajmo vrijednosti M₀, M₁, ... , M₂₅. Te vrijednosti nalaze se u sljedećoj tablici.

Iz tablice iščitavamo redom:

• Za j = 1 imamo h = 14, M₁₄ = 0.0619, pa je k₁ = 12;
• Za j = 2 imamo h = 0, M₀ = 0.0666, pa je k₂ = 0;
• Za j = 3 imamo h = 7, M₇ = 0.0677, pa je k₃ = 19;
• Za j = 4 imamo h = 19, M₁₉ = 0.0633, pa je k₄ = 7;
• Za j = 5 imamo h = 22, M₂₂ = 0.0636, 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 IVIMP OSTUP CIMAA NALIZ EINTU ICIJO MISRE COMSP OSOBN
OSTDA SEZNA BAREM CITAT IJEZI KORIG INALN OGTEK STAVE OMAJE
POZEL JNAAL INIJE BITNA

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. Koliko je u njima Hitt bio u pravu, možda može prosuditi i čitatelj ovog članka nakon što pokuša riješiti nagradne zadatke.

Vrh stranice | Uvod | Supstitucijske šifre | Vigenèreova šifra | Verzija za printanje