Math 480, Spring 2015, Assignment 9

Carefully define the following terms:

1. Man-in-the-middle attack.
2. Witness (to the compositeness of $n$).
3. Carmichael number.

Carefully describe the following algorithms:

1. RSA (describe the entire cryptosystem, including key generation, encryption, and decryption).

Solve the following problems:

1. Problems 3.6, 3.12, and 3.13(a-b).

Coding projects:

1. (RSA) Implement the RSA cryptosystem. (Note that you will need some external source of large prime numbers; as in the previous assignment, try to make your code modular so that you can swap in your own prime generator when it becomes available.)
2. (Witnesses) Write a function that takes a positive integer $n$ as input and returns a list of all witnesses to the compositeness of $n$.
3. (Carmichael numbers) Write a function that takes a positive integer $n$ as input and returns a list of all Carmichael numbers less than or equal to $n$. (You will need a way to decide whether a number without any witnesses is actually prime; slow algorithms are fine for this purpose, since the witness search is already slow.) Use your function to find all Carmichael numbers less than or equal to $1000$.

--------------------End of assignment--------------------