Matematikere krypterer billeder ved hjælp af Sudoku-matematik

Nummerplaceringspuslespillet, Sudoku, består af et 9 x 9 gitter, som skal udfyldes med cifrene 1 til 9.

Der er dog flere yderligere begrænsninger. Hvert ciffer kan kun optræde én gang i hver kolonne, én gang i hver række og én gang i hver af de ni 3 x 3 blokke, der udgør gitteret. Et Soduko-opløsningsgitter er vist nedenfor. Spillere får et antal cifre fra løsningen for at få spillet i gang.

Sudoku har kastet en række interessante udfordringer op for matematikere. Tidligere i år har vi for eksempel set på, hvordan matematikere havde løst 'minimum Sudoku-problemet' for at finde det mindste antal spor, der fører til en unik løsning (svar, 17).

I dag bruger Yue Wu på Tufts University i Medford og et par venner Sudoku til at tackle et andet problem – hvordan man krypterer billeder, før de sendes.

Disse fyre siger, at de særlige egenskaber ved Sudoku-gitteret fører til en helt ny type matrixmatematik, som de har udnyttet til at kryptere billeder.

Først lidt baggrund om matricer. En matrix er simpelthen en rektangulær række af tal. Hvert element i arrayet er unikt identificeret med en gitterreference - dets kolonne- og rækkenummer.

Men Wu og co siger, at det er muligt at identificere elementer i et array på andre måder, hvis du tænker på det som et Sudoku-gitter. I så fald indeholder hvert element et ciffer fra 1 til 9, der opfylder reglerne for Sudoku. Med andre ord, udover rækken og kolonnen har hvert element også et ciffer.

Så i ovenstående gitter er elementet i den første række og første kolonne (1,1) også forbundet med cifferet 8, element (1,2) er forbundet med 7, element (1,3) med 4 og så videre .

Derudover er hvert element også forbundet med en 3 x 3 blok, nummereret som vist i gitteret ovenfor. Så element (1,1) er forbundet med blok 1, element (2,8) med blok 7 og element (8,5) med blok 6 og så videre.

Det gør det muligt at identificere hvert element på andre måder. Så elementet i blok 5, der indeholder cifferet 9, er element (4,5) i konventionel notation; elementet i kolonne 3, der indeholder ciffer 7, er (8,3) i konventionel notation, og elementet i række 6, der indeholder 2, er (6,9).

I alt er der seks forskellige måder at repræsentere hvert element på, siger Wu og co. Hvert af disse systemer er ækvivalente, og det er muligt at konvertere koordinaterne fra et system til et andet ved hjælp af et sæt simple matematiske konverteringsfunktioner.

Disse konverteringsfunktioner er nøglen til scrambling af billeder. Begynd med et billede, der består af 9x9 pixels. Læg derefter en Soduko-løsning oven på dette gitter, så hver pixel nu kan repræsenteres af de nye koordinatsystemer.

Nu, ved at anvende en af ​​konverteringsfunktionerne på gitteret, skifter pixelpositionen, og billedet blandes sammen.

Det, Wu og co har opdaget, er, hvordan man anvender en kort sekvens af konverteringsfunktioner, der fuldstændig forvrider billedet. Det er nyttigt, fordi det er helt deterministisk og alligevel producerer et tilsyneladende tilfældigt resultat (som vist på det øverste billede).

Dette svarer til en slags kryptering, hvor den originale Sudoku-løsning er nøglen. (For større billeder, fliser du blot billedet med flere Sudoku-gitter.)

Wu og co har foretaget en indledende sammenligning mellem deres metode og andre billedkrypteringsalgoritmer og siger, at den matcher eller overgår dem.

Og da der for et 256 x 256 billede er mindst 256!=2^1684 mulige Sudoku-matricer, er det ikke let for en modstander at ramme løsningen ved et uheld eller endda ved brute force.

Wu og co gør ingen påstande om dets potentielle sikkerhed, men der er helt klart plads til yderligere udforskning her.

Utroligt, hvad Sudoku kan gøre for menneskeheden!

Ref: arxiv.org/abs/1207.5856 : Sudoku Associated Two Dimensional Bijections for Image Scrambling

skjule