Szyfr Hilla
Poligramowy Szyfr Podstawieniowy
Szyfr ten jest uważany za pierwszy podstawieniowy szyfr poligramowy, w którym da się praktycznie i efektywnie operować na więcej niż trzech znakach równocześnie.
Szyfr Hilla został stworzony w roku 1929 przez Lester'a S. Hill'a, amerykańskiego matematyka.
W szyfrowaniu za pomocą szyfru Hilla każdej literze alfabetu łacińskiego przyporządkowuje się unikalny numer, z przedziału od 0 do 25. Najczęściej stosowane jest najprostsze przyporządkowanie (A = 0, B = 1, ..., Z = 25), ale można wybrać również inną kombinację.
Tekst jawny jest na początku dzielony na n-literowe bloki tekstu. Szyfrowanie polega na przemnożeniu wszystkich bloków tekstu jawnego przez jedną sekretną macierz o wymiarach n x n, zawierającą również liczby z przedziału od 0 do 25. Wszystkie liczby powstałe w wyniku mnożenia powinny być podzielone modulo przez 26. Macierz może być zdefiniowana na podstawie sekretnego słowa kluczowego, które zawiera n2 liter (wystarczy zignorować pozostałe niepotrzebne litery).
Algorytm używany do deszyfrowania jest podobny do procesu enkrypcji. Należy podzielić szyfrogram na bloki (każdy z n literami), a następnie mnożyć bloki z macierzą odwrotną modulo 26 do macierzy użytej podczas szyfrowania.
Szyfrowanie i Deszyfrowanie
Aby zaszyfrować wiadomość o treści vino przy użyciu macierzy 2 x 2 należy w pierwszej kolejności podzielić wiadomość na dwa dwuliterowe bloki, a następnie zamienić litery na liczby:
,
-->
,
Jako sekretny klucz przyjęto poniższą macierz:
K =
Dla której łatwo wyznaczyć macierz odwrotną modulo 26, wykorzystywaną podczas deszyfrowania:
K-1 =
Szyfrowanie dwóch bloków tekstu jawnego polega na przemnożeniu ich przez macierz klucza:
x
=
=
x
=
=
Wynikiem szyfrowania jest szyfrogram składający się z czterech liczb 15 14 9 25 czyli oniy. Deszyfrowanie przebiega w analogiczny sposób. Litery szyfrogramu są zamieniane na liczby, dzielone na dwa dwuliterowe bloki i mnożone przez macierz odwrotną klucza K-1:
x
=
=
x
=
=
Cztery otrzymane liczby mogą być zamienione na oryginalny tekst vino.
Podstawowa wersja szyfru Hilla jest podatna na ataki ze znanym tekstem jawnym, ponieważ cały proces enkrypcji jest liniowy. Napastnik, który dysponuje n2 parami liter odpowiadających sobie znaków tekstu jawnego i szyfrogramu może zbudować liniowy system równań, stosunkowo łatwy do rozwiązania. Dodając parę dodatkowych par, umożliwia się wybranie właściwego rozwiązania, w przypadku otrzymania więcej niż jednego. Rozwiązywanie równań liniowych zajmuje zwykle mało czasu i nie jest skomplikowane.
Liczba możliwych kluczy szyfrujących
Istnieje 26n2 różnych macierzy o wymiarach n x n, które zawierają jedynie numery od 0 do 26. Jednakże, aby macierz mogła być sekretnym kluczem szyfrującym, musi być odwracalna.
Ilość odwracalnych macierzy może zostać określona przy użyciu chińskiego twierdzenia o resztach (ang. the Chinese Remainder Theorem). Macierz jest odwracalna modulo 26 wtedy i tylko wtedy jeśli jest odwracalna modulo 13 i modulo 2.
Liczba macierzy odwracalnych n x n modulo 2 jest określona przez rząd pełnej grupy liniowej GL(n,Z2):
2n2(1 - 1/2) (1 - 1/22) ... (1 - 1/2n)
Podobnie, liczba macierzy odwracalnych n x n modulo 13 może być obliczona w podobny sposób:
13n2(1 - 1/13) (1 - 1/132) ... (1 - 1/13n)
Wreszcie, można określić ilość możliwych macierzy odwracalnych modulo 26, która jest równa iloczynowi dwóch poprzednich wielkości:
26n2(1 - 1/2) (1 - 1/22) ... (1 - 1/2n)(1 - 1/13) (1 - 1/132) ... (1 - 1/13n)
Wielkość ta może być określona przez mniej więcej 4,64 n2 - 1,7, co jest równe około 116 bitom dla macierzy 5 x 5.
