Cifrul Hill

Maşina cifrului lui Hill, din figura 4 a patentului

În criptografia clasică, cifrul Hill este un cifru al substituției poligrafic bazat pe algebră lineară. Inventat de către Lester S. Hill în 1929, a fost primul cifru poligrafic în care era practic posibil să se opereze cu mai mult de trei simboluri deodată. Pentru a înțelege discuția următoare sunt necesare cunoștințe de teoria matricelor.

Operare

Fiecare literă este tratată ca o cifră din baza 26: A = 0, B =1 ș.a.m.d. Un bloc de n litere este considerat ca un vector cu n dimensiuni, și multiplicat cu o matrice n × n, modulo 26. Componentele matricei reprezintă cheia, care trebuie alese aleatoriu astfel încât matricea să fie inversabilă în $\mathbb {Z} _{26}^{n}$ (pentru a asigura posibilitatea decriptării). Considerăm mesajul 'ACT', și cheia de mai jos (sau GYBNQKURP în litere):

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

Deoarece 'A' este 0, 'C' este 2 și 'T' este 19, mesajul este vectorul:

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

Deci vectorul criptat este dat de:

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

care corespunde criptotextului 'POH'. Acum, presupunem că mesajul nostru este 'CAT', sau:

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

De această dată, vectorul criptat este dat de:

${\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}}\mod 26$

care corespunde criptotextului 'FIN'. Fiecare literă s-a schimbat. Cifrul Hill are proprietatea de difuzie a lui Shannon, iar un cifru Hill n-dimensional are proprietatea de difuzie peste n simboluri deodată.

Decriptare

Pentru a putea decripta, transformăm criptotextul în vector și apoi îl înmulțim cu inversa matricei cheie (IFKVIVVMI în litere). (Există metode standard de calculare a inversei unei matrici; vezi inversarea matricilor pentru detalii.) Găsim că, în $\mathbb {Z} _{26}^{n}$, inversa matricei din exemplul de mai sus este:

${\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}$

Luând criptotextul de mai sus, 'POH', obținem:

${\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}}\mod 26$

care reprezintă 'ACT'.

Complicația care poate apărea este faptul că nu toate matricele au inverse (vezi matrice inversabilă). Există o metodă directă de determinare a acestei proprietăți. Dacă determinantul unei matrice este 0, sau are factori comuni cu modulul (adică factori ca 2 sau 13, în cazul modulului 26), atunci matricea nu poate fi olosită în cifrul Hill. Din fericire, dacă baza nu are factori mici, cele mai multe matrice au inverse. De exemplu, matricea cheie:

${\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}\equiv 6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)\equiv 441\equiv 25\mod 26$

25 este coprim cu 26, deci nu este nici o problemă. Riscul ca determinantul să aibă factori comuni cu modulul poate fi eliminat prin alegerea unui modul prim. În consecință, o variantă utilă de cifru Hill adaugă încă 3 simboluri pentru a crește modulul la 29.