\begin{equation}\label{eq:1}\mathbf{Av} = \mathbf{b}\end{equation}
Se $\mathbf{A}$ è invertibile, per ottenere nuovamente $\mathbf{v}$, bisogna calcolare l'inversa di $\mathbf{A}$ e moltiplicare $\mathbf{b}$ per questa matrice
\begin{equation}\label{eq:2}\mathbf{A^{-1}b} = \mathbf{v}\end{equation}
Se le componenti di $\mathbf{v}$ rappresentassero caratteri alfanumerici si potrebbe sfruttare questo fatto per implementare un cifrario relativamente robusto (almeno in ambiti casalinghi) in maniera abbastanza semplice.
Il cifrario di Hill lavora con operazioni e operandi in modulo. Questo, fortunatamente, non complica le cose in modo eccessivo ma è bene prestare un po' di attenzione prima di passare all'implementazione in codice.
Per prima cosa non bisogna confondere l'operatore reminder (%) del C/C++ (che restituisce il resto della divisione tra due operandi) con $\bmod n$, che è simile all'operatore reminder ma non gestisce valori negativi (lo scopo infatti è quello di restituire valori compresi tra $0$ e $n-1$).
Detto questo, non resta che vedere come operare in modulo $n$ rispetto alle equazioni \eqref{eq:1} e \eqref{eq:2}.
In \eqref{eq:1} l'unica accortezza è applicare $\bmod n$ agli elementi di $\mathbf{A}$ e di $\mathbf{v}$ per ottenere una matrice $\mathbf{B}$ ed un vettore $\mathbf{z}$ tali che
\[B \equiv A \pmod{n}\qquad \text{e}\qquad z \equiv v \pmod{n}\]
e quindi la \eqref{eq:1} diventa
\begin{equation}\label{eq:3}\mathbf{Bz} = \mathbf{w}\pmod{n}\end{equation}
ricordandosi di applicare $\bmod n$ anche agli elementi di $\mathbf{w}$. La codifica è terminata e quello che si ottiene è la stringa criptata.
Per quanto riguarda la \eqref{eq:2}, per ottenere nuovamente $\mathbf{z}$ (a cui poi bisogna applicare $\bmod n$ per ottenere la stringa decriptata) è necessario applicare la sequente formula
\begin{equation}\label{eq:4}\mathbf{\overline{B}w} = \mathbf{z}\pmod{n}\end{equation}
con $\mathbf{\overline{B}}$ che è l'inversa di $\mathbf{B}\pmod{n}$. La formula per calcolarla è la seguente
\begin{equation}\label{eq:5}\mathbf{\overline{B}} = \overline{\Delta}\cdot Adj(\mathbf{B})\end{equation}
dove $Adj(\mathbf{B})$ è la matrice aggiunta di $\mathbf{B}$ e $\overline{\Delta}$ è il reciproco del determinante di $\mathbf{B}\pmod{n}$
\begin{equation}\label{eq:6}\overline{\Delta} = \frac{1}{det(\mathbf{B})} \pmod{n}\end{equation}
Dato il significato di reciproco (o inverso) di un numero, quello che bisogna trovare quindi è un valore $\overline{\Delta}$ che moltiplicato a $det(\mathbf{B})$ sia congruo a 1 modulo n, \begin{equation}\label{eq:7}det(\mathbf{B})\cdot \overline{\Delta}\equiv 1\bmod n\end{equation}
Prima di vedere il codice sono necessarie alcune premesse.
Si è scelto di operare in modulo 257 per due motivi. Primo, per semplicità (permette di lavorare con la maggior parte dei caratteri stampabili). Secondo, il metodo mod_num_inverse() (che trova il reciproco modulo $n$ di un numero; si veda la (6)) funziona solo se i due parametri passati non hanno divisori comuni $> 1$. Se si vuole lavorare con insiemi di caratteri estesi lo si può fare benissimo ma il consiglio è di lavorare in modulo $n$ dove $n$ è un numero primo, così da rendere la vita più facile al metodo mod_num_inverse().
La scelta di operare con matrici $4\times 4$ è stata dettata dal fatto che, in questo modo, risalire alla stringa decriptata da quella criptata (lavorando su frequenze di combinazioni di 4 caratteri) incomincia ad essere un lavoro abbastanza complicato (ci sono infatti $257^4$ combinazioni di 4 caratteri; qualcosina in meno se si escludono i caratteri non stampabili). Non impossibile da scardinare ma sicuramente non alla portata di tutti. Comunque, se si vuole, si possono benissimo adottare matrici di dimensioni maggiori utilizzando quanto visto in [1] per il calcolo dell'inversa.
Infine, si è scelto di omettere qualsiasi commento o spiegazione riguardo la parte di codice relativa al calcolo della matrice aggiunta e del determinante. Si veda [2] per maggiori dettagli.
#include <stdio.h> #include <math.h> #include <locale.h> void crypt(unsigned char*, unsigned char*, int, int, float*); int mod_num_inverse(int, int); int modulo(int, int); void mod_matrix_inverse(float*, float); void adjoint(float*); float det4x4(float*); float det3x3(float, float, float, float, float, float, float, float, float); float det2x2(float, float, float, float); int main(int argc, char *argv[], char *envp[]) { // Per gestire caratteri accentati bisogna disattivare il locale neutrale impostato di default. setlocale(LC_ALL, ""); float m4x4[4][4] = { {3, 1, 2, 4}, {1, 7, 3, 0}, {3, 2, 10, 0}, {8, 2, 6, 1} }; float adj4x4[4][4]; unsigned char message[] = "Questo messaggio può contenere dati sensibili."; const int message_size = sizeof(message) - 1; const int delta = 4 - message_size % 4; unsigned char fixed_message[message_size + delta]; unsigned char crypted_message[message_size + delta]; unsigned char decrypted_message[message_size + delta]; // Se si vuole conservare la matrice m4x4 è necessario copiare elementi in matrice di output adj4x4 for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) adj4x4[i][j] = m4x4[i][j]; } // (message_size + delta) % 4 = 0; così non rimangono mai caratteri in sospeso for (int i = 0; i < message_size + delta; ++i) { if (i < message_size) { fixed_message[i] = message[i]; } else { fixed_message[i] = '\0'; } } printf("Messaggio in chiaro:\n"); printf("%s\n\n", message); // Cripta stringa for (int i = 0; i < message_size + delta - 1; i += 4) crypt(fixed_message, crypted_message, i, 4, &adj4x4[0][0]); printf("Messaggio criptato:\n"); printf("%s\n\n", crypted_message); // Inverte matrice modulo 127 mod_matrix_inverse(&adj4x4[0][0], 1e-6); // Decripta stringa for (int i = 0; i < message_size + delta - 1; i += 4) crypt(crypted_message, decrypted_message, i, 4, &adj4x4[0][0]); printf("Messaggio decriptato:\n"); printf("%s\n", decrypted_message); return 0; } void crypt(unsigned char* mess, unsigned char* crypt_mess, int start, int n, float* a) { int tmp; // Moltiplica vettore con matrice. // Effettua (mod n) su elementi del vettore risultante. // Vedi eq. (3) e (4) for (int i = 0; i < n; i++) { tmp = 0; for (int j = 0; j < n; j++) tmp += (int)a[n*i + j] * mess[start + j]; crypt_mess[start + i] = modulo(tmp, 257); } } // Vedi eq. (6) e (7); abbastanza bruteforce come metodo ma è il meno restrittivo su parametri a ed n int mod_num_inverse(int a, int n) { a = modulo(a, n); for (int x = 1; x < n; x++) { int tmp = (a * x) % n; if ((a * x) % n == 1) return x; } return -1; } // (mod n) int modulo(int a, int b) { int r = a % b; return r < 0 ? r + b : r; } // Trova l'inversa di una matrice (mod n) // vedi eq. (5) e [2] void mod_matrix_inverse(float *a, float tol) { float det; det = det4x4(a); adjoint(a); if (fabs(det) < tol) fprintf(stderr, "Errore di tolleranza; prababile matrice singolare"); det = mod_num_inverse(det, 257); if (det != -1) { for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) a[4 * i + j] = modulo((a[4 * i + j] * det), 257); } else { fprintf(stderr, "Errore in modInverse(): determinante e modulo non devono avere divisori comuni maggiori di 1"); } } void adjoint(float* a) { float a0, a1, a2, a3; float b0, b1, b2, b3; float c0, c1, c2, c3; float d0, d1, d2, d3; a0 = a[4 * 0 + 0]; a1 = a[4 * 0 + 1]; a2 = a[4 * 0 + 2]; a3 = a[4 * 0 + 3]; b0 = a[4 * 1 + 0]; b1 = a[4 * 1 + 1]; b2 = a[4 * 1 + 2]; b3 = a[4 * 1 + 3]; c0 = a[4 * 2 + 0]; c1 = a[4 * 2 + 1]; c2 = a[4 * 2 + 2]; c3 = a[4 * 2 + 3]; d0 = a[4 * 3 + 0]; d1 = a[4 * 3 + 1]; d2 = a[4 * 3 + 2]; d3 = a[4 * 3 + 3]; a[4 * 0 + 0] = det3x3(b1, b2, b3, c1, c2, c3, d1, d2, d3); a[4 * 0 + 1] = -det3x3(a1, a2, a3, c1, c2, c3, d1, d2, d3); a[4 * 0 + 2] = det3x3(a1, a2, a3, b1, b2, b3, d1, d2, d3); a[4 * 0 + 3] = -det3x3(a1, a2, a3, b1, b2, b3, c1, c2, c3); a[4 * 1 + 0] = -det3x3(b0, b2, b3, c0, c2, c3, d0, d2, d3); a[4 * 1 + 1] = det3x3(a0, a2, a3, c0, c2, c3, d0, d2, d3); a[4 * 1 + 2] = -det3x3(a0, a2, a3, b0, b2, b3, d0, d2, d3); a[4 * 1 + 3] = det3x3(a0, a2, a3, b0, b2, b3, c0, c2, c3); a[4 * 2 + 0] = det3x3(b0, b1, b3, c0, c1, c3, d0, d1, d3); a[4 * 2 + 1] = -det3x3(a0, a1, a3, c0, c1, c3, d0, d1, d3); a[4 * 2 + 2] = det3x3(a0, a1, a3, b0, b1, b3, d0, d1, d3); a[4 * 2 + 3] = -det3x3(a0, a1, a3, b0, b1, b3, c0, c1, c3); a[4 * 3 + 0] = -det3x3(b0, b1, b2, c0, c1, c2, d0, d1, d2); a[4 * 3 + 1] = det3x3(a0, a1, a2, c0, c1, c2, d0, d1, d2); a[4 * 3 + 2] = -det3x3(a0, a1, a2, b0, b1, b2, d0, d1, d2); a[4 * 3 + 3] = det3x3(a0, a1, a2, b0, b1, b2, c0, c1, c2); } float det4x4(float *a) { float det; float a0, a1, a2, a3; float b0, b1, b2, b3; float c0, c1, c2, c3; float d0, d1, d2, d3; a0 = a[4 * 0 + 0]; a1 = a[4 * 0 + 1]; a2 = a[4 * 0 + 2]; a3 = a[4 * 0 + 3]; b0 = a[4 * 1 + 0]; b1 = a[4 * 1 + 1]; b2 = a[4 * 1 + 2]; b3 = a[4 * 1 + 3]; c0 = a[4 * 2 + 0]; c1 = a[4 * 2 + 1]; c2 = a[4 * 2 + 2]; c3 = a[4 * 2 + 3]; d0 = a[4 * 3 + 0]; d1 = a[4 * 3 + 1]; d2 = a[4 * 3 + 2]; d3 = a[4 * 3 + 3]; det = a0 * det3x3(b1, b2, b3, c1, c2, c3, d1, d2, d3) - a1 * det3x3(b0, b2, b3, c0, c2, c3, d0, d2, d3) + a2 * det3x3(b0, b1, b3, c0, c1, c3, d0, d1, d3) - a3 * det3x3(b0, b1, b2, c0, c1, c2, d0, d1, d2); return det; } float det3x3(float a0, float a1, float a2, float b0, float b1, float b2, float c0, float c1, float c2) { float det; det = a0 * det2x2(b1, b2, c1, c2) - a1 * det2x2(b0, b2, c0, c2) + a2 * det2x2(b0, b1, c0, c1); return det; } float det2x2(float b0, float b1, float c0, float c1) { return b0 * c1 - c0 * b1; }
Questo è il risultato finale
Riferimenti
[1] Matrice inversa (con decomposizione LU)
[2] Matrice inversa in Computer Graphics
[3] Elementary Number Theory - Rosen
[4] http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
Nessun commento:
Posta un commento