Project 2 — Public-key Crypto

Due Monday, October 30 at 6pm

In this assignment, you'll build on the functionality you implemented for Project 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'll ask you to provide certain functions missing from the code we provide via chisubmit. As before, you must not use any crypto libraries; the only primitives you may use are the ones we gave you and ones you implemented from scratch yourself.

In this assignment you will implement three facilities by modifying three Java code files. You will modify RSAKeyPair.java to generate an RSA key pair. You will modify RSAKey.java to implement secure RSA encryption and decryption, and to create and verify digital signatures. You will modify KeyExchange.java to implement a 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 guarantees. We have put a comment saying "IMPLEMENT THIS" everywhere that you have to supply code.

RSAKeyPair. 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 called rand to get pseudorandom bits. numBits 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.

getPrimes() is a method we've added in order to help us with the grading process. Typically, you would not explicitly have a method to return these primes. The primes may be returned in either order.

RSAKey. Your RSAKey class should implement the following API:

public class RSAKey {
    private static final int oaepK0SizeBytes = 32;
    private static final int oaepK1SizeBytes = 32;
    
    public RSAKey(BigInteger theExponent, BigInteger theModulus) // already implemented
    public BigInteger getExponent()                              // already implemented   
    public BigInteger getModulus()                               // already implemented
    
    public byte[] encrypt(byte[] plaintext, PRGen prgen)                        
    public byte[] decrypt(byte[] ciphertext)
    
    public byte[] encodeOaep(byte[] input, PRGen prgen)
    public byte[] decodeOaep(byte[] input)
    public byte[] addPadding(byte[] input)
    public byte[] removePadding(byte[] input)
    
    public byte[] sign(byte[] message, PRGen prgen) 
    public boolean verifySignature(byte[] message, byte[] signature)
    
    public int maxPlaintextLength()
}

The RSAKey class implements core RSA functions, namely encrypting/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 encrypt() method should encrypt the plaintext using optimal asymmetric encryption padding (OAEP) as discussed in class. It is not enough to simply exponentiate and mod the plaintext. encrypt() , sign() , and encodeOaep() take a PRGen parameter, in case the implementation wants to use some pseudorandom bits. The decrypt() method should be able to decrypt ciphertexts encrypted with encrypt() . If an error occurs during encrypt() or decrypt() , the methods should return null . Your code for OAEP encoding and decoding should be in the provided encodeOaep() and decodeOaep() methods. Your other methods should call these utility methods to encode/decode when necessary. The constants oaepK0SizeBytes and oaepK1SizeBytes specify the size in bytes of the k0 and k1 portions of the OAEP encoding.

The addPadding() method is used to pad the input to encodeOaep() if it is too short. This is needed to guarantee security because otherwise the exponentiated message might be smaller than the modulus. The removePadding() method is used to remove this padding from output of decodeOaep(). Padding can be performed using a padding scheme similar to those we discussed in class in conjunction with CBC mode encryption.

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. You should not include the entire 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 signature algorithm that we discussed in class is deterministic, and so if you implement it, you do not need to use the PRGen parameter to the sign() method.

Extra credit: There is, however, a signature algorithm that is superior to the one that we discussed that does use pseudorandomness. Implement it instead of the one we discussed in class and also submit a README file answering the following questions as specifically as possible: What is the better algorithm called? How does it work? Why is it better? Hints: (1) you may want to start here; (2) the "hash and sign" scheme we discussed in class is technically called RSA-FDH.

The maxPlaintextLength() method should return the largest x such that any plaintext of size x bytes can be encrypted with this key. Your code must correctly operate on plaintexts that are any size less than or equal to the size returned by maxPlaintextLength().

KeyExchange. Your KeyExchange class should implement the following API:

public class KeyExchange {
    public static final int OutputSizeBits
    public static final int OutputSizeBytes
    
    public KeyExchange(PRGen rand)
    
    public byte[] prepareOutMessage() 
    public byte[] processInMessage(byte[] inMessage) 
}

The constructor should prepare to do a key exchange. rand is a secure pseudorandom generator that can be used by the implementation.

Once the KeyExchange object is created, two operations have to be performed to complete the key exchange:

