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 BigInteger
s.
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:
- Invoke the
prepareOutMessage
method on each object and send the returned values to the other. - 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
isnull
, then throw aNullPointerException
. - If the
inMessage
is an invalid/insecure Diffie-Hellman exchanged message, returnnull
. - 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, becauseBigInteger
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 andbyte[]
arrays can present issues of consistency and formatting. We recommend using the code provided inHW2Util.java
to do this.
- 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
- 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 theRSAKey.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
anddecrypt
). - OAEP encoding/decoding on fixed-length inputs (
encodeOaep
anddecodeOAEP
). - Combining modular exponentiation and OAEP on fixed-length inputs.
- Reversible padding in
addPadding
andremovePadding
. - 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.
- Modular exponentiation on fixed-length inputs (
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.