Szyfr Hilla

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Szyfr Hillaszyfr należący do grupy polialfabetycznych szyfrów podstawieniowych bazujący na algebrze liniowej.

Operacje[edytuj | edytuj kod]

Każdą literę koduje się jako numer. Najczęstszy schemat korzysta z układu: A = 0, B =1, ..., Z=25, jednak nie jest to niezmienna zasada tego szyfru. Blok n jest przedstawiany w postaci wektora o n wymiarach. Następnie jest mnożony przez macierz o wymiarach n × n, modulo 26 (wartość wynika z liczby elementów w układzie). Cała tablica traktowana jest jako klucz. Należy sprawdzić, czy macierz jest odwracalna w \mathbb{Z}_{26}^n (by upewnić się że deszyfrowanie będzie możliwe).

Szyfrowanie[edytuj | edytuj kod]

Niech tekstem jawnym będzie 'ACT', a kluczem jest macierz (lub GYBNQKURP w postaci literowej):

\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix}

ponieważ 'A' jest 0, 'C' jest 2 a 'T' jest 19, tekst jawny jest wektorem:

\begin{pmatrix} 0 \\ 2 \\ 19 \end{pmatrix}

Wersja zaszyfrowana jest otrzymywana przez:

\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \begin{pmatrix} 0 \\ 2 \\ 19 \end{pmatrix} = \begin{pmatrix} 67 \\ 222 \\ 319 \end{pmatrix} \equiv \begin{pmatrix} 15 \\ 14 \\ 7 \end{pmatrix} \pmod{26}

co można przedstawić w postaci liter 'POH'. Teraz przypuśćmy że tekstem jawnym jest 'CAT' czyli:

\begin{pmatrix} 2 \\ 0 \\ 19 \end{pmatrix}

Tym razem wersja zaszyfrowana przedstawia się jako:

\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \begin{pmatrix} 2 \\ 0 \\ 19 \end{pmatrix} \equiv \begin{pmatrix} 31 \\ 216 \\ 325 \end{pmatrix} \equiv \begin{pmatrix} 5 \\ 8 \\ 13 \end{pmatrix} \pmod{26}

co jest równoznaczne z tekstem 'FIN'. Każda litera została zmieniona. Kryptosystem zapewnia zatem dyfuzję

Deszyfrowanie[edytuj | edytuj kod]

By odszyfrować, wiadomość zamieniamy zaszyfrowany tekst na wektor, i następnie mnożymy przez odwróconą macierz stanowiącą klucz (istnieją metody wyliczania macierzy odwrotnej; zobacz wyznaczanie macierzy odwrotnej). Przy działaniu w \mathbb{Z}_{26}^n macierz odwrotna z przykładu wynosi:

\begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix}^{-1} \equiv \begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix} \pmod{26}

wykorzystując wiadomość zaszyfrowaną 'POH', otrzymamy:

\begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix} \begin{pmatrix} 15 \\ 14 \\ 7 \end{pmatrix} \equiv \begin{pmatrix} 260 \\ 574 \\ 539 \end{pmatrix} \equiv \begin{pmatrix} 0 \\ 2 \\ 19 \end{pmatrix} \pmod{26}

co daje nam w formie liter 'ACT', czyli tekst jawny.

Zobacz też[edytuj | edytuj kod]