Storia della crittografiaCifrari poligrafici
Hill cipher
Calcolo matrici in aritmetica modulare

Testo chiaro
Alfabeto = ABCDEFGHIJKLMNOPQRSTUVWXYZ(*)

Matrice chiave
$$ K = \begin{pmatrix}13 & 4 \\ 3 & 3\end{pmatrix}$$$$ |K| = 1$$$$ K^{-1} = \begin{pmatrix}3 & 22\\23 & 13\end{pmatrix} $$
Chiaro
CIFRARIODIHILL
CI2
8
6
4
GE
FR5
17
3
14
DO
AR0
17
16
25
QZ
IO8
14
4
14
EO
DI3
8
19
7
TH
HI7
8
19
19
TT
LL11
11
5
14
FO
Cifrato
GEDOQZEOTHTTFO

La cifra di Hill (Hill cipher) è la più semplice cifra basata sul calcolo matriciale, o, che è lo stesso, sui sistemi algebrici lineari; fu proposta dal matematico americano Lester Sanders Hill in due articoli comparsi nel 1929 e nel 1931. Di qui il nome di Hill cipher.

Si tratta di un cifrario poligrafico, nel senso che cifra per gruppi di $n$ lettere, usando matrici $n \times n$.

Il testo chiaro viene quindi diviso in gruppi di $n$ lettere, queste vengono convertite in numeri da $0$ a $25$(*) (se si usa l'alfabeto internazionale), ed ogni gruppo viene moltiplicato, righe per colonne, per una matrice segreta $n \times n$ che costituisce la chiave del cifrario. Per decifrare si userà la matrice inversa, che esiste solo se la matrice segreta ha determinante diverso da zero, che è quindi condizione necessaria perché il cifrario funzioni. Ovviamente i calcoli vanno eseguiti nell'aritmetica modulo 26(*).

In formule il blocco cifrato $c$ si ottiene con il prodotto della matrice $K$ per il blocco chiaro $b$

$$ c = K \times b $$

Come esempio prendiamo il messaggio:

CIFRARIO DI HILL

lo spezziamo in gruppi di due lettere (se il numero fosse dispari, si aggiungerà una nulla alla fine) e convertiamoli nei corrispondenti numeri ordinali:

$$ \begin{matrix}CI & FR & AR & IO & DI & HI & LL \\2,8 & 5,17 & 0,17 & 8,14 & 3,8 & 7,8 & 11,11 \end{matrix} $$

Come chiave prendiamo la matrice:

$$ \left ( \begin{matrix} 13 & 4 \\ 3 & 3 \end{matrix} \right ) $$

Moltiplichiamo il primo gruppo $2-8$ per la chiave:

$$ \begin{pmatrix} 13 & 4 \\ 3 & 3 \end{pmatrix} \times \begin{pmatrix}2 \\ 8 \end{pmatrix} = \begin{pmatrix} 13 \times 2 + 4 \times 8 = 6 \\ 3 \times 2 + 3 \times 8 = 4 \end{pmatrix} = \begin{pmatrix} 6 \\ 4 \end{pmatrix}$$

Si ottiene così la coppia $\left( 6 \quad 4 \right) $ che corrisponde al digramma $GE$ che è quindi la cifra di $CI$. Per i successivi digrammi si prosegue allo stesso modo, come mostrato dalla tavola a lato.

La tavola a lato è interattiva: è possibile cambiare il testo da cifrare e l'ordine della matrice; appare una matrice predefinita, che può anche essere generata a caso, ma sempre con determinante 1. Se il testo chiaro ha una lunghezza che non è multipla dell'ordine, viene riempito di nulle fino al necessario.


Decifrare

Per decifrare si ripete la stessa procedura, moltiplicando i gruppi cifrati per la matrice inversa, che va ovviamente calcolata una volta per tutte e che è la chiave decifrante. Riprendendo l'esempio visto sopra:

$$ \begin{pmatrix} 3 & 22\\23 & 13 \end{pmatrix} \times \begin{pmatrix} 6 \\ 4 \end{pmatrix} = \begin{pmatrix} 3 \times 6 + 22 \times 4 = 18 + 10 = 2 \\ 23 \times 6 + 13 \times 4 = 8 + 0 = 8 \end{pmatrix} = \begin{pmatrix} 2 \\ 8 \end{pmatrix}$$


Sicurezza

La sicurezza per matrici $2 \times 2$ è analoga a quella di altre cifre poligrafiche che cifrano digrammi con digrammi come il Playfair cipher che è anzi considerato più sicuro. Ovviamente è maggiore per matrici di ordine superiore; nel suo articolo Hill sosteneva che per ordini superiori a 4, il cifrario è praticamente inattaccabile. Trattandosi di operazione lineare, questa cifra può però essere forzata dalla crittanalisi lineare, solo che si venga in possesso di un congruo numero di coppie chiaro-cifrato.


Riferimenti bibliografici
X Attenzione: si possono immettere al massimo 32 lettere; tutti i segni estranei all'alfabeto vengono eliminati; le minuscole vengono convertite in maiuscole.
X Nel suo articolo del 1929, Hill proponeva in realtà di rappresentare le lettere con numeri tra 0 e 25 in modo disordinato, in pratica introducendo una sorta di pre-cifratura monoalfabetica al suo metodo.
X Un'aritmetica finita di ordine 26 presenta qualche problema non essendo 26 un numero primo. Cade la legge di annullamento del prodotto, per esempio $13 \times 2 = 0$ e quindi possono darsi matrici a determinante nullo, pur non avendo righe o colonne proporzionali.
Esempio: $ \left ( \begin{matrix} 14 & 1 \\ 2 & 2 \end{matrix} \right ) = 14 \times 2 - 2 = 26 \simeq 0 $
Ne segue che ci sono numeri che non ammettono elemento inverso, come i numeri pari, vedi pagina Calcolo inverso ... per maggiori dettagli.