Sudoku Inspired Algorithm used for Encrypting Images

Yue Wu at Tufts University in Medford along with a couple of friends has used Sudoku’s 9×9 grid to formulate a completely new type of matrix mathematics. For readers who are not so mathematics savvy, a matrix is a rectangular array of numbers wherein each element can uniquely identified by its row and column number – in other words, its grid reference.

As Sudoku is the reference for new technique, according to Wu and co [PDF] it is possible to identify elements in an array such that each of the elements contains a digit from 1 to 9 and that it satisfies the rules of Sudoku. This means that each element can now be identified by a row reference, a column reference and a digit.

Considering the above Sudoku puzzle as the reference, the element in the first row and first column (1,1) is also associated with the digit 8, element (1,2) is associated with  7, element (1,3) with 4 and so on.

Further each element is also associated with a 3 x 3 block, numbered as shown in the grid above. So element (1,1) is associated with block 1, element (2,8) with block 7 and element (8,5) with block 6 and so on.

Through conventional notation, element in block 5 containing the digit 9 is element (4,5); the element in column 3 containing digit 7 is (8,3) and the element in row 6 containing  2 is  (6,9).

This means that there are a total of six different ways of representing each element according to Wu. Through the use of simple mathematical functions, the co-ordinates in one system can be converted to that of the other. 

When we consider encryption, these simple conversion functions are the key to scrambling images. So, how to go about it? One can start with an image made up of 9×9 pixels. Next, superimpose a Sudoku solution onto this grid such that each of the pixels can now be represented by the new coordinate systems. Now using any one of the conversion functions swap the position of pixels. This will effectively scramble the image.

Wu and his buddies have found a way to apply only a short sequence of deterministic conversion functions that completely scrambles the image producing a seemingly random result (see image below). How to get the original image back? Well using the original Sudoku as the key, the original image can be recovered.

Performance of the algorithm has been studied by Wu and co and they have found through initial comparison that their method of scrambling images either matches or outperforms other methods.

Talking about the strength of the algorithm, they say that even for a 256×256 image, there are at least 256!=2^1684 possible Sudoku matrices making it very hard for a cracker to nail the solution by accident or even by brute force.