CS475: Computer Networks - Encrypted Chat Protocol (100 Points)

Assignment Goals

The goals of this assignment are:

1. To relate the mathematics of modern encryption systems to applied principles of information hiding
2. To implement mathematical theory in the Java programming language
3. To design and implement a network protocol with a client and a server

The Assignment

This assignment is adapted from Prof. Mongan’s assignments in communications and introductory cryptography [¹, ², ³], and from the CS Unplugged Public Key Encryption lesson module [⁴].

Part 1: A Threaded Chat Program

Begin by writing a multi-threaded chat program. Allow users to send and receive String data, and use a special message (that you can decide) to quit the program. When the user enters this quit message, be sure to send your partner the quit message, so that both sides exit gracefully!

Your program should spawn a thread whenever a connection is accepted by the server, and this thread should spawn threads to send and receive data, so that these occur asynchronously. It is possible to re-use the connection thread as either the sending or receiving loop, such that this connection thread only needs to spawn one additional thread for the second communications loop.

Part 2: Encrypting Messages with the RSAMath Library

The mathematics functions used in this assignment are provided in the jar file library rsamath.jar. First, download the jar to a location you’ll remember. To use this jar, after creating a Java project in NetBeans as usual, right-click on the project in your left project navigation pane (you can click the Window menu and select Projects if you don’t see this), and click Properties, as shown:

Click the Libraries category on the left side of the window that appears. Then click, the + sign next to the word Classpath, and click Add JAR/Folder, as shown:

Finally, navigate to the jar file you downloaded earlier, and double click on it to add it to your project. Click OK to close the window, and you’re done!

To see which functions are available in the RSAMath library, see the Javadoc. The RSAMath class is implemented in the cs4hs11.rsalibrary package, which you can import in your program. If you get an error indicating that the RSAMath methods are not static, you can create an RSAMath object and then call the functions on the resulting object. Here is a listing of the methods you’ll find in this library:

Step 1: Encrypting Characters Using A Public/Private Key that We Create

Generate a Public/Private Key Pair

Write a function to generate a public and private key pair and print these to the screen. Write a main() function to test this functionality.

A number N is prime if no number from 2 to N-1 divides evenly into it. That is, \((N (mod \; k)) \ne 0\) for all \(k \in [2, N-1]\).

Once you generate those prine numbers (let’s call them A and B), you can generate your public key (E, C) and private key (D, C). Recall that the value C is shared between the public and private key, and that E and C are made available to others so that they can encrypt data to you. Your private key (D, C) is needed to decrypt those values, so you must keep the value D a secret!

To generate your public key:

1. Choose two prime numbers A and B. Make these prime numbers at least 2 digits in length, but no more than 3 digits. In practice, the values are much larger, but this is a demonstration.
2. Compute \(C = AB\).
3. Compute \(M = \phi(C)\) by computing (A-1)*(B-1). This will be equal to the result of the RSAMath.totient(C) method if your values of A and B are prime.
4. Compute E, a value co-prime to M. The RSAMath.coprime(M) method can help you do this.
5. Compute D, the modular inverse of \(E (mod \; M)\). The RSAMath.mod_inverse(E, M) method can help you do this.

Here is an example:

So, to get started, you can compute E as follows:

// do this import at the very top
// import cs4hs11.rsalibrary.RSAMath;

long A; // assign this to a prime number, perhaps from the Scanner or by computing one via a function
long B; // assign this to a prime number, perhaps from the Scanner or by computing one via a function
long C = A*B;

RSAMath rsa = new RSAMath();
long M = (A-1)*(B-1); // equal to rsa.totient(C), but much easier to compute! 
long E = rsa.coprime(M);

Encrypt Data Using a Public Key

Given a public key (E and C) as parameters, write a function to encrypt a given value, and return the encrypted value. Print this value to the screen.

Here is an example:

The RSAMath.endecrypt(X, E, C) function will help you to do this, by encrypting the value X using the encryption key E and C.

Decrypt Data Using a Private Key

Similarly, accept a private key (D and C) as parameters, write another function to decrypt a given value, and return that decrypted value. Print it to the screen as well.

