Assignment Two: Asymmetric Cryptography

In this assignment, you will implement several components that facilitate asymmetric encryption, towards the goal of a secure client-server communication system. As in the previous assignment, we will give you some of the code you need, and you must implement functionality to complete the assignment requirements. The following files are provided for you:

File Name Description
a1.jar This is a java archive file containing compiled solutions to the previous assignment. It is highly recommended that you add this file to your classpath and use the solutions within it instead of the .java files from the previous assignment.
DHConstants.java This class provides constants for use with the Diffie-Hellman algorithm. Namely, we provide a g and p value in the form of BigIntegers to be used as your initial primes.
HashFunction.java This provides a convenient wrapper for the hash function that you should use in your RSA implementation.
HW2Util.java This utility class helps facilitate conversion between BigInteger and byte[] data types.
KeyExchange.java This is a partially implemented class that facilitates secure key exchange over an insecure channel. You must add code to implement the methods that are marked with IMPLEMENT THIS. Your additions must work as described below and provide the required security guarantees.
RSAKey.java This is a partially implemented class representing an RSA key that can perform RSA-OAEP encryption and decryption, RSA signature generation, and RSA signature verification. You must add code to implement the methods that are marked with IMPLEMENT THIS. Your additions must work as described below and provide the required security guarantees.
RSAKeyPair.java This is a partially implemented class that will generate RSA private/public key pairs. You must add code to implement the methods that are marked with IMPLEMENT THIS. Your additions must work as described below and provide the required security guarantees.

RSAKeyPair.java

Your key pair generator class will 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();
}

All of the interesting work in the RSAKeyPair class happens in the constructor. This constructor should create a key pair using the RSA algorithm discussed in lecture. It will use the provided PRGen rand argument to get pseudo-random bits that are required for the algorithm. The numBits argument is the size (in bits) of each prime that will be used in the algorithm. The key pair should be stored and returned as two separate RSAKey objects (one for the private key, one for the public key).

The getPrimes() method helps with automated grading. Invoking this method should return the two primes that were used in key generation. In real life, this wouldn’t usually be necessary (we don’t always keep track of the primes used for generation). The primes may be returned in any order as a two-element array of BigIntegers.

RSAKey.java

This is the most challenging part of this assignment. Your RSA key class wil implement the following API:

public class RSAKey {
    public RSAKey(BigInteger theExponent, BigInteger theModulus);
    
    public BigInteger getExponent();    // already implemented
    public BigInteger getModulus();     // already implemented

    public byte[] addPadding(byte[] input);
    public byte[] removePadding(byte[] input);

    public byte[] encodeOaep(byte[] input, PRGen prgen);
    public byte[] decodeOaep(byte[] input);

    public int maxPlaintextLength();

    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);
}

The RSAKey class implements core RSA functions. Note that the same class is used for both public and private keys, even though it would be unlikely for one key to use all of the methods. For example, using a public key to sign something (or a private key to encrypt something) is not very meaningful. It is important to remember that the result of calling encrypt on one key can only be decrypted by the other key. Similarly, you must call verifySignature on the public key, if the message was signed by the private key.

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.

The sign method should generate a signature (array of bytes) that can be verified by the verifySignature method. 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 is reflected in the API for verifySignature, which accepts the message as one of its arguments.

The encrypt method should encrypt the given plaintext using optimal asymmetric encryption padding (OAEP), as discussed in lecture. 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 implementation of OAEP encoding/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 method should return null or throw an exception.

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.

The maxPlaintextLength method should return the greatest length l such that any plaintext that is l bytes long can be encrypted/decrypted by the RSAKey object. 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.

KeyExchange.java

Your key exchange class will implement the following API:

public class KeyExchange {
    public static final int OUTPUT_SIZE_BYTES;  // already implemented
    public static final int OUTPUT_SIZE_BITS;   // already implemented

    public KeyExchange(PRGen rand, boolean iAmServer);

    public byte[] prepareOutMessage();
    public byte[] processInMessage(byte[] inMessage);
}

