CTX - 07 - Cifrari Classici

Notiamo che il numero di chiavi per questo sistema è molto limitato: escludendo la chiave di cifratura \(k_c = 0\), che non muove l'alfabeto, le chiavi sono infatti solamente \(25\).

Inoltre, la chiave di cifratura \(k_c\) e quella di decifrazione \(k_d\) sono essenzialmente la stessa. In altre parole, sapendo \(k_c\) non ci costa niente calcolarci \(k_d\) e viceversa. Questo vuol dire che se un nemico conosce il modo in cui nascondiamo i messaggi, conoscerà anche il modo in cui può invertire questo processo.

Notiamo infine che le operazioni di cifratura e decifratura richiedono entrambe \(O(\log n)\) se si conosce la chiave. In realtà, anche se non si è a conoscenza della chiave, si può semplicemente fare un brute-force, provando tutte le possibili chiavi, che sono molto poche, per vedere qual'è la chiave giusta. Anche senza fare il brute-force, ci basta congettutare che ad una lettera cifrata corrisponda una lettera in chiaro, e se siamo corretti siamo in grado di calcolare la chiave in modo banale. Per fare queste congetture possiamo effettuare una analisi delle frequenze, ma di questo ne parleremo successivamente.

Concludiamo osservando che rompere questo schema risulta estremamente elementare con l'utilizzo dei computers.

Nuovamente, entrambe le operazioni di cifratura e decifratura richiedono tempo polinomiale rispetto ad \(n\), e sono quindi considerate facili da eseguire, se si possiede la chiave. E nuovamente, se conosco la chiave per cifrare mi posso calcolare velocemente quella per decifrare. Le chiavi sono quindi simmetriche anche in questo caso.

Questa volta abbiamo però aumentato il numero di chiavi, arrivando ad un totale di \(312\) chiavi. Una chiave è infatti definita da una coppia \((a, b)\), con \(MCD(n, a) = 1\). Dunque,

\[\begin{split} \text{number of keys} &= \varphi(n) \cdot n \\ &= \varphi(26) \cdot 26 \\ &= \varphi(2)\varphi(13) \cdot 26 \\ &= 12 \cdot 26 \\ &= 312 \end{split}\]

Siamo quindi riusciti ad aumentare il numero delle chiavi. Possiamo essere sicuri che adesso il sistema risulta effettivamente più sicuro rispetto al semplice cifrario di cesare? La risposta a questa domanda in realtà è negativa: no, non risulta più sicuro. Infatti, anche se il numero di chiavi è aumentato, arrivando ad un punto che forse un attaccante non avrebbe abbastanza pazienza per provare tutte le combinazioni a mano, non abbiamo comunque risolto uno dei problemi fondamentali per questo tipo di schemi: la frequenza delle lettere dei linguaggi naturali.

Le lettere utilizzate nei linguaggi naturali non appaiono tutte con la stessa frequenza, alcune sono più frequenti di altre. Questo vuol dire che schemi di cifratura che associano ad una lettera un'altra lettera, ovvero schemi monoalfabetici, non riescono ad eliminare completamente questo tipo di informazione: la lettera cifrata che appare più frequentemente sarà molto probabilmente associata ad una delle più lettere più frequenti nel particolare linguaggio. Un crittoanalista può quindi fare delle congetture, associando a lettere del testo cifrato determinate lettere del testo in chiaro, per cercare di scoprire la chiave. Per maggiori informazioni si rimanda a Zipf's law.

Supponiamo di essere un crittoanalista interessato a rompere uno schema di cifratura affino. In particolare vogliamo scoprire il valore della chiave di cifrazione \((a, b)\) da cui poi possiamo ricavare la chiave di decifrazione \((a^{-1}, -b)\) in modo veloce. Supponiamo infine di aver trovato aver trovato un certo testo cifrato \(c = (c_1, c_2, ...c_n) \in C\) e un certo testo in chiaro \(p = (p_1, p_2, ..., p_n) \in P\).

Quello che possiamo fare è congetturare che a determinate lettere del testo cifrato corrispondano determinate lettere del testo in chiaro. In altre parole, possiamo congetturare che la chiave \((a, b)\) rispetta il seguente sistema di congruenze

\[\begin{cases} c_1 \equiv ap_1 + b \mod 26 \\ c_2 \equiv ap_2 + b \mod 26 \end{cases}\]

Per ottenere la chiave, possiamo quindi risolvere il sistema. Nella risoluzione troviamo la seguente equazione congruenziale

\[c_1 - c_2 \equiv a(p_1 - p_2) \mod 26\]

A questo punto possono succedere varie cose:

• Se \(MCD(p_1 - p_2, 26) \not | c_1 - c_2\), allora non ho soluzioni e la mia congettura è sbagliata. Devo tentare con una congettura diversa.

