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

1.2. Supstitucijske šifre

Znameniti rimski vojskovođa i državnik Gaj Julije Cezar u komunikaciji sa svojim prijateljima koristio se šifrom u kojoj su se slova otvorenog teksta zamjenjivala slovima što su se nalazila tri mjesta dalje od njih u alfabetu (A ↦ D, B ↦ E, itd.). Pretpostavljamo da se alfabet ciklički nastavlja, tj. da nakon zadnjeg slova Z, ponovo dolaze A, B, C. Ako bi smo upotrijebili današnji engleski alfabet od 26 slova, onda bi poznata Cezarova izreka

VENI VIDI VICI

bila šifrirana ovako:

YHQL YLGL YLFL.

Cezarovu šifru možemo pregledno zapisati na sljedeći način: 
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
U daljnjim primjerima koristit ćemo se engleskim (međunarodnim) alfabetom od 26 slova. Ukoliko ćemo raditi s otvorenim tekstom na hrvatskom jeziku, onda ćemo Č i Ć zamijeniti s C, a Đ, Dž, Lj, Nj, Š, Ž redom s DJ, DZ, LJ, NJ, S, Z.

Danas se Cezarovom šifrom nazivaju i šifre (tj. kriptosustavi) istog oblika s pomakom različitim od 3. Da bismo Cezarovu šifru precizno definirali u smislu Definicije 1.1, uvest ćemo prirodnu korespodenciju između slova alfabeta (A - Z) i cijelih brojeva (0 - 25).

Skup {0,1,2,...,25} označavat ćemo sa Z26 i pretpostavljat ćemo da su na njemu definirane operacije zbrajanja, oduzimanja i množenja na isti način kao u skupu cijelih brojeva, ali tako da se rezultat (ukoliko nije iz skupa {0,1,2,...,25}) na kraju zamijeni s njegovih ostatkom pri dijeljenju s 26. Koristit ćemo oznake a +26 b ili (a + b) mod 26, te analogno za oduzimanje i množenje. Skup Z26, uz operacije +26 i ·26 čini prsten. Potpuno analogno se definira skup Zm i operacije na njemu za proizvoljan prirodan broj m.

Primijetimo da na ovom mjestu zamjena slova brojevima još nije bila nužna (mogli bismo sve definirati u terminima zamjena slova i njihovog pomicanja unutar alfabeta, te pojasniti što se događa kad "preskočimo" zadnje slovo), no uskoro će korištenje ovog matematičkog rječnika postati nužno.

Dakle, Cezarovu šifru možemo definirati na sljedeći način:

Neka je P = C = K = Z26. Za 0 ≤ K ≤ 25 definiramo

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

Šifra je definirana nad Z26 budući da koristimo 26 slova, pa imamo sljedeću korespondenciju, koja za svako slovo alfabeta daje njegov "numerički ekvivalent": 


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
U Cezarovoj šifri su osnovni elementi (simboli) otvorenog teksta slova (odnosno njihovi numerički ekvivalenti), a ključ K određuje za koliko mjesta udesno ćemo pomicati slova pri šifriranju. Očito je dK(eK(x)) = x, kao što se zahtjeva u definiciji kriptosustava. Za K = 3 dobiva se originalna Cezarova šifra. Postoje naznake da je Cezarov nećak, prvi rimski car August, koristio najjednostavniju verziju ove šifre, pomičući slova samo za jedno mjesto u alfabetu, tj. uzimajući da je K = 1.

Primjer 1.1: Dekriptirati šifrat   PWNUYTLWFKNOF   dobiven Cezarovom šifrom.

Rješenje. Budući da je prostor ključeva jako mali (ima ih 26) zadatak možemo riješiti "grubom silom", tj. tako da ispitamo sve moguće ključeve, sve dok ne dođemo do nekog smislenog teksta. Za d0, d1, d2, ... dobivamo redom: 


              P W N U Y T L W F K N O F
              O V M T X S K V E J M N E
              N U L S W R J U D I L M D
              M T K R V Q I T C H K L C
              L S J Q U P H S B G J K B
              K R I P T O G R A F I J A
Dakle, ključ je K = 5, a otvoreni tekst je KRIPTOGRAFIJA.


Da bismo dobili barem malo sigurniju šifru, možemo promatrati funkcije za šifriranje koje će uključivati više od jednog parametra. Najjednostavnija takva funkcija je afina funkcija e(x) = ax + b. No, tu se pojavljuje jedan novi problem jer takva funkcija na skupu Z26 ne mora imati inverz (ne mora biti injekcija). Zato parametar a ne može biti proizvoljan, već mora biti relativno prost s modulom 26.

Afina šifra definira se na sljedeći način:

Neka je P = C = Z26, te neka je K = { (a,b) ∈ Z26 × Z26 : (a, 26) = 1 }. Za K = (a,b) ∈ K definiramo