The constructor of this class should prepare to do a Diffie-Hellman Key Exchange. The rand argument is a secure pseudo-random generator that should 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. For 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 must happen for the key exchange process to complete:

  1. Invoke the prepareOutMessage method on each object and send the returned values to the other.
  2. Receive the other participant’s message and pass it as an argument to the receiving object’s processInMessage method.

These two things can happen in any order. Your code must work regardless of the order (i.e., program it in a way that would work when two computers were sending the message over the network).

The behavior of the processInMessage should include the following properties:

  • If the inMessage is null, then throw a NullPointerException.
  • If the inMessage is an invalid/insecure Diffie-Hellman exchanged message, return null.
  • Otherwise, return the digest (hashed) value with length OUTPUT_SIZE_BYTES with the following security guarantee: if both participants have the same non-null digest value, then this digest value cannot be known to an adversary who might observe or tamper with the exchanged message.

Getting Started

  • Read all of the comments and code annotations in the provided Java files (including helper files). Being familiar with this framework will be very helpful before you get started.
  • Become familiar with the java.math.BigInteger class.
    • Since you will be doing math with very large integers, you will want to use this class for any such operations. This class provides several functions that you may find useful for this assignment. It was originally designed with RSA implementation in mind. Using BigInteger doesn’t violate our rule against using external cryptographic primitives, because BigInteger provides basic mathematical functions (not cryptography).
    • If you find yourself writing complex mathematical algorithms (e.g., testing primality, generating prime numbers, finding greatest common denominators, inverting modular exponentiation), you are doing more work than you should be doing. Find an appropriate method in BigInteger.
    • Converting back and forth between BigInteger objects and byte[] arrays can present issues of consistency and formatting. We recommend using the code provided in HW2Util.java to do this.
  • Review the properties and implementation requirements for a secure Diffie-Hellman Key Exchange and consider the case of concurrent participants. Implementing KeyExchange.java is independent of the RSA components of this assignment, and can be done at any point.
  • Review the requirements and algorithm for generating RSA key pairs, including special cases and properties of intermediate values. You should implement and test RSAKeyPair.java before diving into the RSAKey.java, since you will want to make sure you are using correctly generated RSA key exponents and moduli when testing your RSA keys.
  • When implementing RSAKey.java, it may be beneficial to implement it incrementally:
    • Modular exponentiation on fixed-length inputs (encrypt and decrypt).
    • OAEP encoding/decoding on fixed-length inputs (encodeOaep and decodeOAEP).
    • Combining modular exponentiation and OAEP on fixed-length inputs.
    • Reversible padding in addPadding and removePadding.
    • Determining an equation for maximumPlaintextLength and combining all the stages: pad -> encode -> exponentiate -> exponentiate -> decode -> un-pad. This will take some time to test and debug.

Java Command Line Tips

Always run your tests with assertions enabled by using the -ea flag.

If you are confident that your solution to Assignment One is correct, you could use those .java files for testing your implementation of Assignment Two. Alternatively, you can use our reference solution to Assignment One, which is provided a pre-compiled JAR file (library). Note that this library does not contain source code. Attempting to “de-compile” this JAR file may constitute academic misconduct.

To compile and execute your Assignment Two code using the JAR file, you need to include it in your classpath.

For example, using Linux/Mac command line, you may run:

$ javac -cp hw1.jar KeyExchange.java
$ java -ea -cp hw1.jar:. KeyExchange

For Windows command line, you may run:

$ javac -cp "hw1.jar" KeyExchange.java
$ java -ea -cp "hw1.jar;." KeyExchange

If you are testing and running using an IDE, please refer to the IDE’s user manual on how to add .jar files to the classpath.

Submission Requirements

Submit the following files to Gradescope:

  • KeyExchange.java - Source code file containing your fully implemented key exchange class.
  • RSAKey.java - Source code file containing your fully implemented RSA key class.
  • RSAKeyPair.java - Source code file containing your fully implemented RSA key-pair generation class.