The procedure is similar to that used to encrypt a value. The RSAMath.endecrypt(X, D, C) function will help you to do this, by encrypting the value X using the encryption key E and C.

Here is an example:

What do you notice about the encryption and decryption functions you just wrote? (Click to reveal)

They're exactly the same! They only differ in the input parameters (what values are used for the keys). This is because the mathematics results in the computation of the modular inverse of the value. The same function can be used on two different problems!

Step 2: Communicating Secret Messages to a Partner Using Only Their Public Key

Now, write a program to accept your partner’s public key, and your private key. You can exchange keys using your socket protocol. Read a String, and for each character in the String, obtain its ASCII value and encrypt it with your partner’s public key. Send those encrypted values to your partner.

Encrypting a Message to Your Partner Using Their E and C Key Values

Each encrypted value X will be the ASCII value of each character in a String. You can iterate over the characters of the string, and obtain a char value representing each character in the loop. A char is really an integer whose value is the ASCII value of that character. So, you can obtain the numeric ASCII value of the character by casting the char to a long (a long is a whole number like an int, but it is double the size of an int):

long asciiX = (long) x; // where c is a char

Decrypting a Message from Your Partner Using Your D and C Key Values

Given a set of integers that are values encrypted by your partner using your public key, write a program that decrypts each of those values (using a loop!) and decrypt to the original secret message. Decide on a way to determine when you are finished so that you exit the loop nicely. Write down how you decided to do this!

The procedure to do this is similar to that used to encrypt each character, except that the value to be decrypted is the encrypted value of the ASCII value used before, and the key is the private key (D, C) associated with the public key that was used to encrypt it. You can cast the ASCII value you obtain as a long back to a char, and either print it or concatenate it with a String.

Hint: You will encrypt data using your partner’s public key values E and C, and decrypt usnig your own private key values D and C. The values of C will not be the same, since they are for two different keys (your partner’s and your own)!

When you decrypt a secret message using your own private key, you’ll get back a long, as follows:

long decrypted = RSAMath.endecrypt(encrypted, D, C);

You can convert the long back to a char for printing as follows:

char decryptedChar = (char) decrypted;

Part 3: Integrating Encrypted Traffic into Your Protocol

Modify your program to send your public key values at the start of the program over your socket, and receive your partner’s public keys. Instead of sending character data, send long integers representing each encrypted character of your user’s messages. Similarly, when receiving a message, receive these long integers, and decrypt them.

One consideration is how to let your receiver know you’re finished sending encrypted values. One way to do this is to send a 0 at the end of your transmission, which you’ll note is the null terminator. Another option is to send an int representing the number of encrypted character values you’re about to transmit. You get to choose!

Summary

As a summary, here is what to do. You might want to write separate programs (projects) for each of these, and export and submit each of them. It’s up to you!

• Using a multi-threaded socket connection, write a server that accepts connections from various clients, and spawns a thread for each such connection. For each connection, spawn a sending thread and a receiving thread that allows the user to input and receive messages from their corresponding partner. Choose a special message that will cause both sides to quit.
• Add message encryption and decryption to your program. To do this, first generate a key to share with the class. Share your E and C public key, but keep your D private key value a secret that you will use later!
• Exchange public keys before exchanging messages over the socket. To do this, you can have your sender thread send E and C as a first step, or have your socket send and receive E and C prior to spawning the sender and receiver threads. Pass these values to your sender and receiver as needed, either through the constructor, or though setter methods. You can pass the same variables to both the sender and receiver threads (for example, partnerE and partnerC), and use them to encrypt in the sender, but read them prior to your receive loop in the receiver. Alternatively, you can pass your sender object to the constructor of your receiver, and have the receiver call a setter method in the sender when it receives your partner’s public key E and C.
  • After your receiver reads your partner’s keys, it can start the general receive loop of messages to be decrypted. Similarly, your sender can start its loop to read your user’s messages from the console, encrypt them, and send over the network. To ensure that you don’t try to encrypt any messages from the sender prior to setting your partner’s encryption keys, it’s a good idea to have a line like this prior to your sender thread loop: while(this.partnerE == -1 || this.partnerC == -1); to wait until those keys are set by the receiver. You can set partnerE and partnerC to -1 in the constructor of the sender thread class.