eK(x) = ax + b mod 26, dK(y) = a-1(y - b) mod 26.

Ova šifra se zove afinom zato što su funkcije šifriranja afine. Provjerimo je li uvjet dK(eK(x)) = x zadovoljen. Zaista,

dK(eK(x)) = dK(ax + b) = a-1 (ax + b - b) = x.

Ovdje a-1 označava multiplikativni inverz broja a u prstenu Z26. Budući da broj 26 nije prost, nemaju svi elementi iz Z26 multiplikativni inverz, već ih imaju upravo brojevi koji su relativno prosti s 26, tj. za koje vrijedi da je najveći zajednički djelitelje od a i 26 jednak 1 (to pišemo: (a, 26) = 1). Prikažimo te brojeve zajedno s njihovim inverzima:

a 1 3 5 7 9 11 15 17 19 21 23 25
a-1 1 9 21 15 3 19 7 23 11 5 17 25


Primjer 1.2: Neka je K = (7, 3). Šifrirati otvoreni tekst   ZADAR.

Rješenje. Koristeći ranije navedenu tablicu, slova otvorenog teksta poistovjećujemo s njihovim numeričkim ekvivalentima. Imamo: 


 25 · 7 + 3 ≡ 22 (mod 26), 
 0 · 7 + 3 ≡ 3 (mod 26), 
  3 · 7 + 3 ≡ 24 (mod 26), 
 17 · 7 + 3 ≡ 18 (mod 26),
pa je šifrat   WDYDS.

Primjer 1.3: Dekriptirati šifrat

OZWHRYEZCVWFCTPCUWRCFPYHWI

dobiven afinom šifrom.

Rješenje. Imamo φ(26) · 26 = 12 · 26 = 312 mogućih ključeva. To je još uvijek premalo, pa bi uz pomoć računala sigurno mogli primijeniti "grubu silu", kao u Primjeru 1.1.

No, postoji i elegantniji način ukoliko znamo kojim je jezikom pisan otvoreni tekst. Recimo da nam je poznato da je u ovom slučaju otvoreni tekst pisan hrvatskim jezikom. Frekvencijom slova u hrvatskom, a i nekim drugim jezicima, detaljnije ćemo se pozabaviti malo kasnije. Za sada nam je potrebna samo činjenica da su najfrekventnija slova u hrvatskom jeziku A, I, O, E, N, i to upravo u tom redoslijedu. U našem šifratu uočavamo da su najfrekventnija slova C i W, koja se javljaju po 4 puta. Iako je naš šifrat prekratak, možemo ipak očekivati da su ova dva slova šifrati od A, I, O, E ili N. Pa pogledajmo kakve smo sreće.

Imamo eK(A) = a · 0 + b = b, eK(I) = 8a + b. Pretpostavimo da je eK(A) = C i eK(I) = W. Dobivamo da je b = 2 i 8a + b ≡ 22 (mod 26), odakle je a = 9. (Općenito se linearne kongruencije rješavaju pomoću (proširenog) Euklidovog algoritma, no u slučaju malog modula, kao što je naš modul 26, dovoljno je uvrstiti sve dopustive (invertibilne) a-ove, te provjeriti koji zadovoljava kongruenciju.) Dakle, dobili smo da je eK(x) = (9x + 2) mod 26. Tada je dK(y) = 3(y - 2) mod 26. Primijenimo li funkciju dK na naš šifrat, dobivamo otvoreni tekst (s umetnutim razmacima i "kvačicama"):

KRIPTOGRAFIJA ZNAČI TAJNOPIS.


Cezarova i afina šifra su specijalni slučajevi supstitucijske šifre, koja je definirana na sljedeći način:

Neka je P = C = Z26. Prostor ključeva K se sastoji od svih permutacija skupa {0, 1, 2, ... , 25}. Za svaku permutaciju π ∈ K definiramo eπ(x) = π(x), dπ(y) = π-1(y), gdje je π-1 inverzna permutacija od π.

Ovdje imamo čak 26! ≈ 4 · 1026 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 je moguće lako dekriptirati koristeći statistička svojstva jezika na kojem 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 na kojem pretpostavljamo da je napisan otvoreni tekst. Vrlo je vjerojatno da najfrekventnija slova šifrata odgovaraju najfrekventnijim slovima jezika. Ta vjerojatnost je to veća što je dulji šifrat. Također, korisni mogu biti i podatci o najčešćim bigramima (parovima slova) i trigramima (nizovima od tri slova) u jeziku. Kod nizova od četiri ili više slova, frekvencije već uvelike ovise o sadržaju teksta, i najfrekventniji nizovi obično dolaze od jedne riječi koja se često ponavlja u tekstu (npr. osobnog imena).

