Cifrario di Hill

Nella crittografia classica, il Cifrario di Hill è un cifrario a sostituzione monoalfabetica poligrafica basato sull'algebra lineare. Ideato da Lester S. Hill nel 1929, è stato il primo cifrario poligrafico in cui era possibile nella pratica (anche se con difficoltà) operare con più di 3 simboli alla volta. La seguente discussione presuppone una conoscenza basilare della teoria delle matrici.

Cifratura

Nella cifratura, ogni lettera è per prima cosa codificata in numero. Lo schema usato più di frequente è semplicemente: A = 0, B = 1, ..., Z = 25, ma questa non è una caratteristica essenziale del cifrario. Un blocco n di lettere è quindi considerato come uno spazio vettoriale di dimensione n, e moltiplicato per una matrice n x n, modulo 26 (se si usa un numero più alto di 26 nel modulo base, allora si può usare uno schema numerale diverso per codificare le lettere, ed è possibile anche utilizzare spazi e punteggiatura). L'intera matrice è considerata la chiave del cifrario e deve essere casuale, a patto che sia invertibile in $\mathbb {Z} _{26}^{n}$ (per assicurare che la decrittazione sia possibile). Considerando il messaggio 'TUO' e la seguente chiave (che in lettere sarebbe Y Y P R Z W I Z J):

${\begin{pmatrix}24&24&15\\17&25&22\\08&25&09\end{pmatrix}}$

Considerando che ‘T' è ‘19', ‘U' è ‘20' e ‘O' è ‘14', il messaggio è il vettore:

${\begin{pmatrix}19\\20\\14\end{pmatrix}}$

Conseguentemente il vettore cifrato è dato da:

${\begin{pmatrix}24&24&15\\17&25&22\\08&25&09\end{pmatrix}}{\begin{pmatrix}19\\20\\14\end{pmatrix}}={\begin{pmatrix}1146\\1131\\778\end{pmatrix}}{\pmod {26}}\equiv {\begin{pmatrix}02\\13\\24\end{pmatrix}}$

che corrisponde al testo crittato ‘CNY'.

Il calcolo è dato dalla moltiplicazione matrice × testo in chiaro. Dopo aver effettuato questo calcolo, al risultato si toglie il modulo (in questo caso 26) tante volte quante ne servono per avere come differenza un numero inferiore del modulo stesso e che dia, quindi, in risultato una lettera ben definita.

$C\leftarrow 02=24\cdot 19+24\cdot 20+15\cdot 14{\pmod {26}}$

$N\leftarrow 13=17\cdot 19+25\cdot 20+22\cdot 14{\pmod {26}}$

$Y\leftarrow 24=08\cdot 19+25\cdot 20+09\cdot 14{\pmod {26}}$

Decifratura

Per decifrare riscriviamo il testo codificato come vettore, che poi moltiplicheremo semplicemente per la matrice inversa della matrice chiave (IFKVIVVMI in lettere). Ci sono metodi standard per calcolare la matrice inversa; si veda matrice invertibile per i dettagli. Si trova che la matrice inversa in $\mathbb {Z} _{26}^{n}$ di quella dell'esempio precedente è:

${\begin{pmatrix}13&03&23\\23&18&13\\17&08&10\end{pmatrix}}$

E quindi:

${\begin{pmatrix}13&03&23\\23&18&13\\17&08&10\end{pmatrix}}{\begin{pmatrix}02\\13\\24\end{pmatrix}}={\begin{pmatrix}617\\592\\378\end{pmatrix}}={\begin{pmatrix}19\\20\\14\end{pmatrix}}=$

che ci fa tornare a 'TUO', come si voleva.

C'è ancora da discutere una complicazione presente nella scelta della matrice di codifica: non tutte le matrici sono invertibili. Una matrice ha un inverso se e solo se il suo determinante non è zero e non ha fattori in comune con il modulo base. Perciò, se si lavora modulo 26 come sopra, il determinante non deve essere zero e non deve essere divisibile per 2 o 13. Se il determinante è zero, o ha fattori in comune con il modulo base, allora la matrice non può essere usata nel cifrario di Hill e deve essere scelta un'altra matrice (altrimenti non sarebbe possibile decrittare). Fortunatamente, matrici che soddisfano le condizioni per essere usate nel cifrario di Hill sono piuttosto comuni.

Riferendosi all'esempio fatto, il determinante è:

