1.5. Hillova šifra

Neka je m fiksan prirodan broj. Neka je P = C = (Z26)m, te K = {m × m invertibilne matrice nad Z26}. Za K ∈ K 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 Z₂₆ ako i samo ako joj determinanta ima inverz u Z₂₆, tj. ako je (det A, 26)=1.

Primjer 1.10: Neka je

K =

5 8 22 2 5 24 10 20 17

,

te neka je otvoreni tekst   UTORAK.

Njegov numerički ekvivalent je (20, 19, 14, 17, 0, 10). Računamo:

(20  19  14)

5 8 22 2 5 24 10 20 17

= (278  535  1134) mod 26 = (18  15  16) = SPQ,

(17  0  10)

5 8 22 2 5 24 10 20 17

= (185  336  544) mod 26 = (3  24  24) = DYY.

Dakle šifrat je   SPQDYY.

Primijetimo da ukoliko bi tekst umjesto s UTO započeo sa STO, onda bi šifrat započeo sa

(18  19  14)

5 8 22 2 5 24 10 20 17

= (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 x_j = ( x_1j, x_2j, ... , x_mj), y_j = ( y_1j, y_2j, ... , y_mj), j = 1, 2, ... , m, takvih da je y_j = e_K(x_j), j = 1, 2, ... , m. Definirajmo dvije m × m matrice X = (x_ij) i Y = (y_ij). 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: e_K(25, 0) = (19, 7), e_K(6, 17) = (22, 9), e_K(4, 1) = (10, 1). Iz prva dva para dobivamo matričnu jednadžbu

25 0 6 17

K =

19 7 22 9

.

Ako je A = (a_ij) 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

17 0 -6 25

=

25 0 8 23

,

pa je

K =

25 0 8 23

19 7 22 9

=

7 19 8 3

.

Provjerimo to na trećem paru:

(4  1)

7 19 8 3

= (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.