Začetci analize frekvencija se mogu naći u 14. stoljeću u djelu arapskog autora Ibn ad-Duraihima. Njegova zapažanja su objavljena u odjeljku posvećenom kriptologiji u velikoj enciklopediji u četrnaest svezaka čiji je autor Qalqashandi. Odjeljak ima naslov "O skrivanju tajnih poruka u pismima". Nedavno pronađeni rukopisi sugeriraju međutim da su arapski lingvisti tu metodu poznavali možda i pet stoljeća ranije. Čini se da su u europskoj kriptografiji metodu analize frekvencija u kriptoanalizi prvi počeli koristiti talijanski kriptografi u 15. stoljeću. Naime, poznato je da su svoje poruke šifrirali na način da su najfrekventnija slova zamjenjivali s više različitih simbola, pa na osnovu toga možemo zaključiti da im je bilo poznato kako analiza frekvencija slova može dovesti do razbijanja supstitucijske šifre. Za razliku od znanstvenika ad-Duraihima, oni svoja saznanja nisu javno objavljivali, već su ih nastojali što bolje unovčiti. Naime, mnoge su tadašnje talijanske kneževine imale ljude plaćene za razbijanje šifriranih poruka (jedan od najpoznatijih je venecijanski "tajnik za šifre" Giovanni Soro), i taj se posao često prenosio unutar obitelji. Ovakvu situaciju u kojoj praktički istovremeno do otkrića značajnih za kriptografiju dođu znastvenici koji žele što prije objaviti svoje rezultate i dobiti za njih priznanje, te ljudi iz obavještajnih ili komercijalnih institucija koji ne žele ili ne smiju odmah objaviti svoje rezultate, susrećemo često u povijesti kriptografije sve do današnjih dana (npr. pitanje prvenstva kod otkrića diferencijalne kriptoanalize ili kriptosustava s javnim ključem).

Navest ćemo osnovne podatke o frekvenciji slova, bigrama i trigrama za hrvatski, engleski i njemački jezik. Pritom smatramo da u tekstu nema interpunkcijskih znakova ni razmaka između riječi (u protivnom bi kriptoanaliza bila puno lakša), te da su slova Č, Ć, Đ, Dž, Lj, Nj, Š, Ž iz hrvatske abecede zamijenjena na prije opisani način slovima iz međunarodnog alfabeta. Podatci za hrvatski jezik su dobiveni analizom tekstova iz dnevnog tiska, dok su podatci za engleski i njemački jezik preuzeti iz literature [Bauer, Stinson].

FREKVENCIJA SLOVA (u promilima)
HRVATSKI   ENGLESKI   NJEMAČKI
               
A 115   E 127   E 175
I 98   T 91   N 98
O 90   A 82   I 77
E 84   O 75   R 75
N 66   I 70   S 68
S 56   N 67   A 65
R 54   S 63   T 61
J 51   H 61   D 48
T 48   R 60   H 42
U 43   D 43   U 42
D 37   L 40   L 35
K 36   C 28   G 31
V 35   U 28   O 30
L 33   M 24   C 27
M 31   W 23   M 26
P 29   F 22   B 19
C 28   G 20   F 17
Z 23   Y 20   W 15
G 16   P 19   K 15
B 15   B 15   Z 11
H 8   V 10   P 10
F 3   K 8   V 9
      J 2   J 3
      Q 1   Y 1
      X 1   X 0
      Z 1   Q 0

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 %).

Ovdje je važno uočiti na je JE najfrekventniji bigram, iako J nije među najfrekventnijim slovima. Više od pola pojavljivanja slova J otpada na bigram JE. Druga zanimljivost je da su svi najfrekventniji bigrami oblika suglasnik-samoglasnik ili samoglasnik-suglasnik, osim bigrama ST i PR. Konačno, najfrekventniji recipročni bigrami su NA i AN (1.5 % + 1.4 %), te NI i IN (1.3 % + 0.9 %). Jedino kod ovih dvaju parova su frekvencije obaju bigrama veće od 0.9 %.

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 (3.2 %), HE (2.5 %), AN, IN, ER, RE, ON, ES, TI, AT (1.2 %),

a trigrami THE (3.5 %), ING (1.1 %), AND (1.0 %), ION, TIO, ENT, ERE, HER (0.7 %).

U njemačkom jeziku najfrekventniji bigrami su

ER (4.1 %), EN (4.0 %), CH (2.4%), DE, EI, ND, TE, IN, IE, GE (1.5 %),

a trigrami EIN (1.2 %), ICH (1.1 %), NDE (0.9 %), DIE, UND, DER, CHE, END (0.8 %).


Primjer 1.4: Dekriptirati šifrat 

TQCWT QCKIQ RWNOQ OBCEW OQVKB UKAPK

