Cifrario matriciale
I cifrari con matrici o cifrari di Hill sono un tipo di cifrario simmetrico a blocchi utilizzato in crittografia che utilizzano una matrice quadrata (A) come chiave moltiplicativa e un vettore (b) come chiave additiva. $$ c = A \cdot p + b \mod 26 $$
Questi cifrari suddividono il testo in blocchi di lunghezza "s" e traducono ogni lettera del blocco nel suo equivalente numerico, poi applicano una trasformazione lineare per cifrare il testo.
Di fatto, un cifrario matriciale utilizza la stessa logica del cifrario affine ma, in questo caso, le chiavi sono una matrice e un vettore anziché due numeri interi.
Nota. Questo vuole dire che le combinazioni della cifratura sono molte di più rispetto al cifrario affine e l'operazione di decifratura di un messaggio intercettato è più complessa.
La funzione cifrante
La cifratura è espressa dalla formula:
$$ c = A \cdot p + b \mod 26 $$
dove:
- \( c \) è il vettore del testo cifrato. E' composto da $ s $ lettere del testo cifrato.
- \( A \) è una matrice di cifratura. Si tratta di una matrice quadrata di ordine $ s $, ovvero con $ s $ righe e $ s $ colonne. E' la chiave moltiplicativa.
- \( p \) è il vettore di lunghezza $ s $ che rappresenta il blocco di testo in chiaro. E' composto da $ s $ lettere del testo in chiaro.
- \( b \) è il vettore di traslazione di lunghezza $ s $. E' la chiave additiva del cifrario matriciale.
La trasformazione è fatta modulo 26, che corrisponde al numero di lettere dell'alfabeto inglese.
La funzione decifrante
La funzione decifrante è, invece, espressa dalla formula:
$$ p = A^{-1} \cdot (c - b) \mod 26 $$
Dove A-1 è la matrice inversa della matrice di cifratura A.
Nota. Per poter decifrare il messaggio è necessario che la matrice \( A \) sia invertibile modulo 26, cioè deve esistere una matrice \( A^{-1} \) tale che \( A A^{-1} \equiv I \mod 26 \), dove \( I \) è la matrice identità.
Un esempio pratico
Faccio un esempio pratico di cifratura e decifratura con il cifrario di Hill utilizzando la matrice e il vettore dati seguenti:
$$ A = \begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix} $$
$$ b = \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$
Per semplicità utilizzo un vettore nullo come vettore di spostamento e una matrice quadrata 2x2 come matrice cifrante.
Per cifrare, devo prima convertire le lettere del messaggio in chiaro in numeri.
Utilizzando l'alfabeto inglese dove \( A = 0, B = 1, ..., Z = 25 \), converto un messaggio di due lettere.
Supponiamo che il messaggio sia "HI" che corrisponde ai codici numerici H = 7 e I = 8.
Quindi, il vettore del messaggio in chiaro da cifrare è il seguente:
$$ p = \begin{pmatrix} 7 \\ 8 \end{pmatrix} $$
Ora applico la trasformazione affine per cifrare \( p \):
$$ c = Ap + b \mod 26 = \begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix} \begin{pmatrix} 7 \\ 8 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \end{pmatrix} \mod 26 $$
Calcolo il prodotto di questa matrice per il vettore \( p \) modulo 26:
$$ c = \begin{pmatrix} 1 \cdot 7 + 2 \cdot 8 \\ 4 \cdot 7 + 3 \cdot 8 \end{pmatrix} \mod 26 = \begin{pmatrix} 7 + 16 \\ 28 + 24 \end{pmatrix} \mod 26 = \begin{pmatrix} 23 \\ 52 \end{pmatrix} \mod 26 $$
Questo mi dà:
$$ c = \begin{pmatrix} 23 \\ 0 \end{pmatrix} \mod 26 $$
Dove 23 corrisponde alla lettera "X" dell'alfabeto inglese e 0 corrisponde alla lettera "A".
Quindi il messaggio cifrato per "HI" è "XA".
Come si decifra il messaggio cifrato?
Per decifrare il messaggio, devo utilizzare la matrice inversa modulo n=26 della matrice \( A \) che in questo caso è la seguente:
$$ A^{-1} = \begin{pmatrix} 15 & 16 \\ 6 & 5 \end{pmatrix} \mod 26 $$
Applico questa matrice al messaggio cifrato "XA" ovvero il vettore (23,0) nella funzione decifrante.
$$ p = A^{-1} \cdot (c-b) \mod 26 = \begin{pmatrix} 15 & 16 \\ 6 & 5 \end{pmatrix} \cdot ( \begin{pmatrix} 23 \\ 0 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \end{pmatrix} ) \mod 26 $$
Svolgo i calcoli. Essendo b un vettore nullo, la sottrazione è molto semplice.
$$ p = A^{-1} \cdot (c-b) \mod 26 = \begin{pmatrix} 15 & 16 \\ 6 & 5 \end{pmatrix} \cdot \begin{pmatrix} 23 \\ 0 \end{pmatrix} \mod 26 $$
A questo punto calcolo la moltiplicazione riga per colonna tra la matrice 2x2 e il vettore.
$$ p = \begin{pmatrix} 15 \cdot 23 + 16 \cdot 0 \\ 6 \cdot 23 + 5 \cdot 0 \end{pmatrix} \mod 26 $$
$$ p = \begin{pmatrix} 345 \\ 138 \end{pmatrix} \mod 26 $$
$$ p = \begin{pmatrix} 7 \\ 8 \end{pmatrix} \mod 26 $$
Questo mi restituisce il messaggio originale in forma numerica, 7 e 8, che tradotto in lettere è "HI".
Questo esempio dimostra come il cifrario di Hill può essere utilizzato per cifrare e decifrare un messaggio.
Osservazioni
Qualche osservazione e nota a margine:
- Quante sono le combinazioni possibili del cifrario matriciale?
Le combinazioni dipendono dalla dimensione della matrice di cifratura e dal vettore di spostamento. Ad esempio, per una matrice di cifratura 2×2 nel cifrario di Hill, il numero di combinazioni possibili è determinato dal numero di matrici invertibili 2×2 modulo 26. Affinché una matrice sia invertibile modulo 26, il suo determinante deve essere coprimo con 26, ovvero il determinante e 26 devono avere 1 come massimo comun divisore. $$ MCD(\det(A), 26) = 1 $$ I primi tre elementi della matrice quadrata possono essere valori da 0 a 25, quindi le combinazioni possibili sono 263. L'ultimo elemento della matrice può ospitare solo numeri che generano un determinante coprimo con 26. Il numero 26 ha come fattori primi 2 e 13. Quindi, un numero è coprimo con 26 se non è divisibile né per 2 né per 13. Ci sono ϕ(26) numeri coprimi con 26, dove ϕ è la funzione di Eulero. In questo caso, ϕ(26)=12. Quindi, ci sono 12 possibili valori per il determinante di una matrice 2×2 affinché sia invertibile modulo 26. Complessivamente questo genera 210912 combinazioni $$ 26^3 \cdot 12 = 210912 \ \text{combinazioni} $$ A queste devo aggiungere quelle del vettore di spostamento. Se il vettore b non è nullo nel cifrario di Hill, devo calcolare anche una traslazione dopo la moltiplicazione della matrice. In questo caso il vettore b ha due elementi. Ogni elemento può assumere un valore da 0 a 25 indipendentemente dall'altro. Quindi, il vettore ha 262 combinazioni possibili, ovvero 262262 possibili vettori. Il numero totale delle combinazioni possibili è il prodotto delle combinazioni della matrice per quelle del vettore. $$ (26^3 \cdot 12) \cdot ( 26^2) = 210912 \cdot 262262 = 142.576.512\ \text{combinazioni} $$ Complessivamente ci sono oltre 142 milioni di cifrature possibili se il vettore b non è nullo.
E così via.