• Se \(MCD(p_1 - p_2, 26) = 1\), allora ho una sola soluzione che me la calcolo nel seguente modo:

  \[\begin{cases} a = (p_1 - p_2)^{-1} \cdot (c_1 - c_2) \\ b = c_2 - p_2(p_1 - p_2)^{-1} \cdot (c_1 - c_2) \end{cases}\]

  Una volta calcolata la chiave \((a, b)\) la posso poi provare con altro testo cifrato. Se continua a funzionare, allora ho scoperto la vera chiave; altrimenti faccio un'altra congettura, basandomi su nuove informazioni o rivedendo quelle vecchie.

• Se \(MCD(p_1 - p_2, 26) = d\), allora mi possono risolvere l'equazione ridotta

  \[\frac{p_1 - p_2}{d} a \equiv \frac{c_1 - c_2}{d} \mod \frac{26}{d}\]

  che, per costruzione, ha una soluzione univoca. Partendo dalla singola soluzione, mi calcolo tutte le soluzioni che sono congrue tra loro modulo \(\frac{26}{d}\), ma non modulo \(26\). Per ciascuna soluzione calcolata, la testo con altro testo cifrato, per verificare se la soluzione funziona oppure no. Se nessuna solutione mi è utile, allora devo fare un'altra congettura.

Notiamo che la crittoanalisi non è mai una procedura sicura, e che in generale è molto complessa e dispendiosa da effettuare, specialmente quando abbiamo poche informazioni sul nemico e sui cifrari che sta utilizzando. In ogni caso, l'analisi delle frequenza del testo cifrato ci permette di fare delle buone congetture, che possono poi essere verificare nel metodo appena descritto. Ovviamente queste congetture funzionano solamente per cifrari basati sulla sostituzione alfabetica.

Per i cifrari di Hill è necessario che la matrice utilizzata per cifrare sia invertibile. Ricordiamo che una matrice \(A\) è invertibile, se esiste un'altra matrice \(B\) tale che

\[AB = BA = I\]

dove \(I\) rappresenta la matrice identica (quella con tutti \(1\) nella diagonale e \(0\) nel resto). La matrice \(B\) viene poi rappresentata con il simbolo \(A^{-1}\), per rappresentare che è l'inversa di \(A\).

Un teorema ben noto dell'algebra lineare afferma come condizione necessaria e sufficiente all'esistenza della matrice inversa il fatto che il determinate della matrice sia diverso da \(0\), ovvero

\[\textit{$A$ è invertibile $\iff$ $det(A) \neq 0$}\]

Questo è vero quando gli elementi di \(A\) fanno parte di un campo. Nel nostro caso però, gli elementi di \(A\) fanno parte di un anello, e quindi per l'esistenza dell'inversa non ci basta più che \(det(A) \neq 0\). In particolare abbiamo il seguente risultato:

Teorema: Sia \(A\) una matrice \(k \times k\) a coefficienti in \(\mathbb{Z}_n\). Le seguenti proposizioni sono equivalenti.

1. \(MCD(det(A), n) = 1\)

2. \(A\) è invertibile

3. Esiste \(\varphi_{A}: \mathbb{Z}_n^k \to \mathbb{Z}_n^k\), con

   \[\varphi_{A}(\underline{x}) := A \cdot \underline{x} \mod n\]

   tale che \(\varphi_{A}\) è biiettiva.

4. \(A \cdot \underline{x} = 0 \iff \underline{x} = 0 \mod n\)

Dimostrazione: Procediamo per punti

• \((1) \implies (2)\)

  Se \(det(A)\) è coprimo con \(n\), allora possiamo calcolare \(det(A)^{-1}\) in \(\mathbb{Z}_n\), e quindi anche

  \[A^{-1} = det(A)^{-1} \cdot agg(A)\]

  dove \(agg(A)\) è la matrice aggiunta di \(A\), i cui elementi sono i complementi algebrici dei corrispondenti elementi della trasporta di \(A\). Ma allora \(A\) è invertibile.

  ---

• \((2) \implies (4)\)

  Notiamo che

  \[\begin{split} A \cdot \underline{x} = 0 &\iff (A^{-1}A) \cdot \underline{x} = A^{-1} \cdot 0 \\ &\iff I \cdot \underline{x} = 0 \\ &\iff \underline{x} = 0 \end{split}\]

  ---

• \((3) \iff (4)\)

  Infatti, se vale \((4)\), allora il nucleo di \(\varphi_A\) è composto da un solo elemento, e quindi la \(\varphi_A\) è iniettiva, ovvero vale la \((3)\). Infatti, dati \(a, b \in \mathbb{Z}_n\), e notando che \(\varphi_A\) è una funzione lineare, si ha che

  \[\begin{split} \varphi_A(a) = \varphi_A(b) &\iff \varphi_A(a) - \varphi_A(b) = 0 \\ &\iff \varphi_A(a - b) = 0 \\ &\iff a - b = 0\\ &\iff a = b \end{split}\]

  Viceversa, se vale la \((3)\) allora \(\varphi_A\) è iniettiva. Ma allora il nucleo è composto solo da \(0\), ovvero vale la \((4)\).

  ---

