This lab is done in groups of 2. The goal of the lab is to implement asymmetric encryption schemes and use active attacks against them.

Each group will implement one public key encryption scheme and use a chosen ciphertext attack (CCA) against other encryptions. The encryption schemes are RSA, Rabin, and ElGamal. Each group will be providing limited "oracle services" for other groups by deciphering messages of their choice (see below).

Each group needs to pick one of the 3 encryption methods: RSA, Rabin (note: this is the actual Rabin encryption, not just the square root computation), ElGamal. Post here https://wiki.umn.edu/view/UMMCSci4554Spring10/AsymmetricEncryptionLabwhat you have chosen.

Your keys must be computed based on large primes. Use Java
class BigInteger
constructor that generates a random integer that is prime with a high
probability (or a similar function in the language that you are using). Use at least 15 for bit length and 0.999 for certainty.

Pick keys that are not weak: make sure that you are using safe primes
(this may take some trial and error) and Blum integers where
required.

If you run into any computational problems, feel free to adjust the numbers to make the computation do-able. Let me know what the issue is.

When choosing a generator for a prime field, you need to factor p-1 and then use an approach decribed here http://www.adeptscience.co.uk/products/mathsim/maple/powertools/cryptography/HTML/ElGamal.html (and also in the book) to check if g is indeed a generator.

Clearly describe all the steps you took to generate the key. Inlcude all of the conditions you checked and reasons for those.

Choose a random number m (in the appropriate range) as a message. Encrypt m, decrypt it, and if the results match, post your public key and the encrypted message on the wiki.

**Important:** for Rabin decryption find all 4 solutions and
for the CCA part of the lab please return a randomly chosen one of the
four.

Your goal is to decrypt the message m by sendng a ciphertext (different from the encryption of m) to the owners of the public key for decryption. The key owners must provide the correct decryption of the message you send them. Please CC me on your email exchanges.

Every group must break exactly one encryption for each of the three encryption schemes. If you are the only ones using a particular scheme then you will be "breaking" your own encryption.

You will use the following attacks. Note the number of decryptions that you are allowed to ask for. Extra requests may result in points taken off and must be justified in the email.

- A CCA attack based on multiplicative property of RSA (p. 268). You are allowed one request for decryption.
- A CCA attack on Rabin based on obtaining a different square root (pp. 272-273). You are allowed multiple requests for decryption. However, you need to explain why the previous one was not sufficient.
- A CCA attack on ElGamal based on multiplicative property (p. 277). You are allowed one request for decryption.

- How did you construct the message that sent as a decryption request?
- How did you compute the message m based on their response? Show the details.
- Did you gain any additional information? If yes, what is it and how did you compute it?

- All your program code (well-documented) and instructions for running it.
- All the keys and the plaintexts that you used and all the corresponding ciphertexts.
- Detailed explanations of what you were doing and why.