I matematici crittografano le immagini utilizzando la matematica del sudoku

Il puzzle di posizionamento dei numeri, Sudoku, consiste in una griglia 9 x 9 che deve essere riempita utilizzando le cifre da 1 a 9.

Tuttavia, ci sono diversi vincoli aggiuntivi. Ogni cifra può apparire solo una volta in ogni colonna, una volta in ogni riga e una volta in ciascuno dei nove blocchi 3 x 3 che compongono la griglia. Di seguito è mostrata una griglia della soluzione Soduko. I giocatori ricevono un numero di cifre dalla soluzione per iniziare il gioco.

Il sudoku ha lanciato una serie di sfide interessanti per i matematici. All'inizio di quest'anno, ad esempio, abbiamo esaminato come i matematici avevano risolto il 'problema del sudoku minimo' per trovare il minor numero di indizi che portassero a una soluzione unica (risposta, 17).

Oggi, Yue Wu della Tufts University di Medford e un paio di amici usano il Sudoku per affrontare un problema diverso: come crittografare le immagini prima di inviarle.

Questi ragazzi dicono che le proprietà speciali delle griglie di Sudoku portano a un tipo completamente nuovo di matematica a matrice che hanno sfruttato per mescolare le immagini.

Innanzitutto, un po' di background sulle matrici. Una matrice è semplicemente una matrice rettangolare di numeri. Ogni elemento nell'array è identificato in modo univoco da un riferimento alla griglia: la sua colonna e il numero di riga.

Ma Wu e colleghi affermano che è possibile identificare gli elementi in un array in altri modi se lo si pensa come una griglia di Sudoku. In tal caso, ogni elemento contiene una cifra da 1 a 9 che soddisfa le regole del Sudoku. In altre parole, oltre alla riga e alla colonna, ogni elemento ha anche una cifra.

Quindi nella griglia sopra, l'elemento nella prima riga e nella prima colonna (1,1) è associato anche alla cifra 8, l'elemento (1,2) è associato al 7, l'elemento (1,3) al 4 e così via .

Inoltre ogni elemento è anche associato a un blocco 3 x 3, numerato come mostrato nella griglia sopra. Quindi l'elemento (1,1) è associato al blocco 1, l'elemento (2,8) al blocco 7 e l'elemento (8,5) al blocco 6 e così via.

Ciò rende possibile identificare ogni elemento in altri modi. Quindi l'elemento nel blocco 5 contenente la cifra 9 è l'elemento (4,5) in notazione convenzionale; l'elemento nella colonna 3 contenente la cifra 7 è (8,3) in notazione convenzionale e l'elemento nella riga 6 contenente 2 è (6,9).

In totale, ci sono sei modi diversi di rappresentare ogni elemento, dicono Wu e co. Ciascuno di questi sistemi è equivalente ed è possibile convertire le coordinate da un sistema all'altro utilizzando un insieme di semplici funzioni di conversione matematiche.

Queste funzioni di conversione sono la chiave per mescolare le immagini. Inizia con un'immagine composta da 9x9 pixel. Quindi sovrapponi una soluzione Soduko a questa griglia in modo che ogni pixel possa ora essere rappresentato dai nuovi sistemi di coordinate.

Ora, applicando una delle funzioni di conversione alla griglia, scambia la posizione dei pixel, confondendo l'immagine.

Quello che Wu e co hanno scoperto è come applicare una breve sequenza di funzioni di conversione che rimescola completamente l'immagine. È utile perché è completamente deterministico e tuttavia produce un risultato apparentemente casuale (come mostrato nell'immagine in alto).

Ciò equivale a un tipo di crittografia in cui la soluzione originale di Sudoku è la chiave. (Per immagini più grandi è sufficiente affiancare l'immagine con diverse griglie Sudoku.)

Wu e co hanno fatto un confronto iniziale tra il loro metodo e altri algoritmi di rimescolamento delle immagini e affermano che li corrisponde o li supera.

E poiché per un'immagine 256 x 256 ci sono almeno 256!=2^1684 possibili matrici di Sudoku, non è facile per un avversario trovare la soluzione per caso o addirittura con la forza bruta.

Wu e compagni non fanno affermazioni sulla sua potenziale sicurezza, ma qui c'è chiaramente spazio per ulteriori esplorazioni.

Incredibile cosa può fare il Sudoku per l'umanità!

Rif: arxiv.org/abs/1207.5856 : Biiezioni bidimensionali associate a Sudoku per il rimescolamento delle immagini

nascondere