Cifrul Hill

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
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[modificare | modificare sursă]

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[modificare | modificare sursă]

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 matricelor 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\cdot15-10\cdot17)-24(13\cdot15-10\cdot20)+1(13\cdot17-16\cdot20) \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.

Criptografie clasică
Cifruri: ADFGVX | Afin | Alberti | Atbash | Autocheie | Bifid | Carte | Cezar | Cod Smithy | Codul bătăilor | Cuvânt cheie | Două pătrate | Francmasonic | Hill | Nihilist | Patru pătrate | Permutare | Playfair | Polialfabetic | Polybius | Rail Fence | Reihenschieber | Reservehandverfahren | ROT13 | Running key | Schitală | Solitaire | Straddling checkerboard | Substituție | Transpoziție | Trifid | VIC | Vigenère
Criptanaliză: Analiza frecvenței | Index de coincidență
Diverse: Criptogramă | Bacon | Pătratul lui Polybius | Schitală | Straddling checkerboard | Tabula recta
Criptografie
Istoria criptologiei | Criptanaliză | Portalul criptografiei | Subiecte în criptografie
Algoritm cu chei simetrice | Cifru bloc | Cifru stream | Criptografie cu chei publice | Funcție hash criptografică | Cod de autentificare a mesajelor | Număr aleatoriu