Generating Images from Regular Expressions


There is an update to this post, which includes colors: https://ssodelta.wordpress.com/2014/03/25/creating-colored-images-from-regular-expressions/

Source code complete with Javadoc can be found at: http://pastebin.com/ccRK75aq

This post will detail a method for using regular expressions to generate images.

A regular expression is an array of characters, which represents a series of instructions, which for any input either matches or doesn’t match. For a simple example, the regular expression

ssodelta

Only matches the string ssodelta. This makes sense, but we can do pretty nice things with regular expressions. If we for example write

ssodelta|delta

Then the regular expression either matches ssodelta or the string delta. This is because the vertical bar | represents the symbol or. We also have so called quantifiers, the most important of which is the kleene star *.

sso(delta)*

The parentheses group strings together, like regular parentheses in mathematical expressions (2+4)*3, for example. The kleene star * means zero or more, meaning that there can be zero or more delta and it will still match the regular expression. A few matches include ssodelta, ssodeltadelta, ssodeltadeltadelta and so on…

I won’t completely detail regular expression, but if want to read up on it, I suggest close-reading the wikipedia article on the matter, but the bottom line is that regular expressions are really cool. But how can they be used to generate images?

Consider a completely square image, which is divided into 4 quadrants:

img1

We can refer to each of these four quadrants by their numbers 0,1,2,3, and we can further divide these quadrants into four numbers, and label them accordingly.

img2

But what does this have to do with regular expresssions? Well, we can have a regular expression, which only uses the characters 0,1,2,3 and every string adresses an area in this area. For example, the string 022 represents the area marked with red:

img3

We can decide on a resolution n, and generate all strings of length n, parse them through a regular expression, and if it matches, paint it black. For example, the regular expression (0|2)(0+1+2+3)* generates the following image (for any resolution >= 2):

test

This is because the regular expression only matches if the cell begins with a 0 or a 2, which is why the 0th and the 2nd quadrants are painted black, and the rest aren’t.

We aren’t limited to boring checkers though, if we feed the generator the regular expression (1+2+3)*0(1+3)*0(0+1+2+3)*:

really_large_triangle_fractal

Notice the self-similarity in the image, that’s because this image is actually a fractal.

Here is a gallery of other images generated using this technique:

also-cool-fractal bars  dots pik

Notice how often triangles appear in these images.

Although the .java file has an included Javadoc, here’s how you use it to generate images:

Generator g = new Generator(RESOLUTION, IMAGE_SIZE);
g.generateAndExport("REGULAR_EXPRESSION", "EXPORTED_FILE_PATH.png"); //Must be a .png file

If you prefer Python code, check out Jack Morris’ post on the same subject, where he implements it in Python: http://jackm.co.uk/posts/2014/03/25/Using-Regular-Expressions-To-Generate-Images/

Advertisements

Steganography and PNG’s MK-III


This is yet another follow-up post to my posts about encoding hidden messages in PNG’s: Article I, Article II.

Source code: http://pastebin.com/xWzMcayL

So far, we’ve only dealt with concealing text within PNG’s, but what about other things but text? In this post we’ll account for a method for storing arbitrary data within the least significant bits of a .PNG file.

Arbitrary data is, just like the text encoding we’ve used in the past two posts, composed of bits, so there’s no obvious reason why we shouldn’t be able to store other things than text within the least significant bits of the pixel of a .PNG file. However, data stored on the computer is composed of bytes (groups of 8 bits), and because we can store 5 bits per pixel, we can’t encode a byte into a single pixel. Instead, we choose to encode 5 bytes (40 bits) into 8 consecutive pixels (40 bits), which fits neatly. So, to store a file within a .PNG file, we’ll read it as bytes, and split these into groups of 5 bytes. Then we’ll “jump” (as explained in Article II) accordingly, and store these 5 bytes within the next 8 pixels. We’ll add 5 blank bytes (0x00) at the end of our data as an “exit code” – otherwise the program will read random bytes indefinitely.

We’ve used this to encode an image onto one of theses images of Barack Obama:

barack_osama barackobama

Hint: The password is ‘realobama’

The program is not limited, however, by images. You can encode literally any byte-string unto the least significant bits of an image. This includes .txt-files, .zip-files and even executables (!). So if you want to send a secret file within an image, this is the program for you!

The source code is found at the top of this post. Note: You need the Group-class found in Article II for the program to work properly.