• Encrypt messages prior to sending them over the socket, and decrypt them upon receiving them over the socket. Note that you will now receive long integers instead of characters.

A Note About Export Controls

Some governments, including the United States, have export controls on cryptographic technologies.

(Optional Reading) Additional Background

Using the Product of Large Prime Numbers for Public and Private Keys

We will generate a public key (that we share with the public, like our map with the number sums filled in above), and a private key (that we keep to ourselves, like the solution to the Vertex Cover problem that extracts the secret meaning from our encrypted message), using the RSA Cryptosystem. This system is based upon the product of two large prime numbers. The private key relies on the idea that it is very difficult to obtain the original prime factors from these large products.

Notice that many problems such as the map and the knapsack relied on modular arithmetic, using things that you’ve seen in school like “coprime” and “gcd.” Another difficult problem is factoring large numbers and finding large prime numbers. How did we get the modular inverse of 588 mod 881? It’s because we made sure that they were coprime to each other. Given numbers that don’t have any factors (3 and 7, 9 and 25) in common, what’s their gcd? 1 is the only number that divides them both. This means that we can find a modular inverse of the one number mod the other number, because there exists a number \(r^{-1}\) (in this case, \(r^{-1}\) is known as the Modular Inverse, not the traditional arithmetic inverse) such that \(rx = 1 (mod \; p)\).

Some interesting relationships in mathematics (called Fermat’s Little Theorem) show us that when two numbers are coprime, we can compute the modular inverse of their product r: \(r^{-1} = r^{\phi(M) - 1} (mod \; M)\). \(\phi(M)\) is known as Euler’s Totient Function, and it is simply a count of the number of integers 1 <= k < M that are coprime to m. \(\phi(24) = 8\) (because the totatives of 24 are 1,5,7,11,13,17,19,23). So for r = 588 and q = 881, as in the Knapsack Example, we can compute the modular inverse of 588 (mod 881) as follows: \(588^{-1} = 588^{\phi(881)-1} (mod \; 881)\). Unfortunately, it is very difficult to compute \(\phi(M)\), and therein lies the secret! If you generate r by multiplying together two large prime numbers that you already know (this is why finding large prime numbers is an interesting problem!), you can generate a number for which it is too difficult to compute Euler’s Totient. You can very easily compute the Totient with a loop that counts all values from 2 to C, and increments a counter if the greatest common divisor of each value and C is 1. Thus, you (and probably only you) can compute the modular inverse of values mod \(M = \phi(C)\).

For now, we can look up \(\phi(881)\) on a website like http://primefan.tripod.com/TotientAnswers1000.html, but it turns out that 881 is prime, meaning that no numbers greater than 1 other than itself divide into it. So this means \(\phi(881) = (881 - 1) = 880\) (the other 880 numbers). So \(588^{-1} = 588^{880-1} (mod \; 881) = 588^{879} (mod \; 881) = 588^{879} (mod \; 881)\). That’s \(1.917e+2434 (mod \; 881)\), or 442. See how much easier that makes the problem above to solve? Yet, it’s harder for those that don’t know the base number r and the modular inverse q, so we keep those secret. Instead, we give our partner(s) enough information to generate encrypted values to us that we can decrypt using this approach.

To generate RSA keys, first select two prime numbers A (say, 47) and B (say, 71). Normally, A and B should be very large – a small map was easy to break, after all! Multiply them together and call that \(C = AB = 47 \times 71 = 3337\).

Now compute \(\phi(C) = \phi(AB) = \phi(A)\phi(B) = (A-1)(B-1) = 46 \times 70 = 3220\), and call this number (the totient of C) M. Pick an encryption key that is coprime to \(M = 3220\). There are mathematical ways of doing this (the Extended Euclidean GCD Algorithm), but let’s just pick one since we’re using small enough numbers – how about 79. Take my word for now that it is easy to do, especially with a computer. Call this \(E = 79\).