OQOQB CQPQA JGDUQ EQORW TSJGR WEQKY

WGTWC JKRBI KZGVO GBQ
dobiven supstitucijskom šifrom, ako je poznato da je otvoreni tekst na hrvatskom jeziku.

(Zbog preglednosti se kod duljih šifrata obično stavlja razmak nakon svakog petog slova - to naravno nema nikakve veze s razmacima u otvorenom tekstu, za koje smo se dogovorili da ćemo ih zanemarivati kod šifriranja.)

Rješenje. Napravit ćemo (istovremeno) analizu frekvencija slova i bigrama tako da za svako slovo u alfabetu napišemo sve njegove sljedbenike u šifratu (za zadnje slovo u šifratu stavljamo *). Dobivamo sljedeću tablicu: 


A |   P, J                      
B |   C, U, C, I, Q                  
C |   W, K, E, Q, J                 
D |   U                 
E |   W, Q, Q                 
F |                                         
G |   D, R, T, V, B                 
H |                    
I |   Q, K                  
J |   G, G, K                  
K |   I, B, A, O, Y, R, Z
L |   
M |
N |   O
O |   Q, B, Q, Q, Q, R, G
P |   K, Q
Q |   C, C, R, O, V, O, B, P, A,  E, O, K, *
R |   W, W, W, B
S |   J
T |   Q, Q, S, W
U |   K, Q
V |   K, O
W |   T, N, O, T, E, G, C
X |   
Y |   W
Z |   G
Iz tablice iščitavamo da su najfrekventnija slova:

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

a najfrekventniji bigrami:

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

Logično je pretpostaviti da je e(A) = Q. Uočavamo također recipročne bigrame OQ i QO, što nas navodi na e(N) = O. Nadalje, većina pojavljivanja slova R vezana je uz bigram RW, te da je W jedno od najfrekventnijih slova. To nas vodi na pretpostavku da je e(J) = R i e(E) = W. Pokušajmo otkriti šifrat čestog bigrama ST (najčešćeg od neotkrivenih). Najozbiljniji kandidati su BC i JG. Možemo uzeti neki od njih, pa vidjeti što ćemo dobiti. Mi ćemo krenuti s BC, jer frekvencije od B i C odgovaraju očekivanim frekvencijama od S i T. Dakle, uzmimo da je e(S) = B i e(T) = C. Od najfrekventnijih slova u hrvatskom jeziku, još nismo odgonetnuli šifrate od I i O. Glavni kandidati su K i G, i to upravo tim redoslijedom. Pa uzmimo da je e(I) = K i e(O) = G. Rezimirajmo ono što smo do sada pretpostavili: 

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       q       w       k r       o g       b c
Ubacimo ove pretpostavke u polazni šifrat: 

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
Sada već imamo dovoljno elemenata otvorenog teksta da možemo postupno odgonetavati čitave riječi (npr. prva riječ: matematika, zadnja riječ: odnosa). Konačno dobivamo otvoreni tekst 

Matematika je znanstvena disciplina nastala 
proučavanjem brojeva i geometrijskih odnosa.
Alfabet šifrata izgleda ovako: 
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
Uočavamo pojavljivanje riječi "kriptografija" unutar alfabeta šifrata. Radi se o varijanti supstitucijske šifre koja se naziva Cezarova šifra s ključnom riječi. U njoj ključ predstavlja ključna riječ (u ovom slučaju KRIPTOGRAFIJA), te broj (u ovom slučaju 8) koji označava poziciju na kojoj počinjemo pisati ključnu riječ (bez ponavljanja slova). Naravno, da smo znali da je riječ upravo o ovoj varijanti, dekriptiranje bi nam bilo još lakše, no i bez toga nismo imali puno problema.

Možemo zaključiti da je usprkos velikom prostoru ključeva, supstitucijska šifra vrlo laka za kriptoanalizu. To je bilo poznato već početkom 15. stoljeća, kada je u Italiji počela uporaba homofona, tj. šifriranje najfrekventnijih slova s više različitih simbola. Tu se ne zamjenjuje slovo za slovo, već npr. slovo za dvoznamenkasti broj, tako da je moguće šifrirati najfrekventnija slova na nekoliko različitih načina, dok će ona niskofrekventna i dalje imati samo jednu zamjenu. To svakako povećava sigurnost šifre, ali i dalje analiza frekvencija bigrama i trigrama može dovesti do rješenja. Također se može iskoristiti djelomično ponavljanje. Primjerice, ako kod šifriranja slova pomoću dvoznamenkastih brojeva naiđemo na nizove 


12 17 37 23 57    i    12 17 42 23 57,
onda je prilično izvjesno da 37 i 42 predstavljaju isto slovo otvorenog teksta, pa ih možemo "spojiti" u analizi frekvencija.

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