Project 2: Whispers in the Dark

Due by: Friday, October 10, 2025 at 11:59 p.m.

Introduction

Big Brother is watching! As we all know, our government has been infiltrated by Emperor Penguins hell-bent on destruction of the human race. Some of the top officials in the state and federal governments are actually penguins wearing human suits. We have sat by heedless as they wrapped their flippers tightly around the reins of power.

Is it too late? They control the media. They scour the Internet. But they cannot crack strong encryption ... The only solution is to organize a grass-roots rebellion through encrypted messages.


Overview

You will be given a bare-bones chat program that can function as both a client and a server. Your job is extend the functionality of the program to perform two cryptographic tasks. The first is to perform a Diffie-Hellman key exchange, which allows two parties to decide on a key securely without making prior arrangements or depending on a public key server. The second is to use the key that you agree upon to encrypt your messages with 128-bit AES encryption. The drawback is that you have to implement AES.

Your additions will focus on these two features.


The Bare-Bones Chat Client

The source for a bare-bones chat client is provided in the file Chat.java. When the program is fired up, it asks whether it is going to be a client or a server.

The Server

The server version of the program asks for a port number. You can use whichever port you want provided that it is not one in use by the system for other purposes. Port 4444 is a reasonable choice. Once you enter the port number, the server will wait indefinitely for a client chat program to make contact with it. Once that happens, they will establish a socket connection and be able to send data back and forth.

Both the client and the server are multi-threaded. After the initial setup, both versions of the program operate identically. The Receiver thread waits for messages. When it gets one, it prints it to the screen. The Sender thread waits for the user to type something. When he or she does, it prepends the chat handle to the message and then sends it over the network. As you can see, sending and receiving data over the network looks almost identical to writing and reading to files.

The Client

The client version of the program asks for an IP address and a port number. In order to have a successful connection, a server program must be waiting for a connection before the client tries to connect. The client should use the IP address of the server computer as well as the port it is using. To find out what IP address the server has, you can use the ipconfig command from the command line (or ifconfig if you are working in Linux).

Although Java networking is relatively easy to use, the Windows software firewalls on the lab machines as well as the network configuration that ITS uses can prevent Java programs from making socket connections with each other. Although I hope that we are able to use these chat programs to communicate from one machine to another, it may not be possible. To test your program, you can open a chat session on a machine with itself. To do so, run two copies of the chat program on the same machine. When the programs are running, choose whatever port you like and 127.0.0.1 as the IP address for the client. This IP address is known as a loopback address and allows a computer to send messages to itself.

Diffie-Hellman Key Exchange

A Diffie-Hellman key exchange is a clever and reasonably secure way to exchange keys with another party with minimal pre-arrangement. It is susceptible to a man-in-the-middle attack, but the attacker will have to intercept all future messages and re-encrypt them.

A Diffie-Hellman key exchange between Alice and Bob follows the following steps:

  1. The parties agree on a large prime P and a generator G. This information is public and does not detract from the security of the scheme if it is known by attakers.
  2. Alice creates a secret integer a < P.
  3. Alice finds A = Ga mod P.
  4. Alice sends A to Bob.
  5. Bob creates a secret integer b < P.
  6. Bob finds B = Gb mod P.
  7. Bob sends B to Alice.
  8. Alice finds S = Ba mod P.
  9. Bob finds S = Ab mod P.
  10. Since S = Ab mod P = Ba mod P = Gab mod P, Alice and Bob both have the same secret key S, which is a combination of both of their secrets.

The difficult part of the process is generating a large prime P and the generator G. (In this sense, a generator G is any number that, when raised to every power between 1 and P - 1, will produce every number between 1 and P - 1, though not in order.) For our purposes, use the following values for P and G:

  • P =
    1503964590181214937350756351313736462379772880268214049849947634651026866604558
    1988639991763652366004969935036371876440439844733512483209411053271110086101602
    4507364395416614225232899925070791132646368926029404477787316146244920422524801
    906553483223845626883475962886535263377830946785219701760352800897738687
  • G =
    1050035961690893947732787406738832829223024584503536341519911998163634055340401
    6182517655380670294469669909010317193946311892045257617589031202110099447145387
    0037718208222180811650804379510819329594775775023182511986555583053247825364627
    124790486621568154018452705388790732042842238310957220975500918398046266