${\begin{vmatrix}06&24&01\\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{\pmod {26}}$

Così, modulo 26, il determinante è 25. Poiché questo non ha fattori comuni con 26, la matrice può essere usata nel cifrario di Hill. Il rischio del determinante di avere fattori comuni con i moduli può essere eliminato utilizzando come modulo un numero primo. Di conseguenza un'utile variante del cifrario aggiunge tre simboli ulteriori (ad esempio spazio, punto e punto di domanda) per portare il modulo a 29.

Sicurezza

Per quanto riguarda la sicurezza, sfortunatamente, il cifrario di Hill nella sua versione di base è vulnerabile ad un known-plaintext attack (KPA) in quanto è completamente lineare. Un avversario che intercetti n² coppie di caratteri in chiaro e cifrati può impostare un sistema lineare che può (di solito) essere risolto facilmente; può capitare che il sistema sia indeterminato, ma in questo caso basta aggiungere alcune altre coppie di caratteri in chiaro e cifrati per poterlo risolvere. Calcolare la soluzione con un algoritmo standard di algebra lineare richiede poco tempo.

Mentre limitarsi a moltiplicare per una matrice non costituisce un cifrario sicuro, può comunque essere un passaggio utile quando combinato con altre operazioni non lineari, perché genera diffusione. Ad esempio, una matrice scelta in modo opportuno può far sì che piccole differenze del vettore iniziale (testo in chiaro) diano origine a differenze molto maggiori dopo la moltiplicazione (testo cifrato). A questo scopo alcuni cifrari moderni usano al loro interno moltiplicazioni per matrici. Un esempio è dato dal passo MixColums di AES. Anche la funzione g in Twofish è una combinazione di S-box non lineari e della moltiplicazione per una matrice (MDS).

Lunghezza della chiave

La lunghezza della chiave è il logaritmo binario del numero delle possibili chiavi. Ci sono $26^{n^{2}}$ matrici di dimensione n x n, perciò $\log _{2}(26^{n^{2}})\approx 4,7n^{2}$ è un limite superiore per la dimensione di una chiave del cifrario di Hill usando matrici n x n. Questo è solo un limite superiore, perché non tutte le matrici sono invertibili e quindi non tutte possono essere usate come chiavi. Il numero della matrici invertibili può essere calcolato con il teorema cinese del resto. Vale a dire, una matrice è invertibile modulo 26 se e solo se è invertibile modulo 2 e modulo 13. Il numero di matrici n x n invertibili modulo 2 è uguale all'ordine del gruppo generale lineare GL(n, Z₂), e cioè:

$2^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})$

Allo stesso modo, il numero delle matrici invertibili modulo 13 (GL(n, Z₁₃)) è

$13^{n^{2}}(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n})$

Quindi il numero delle matrici invertibili modulo 26 è il prodotto di questi due numeri:

$26^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n})$

Inoltre sembra che sia prudente evitare di avere troppi zeri nella matrice chiave, poiché riducono la diffusione. Il risultato è che il numero effettivo della chiavi per il cifrario di Hill è all'incirca 4.64 n² − 1.7. Per un cifrario 5 x 5 si tratta di circa 114 bit. Chiaramente il test sistematico di tutte le chiavi non è l'attacco più efficiente fra quelli noti.

Implementazione meccanica

Lavorando su due simboli, il cifrario di Hill non offre vantaggi particolari rispetto al cifrario Playfair o al cifrario bifido, ed in effetti è più debole di entrambi e leggermente più laborioso da calcolare con carta e penna. Al crescere della dimensione diventa velocemente infattibile calcolarlo a mano. Tuttavia un cifrario di Hill di dimensione 6 è stato implementato meccanicamente da Hill, in collaborazione con un'altra persona, ottenendone il brevetto ((EN) US1,845,947, United States Patent and Trademark Office, Stati Uniti d'America.). Questa macchina realizzava un moltiplicazione modulo 26 per una matrice 6 × 6 utilizzando un sistema di ruote e cinghie. Sfortunatamente il sistema delle ruote, e con esso la chiave, era fisso, quindi per sicurezza era consigliato effettuare una cifratura a tre passi: un primo passo nonlineare (segreto), la cifratura con la macchina, che dà diffusione, e infine un altro passo non lineare (segreto). Questa combinazione di cifrature era molto potente nel 1929, e sembra mostrare che Hill avesse capito i concetti di attacco meet-in-the-middle e di confusione e diffusione.

Bibliografia

• Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly 36, giugno-luglio 1929, pp 306–312.
• Lester S. Hill, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly 38, 1931, pp 135–154.
• Jeffrey Overbey, William Traves e Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, 29(1), gennaio 2005, pp 59–72. (PDF)
• Shahrokh Saeednia, How to Make the Hill Cipher Secure, Cryptologia, 24(4), ottobre 2000, pp353–360.

Voci correlate

• Cifrario di Vigenère
• Cifrario di Cesare
• Cifrario Playfair
• Cifrario di Vernam