Call prepareOutMessage on this object, and send the result to the other participant.
Receive the result of the other participant's prepareOutMessage, and pass it in as the argument to a call on this object's processInMessage.

For a given KeyExchange object, prepareOutMessage and processInMessage could be called in either order, and KeyExchange should produce the same result regardless.

The call to processInMessage should behave as follows:

If passed a null value, then throw a NullPointerException.
Otherwise, if passed a value that could not possibly have been generated by prepareOutMessage, then return null.
Otherwise, return a "digest" value of length OutputSizeBits with the property described below.

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 third parties can observe and modify the messages sent between the participants.

The code performing the exchange is not required to check whether the two participants end up with the same digest value; the code calling these methods must verify that property.

Compiling and running. This assignment makes use of the classes you implemented in Project 1. To avoid doubly penalizing you for any mistakes you may have made in the previous assignment, we are providing you with a compiled reference implementation of Project 1 in project1.jar . This assignment also makes use of Java assertions. To ensure that you use project1.jar and enable assertions, please compile the code with the following command:

javac -cp project1.jar:. [.java files]

and run it with:

java -ea -cp project1.jar:. [main class]

As before, we will be testing your code with Java 8, and so please use that version when compiling and running your implementation. You can check your Java version by typing javac -version and verifying that the version begins with 1.8.0_ . (If you only have the java command but not the javac command, you have the Java runtime, but you need to install the Java Development Kit.) You can download the Java Development Kit here.

Support code. Public key cryptography uses integers that are far larger than Java's built-in int or long types, and so neither those types nor the standard math operators like + or * will work. As a result, the most important piece of support code is Java's BigInteger class, which was originally designed with RSA implementation in mind. Familiarize yourself with its functions, especially those that might be particularly useful like modPow() and gcd().

We are also providing you with additional utility functions in Proj2Util.java:

public class Proj2Util {
	public static final int HashSizeBits = PRF.OutputSizeBits;
	public static final int HashSizeBytes = HashSizeBits/8;
	
	public static BigInteger generatePrime(PRGen rand, int numBits)
	
	public static byte[] hash(byte[] val)
	public static byte[] hash(byte[] inBuf, int inOffset, int numBytes)
	
	public static BigInteger bytesToBigInteger(byte[] buf)
	public static byte[] bigIntegerToBytes(BigInteger x, int outputSize)
}

generatePrime() generates a pseudorandom numBits prime number using the supplied PRGen .

The two variants of hash() implement an un-keyed hash function. Note that they are implemented simply by invoking a PRF with a fixed, non-secret key.

As converting between BigInteger s and byte[] arrays is surprisingly hard to get right, we have provided bigIntegerToBytes() and bytesToBigInteger().

Finally, we are providing you with constants suitable for use in the Diffie-Hellman algorithm in DHParams.java.

Assignment Tips and Tricks.

If you find yourself writing complex functions involving BigIntegers (e.g. manually testing primality, manually generating primes, manually finding the GCD of two numbers, manually finding d given p, q, and e, etc.), you're doing way more work than you need to.
Start with RSAKeyPair. While it is true that it contains instances of RSAKey, RSAKeyPair does not use any of the methods that you'll be implementing in RSAKey.
An RSAKey object does not know if it is "private" or "public". Indeed, it is even possible to sign messages using a public key or encrypt using a private key, though neither of these strange operations are likely to be useful in practice.
As in Project 1, the spec is deliberately vague regarding how you should accomplish each task. There is a significant design component to each problem.
There is a bit more programming this week. Yet, the amount of code in our reference solutions for RSAKeyPair, RSAKey, and KeyExchange combined is still less than 400 lines of code in total.
For maximum elegance in RSAKey, your message should only be in BigInteger format for the purposes of exponentiation and modular reduction. In other words, when you're encoding or decoding OAEP and adding or removing padding, it's much easier to deal with your input in terms of byte[].

A few words about grading. As before, some of your grade will be based on whether your code passes certain automated tests. But, as stated previously, the security of your implementation ultimately depends on its design and cannot be verified by testing alone. An implementation that compiles, runs, and appears to work may in fact be insecure. As a result, manual inspection of your design will determine a large part of your grade.