With these choices of P and G, you can choose any 1023-bit integers for a and b. You should use the BigInteger class to hold P and G, to generate a and b, and to do all of the necessary modular arithmetic.

Once you have worked out the Diffie-Hellman parameters, the two parties in your chat should perform the key exchange with the client taking on the role of Alice and the server taking on the role of Bob. Note that using ObjectInputStream and ObjectOutputStream allow you to send whole objects across the networking in Java without the need to do any parsing. If you are not familiar with these classes, please read their documentation.

Or Don't Use BigInteger... (Extra Credit Opportunity)

For extra credit, you can choose to implement your own class to hold arbitrarily large integers. You are permitted to use any of the classes in the Java Collections Framework to aid in this task. Efficient implementations will store the data as lists of byte, int, or long values. Use a great deal of care, since these values are all signed in Java.

The minimum functionality that the class must support is whatever is needed to do the Diffie-Hellman key exchange:

  • Generation of a random 1023-bit number (This functionality is easy using a Random object once you have settled on your internal representation for large numbers.)
  • Fast exponentiation
  • Modulus
  • Extraction of bytes for use as a key

Although this list gives the minimum required functionality, you will clearly have to support multiplication in order to do exponentiation. Subtraction and a way to compare the values of two numbers will almost certainly be required to perform a modulus operation.

Before you start working on this extra credit, make sure that your project is working with BigInteger. Then, you can drop in your code as a replacement for BigInteger.

AES

Once you have performed the Diffie-Hellman key exchange, you will have a key. I specified a key in the neighborhood of 1023 bits to discourage any attacks that rely on finding the discrete logarithm of Gab. However, you only need 128 bits for an AES key. Using the toByteArray() method of the BigInteger class (or equivalent), you can get a sequence of bytes that represents the secret that your client and server have agreed upon. Use the first 128 bits (16 bytes) as your AES key.

Then, all chat messages sent back and forth should be encrypted with 128-bit AES using this key. Note that I have already set up the chat so that it is sending an array of bytes rather than String values. All you have to do is encrypt and decrypt those bytes using AES.

Note that you will need 128-bit (16 byte) blocks to encrypt with AES. If your message when converted to byte values is not an even multiple of 16, pad with bytes of value 0. Then, when you decrypt the message on the other side, strip away any 0-valued bytes from the end of the message.

The Algorithm

We have discussed the algorithm in class, and the book has additional details. There is a lot going on in the algorithm. Although the high level description is straightforward, the devil is in the details.

AES using a 128-bit key on 128-bit blocks has an initial round that only adds the round key, 9 normal rounds, and a 10th final round that is exactly like the previous rounds except that it has no mix columns.

Here is an outline of the encryption algorithm.

  • Load data into state
  • Generate round keys
  • Initial round
    • Add round key
  • Normal rounds (1 - 9)
    • Substitute bytes
    • Shift rows
    • Mix columns
    • Add round key
  • Final round (10)
    • Substitute bytes
    • Shift rows
    • Add round key

Load Data into State

The state that holds the data in AES is a 4 × 4 matrix of bytes. This data is loaded column by column not row by row. Thus, the sequence of bytes 0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0xA, 0xB, 0xC, 0xD, 0xE, 0xF would be loaded into the state as follows:

0x0 0x4 0x8 0xC
0x1 0x5 0x9 0xD
0x2 0x6 0xA 0xE
0x3 0x7 0xB 0xF

Generate Rounds Keys

We did not discuss the AES key schedule in any depth in class. It is somewhat confusing. 128-bit AES uses 11 round keys. The first round key is simply the overall key itself. For each of the remaining 10 rounds, you take the last 4 bytes of the previous round key, store it in a temporary location, and run it through the key schedule core. After the core, you XOR the data in the temporary location with the corresponding 4 bytes from the previous round key and store it in the temporary location. These 4 bytes become the next 4 bytes of the current round key. You repeat this process until you generate all 16 bytes of the round key.

The schedule core is straightforward: Shift the 4 bytes in the temporary location one byte to the left (moving the first byte into the last position). Then replace the 4 shifted bytes in the temporary location with their substitutions from the AES S-box. The values in the AES S-box are here. Then, only the first byte of the temporary location is XORed with the RCON value for the given round. The RCON values are here. (Note that location 0 of the RCON value is not used.)

Add Round Key

