In this assignment, you will write a chat server and client, using a protocol we will agree upon as a class. Your chat server/client will then implement a subset of the RSA cryptosystem, which you will implement into your program. Your program should be able to encrypt with anyone's public key, and decrypt with your private key (both given to the program). How you do this is up to you! Finally, you will write a program to brute-force crack your partner's public key. Once you have done this, write a program that intercepts another classmate's traffic and, given their public key, determine the private key and the original message. Implement your miniRSA library with the following functions. Note, I recommend using long instead of int in case larger keys are used.

Now, use these functions to write programs to generate an RSA public/private keypair, and encrypt/decrypt given the appropriate key.

The RSA encryption algorithm works as follows:

1. Compute two *different* prime numbers a and b (a number is prime if every number below it fails to divide evenly into that number that is, n % i != 0 for all i do not make the user enter actual prime numbers! Perhaps have the user enter m and n, and you compute the mth and nth prime numbers to use here.

2. Compute c = a * b, and m = (a-1)(b-1)

3. Compute e, the encryption key, which is any composite number coprime to m and to c, with e mod m > 1 -- note that you may wish to start searching for a co-prime at m*2, and search upwards from there.

4. Compute d, the modular inverse of e mod m

5. Your key output might (or might not) look like the below -- don't try to match this exactly!

Here, my public key is (451, 2623) and the private key is (1531, 2623).

6. Encrypt a number x (perhaps an ASCII value see an ASCII table for conversions!) using the encryption key e and c, by taking x and raising it to the power of e mod c

7. Decrypt a number y using the decryption key d and c, by taking y and raising it to the power of d mod c.

Cracking your RSA key might look like this (again, don't try to match this exactly -- just ensure that your decryption key "undoes" your encryption key and gives you your original letters back).

Use all of the above to write your chat program with encryption and cracker. Your program should be threaded in a way that allows for asynchronous sending and receiving of data. Your finished server might look like this:

I must be able to run your makefile by typing MPRIME=8 NPRIME=13 make genkey and E=1337 C=65535 make keycrack and PORT=8080 E=1337 C=65535 D=3371 DC=65533 make server and PORT=8080 E=1337 C=65535 D=3371 DC=65533 make client to test your programs.

Where:

E and C are your partner's encryption key E and C.

D and DC are your own decryption key D and C.

Method Summarv intl coprime (int x) intendecrvpt (int msg_or_cipher, int key, int c) int GcD(int a, int b) Using a java.util Random number generator, pick a random integer that is coprime to the given input parameter x Given an integer representing an ASCII character value, encrypt it via the RSA crypto algorithm. intmod inverse (int base, int m) int modulo (int a, int b, int c) int totient (int n) Compute the modular inverse base. 1 % m. Computes Math mod(Math pow(a, b), c), for large values of a, b, andc Compute Euler's Totient