CS 2 (Winter 2021) Lab 10: Steganography

This lab focuses on using two-dimensional arrays, representation of images, and representation of numbers.


Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

Goals and Outcomes

One tool in Computer Science that we’ve seen over and over again this term is abstraction.
There are often many different ways of representing the same thing–each of which is useful in its own place. You deal with this regularly; for example png and jpg are different file formats for images, but they both “look” like images. Today, we will explore different representations of colors, images, and text. Along the way, we will explore a data-hiding technique called least-bit steganography which is one way to hide text in images.

By the end of this lab, you will…

Color Representation and Visual Perception

There are actually a surprisingly large number of ways to represent colors. Among the most common is a representation called “argb” which is used in pngs and stands for “alpha red green blue”. A single color can be described as four separate values that determine different aspects of the color:

In this lab, we will keep the “alpha” constant and only worry about the red, green, and blue values. This is an unnecessary simplification, but it makes the idea easier to explain. Assuming “alpha” is specified at “fully opaque”, the rgb values completely determine which color we’re talking about.

Consider the two following colors:

These two colors look indistinguishable to humans because of deficiencies in our visual perception systems, but to a computer, they really are different colors.
The “computer science” problem here is “how can we abuse this?”. The most common way this can be abused is in what’s called “lossy image compression”–we can use slightly different colors than in an original image to make it more “uniform” and thus easier to compress. We will explore a different usage of this phenomenon: transmitting secret data!

To do this, we’ll need to understand a bit about how ARGB values, images, and text are stored on computers. \end{question}

Pixels and Images

A pixel is conceptually a tiny square inside an image, and it has a single ARGB value. Pixels on a screen or in a photo line up in rows and columns. For example if a photo has a black border, it might have black pixels in the top and bottom few rows as well as the columns on the left and right edges of the image.

More formally, an image is a rectangular matrix of pixels which we can manipulate with all kinds of algorithms. In Java, we represent matrices as two-dimensional arrays. A two-dimensional array is represented as an array-of-arrays. Consider the following pictorial example of matrix and Java representations:

\[\begin{bmatrix} x_{00} & x_{01} & x_{02} & \dots & x_{0n} \\ x_{10} & x_{11} & x_{12} & \dots & x_{1n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{d0} & x_{d1} & x_{d2} & \dots & x_{dn} \end{bmatrix}\]
  {x[0][0], x[0][1], x[0][2], ..., x[0][n]},
  {x[1][0], x[1][1], x[1][2], ..., x[1][n]},
  {  ...   ,  ...   ,  ...  , ...,   ...  },
  {x[d][0], x[d][1], x[d][2], ..., x[d][n]}

The syntax for two-dimensional arrays is nearly identical to the syntax for one-dimensional arrays:

// To declare a two-dimensional int array with $$a$$ rows and $$b$$ columns:
int[][] array = new int[a][b];

// To loop through our array, we use two nested for loops:
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array[0].length; j++) {

Image Transposition

To explore 2D arrays, your first task is to write a “transpose” method in our Image class. Do not worry about the starter code which works with the internal Java implementation of png images. You only have to work with the two-dimensional array representation. This is, once again, an example of abstraction.

public Image transpose()

Returns a new Image which is a transpose (i.e., exchanges the rows and columns) of the original image. Does not modify the original Image.

You should loop through all of the pixels and put them into a new 2D Array.

It’s All Bits and Bytes!

ARGB Values as Bits

Each “channel” (single color value) of the ARGB pixel is represented as a number between 0 and 255. Normally, we write numbers in base 10, where the \(i\)th digit from the right represents how many \(10^i\)’s there are (hence the names “1’s digit”, “10’s digit”, etc.). Because computers are ultimately combinations of on/off switches, it is useful to look at binary representations of numbers. In particular, if we have a number \(N = (b_nb_{n-1}\cdots b_0)_2\), where \(b_i \in \{0, 1\}\), then \(\displaystyle N = \sum_{i=0}^{n}{b_i2^i}\). We call the individual “digits” bits; \(b_0\) is called the least-siginificant bit, because it contributes the smallest amount to the number’s value.

Text as Bits

All letters and symbols have numerical representations called ASCII codes. These are defined via a standard that is assumed to be used across all computers. We can use ASCII to convert letters from our messages into numbers. For example, 'A' == 65, 'a' == 97, and '!' == 33. You do not need (nor should you!) learn any of these actual values. The key idea here is that chars and ints are interchangable via casting. For example, this code snippet prints A:

char c = (char)65;

We can also convert from a char to a string by adding it to an empty string, like so:

String s = "" + j;

Putting it Together

Because pixels are so small, the difference in color between \(x\) and \(x+1\) is trivial enough to not be visible. Thus, this gives us the ability to store one bit of information per channel per pixel. To simplify our code, we will only hide data in the red channel. So, we can hide a single bit in a single pixel. This means that we can store a single ASCII value (which takes 8 bits) in 8 pixels.

If we iterate through the array going from the left to right, from top to bottom, collecting the least significant bits of every red channel, it will result in a series of bytes which we can interpret as an ASCII string (our hidden message!)

public String decodeText()

Returns the String hidden in the Image in the red channel LSBs of this image. Any recovered character with the value zero should be omitted.

Loop through all of the pixels and get the hidden bit using the getLowestBitOfR method in the Pixel class. Then, use sets of 8 bits to reconstruct bytes. Make sure to start filling in the bits from the right of the byte. That is, if \(h_0, h_1, h_2, ...\) are the bits recovered, then the first byte recovered should be \((h_7h_6h_5h_4h_3h_2h_1h_0)_2\). Each byte should give you a number which can cast into a char to get the ASCII value. Accumulate the chars, and return the final message.

public Image hideText(String text)

Takes in a message to be hidden, and then returns a new Image with the red channel LSBs manipulated to hold the message. Zeroes out all the red channel LSBs after the message is complete.

This method is the inverse of decodeText, and, as such, it will look very similar.
You will find the fixLowestBitOfR method in the Pixel class and the charAt method in the String class useful.

Checking the Results on gitlab

Getting Checked Off

At the end of every lab, you will need to call over a member of course staff to review your work. Sometimes, we will ask you to think about questions that you’ll review with the person who checks you off. For this lab, please answer the following questions:

Submit OpenEndeds For Credit