Adding the round keys is how the keys are combined with the ciphertext. For the current round, XOR the round key with each byte of the state. The bytes from the round key should be used in the same order that bytes are loaded into state. (Use the bytes down each column.)

Substitute Bytes

In both the round key generation and in each normal round of AES, individual bytes are substituted for other bytes using an S-box. The S-box is given here. If you store your state as byte values, realize that Java uses signed bytes. Thus, the value for each byte value is between -128 and 127, inclusive. Since you need to look up a substitution for these values in an array, you should add 256 to negative values when looking them up to normalize them to be between 0 and 255, inclusive.

Shift Rows

Shifting the rows is one of ways diffusion is generated in AES. Row 0 is rotated to the left 0 bytes. Row 1 is rotated to the left 1 byte. Row 2 is rotated to the left 2 bytes. Row 3 is rotated to the left 3 bytes.

Mix Columns

Mix columns also generates diffusion. It is one of the more difficult steps in the encryption process to get exactly right. Each individual column is combined with itself. Rather than describe it clumsily, I refer you to the Wikipedia article.

Decryption

Decryption is much like encryption. Its steps proceed in reverse order from encryption.

  • Load data into state
  • Generate round keys
  • Inverse final round (10)
    • Add round key
    • Inverse shift rows
    • Inverse substitute bytes
  • Inverse normal rounds (9 - 1)
    • Add round key
    • Inverse mix columns
    • Inverse shift rows
    • Inverse substitute bytes
  • Inverse initial round
    • Add round key

Inverse Shift Rows

Do exactly the opposite of shifting the rows. Row 0 is not changed. Row 1 is shift right by 1. And so on.

Inverse Mix Columns

Inverting the mix columns is so confusing that I provide the source code for this method and the supporting Galois multiplication below. 

private static void inverseMixColumns(byte[][] state) {
	byte[] a = new byte[SIZE];  

	for (int j = 0; j < SIZE; ++j) {	
		for (int i = 0; i < SIZE; ++i)
				a[i] = state[i][j];

		state[0][j] = (byte) (galoisMultiply(a[0],14) ^ galoisMultiply(a[3],9) ^ galoisMultiply(a[2],13) ^ galoisMultiply(a[1],11));
		state[1][j] = (byte) (galoisMultiply(a[1],14) ^ galoisMultiply(a[0],9) ^ galoisMultiply(a[3],13) ^ galoisMultiply(a[2],11));
		state[2][j] = (byte) (galoisMultiply(a[2],14) ^ galoisMultiply(a[1],9) ^ galoisMultiply(a[0],13) ^ galoisMultiply(a[3],11));
		state[3][j] = (byte) (galoisMultiply(a[3],14) ^ galoisMultiply(a[2],9) ^ galoisMultiply(a[1],13) ^ galoisMultiply(a[0],11));
	 }
}

private static byte galoisMultiply(int a, int b) {
	int p = 0;	
	int highBit;
	
	for (int i = 0; i < 8; ++i) {
		if ((b & 1) == 1) 
			p ^= a;
		highBit = a & 0x80;
		a <<= 1;
		if (highBit == 0x80) 
			a ^= 0x1b;		
		b >>= 1;
	}
	
	p &= 0xff;
	
	return (byte)p;
}

Inverse Substitute Bytes

The process of substituting the bytes can be inverted with another lookup table which does the inverse mapping. The lookup table for the inverse S-box is here.


Resources

This project is challenging, but there are many resources to help. The first, of course, is the textbook. Here are a number of websites to help you along:

Follow the examples in the last two links. Make sure your output matches at each step.

Hints

  • Start early.

  • Don't forget that Java uses signed byte values. You might have to be careful with casting and adding 256 in cases where the values are negative. Don't overcorrect!

  • Test each step of AES.

Submit

Zip up all the .java files you use to solve this problem from your src directory, including Chat.java and AES.java, and upload this zip file to Brightspace. Zip up only the source files, not the entire project. All work must be submitted by Friday, October 10, 2025 at 11:59 p.m. unless you are going to use a grace day.

All work must be done within assigned teams. You may discuss general concepts with your classmates, but it is never acceptable for you to look at another teams' code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.


Grading


Your grade will be determined by the following categories:

Category Weight
Diffie-Hellman exchange 30%
AES encryption 30%
AES decryption 30%
Style and comments 10%

Successful implementation of your own replacement for the BigInteger class is worth up to 20% extra credit.

Code that does not compile will automatically score zero points.