Future plans: This program is easily susceptible to deciphering – even without knowing the passphrase. I might construct a decoder eventually.

Here’s how to use it with the new features:

//Encoding
Encoder e = new Encoder("path-of-image-file.png");
e.encodeFile("path-of-file-to-encode", "password");
e.saveFile("new-embedded-image.png"); //Again, we encourage .PNG

//Decoding
Encoder e = new Encoder("path-of-image-file.png");
e.saveContentFile("path-of-extracted-file", "password");

Steganography and PNG’s MK-II


Note, this is a follow-up post to the post on embedding secret information inside of  PNG-files: Steganography and PNG’s

Source code: http://pastebin.com/nTS9Dp0M

In my last post, I introduced the concept of concealing information within the least significant bits of an image file. However, there was a major flaw in the design – it was far too easy to read the hidden information, as it embedded it into the bits systematically.

In this post we’ll introduce keys and develop a method for embedding information inside of an image file, that requires a password to extract the original bits. If we look at how the encoder embedded bits in the original post, we’ll see that it “jumps” one pixel at the time on the x-axis and warps on the y-axis when needed. If we change these “jumps”, we can change which bits get selected in a reproducible manner. Great!

However, there’s a fatal pitfall that we must avoid to implement this idea – the jumps must not repeat the same pixels over and over again. It is absolutely vital that it selects a unique pixel every time. We can actually look at these jumps as multiples of an element in a group. An element m of the group Z_n / Z is a generator of the group, if it’s coprime to n (i.e. gcd(n, m) = 1). To accomplish this, we can just select the jump interval to be a prime (note, this assumption is wrong), then we’ll make sure never to repeat the same pixel over and over again. Fantastic!

For the key, we’ll take as input any string. The key (which needs to be an integer) will be the hashcode of the string modulus the size of the group (for an image of size w \cdot h the size of the group is w \cdot h). Then we’ll find the closest prime using a simple primality test, and we’re good to go.

barack barack_2

Hint: The password is ‘obama’

The only weakness as far as I see it, is that the program starts encoding at (0, 0) every time, but I’ll get around to changing that eventually.

Steganography and PNG’s


Source code for this project can be found at: http://pastebin.com/GiSavbfz

Steganography is the act of hiding a message in such a way, that only the intended recipient is able to retrieve it, often in plain sight. Note, this is not  the same as cryptography – cryptography is a completely different discipline. Sidenote, if you actually intend to send secret messages to someone else, please, please do not use steganography. Steganography is fun and all, but it’s not a reliable secure way to transmit secret information.

An image is composed of a bunch of RGB codes for every pixel. Each color code has a corresponding integer value associated with it (between 0 and 255), and integers are composed of bits. This means that every pixel has three 8-bit binary codes associated with it, giving the pixel its color. However, not all bits in the binary code are of equal importance. Altering the final two bits of say the red color code will hardly be noticeable for us humans. How can we use this to transmit secret information?

A message is, just like the color codes, composed of bits. And because altering the least significant bits in the color codes won’t make a noticeable difference, we can encode a message into the least significant bits of the color codes. Clever, eh?

In our implementation, we choose a 5-bit alphabet for encoding our messages. We won’t need anymore if we’re sending top-secret information to our pals – styling and unicode is not of importance. We’re choosing the letters A-Z (0-25), space, and basic punctuation (dots, commas, exclamation mark, question mark and apostrophe), for a total of 32 characters, which fits neatly inside 5 bits.

The human eye is best able to detect changes in contrast in the green channel, so we’ll take two bits from the red channel, two bits from the blue channel, and one bit from the green channel for each pixel. This means we can encode one character into one pixel on the image, which allows us to transmit pretty huge messages in just a single image.

00000000
00000000
00000000

The black bits our ours, the rest are reserved for the pixel. We went ahead and encoded a message onto on of these images of Barack Obama:

obama_yes obama_terror

Can you tell which is the fake Barack Obama?

You can find a link to the source code at the top of this post. Here’s how you use it:

//To encode a message
Encoder e = new Encoder("path-to-image.png");
e.encodeMessage("your-message-here");
e.saveImage("path-of-new-image.png"); //We advise against using lossy image formats, such as JPEG, as they'll ruin the hidden message.

//To retrieve a message
Encoder e = new Encoder("path-to-image.png");
String hiddenMessage = e.getMessage();