The decryption key is the modular inverse of the encryption key \(E (mod \; 3220)\). Call this \(d = 79^{-1} = 79^{\phi(3220)-1} (mod \; 3220)\). Recall how to do this (keep in mind that 79 is coprime to M = 3220 – what a great idea, because we can use our formula!). So \(r^{-1} = r^{\phi(M) -1} (mod \; M)\) works. According to http://www25.brinkster.com/denshade/totient.html, \(\phi(M) = 1056\), but we could compute it. So now we have \(79^{-1} = 79^{1056 - 1} (mod \; 3220) = 791055 (mod \; 3220) = 1019\).

The encryption key \(C = 3337\) and \(e = 79\) make up the public key. The private key is \(d = 1019\) and \(C = 3337\). If we want to send the value 688, we compute \(688^{79} (mod \; 3337) = 1570\). To decrypt it, take \(1570^{1019} (mod \; 3337) = 688\). It actually works the other way, too. We can encrypt with the private key and decrypt with the public key. It all works because of the modular properties of relatively prime numbers. They easily “undo” each other, but it’s hard to reconstruct one number from the other.

But why would we ever want to do that? What value would we gain by being the only person who could encrypt something (with our private key) that the whole world could decrypt (with our public key)? (Click to reveal)

The information would not be private, because anyone could decrypt it. However, the public could be sure that you were the only person that could have generated that data. If we submit a document, and an exact copy of the document encrypted with our private key, the public could decrypt it and verify that it matches the non-encrypted document we sent out. This is the basis of a digital signature!

The idea is that 1019 is very difficult to find even knowing \(e = 79\) and \(C = 3337\). That’s because we’d need to be able to factor 3337 into two numbers that, when one is subtracted from each and multiplied together, give 3220 – such that 79 is relatively prime to that number. If factoring was easy, we could try every number until we found it. Luckily, it isn’t so easy. Still, cryptosystems are subject to attacks similar to those you do in the newspaper, and there are some tricks (padding, salting) to dealing with that. What would you do? Some devices like RSA keys generate RSA values every minute. This is because we believe that even if these numbers can be factored, it would take more than a minute to do so, and thus the security maintained.

An Unplugged Activity

If you had to pass secret messages around the room, but had to do so by passing notes to the people immediately adjacent to you, how could you go about “securing” the messages so that only your partner at the other side of the room could read your note? You and your partner would have to agree on some encoding for the message. Many such encodings exist:

• Caesar Cipher
• One-Time Pad
• Linear Feedback Shift Register
• The Enigma Machine

One limitation is that you and your partner must agree upon the details of the encoding. But how do you exchange that information? You’d have to pass it through your neighbors again, and thus would not be a secret. Public Key Cryptography provides us with mechanisms by which we can generate a key (a basis for an encoding), and make just enough information about it publicly available that others can use it to secure messages to us. Everyone gets to see this information - it’s enough to encrypt a message, but, amazingly, it’s not enough to decrypt it! Often, these cryptosystems are used to generate and send symmetric keys like the ones above, and this is the subject of secure Key Exchange algorithms.

We need a scheme whereby the sender can know something public - everyone can know it! Knowing the public part tells you nothing about how to decode a message, but actually allows you to encode the message for the recipient to secretly decode. The secret is never shared, so it is never transmitted. How can we do this? The idea is to generate a piece of information that contains the mechanism for encryption and decryption, but in such a way that it is very difficult to extract that mechanism - this is akin to extracting the original ingredients from a stew. For example, William Stanley Jevons proposed in 1874 that it is very difficult to identify two numbers that, when multiplied together, would result in Jevons’s Number: 8,616,460,799. Given enough time, you might determine that the two numbers are 89,681 and 96,079 (which each happen to be prime numbers, so there are no other factors aside from Jevons’s Number itself and 1); however, you could imagine this becoming more and more difficult as the target number gets larger and larger. As another example, we could use difficult-to-compute graph algorithms like the Vertex Cover problem as shown in this example.

