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 ako 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 otpornim na jednostavnu analizu frekvencija u napadu "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 mogao, po sugestiji kriptoanalitičara, ubaciti određeni tekst, tj. "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 gore opisanim postupkom neće biti u skladu s daljnjim parovima otvoreni tekst - šifrat.