:: Crittografia - Il cifrario di Hill ::
Torna alla pagina di Crittografia
Crittografia
Il cifrario di Hill è basato su di un sistema lineare di m equazioni in m incognite, quindi facilmente risolvibile.
A che servono queste equazioni? Servono per produrre m lettere in output a partire da m lettere di testo in chiaro, aumentando quindi la diffusione.
Il testo in chiaro lo vediamo come un array di lettere, così indicizzate: p0, p1, p2 ... pn.
Il sistema lineare invece è il seguente:
c1 = k11p1 + k12p2 + ... k1mpm mod 26 c2 = k21p1 + k22p2 + ... k2mpm mod 26 .............................. cm = km1p1 + km2p2 + ... kmmpm mod 26
Questo vuol dire che le lettere da c1 a cm saranno l'output delle lettere da p1 a pm.
Visto che scritto così è caotico, facciamo il caso di m = 2:
c1 = k11p1 + k12p2 mod 26 c2 = k21p1 + k22p2 mod 26
Per rappresentarlo in modo compatto, lo possiamo vedere in forma matriciale:
┌ ┐ ┌ ┐ ┌ ┐ │ k11 k12 │ │ p1 │ │ c1 │ │ │ │ │ = │ │ mod 26 │ k21 k22 │ │ p2 │ │ c2 │ └ ┘ └ ┘ └ ┘
Per risolvere codesta cosa, moltiplichiamo il vettore colonna per la matrice. Questo vuol dire che, come dicevo sopra, faccio:
c1 = k11p1 + k12p2 mod 26 c2 = k21p1 + k22p2 mod 26
Questo è il modo in cui si segna la moltiplicazione di una matrice per una colonna, ed è il modo con cui si rappresenta sotto forma matriciale un sistema lineare di m equazioni.
In modo alternativo, se decido di non usare la forma del sistema lineare, posso usare la matrice trasposta, ma mettere il testo in chiaro in una matrice [1 x 2].
Tradotto graficamente, è così:
┌ ┐
┌ ┐ │ k11 k21 │ ┌ ┐
│ p1 p2 │ │ │ = │ c1 c2 │ mod 26
└ ┘ │ k12 k22 │ └ ┘
└ ┘
In questo caso, con i valori k disposti in questo modo, le moltiplicazioni sono sempre le stesse. Da notare quindi che i valori k sono stati trasposti, ovvero nella prima colonna c'è quella che prima era una riga, ovvero i primi 2 valori di k, e nella seconda colonna c'è la seconda riga.
Occorre quindi mettersi d'accordo su come è rappresentata la matrice, perché nel primo caso essa è la diretta rappresentazione di un sistema lineare, su cui è basato il cifrario di Hill. Nel secondo, non lo è affatto, ma è la sua trasposta. I conti escono tuttavia uguali.
Decrittografia
La decrittografia è semplice: devo moltiplicare la matrice inversa per il mio vettore colonna di testo cifrato, ed ottenere così il vettore colonna di testo in chiaro.
Quindi, se diamo alle matrici nomi di lettere maiuscole, abbiamo:
C = KP P = CK-1
E come si trova la matrice inversa di una data matrice, sempre tenendo in considerazione il nostro caro modulo 26? Ricordiamo che il Δ deve essere diverso da 0, per avere l'inversa.
Il barbatrucco è semplice, se ho Δ = 1:
Facciamo un esempio per intenderci, per vedere com'è la matrice inversa.
┌ ┐ ┌ ┐ ┌ ┐ │ 3 2 │ │ 5 2-1 │ │ 5 24 │ │ │ => │ │ => │ │ │ 7 5 │ │ 7-1 3 │ │ 19 3 │ └ ┘ └ ┘ └ ┘
Infatti, per ottenere 0 a partire da 2, in modulo 26, devo sommare 24 (ovvero, sottrarre 2 a 26). Idem per il 7: sottraggo 7 a 26, ed ottengo 19.
Poi si risolve il sistema lineare esattamente come prima.
La cosa funziona anche per la matrice trasposta, ovviamente, ricordandosi di mettere la matrice 1x2 prima etc. etc.
Se invece il Δ NON è 1, (e ovviamente non è 0...), devo fare altrimenti:
Che cos'è l'inverso moltiplicativo del Δ? È quel numero che risolve l'equazione
Δ * x = 1 mod 26
Vi ricordo che, per avere un inverso in Z26, occorre che Δ e 26 siano coprimi.
Per esempio, l'inverso della matrice
5 8 9 2 17 3 è 1 15
Notate come mi sono stufato di fare la grafichina bella in ASCII.
Come ho ottenuto sta roba? Beh, come ho appena detto, ho invertito gli elementi della diagonale principale e ho preso l'inverso additivo di 8 e 17:
3 -8 3 18 -17 5 = 9 5
Il Δ della matrice originaria è 5*3 - 8*17 = -121, che in modulo 26 è 9.
L'inverso del Δ è quindi quel numero che, moltiplicato per Δ, mi dà 1.
Δ * x = 1 mod 26
Si dà il caso che 9 * 3 = 27 = 1 mod 26, quindi Δ-1 = 3
E allora moltiplico il tutto, sempre modulando con il 26: 3 18 3*3 18*3 9 54 9 2 9 5 * 3 = 9*3 3*5 = 27 15 modulo 26 = 1 15
Oh, siamo felici!:) Checcarinoooo:)
Attacchi crittografici
Se m=2, Hill nasconde la frequenza dei bigrammi. Se m = 3, nasconde anche quella dei trigrammi etc. etc.
Questo vuol dire che è ben resistente ad un attacco in cui si conosce solo il testo cifrato, perché non c'è analisi della frequenza che tenga.
Ma è invece vulnerabile ad un attacco known plaintext, ovvero quando ho una coppia testo in chiaro - testo cifrato. Anzi, ad essere precisi, qui mi servono m coppie di testo in chiaro e cifrato.
Il motivo è piuttosto semplice. Qui parliamo di matrici, che indico con le lettere maiuscole.
Sappiamo come è fatto Hill:
Y = K * X
dove K * X è una moltiplicazione per matrici.
Ma se è vero questo, allora è sicuramente vero che:
Y * X-1 = K * X * X-1 => Y * X-1 = K
Infatti, se ho X, so anche calcolare la sua inversa (se possibile), e se moltiplico a destra e a sinistra, ottengo esattamente la cosa qui sopra, ovvero la matrice K!
Spiegandomi meglio: