Recent Demonstrations: Visual Encryption

When I was a kid, dinosaurs and secret codes were topics of surefire interest, since one was useful for eating your little sister and the other one for denying her the password to the clubhouse. I haven’t noticed any Demonstrations about dinosaurs yet (I continue to keep an eye out), but interesting ones about cryptography turn up regularly, including a couple of neat recent entries on visual encryption: Michael Schrieber’s Visual Encryption Pad and Paul van der Schaaf’s Graphical Modulo-4 Image Encryption.

One cipher (if you can call it that) common in my kiddie code books involved printing a message in red stipple overlaid with a noise field of blue stipple. You could use the piece of red cellophane included in the back of the book to mask out the blue part and reveal the secret message. The Visual Encryption Pad Demonstration is the sophisticated cousin of this scheme, involving the overlay of a random bit mask (the key) with another bit mask of the same size (the message). Applying a set of rules to the combination of bits at a given pixel (in the case of this Demonstration, XNOR) reveals the message, which might look like this:

If your spies in the field don’t have computers, and you are limited to passing around messages on microfilm or something, then the only bit-combination rule set you will be able to use is OR. And of course your messages are limited to one bit per pixel. The Graphical Modulo-4 Image Encryption> scheme, on the other hand, can encode more than one bit per pixel, even on physical media. Let me quote some snippets of the Demonstration’s code and describe how they work, and then I’ll discuss a couple of extensions that suggest themselves.

Our key and message will each consist of a hexagonal grid, and at each grid location will sit one half-hexagon:

The half-hexagons in the key will be rotated by random multiples of π/3 (the allowed discrete rotations of the hexagon). The half-hexagons in the message will be rotated by the corresponding rotation in the key, plus an amount that depends on the gray level of that pixel in the source image. To decode, you lay the key on the message, as with Visual Encryption Pad. Now, though, each pixel in the decoded image will consist of two overlapping hexagons. The possible overlaps of half-hexagons are these (I’ve colored the key and message polygons reddish and blue, so you can see the purple where they overlap):

Note that in each configuration there are either zero, one, two or three pie slices exposed. So by means of this hexagonal-pixel scheme we can represent a 2-bit grayscale image.

Let’s try it. In keeping with the recent Dmitri Mendeleev theme in the blog, here is a portrait of Mr. Mendeleev, reduced to four gray levels:

This image has about 3,000 pixels. This will be our message: pretend he’s a high-ranking Soviet scientist preparing to defect to the West, whom you want your operative to be able to identify at the extraction point. That, or you want to use his name as the clubhouse password. We can ensure there are in fact four gray levels:

Now we need a key:

This key is just a matrix of random multiples of π/3 (modulo 2π). The matrix has the dimensions of the image. Note there are no hexagons involved yet; the matrix values are just real rotation values. Now we’ll convert the gray levels in the image to rotations, and add them to the key. This will yield an “encrypted image,” although again there aren’t any hexagons involved yet.

Gray level 1 (black) has been mapped to a rotation of π, and gray level 4 (white) has been mapped to a rotation of 0. You can visualize this matrix in a number of ways—ReliefPlot[] is useful because it automatically turns the matrix upside down, with row 1 at the bottom.

You can still make out the vestiges of a face here, but converting these values to rotations of polygons will reduce them all modulo 2π and essentially erase any visual structure. Now we render the hexagons in the encrypted image.

This piece of code (as complicated as it gets in this application) makes a table of half-hexagon vertex coordinates, with each coordinate set rotated as indicated by our encryptedImageDataSet and then translated to its position in the hex grid. The reflection transform looks weird, but just swaps x and y coordinates at each point, converting a vertically aligned hex grid to a horizontally aligned one. The hexEncryptedImageDataSet is a list of pairs suitable for feeding to GraphicsComplex[]. The result of that can be fed to Graphics[], and the result of that can be fed to Rasterize[]. The key is rendered in the same way, so we’re just about done. Here’s what they look like: message, key and the overlay of the two, with Mendeleev starting to look like one of those Che Guevara silkscreens. I squash the images to preserve the aspect ratio, since mapping onto a horizontally aligned hexagonal grid makes an image a little taller.

Animation

Here is an animation of the decoding. You can of course do all of this yourself if you download the Demonstration or this notebook, or both.

More Is Better

So far, we haven’t done anything not already in the Demonstration (which incidentally takes about a page of code). The decoded image won’t win any awards for image quality, principally because the brightest white level you can represent is already 50% black, and also because rendering the image anywhere close to its native DPI tends to introduce graphical scaling issues that compromise the color-averaging effect at each pixel. But it’s important to note that no compression has taken place. If you were a spy holding two cigarette papers up to a light bulb in a train compartment while the KGB lurked outside in the corridor, you would have to make do. If you were a spy with Mathematica, however, you could reconstruct the original image without loss.

You can see why the author chose a hexagonal grid for this encryption scheme: the hexagon is the most-sided polygon that yields a regular tessellation of the plane. One could have done this same project with squares, for example, but then the message would have been limited to three gray levels:

Is the hexagon is as good as it gets? There is one semiregular tessellation of the plane, the truncated hexagonal tiling, that might be interesting for these purposes. It is made of dodecagons and looks like this:

With overlapping dodecagons as pixels, we could accommodate 12/2 + 1 = 7 gray levels. The possible overlaps look like this:

Moving up to seven gray levels sounds promising, but there is the disadvantage of having a little filler triangle at every vertex. How much of the image area is lost to these triangles? The formula for the area of a polygon with n sides and side length s is:

For an image x pixels wide and y pixels tall, there will be xy dodecagons and 2(x – 1)(y – 1) triangles; the ratio of triangle area to dodecagon area for an a x a image reduces to

Let Mathematica do the limit:

This limit is approached from below, so in practice we’ll lose about 7% of the picture area for the smallish images we’re dealing with here. That doesn’t sound unacceptable, so I’ll keep going. In this notebook I’ve wrapped some functions around the Demonstration code, and duplicated a set of these to work on dodecagons instead of hexagons. The grid units and pixel primitives are of course different in the dodecagon scheme, but the code is otherwise almost identical to that used in the Demonstration and no additional steps are necessary. We can compare a decoded 4-level Dmitri and a decoded 7-level Dmitri side by side:

As you can see the little interstitial triangles are noticeable on the right but not a deal-breaker.

Steganography

I might be able to convince you with the images above that the modest improvement in image quality is worth it for its own sake, but now I’d better reveal my ulterior motive, which is to hide a message in the image.

The application so far has involved encrypting a source image with a key, which creates something that looks dubious. If the KGB or your little sister found the encoded message on you, they would suspect you were up to something. After playing with the image encryption, I found myself wondering whether the procedure could be easily inverted, so that a key applied to a normal-looking image (“normal”) would reveal a secret message. Since we are only depending on the fractionally black content of each pixel to communicate the image content (for a half-black hexagon, your eye doesn’t care whether the top half or the bottom half is black), perhaps we could use the phases of the pixels to store information. In effect, rendering the image as partially filled polygons introduces a channel. We won’t be able to make use of the all-black pixels, because you can’t tell which way those are rotated. But the remaining 6 values (3 for hexagons) would be able to take on one of 12 (6 for hexagons) rotational positions within each pixel. If n is the number of non-black pixels in the image, then we can encode n Log[2, 12] bits in our side-channel. For the 7-level Dmitri, that works out, in bytes, to

The function grayify[] here just converts the source image to a grayscale image with the specified number of levels. This picture may not be worth a thousand words, but it’s worth about a thousand characters (for more capacity you could even hide things in the little triangles). What can we fit in this 1 KB? For Mendeleev’s sake it would be have to be a periodic table.

You can in fact one-line a much fancier periodic table than this (for starters, there is a nice one in the ElementData[] documentation), but this one has the virtue of being only 385 B. We could compress it or encrypt it secondarily if we liked. I have to construct a base-12 representation of the secret message, but that turns out to also be a one-liner:

The procedure from here on is a bit different from the Demonstration, as we have to construct a stand-alone polygonal representation of the source image. The pixels in the encoded image are filled directly from the seven possible primitives, and do not derive any additional rotation from their gray level. As before, though, we generate a key of rotations. We add this to the secret message rotations we just made, and apply the total rotations to the image polygons. The resulting image contains pixels that have been rotated relative to the key only where the secondary channel is in use.

This notebook contains a function, steganify[], that accepts a source image and a message, and returns an image with the message encoded in it and a key. Applying this to Dmitri and the periodic table, we get:

The encoding on the left, believe it or not, contains the periodic table. The reddish image in the middle is the key. Compositing the first two gives the image on the right. If you look closely at the top quarter or so of the overlay (see the larger version), you can see reddish confetti among the blue and purple. These are pixels where the encoding and key polygons are out of phase; the phase difference corresponds to the base-12 digit of the message at that point. Everywhere else you see either blue or purple, meaning the encoding and the key polygons overlap.

Extracting the periodic table from a rasterized encoding and key would be tough with or without a computer, although if your message recipient were imprisoned in the gulag and had time on his hands, he could work through the overlay polygon by polygon, noting the phase difference at each pixel, and eventually reconstruct the message.

Mathematica proves exceedingly useful in situations like this, where an idea gives you an idea and you want to see where they lead together. I find it transitions nicely between casual and in-depth investigation: I start out intending to spend five minutes with a neat-looking Demonstration and find I’ve gotten far deeper into it than I’d ever planned. The only downside, as far as I can tell, is that there’s nothing to keep your little sister from using it too.

Download this notebook.