CSci 4554 Lab 4. Asymmetric Encryption and Chosen Ciphertext Attacks.

Due Friday, April 23rd at 11:59pm (by e-mail)

40 points total

Description

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).

Tasks for the lab:

Encryption implementation

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.

Choosing a key

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.

Encrypting and decrypting a message

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.

Chosen Ciphertext Attack

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.

For each broken encryption please write down answers following to the following questions:
  1. How did you construct the message that sent as a decryption request?
  2. How did you compute the message m based on their response? Show the details.
  3. Did you gain any additional information? If yes, what is it and how did you compute it?

What to submit (by e-mail to me, CC your partner)

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

CSci 4554 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.