15-123 Effective Programming in C and UNIX
Lab 5 – Image Encryption with BMP Images
Due Date: Saturday March 28th, 2009 by 11:59pm
Background:
Encryption is a method used to protect data from intruders during transmission. The idea of data
encryption is to scramble data using a specific key, so attackers would need to know the key to
decrypt the data. The reverse of data encryption is called decryption. Decryption algorithm will
recreate the original data file. For example, a naïve encryption of an ASCII file is to encrypt each
character just by adding 1 to each character. That is replacing each character by its successor in
the ASCII table. So ‘a’→‘b’ , ‘b’→‘c’, …, ‘t’→’u’. So the word “bat” would be encrypted as
“cbu”. Now applying the decryption algorithm (or just subtracting one from each of the
encrypted characters “cbu” or by replacing with its predecessor will produce the original word
“bat”. Although there are number of research results available on image encryption, our goal in
this assignment is not to use one of the more advanced algorithms, but try out number of simple
algorithms, some of your choosing, that would allow us to work with binary files, do some bit
manipulations, encode and decode image files. For simplicity we will consider only the
uncompressed image formats like BMP (jpeg and gif are compressed forms of images). Here is
some background information about BMP’s.
The BMP file format:
The images we are planning to encrypt are in the BMP file format, which is one of the most
popular uncompressed file formats for images.
Note that you will need to find a way to view the images for this assignment. I recommend
writing and testing the program on Andrew Unix and using SSH File Transfer Client to view the
files on the local machine using MS Paint to see if the encryption is working. If you are working
on a Linux cluster machine, you can also use the command “display” ($ display
image.bmp) to view the image assuming x terminal is installed.
Your program should be able to encrypt any bitmap file of size n by m pixels. The actual size of
a BMP image of n by m pixels is given by (3·n·m + 54+ some extra bytes) bytes. Each BMP file
allocates 54 bytes for header information, and each pixel takes up 3 bytes for Red, Green and
Blue (RGB). Extra bytes may be used for padding purposes. We should not encrypt the BMP
header or the extra bytes. You should just read the first 54 bytes into an array, and when you
write it out again, you should just write the header bytes unchanged. The pixels of a color image
are stored in RGB format, which means that each pixel is represented by three bytes, one for red,
one for green, and one for blue. One byte can store numbers in the range 0-255. So the color red
is (255, 0, 0) and green is (0, 255, 0). And (128, 0, 0) make dark red, and (255, 0, 255) makes
purple since purple is red + blue. It is important to note that the pixels are stored from left to
right and from bottom to top (upside down!). So the first m groups of three bytes (3·m bytes) in
the file (after the 54-byte header) correspond to the bottom row of the image, and the last m
groups of three bytes correspond to the top row. Also make sure that you figure out whether
image has extra bytes or not.
The form of a bit map image are given as follows.
You can simply think of the file structure as
The left most RGB is the lower right pixel of the image and last RGB is the upper left pixel of
the image.
Suggested Data Structure:
We really do not need any special data structure to do this program. Just a simple array of
characters is good enough to store all the bytes in the file. However, maintaining some of the
image attributes in a struct such as
typedef struct {
char* data;
char* header;
int height;
int width;
int size;
} Bitmap;
will help us perform the necessary operations on the image. For example, we can invert the
image or shift pixel rows of the image etc. The data field inside the bmp struct will contain the
array of bytes that make up the image. The header field will contain the header information and
will not change in any operations. Each field requires allocation of dynamic memory as needed.
The structure of the 54 byte header of a BMP file is as follows. The first 14 bytes are allocated
for
H
eader
–
54
bytes | R G B R G B
R G B
extra bytes
typedef struct {
unsigned short int type; /* BMP type identifier */
unsigned int size; /* size of the file in bytes*/
unsigned short int reserved1, reserved2;
unsigned int offset; /* starting address of the byte */
} HEADER;
The next 40 bytes are reserved for a structure as follows.
typedef struct {
unsigned int size; /* Header size in bytes */
int width,height; /* Width and height in pixels */
unsigned short int planes; /* Number of color planes */
unsigned short int bits; /* Bits per pixel */
unsigned int compression; /* Compression type */
unsigned int imagesize; /* Image size in bytes */
int xresolution,yresolution; /* Pixels per meter */
unsigned int ncolors; /* Number of colors */
unsigned int importantcolors; /* Important colors */
} INFOHEADER;
The Assignment
In this assignment we plan to complete number of functions so that we can read, write, encrypt
and decrypt images.
Part 1 – In this part of the assignment you are simply trying to read, store and write a BMP
image file. You are to complete the following functions.
//Read the image into mybmp. You must allocate just enough memory to hold the
image bytes. This can be done by first reading the header and figuring out
what the size of the image is
void readImage(char* infile,
Bitmap
* mybmp);
// writes the encrypted image to outfile
void writeImage(char* outfile,
Bitmap
* mybmp);
You also need to complete the main program so that when the command
$ ./lab5 file1 file2
It will simply read BMP file1 and write to BMP file2. When you open file2 using an image
viewer, you should see the same image as in file 1. This will allow us to make sure, we can read
and write BMP images.
Part 2 – In this part of the assignment you are to write a “non-trivial” encryption algorithm to
encrypt your image. You should also write a decryption algorithm to recover the original image.
See “Suggested Algorithms” area below to see some suggestions. A “trivial” algorithm is one
that just negate the bits or uses a flag to mask the bits. A non-trivial algorithm will try to distort
the image while keeping some attributes.
You are to write at least the following functions:
// encrypt the image using a non-trivial algorithm.
void encrypt(
Bitmap
* mybmp);
// decrypt the image. You are free to use the inverse of the encrypt
void decrypt(
Bitmap
* mybmp);
You also need to complete the main program to handle “-e” and “-d” flags
$ ./lab5 –e file1 file2 //encrypt file1 and write to file2
$ ./lab5 -d file2 file1 // decrypt file2 and write to file1
Part 3 – In this part of the assignment you are to write a simple rotate function that will rotate
the current image by 180. This is not difficult if you really think about how the image is stored.
//rotate makes the image upside down or rotation by 180 degrees
void rotate(Bitmap *bitmap);
You also need to complete the main program to handle “-r” flags
$ ./lab5 -r file1 file2 // rotate file1 and write to file2
Part 4 – In this part of the assignment you are to implement a known algorithm that allows us to
hide a message inside an image. Steganography is the art and science of writing hidden messages in
such a way that no-one, apart from the sender and intended recipient, suspects the existence of the
message, a form of security through obscurity[source: Wikipedia]
In this part we will only test the following two images.
//This will apply the following algorithm to an image. Remove all but last
two bits of each color component. Make the resulting image 85 times brighter
void coolAlgorithm(
Bitmap
* mybmp);
This algorithm will take this image
and convert to this image when you apply the above algorithm. That is, remove all but last 2 bits
of each color component. Then multiply (or bit shift) the color component by 85.
[
source: Wikipedia
]
You also need to complete the main program to handle “-r” flags
$ ./lab5 -c file1 file2 // tree is converted to a cat –really cool!!
Style Points
Proper use of functions (passing/returning arguments etc), commenting, style, handin, compile,
indenting, and efficiency of the solution are worth an additional 10 points.
Algorithms for Part 2:
You need to use a “non-trivial” algorithm to decrypt the bytes of the file. A trivial algorithm is
one that negates each bit of the image. The decryption algorithm then will negate the bits again
to get the original image back. Here is what happens to Prof. Guna when we applied that
algorithm to his image.
Here is a series of other encryption algorithms by manipulating the color depth of the original
image.
Be creative and come up with an encryption algorithm that does something really cool (like
complete distortion). Ideally, after you apply your encryption algorithm, we should not be to tell
what the original image was but has a shadow of the image.
Shifting the bit patterns to encrypt may not be a good idea. Be careful! You encryption algorithm
cannot afford to lose any bits! Masking is a good way to turn off some bits and then unmasking
can recover those bits. We will discuss masking techniques in class. Here are some more
examples of encrypted images using a simple mask:
More examples
Running the program:
Use the Makefile to test your program. Your program should run by typing files names and
command line options as follows.
$ ./lab5 –e file1 file2 //encrypt file1 and write to file2
$ ./lab5 -d file2 file1 // decrypt file2 and write to file1
$ ./lab5 -r file1 file2 // rotate file1 and write to file2
$ ./lab5 -c file1 file2 // apply cool algorithm
Extra Credit: There is some opportunity to get extra credit in this assignment. TA’s will
consider giving up to +5 points for really cool algorithms. You should write why it is a really
cool algorithm in a readme.txt file in the handin folder. For more advanced users, you can also
think of how to implement an “edge detection” algorithm. Edges can be detected, in theory, by
observing changes in depth of color intensity, variations in scene illumination, change in material
properties etc. Your algorithm can generalize to images say, passport images of people, so you
can mark the outline. If you are completing this part, give a link to an image folder you tested
with so TA’s can try things out. Mark the outline with a red pixels.
Commenting your code: Please comment your code to show what you are doing. The least
amount of comments is a short description at the beginning of each function that explains what it
does, what parameters it takes, and what the expected output or return value is.
Downloading your code: You can download code from
/afs/andrew.cmu.edu/course/15/123/downloads/lab5
All updates will be available from FAQ.txt from the Bb
Submitting your code: submit main.c to /afs/andrew/course/15/123/handin/lab5/yourid. DO
NOT submit any image files you are using to test the program.