• \((4) \implies (1)\)

  Sia \(m := MCD(det(A), n) \leq n\), e sia \(m' := \frac{n}{m}\).

  Supponendo che tutte le entrate di \(A\) siano divisibili per \(m\) otteniamo

  \[A \cdot \begin{pmatrix} m' \\ m' \\ .\\ . \\ m' \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ . \\ . \\ 0 \end{pmatrix} \mod n\]

  Ora, se \(m = n\), allora \(m' = 1\), e quindi

  \[\begin{pmatrix} m' \\ m' \\ . \\ . \\ m' \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ . \\ . \\ 1 \end{pmatrix} \mod n\]

  Il che non può essere vero, in quanto è vera la \((4)\). Se invece \(1 \leq m < n\) allora l'unico valore possibile per \(m\) è proprio \(1\). Infatti, se \(1 < m < n\), allora \(1 < m' < n\) e nuovamente la verita di \((4)\) mi fa cadere in contraddizione. Dunque \(m=1\) e quindi in questo caso vale \((1)\).

  Supponiamo adesso che esista qualche entrata di \(A\) che non sia divisibile per \(m\). In particolare possiamo assumere, senza perdita di generalità, che nella prima riga vi sia qualche entrata non divisibile per \(m\). In questo caso otteniamo

  \[A \cdot \begin{pmatrix} m' \cdot A_{11} \\ m' \cdot A_{12} \\ \vdots \\ m' \cdot A_{1k} \end{pmatrix} = \begin{pmatrix} m' \cdot det(A) \\ 0 \\ \vdots \\ 0 \end{pmatrix} \mod n\]

  Infatti, dalla prima riga di \(A\) otteniamo

  \[m'(a_{11}A_{11} + a_{12}A_{12} + \ldots + A_{1k}A_{1k}) = m' \cdot det(A)\]

  invece, per le restanti righe di \(A\), con \(i \neq 1\), otteniamo

  \[m'(a_{i1}A_{11} + a_{i2}A_{12} + \ldots + A_{ik}A_{1k}) = m' \cdot 0 = 0\]

  ricordiamo adesso che

  \[m' \cdot det(A) = \frac{n}{m} \cdot det(A) = n \cdot \Big(\frac{det(A)}{m}\Big)\]

  e quindi \(m' \cdot det(A) \equiv 0 \mod n\). Sapendo poi che la \((4)\) è vera otteniamo

  \[\begin{pmatrix} m'A_{11} \\ m'A_{12} \\ \vdots \\ m'A_{1k} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \mod n\]

  il che equivale a dire

  \[\begin{cases} n \,\,|\,\, m'A_{11} \\ n \,\,|\,\, m'A_{12} \\ \,\,\,\, \vdots \\ n \,\,|\,\, m'A_{1k} \\ \end{cases}\]

  Ora, dato che \(m' \cdot A_{1,j} = \frac{n}{m} \cdot A_{1, j}\), il fatto che \(n\) divide \(m' \cdot A_{1, j}\) equivale a dire che esiste un certo \(h\) tale che

  \[m' \cdot A_{1, j} = h \cdot n \iff \frac{n}{m} \cdot A_{1, j} = h \cdot n \iff A_{1, j} = h \cdot m\]

  ovvero che \(m\) divide \(A_{i, j}\), per ogni \(J = 1, \ldots, k\). Questo fatto va in contraddizione con l'assunzione che avevamo fatto inizialmente: il fatto che non tutti gli elementi della prima riga di \(A\) sono divisibili per \(m\). Infatti, se vale l'ipotesi, ovvero se esiste un qualche elemento della prima di \(A\) che non è divisible per \(m\), allora deve esistere anche un complemento algebrico corrispondente ad un elemento della prima riga di \(A\) che non è divisibile per \(m\).

\[\tag*{$\blacksquare$}\]

Supponiamo di voler utilizzare il cifrario di Hill con \(k = 2\) e la chiave per cifrare \(k_c = (A, b)\) tale che

\[A = \begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix} \quad ,\quad b = 0 = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\]

La trasformazione per passare da un testo in chiaro \(P = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}\) ad un testo cifrato è quindi la seguente

\[C = \begin{pmatrix} c_1 \\ c_2 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix} \begin{pmatrix} p_1 \\ p_2 \end{pmatrix} + 0 = \begin{pmatrix} p_1 + 2p_2 \\ 4p_1 + 3p_2\end{pmatrix}\]

Ad esempio, se ho il testo \(\text{YO}\), prendendo gli equivalenti numerici ottengo il vettore \(P = \begin{pmatrix} 24 \\ 14\end{pmatrix}\) e applicando la trasformazione ottengo

\[C = \begin{pmatrix} 24 + 2 \cdot 14 \\ 4 \cdot 24 + 3 \cdot 14\end{pmatrix} = \begin{pmatrix} 0 \\ 8\end{pmatrix}\]

Sostituendo gli equivalenti numerici con le lettere dell'alfabeto infine ottengo il testo \(\text{AI}\).