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

1.5. Hillova šifra

Lester Hill je 1929. godine izumio kriptosustav kod kojeg se m uzastopnih slova otvorenog teksta zamjenjuje s m slova u šifratu. Dakle, radi se o poligramskoj šifri. Ukoliko broj slova u originalnom otvorenom tekstu nije djeljiv s m, poruku trebamo nadopuniti da bismo je mogli podijeliti u blokove od po m slova. Kriptosustav je definiran na sljedeći način:

Neka je m fiksan prirodan broj. Neka je P = C = (Z26)m, te

K = {m × m invertibilne matrice nad Z26}.

Za KK definiramo

eK(x) = xK,
dK(y) = yK-1,

gdje su sve operacije u prstenu Z26.

Hill je preporučio uporabu involutornih matrica, tj. onih kod kojih je K-1 = K. To teoretski smanjuje sigurnost, jer je prostor ključeva manji, ali olakšava postupak šifriranja i dešifriranja. Napomenimo da je matrica invertibilna u Z26 ako i samo ako joj determinanta ima inverz u Z26, tj. ako je (det A, 26)=1.

Primjer 1.10: Neka je
K =
5822
2524
102017
,
te neka je otvoreni tekst
  UTORAK.

Njegov numerički ekvivalent je (20, 19, 14, 17, 0, 10). Računamo:
(20  19  14)
5822
2524
102017
= (278  535  1134) mod 26 = (18  15  16) = SPQ,

(17  0  10)
5822
2524
102017
= (185  200  170) mod 26 = (3  18  14) = DSO.

Dakle šifrat je   SPQDSO.

Primijetimo da ukoliko bi tekst umjesto s UTO započeo sa STO, onda bi šifrat započeo sa
(18  19  14)
5822
2524
102017
= (8  25  24) = IZY.

Hillov kriptosustav s 3 × 3 matricama skriva ne samo sve informacije o frekvencijama slova, već i o frekvencijama bigrama. Stoga već za m ≥ 5 možemo Hillov kriptosustav smatrati gotovo potpuno sigurnim na napad "samo šifrat". Međutim, ovu šifru je vrlo lako razbiti pomoću napada "poznati otvoreni tekst", a pogotovo pomoću napada "odabrani otvoreni tekst". To je i razlog zašto ovaj sustav gotovo uopće nije bio u praktičnoj uporabi (osim kratko vrijeme za šifriranje pozivnih signala radio-stanica).

Nevezano uz Hillovu šifru, spomenimo da je često do uspješnih napada metodom "odabrani otvoreni tekst" dolazilo zbog nespretnosti diplomata koji su uručene im diplomatske note šifrirali u doslovno istom obliku u kojem su im bile uručene. Stoga se u tekst note moglo ubaciti neke dijelove po sugestiji kriptoanalitičara, tj. u njih ubaciti "odabrani otvoreni tekst", te potom presretanjem komunikacije saznati odgovarajući šifrat.

Vratimo se Hillovoj šifri. Pretpostavimo da je kriptoanalitičar odredio vrijednost m, te pretpostavimo da ima barem m različitih parova m-torki xj = ( x1j, x2j, ... , xmj), yj = ( y1j, y2j, ... , ymj), j = 1, 2, ... , m, takvih da je yj = eK(xj), j = 1, 2, ... , m. Definirajmo dvije m × m matrice X = (xij) i Y = (yij). Tako dobivamo matričnu jednadžbu Y = XK, gdje m × m matrica K predstavlja nepoznati ključ. Ukoliko je matrica X invertibilna, kriptoanalitičar može izračunati K = X-1Y i time razbiti šifru. Ako X nije invertibilna, morat će pokušati s nekim drugim skupom od m parova otvoreni tekst - šifrat. Jasno je da kod napada "odabrani otvoreni tekst" nema ovog problema, jer će kriptoanalitičar odabrati otvoreni tekst koji daje invertibilnu matricu.

Primjer 1.11: Pretpostavimo da je otvoreni tekst   ZAGREB   šifriran Hillovom šifrom s m = 2 i da je tako dobiven šifrat   THWJKB. Odredimo ključ K.

Rješenje. Imamo: eK(25, 0) = (19, 7), eK(6, 17) = (22, 9), eK(4, 1) = (10, 1). Iz prva dva para dobivamo matričnu jednadžbu

250
617
K =
197
229
.

Ako je A = (aij) invertibilna 2 × 2 matrica, onda je

A-1 = (det A)-1
a22 -a12
-a21 a11
.

Kod nas je det X mod 26 = 425 mod 26 = 9, pa je (det X)-1 = 3. Stoga je

X-1 = 3
170
-625
=
250
823
,
pa je
K =
250
823
197
229
=
719
83
.

Provjerimo to na trećem paru:

(4  1)
719
83
= (10  1).

Što ako se ne zna m? Pretpostavljajući da m nije jako velik, možemo probati s m = 2, 3, ..., dok ne nađemo ključ. Ako pretpostavljena vrijednost od m nije točna, onda m × m matrica dobivena na gore opisani način neće biti u skladu s daljnjim parovima otvoreni tekst - šifrat.


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