Try sending a message to a classmate. Every character in your word is a number, according to the American Standard Code for Information Interchange (ASCII) table below. As a CS-Unplugged style example, come up with a set of 16 numbers that add up to one of your ASCII values, and put those numbers randomly on the map, labeling each vertex. This is easy to break, though, since the original value is just the sum of these numbers! Instead, take each vertex and its neighbors (there should be 4 nodes each), add up those numbers, and replace each vertex with that sum. Erase or start a new map so that the original numbers can’t be seen. Give that resulting map to another student. Can your classmate decode the message? They should not be able to. Now give it to the student with the private map (the solution to the vertex cover problem - which is difficult to compute, but gives the set of nodes that together touch all the other nodes exactly once). That student adds up only the values on the larger vertices, which is the sum of the values of each node plus the nodes they touch (which is all of them, because they’re the vertex cover nodes!), yielding the original ASCII value. Your partner can easily decode the message. This works by carefully constructing the map such that the highlighted vertices on the private map consist of the nodes that touch all vertices on the graph exactly once. This can be a difficult problem to solve if it is not provided in advance. It is breakable, though, using high school math techniques (systems of equations), in which t(i) = some partial sum of vertex values, knowing the summed values of the vertices and the neighbors on the map. Nevertheless, it is a start. We need another problem that is easy to set up but hard to break without the key.

Another Example: The Knapsack Problem

A similar exercise can be accomplished with an actual cryptosystem using the Knapsack Problem. This system was devised by Whitfield Diffie, Martin Hellman, and Ralph Merkle and is known as the Merkle-Hellman Knapsack Cryptosystem. It was broken by Adi Shamir, who is the “S” (along with Ron Rivest and Leonard Adleman) in the RSA Cryptosystem that we will explore in this assignment! Diffie, Hellman, and Merkle also developed the Diffie-Hellman Key Exchange algorithm (although they may not have been the first to do so) for exchanging keys over an insecure channel.

Try generating a public/private key and a message using the Merkle Hellman Knapsack Cryptosystem.

1. William M. Mongan. 2012. An integrated introduction to network protocols and cryptography to high school students (abstract only). In Proceedings of the 43rd ACM technical symposium on Computer Science Education (SIGCSE ’12). Association for Computing Machinery, New York, NY, USA, 664. DOI:https://doi.org/10.1145/2157136.2157364 ↩

2. William M. Mongan. 2011. Networking Applications, Protocols, and Cryptography with Java. Google CS4HS Workshop at the University of Pennsylvania, Philadelphia, PA. ↩

3. William M. Mongan. 2012. Networking Applications, Protocols, and Cryptography with Java. Tapia Workshop at the University of Pennsylvania, Philadelphia, PA. ↩

4. Bell, Witten, and Fellows. 1998. Computer Science Unplugged - Public Key Encryption. Available at https://classic.csunplugged.org/public-key-encryption/ ↩

Submission

In your submission, please include answers to any questions asked on the assignment page in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in your README file as well. Finally, include answers to the following questions:

• Describe what you did, how you did it, what challenges you encountered, and how you solved them.
• Please answer any questions found throughout the narrative of this assignment.
• If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
• Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
• Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
• Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
• Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
• Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description	Pre-Emerging (< 50%)	Beginning (50%)	Progressing (85%)	Proficient (100%)
Algorithm Implementation (60%)	The algorithm fails on the test inputs due to major issues, or the program fails to compile and/or run	The algorithm fails on the test inputs due to one or more minor issues	The algorithm is implemented to solve the problem correctly according to given test inputs, but would fail if executed in a general case due to a minor issue or omission in the algorithm design or implementation	A reasonable algorithm is implemented to solve the problem which correctly solves the problem according to the given test inputs, and would be reasonably expected to solve the problem in the general case
Code Quality and Documentation (30%)	Code commenting and structure are absent, or code structure departs significantly from best practice, and/or the code departs significantly from the style guide	Code commenting and structure is limited in ways that reduce the readability of the program, and/or there are minor departures from the style guide	Code documentation is present that re-states the explicit code definitions, and/or code is written that mostly adheres to the style guide	Code is documented at non-trivial points in a manner that enhances the readability of the program, and code is written according to the style guide
Writeup and Submission (10%)	An incomplete submission is provided	The program is submitted, but not according to the directions in one or more ways (for example, because it is lacking a readme writeup)	The program is submitted according to the directions with a minor omission or correction needed	The program is submitted according to the directions, including a readme writeup describing the solution

Please refer to the Style Guide for code quality examples and guidelines.