Assignment 2: Asymmetric Cryptography
Introduction

In this assignment, you will add functionality to the code you wrote for Assignment 1, toward the goal of implementing a secure facility for client-server communication across the Internet.

As before, we will give you some of the code you need, and we will ask you to provide certain functions missing from the code we provide. As before, you must not use any cryptography libraries; the only cryptographic primitives you may use are the ones we gave you, and ones you implemented from scratch yourself.

In this assignment you will implement three classes, by modifying three Java code files:

  1. You will modify RSAKeyPair.java to implement RSA key-pair generation.
  2. You will modify RSAKey.java to implement secure RSA encryption and decryption, and to create and verify digital signatures.
  3. You will modify KeyExchange.java to implement secure key exchange.

As in the previous assignment, we have provided you with code files in which some parts are stubbed out. You will replace the stubbed out pieces with code that actually works and provides the required security guarantee. We have put a comment saying IMPLEMENT THIS everywhere that you have to supply code.

Your solution will build on the functionality that you implemented for Assignment 1, but we will test your solution with our own implementation of the Assignment 1 functionality. Your solution must work correctly when we do this — this shouldn’t be a problem as long as you respect the API boundaries between the different classes we have given you. To help you mimic the testing setup that we will use, we are providing a pre-compiled JAR file (library) containing our reference solution to Assignment 1. We recommend that you use this instead of your own solution to Assignment 1.

Objectives
RSAKeyPair.java

Your RSAKeyPair class should implement the following API:

public class RSAKeyPair {
   public RSAKeyPair(PRGen rand, int numBits)
   public RSAKey getPublicKey()                 // already implemented
   public RSAKey getPrivateKey()                // already implemented
   public BigInteger[] getPrimes()
}

For RSAKeyPair, the bulk of the interesting work is performed by the constructor. This constructor should create an RSA key pair using the algorithm discussed in class. The constructor will use the PRGen rand argument to get bits from a pseudo-random generator. The numBits argument is the size in bits of each of the primes that will be used. The key pair should be stored as a pair of RSAKey objects (see next section for more information on RSAKey).

The getPrimes() method helps with the grading process. Invoking getPrimes() should return the two primes that were used in key generation. The primes may be returned in either order in a BigInteger array of length 2. Note that in the real-world implementation, you would not need to have a method to return these primes.

RSAKey.java

Your RSAKey class should implement the following API:

public class RSAKey {
   public RSAKey(BigInteger theExponent, BigInteger theModulus)
   public BigInteger getExponent()
   public BigInteger getModulus()
   public byte[] encrypt(byte[] plaintext, PRGen prgen)
   public byte[] decrypt(byte[] ciphertext)
   public byte[] sign(byte[] message, PRGen prgen)
   public boolean verifySignature(byte[] message, byte[] signature)
   public int maxPlaintextLength()
   public byte[] encodeOaep(byte[] input, PRGen prgen)
   public byte[] decodeOaep(byte[] input)
   public byte[] addPadding(byte[] input)
   public byte[] removePadding(byte[] input)
}

The RSAKey class implements core RSA functions, namely encryption/decryption as well as signing/verification. Note that the RSAKey class is used for both public and private keys, even though some key/method combinations are unlikely to be used in practice. For example, it is unlikely that the sign() method of a public RSAKey would ever be used.

The primary interface for this class includes the sign(), verifySignature(), encrypt(), decrypt(), and maxPlaintextLength() methods. The remaining methods are to help keep the code organized and easier to grade. Each method is commented to help you understand its purpose and requirements.

Note that the encrypt(), sign(), and encodeOaep() methods take a PRGen object as a parameter, in case the implementation wants to use bits from a pseudo-random generator.

The sign() method should generate a signature (array of bytes) that can be verified by the verifySignature() method of the other RSAKey in the private/public RSAKey pair. Recall that an RSA signature does not have a length limit. In the sign() method, you should not include the message as part of the signature; assume that the verifier will already have access to this message. This assumption of access is reflected in the API for verifySignature(), which accepts the message as one of its arguments.

The encrypt() method should encrypt the plain text using optimal asymmetric encryption padding (OAEP) as discussed in class. It is not enough to simply compute modular exponentiation on the plain text. The decrypt() method should correctly recover the plaintext from the ciphertext (if it hasn’t been corrupted). These methods will call the other helper functions to do this job.

Your code for OAEP encoding and decoding should be in the provided encodeOaep() and decodeOaep() methods. When decoding an OAEP message, your code should verify the message’s integrity. If the message shows signs of corruption, then your decodeOaep() should reveal this by returning null or throwing an exception. For full credit, don’t forget to pad the input to the OAEP algorithm if it is too short – this is necessary to guarantee security (otherwise the exponentiated message might be smaller than the modulus).

OAEP encoding requires that its input be a fixed length determined by the RSA key’s parameters. The addPadding() and removePadding() methods should implement a reversible padding scheme to ensure that messages are the correct length before being encoded. You should not call these methods from within encodeOAEP() and decodeOAEP().

The maxPlaintextLength() method should return the largest \(\ell\) such that any plain text of size \(\ell\) bytes can be encrypted with this key and padding scheme. Pay very close attention to this method, as it must consider the key size, the OAEP encoding, and the padding scheme. Calculate this value such that the input to RSA modular exponentiation is always less than the RSA modulus. Your code must correctly operate on plain texts that are any size less than or equal to the size returned by maxPlaintextLength().

KeyExchange.java

Your KeyExchange class should implement the following API:

public class KeyExchange {
   public static final int OUTPUT_SIZE_BYTES
   public static final int OUTPUT_SIZE_BITS
   public KeyExchange(PRGen rand, boolean iAmServer)
   public byte[] prepareOutMessage()
   public byte[] processInMessage(byte[] inMessage)
}

The constructor should prepare to do a Diffie-Hellman Key Exchange. The rand argument is a secure pseudo-random generator that can be used by the implementation. The iAmServer argument is true if and only if that object is the server role of a client-server interaction. Each “exchange” will have two participants: a client and a server. This means two parties (e.g., computers, threads, servers) will create one KeyExchange object each. In our automated testing, we will use the iAmServer boolean as a flag to indicate which object belongs to which role. You may not need to use the iAmServer argument in your implementation, but it may be helpful for debugging.

After two KeyExchange objects are instantiated, two things have to happen for the key exchange process to be complete:

These two things can happen in either order, or even concurrently (e.g., in different threads). This code must work correctly regardless of the order.

The call to processInMessage should behave as follows:

Your KeyExchange class must provide the following security guarantee: If the two participants end up with the same non-null digest value, then this digest value is not known to anyone else. This must be true even if adversaries can observe and modify the messages sent between the participants.

This code is not required to check whether the two participants end up with the same digest value; the code calling this must verify that property.

Getting Started
Java Command Line Tips
Submission Checklist

Submit your files to Gradescope: