APL WikiFun with secret messages hidden in pictures
Contents
A previous Wiki article discussed how to hide a secret message in a block of apparently random text, a 500-year old technique known as a Grille Cypher. For a bit of fun, let's look at the modern equivalent - how to hide a message inside a photograph. In the example below the first picture is unmodified, but the second one has a 1000 word secret message hidden in it. Can you spot the difference?
(Note that the images actually shown on the page are PNGs because at least Chrome does not support BMP any more; however, the technique discussed here works with BNPs only. You can download the BMPs by clicking at the "download as BMP" link)
Although hiding secret messages inside photos might attract the attention of the NSA it does have legitimate uses. For example you could protect the copyright of your own photos by adding a secret watermark.
Pixel Colours
Modern computers typically use a 24-bit encoding for colours. Each of the Red, Green and Blue components of a pixel is represented using 8 bits, so a modern graphics card can display (2*8)*3 or 16777216 different colours. In fact the colour value is often encoded in a 32-bit word with one byte for each of Red, Green and Blue; the high byte is either unused or represents a transparency value.
A person looking at a colour image is very unlikely to notice if we make very slight changes to the pixel values. For example we can flip the bottom bit of the pixel colour, making a tiny change to the red component, and it's almost certain to pass undetected. We can use this to hide a secret message inside a picture.
For the demonstration which follows I'll assume that the photograph has already been read into an APL variable, and that it takes the form of an M x N matrix, where M and N correspond to the dimensions of the photo. Each matrix element is an integer representing the 32-bit encoded colour of a single pixel. (At the end of this article I've included a brief description of how to read in a picture using APLX).
Random Numbers
APL is able to generate random numbers using the ? function. For example to get 10 random numbers in the range 1 - 20 you could type:
10?20 10 9 13 3 20 11 6 16 5 8
Normally if we type 10?20 again we will get a completely different sequence of random numbers. However by re-setting the Random Link ⎕RL we get a repeatable sequence:
save_rl←⎕RL
10?20
20 6 10 7 4 2 14 18 15 19
⎕RL←save_rl
10?20
20 6 10 7 4 2 14 18 15 19
We can use this information when hiding the message in the picture. First we choose a random sequence of pixels to modify, so that the tampering is less likely to be noticed. Provided that the person receiving the modified picture knows the value of ⎕RL we used and the sequence length, they will be able to reconstruct the random sequence so they will know which pixels contain the message.
For simplicity the example below hides ⎕RL at the start of the picture, together with the length of the secret message. If you care about security you could omit ⎕RL and use a pre-agreed value instead!
Converting a value to Binary
We want to hide the secret message by only modifying the bottom bits of randomly selected pixels, which means that we can only store 1 bit of information per pixel. (You could be more sophisticated and modify the bottom bit of each of the Red, Green and Blue components, allowing 3 bits per pixel, but this is left as an exercise for the reader).
This means that we need to convert the secret message to Binary, which can be done using APL's Encode primitive ⊤. Here is an example of an encode of the numbers 1 2 3 4 5 and the corresponding decode:
encoded←(8⍴2) ⊤ 1 2 3 4 5
encoded
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 1 1 0 0
1 0 1 0 1
2 ⊥ encoded
1 2 3 4 5If you're familiar with binary format you can see that each column in encoded corresponds to one of the numbers 1 2 3 4 5 converted to binary.
Modifying the bottom bit of a number
We're now ready to insert our binary-encoded message into some randomly chosen pixels. One way to do this would be to convert the pixel values to binary too, replace the bottom bits with values from our message, and convert back to integers. However, there's an easier way; we compare the current value of each bottom bit to the desired value, and flip it if it's wrong.
For example, imagine you want to insert the binary message 1 0 1 1 0 1 0 1 into the bottom bits of pixels with the values 5012853 1921862 1858884 5282424 9758136 7981975 9492903 6200428. The current values of the bottom bits are found by testing whether the numbers are even:
vals←5012853 1921862 1858884 5282424 9758136 7981975 9492903 6200428
2 | vals
1 0 0 0 0 1 1 0In some cases the current bit already equals the desired bit. In other cases it's a 0 and needs to be a 1; and in other cases it's a 1 and needs to be a 0. We can handle this as follows:
encoded←1 0 1 1 0 1 0 1
vals ← vals + encoded - 2|vals
vals
5012853 1921862 1858885 5282425 9758136 7981975 9492902 6200429Finally we can recover the secret message:
2 | vals 1 0 1 1 0 1 0 1
The final functions
We're now ready to put all the steps together into two functions as follows:
∇ R←bitmap EncodeText text;bm;length;encoded;random;idx;vals ⍝ ⍝ Takes text and encodes it into least significant bits ⍝ of bitmap, where it will be embedded without affecting the ⍝ visual appearance of the bitmap bm←,bitmap ⍝ Each character of text will give 8 binary digits length←8×⍴text ⍝ Encode the value of ⎕RL and the text length. Each one is a 32-bit quantity encoded←,(32⍴2)⊤⎕RL,length ⍝ Encoded the text message too encoded←encoded, ,(8⍴2) ⊤ ⎕av⍳text ⍝ Choose random positions to modify, except for ⎕RL and the length, ⍝ which we'll put at the start of the bitmap so the decoder can find them random←64+length?¯64+⍴bm idx←(⍳64),random ⍝ Modify the bottom bits vals←bm[idx] bm[idx]←vals + encoded - 2|vals ⍝ Reconstruct bitmap with secret text embedded R←(⍴bitmap)⍴bm ∇
∇ R←DecodeText bitmap;bm;rl;random;vals;⎕RL ⍝ Regenerate the sequence of random numbers bm←,bitmap (rl length)←2⊥(32 2)⍴2|64↑bm ⎕RL←rl random←64+length?¯64+⍴bm ⍝ Extract the binary representation of the text vals←2|bm[random] ⍝ Reconstitute the secret message R←⎕av[ 2⊥(8,length÷8)⍴vals ] ∇
Author: SimonMarsden