COS 432, Fall 2012, Homework 2

Homework 2

Due at 11:00am, Monday, October 8

In this assignment, you'll add functionality to the code you wrote for Homework 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. You can download the code we are providing. Create a fresh directory and unzip the downloaded code into it. Then copy into that same directory all of the .java files from your solution to Homework 1. 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 guarantee. We have put a comment saying "IMPLEMENT THIS" everywhere that you have to supply code.

Although your solution may call on code that you wrote for Homework 1, your solution to this homework should not rely on any specific properties of your Homework 1 code. We will test your solution with our own implementation of the Homework 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.

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 constuctor 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 {
    public RSAKey(BigInteger theExponent, BigInteger theModulus) // already implemented
    public BigInteger getExponent()                              // already implemented   
    public BigInteger getModulus()                               // already implemented
    public byte[] encrypt(byte[] plaintext)                        
    public byte[] decrypt(byte[] ciphertext)
    public byte[] sign(byte[] message) 
    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. Implementation of OAEP will require the usage of truly random bits. The only valid source for such random bits in our course is the .get() method in TrueRandomness. You will need to structure your code to ensure that the .get() method is only called once, no matter how many RSAKeys are generated and no matter how many times RSAKey's methods are called. See the tips section for a bit more on this. The decrypt() method should be able to decrypt the ciphertext.

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 mssage as one of its arguments.

The verifySignature() method should be used by a public RSAKey object to verify a signature generated by the corresponding private RSAKey's sign() method.

The maxPlaintextLength() method should return the largest N such that any plaintext of size N bytes can be encrypted with this key.

KeyExchange. 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 key exchange. rand is a secure pseudorandom generator that can be used by the implementation. iAmServer is true if and only if we are playing the server role in this exchange. Each exchange has two participants; one of them plays the client role and the other plays the server role.

Once the KeyExchange object is created, two things have to happen for the key exchange process to be complete:

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.

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:

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

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.

Assignment Tips and Tricks. This list may grow in response to Piazza questions.

Make sure to run your code with the java -ea flag, so that assertions are enabled.
Since you'll be doing math with very large integers, you'll probably want to use the java.math.BigInteger library class for any such operations. This class provides myriad functions that you may find useful for this assignment, particularly as BigInteger was originally designed with RSA implementation in mind. (Using BigInteger doesn't violate our rule against using external crypto primitives, because BigInteger provides basic mathematical functions, and not crypto.)
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. Find the appropriate BigInteger method.
One particularly useful BigInteger function is modPow().
In class, we said that given public and private keys (d, N) and (e, N), we have that x = (x^(de) mod N), iff 0 < x < N. Thus, if you're going to use the built in BigInteger functions to encrypt and decrypt, it is important that you represent your input message as a positive BigInteger.
Be very careful when converting between BigIntegers and byte[] arrays! In particular:
- When a byte[] is converted into a BigInteger, you have to use the BigInteger(int signum, byte[] magnitude) to guarantee that your BigInteger is positive. This is important when you are encrypting.
- When a BigInteger is converted into a byte[] using .toByteArray(), you will have either exactly 0 or 1 leading zeros (you get a leading 1 when the highest order byte is greater than 0x7F, since the byteArray is supposed to represent a 2s complement integer). So for example if you convert byte[]{0x00, 0x00, 0x00, 0x01} to a BigInteger and back, you will lose your leading zeros, and if you convert byte[]{0x00, 0x00, 0xAB} to a BigInteger and back, you will get {0x00, 0xAB}. This is important when you are decrypting.
- We recommend that you create a private method (or methods) to facilitate BigInteger to byte[] conversions. See this Piazza post for more details.
- If you'd like a visual picture: In this first diagram, we see that decrypt can fail due to an extra 0x00 that is added on when the recovered plaintext BigInteger is converted into an array. In this second diagram, we see that adding an extra marker byte during the encoding step (that will be removed during the decoding step) can prevent the extra leading zero from appearing. Note that this technique also preserves any leading zeros that might have been present at the front of the OAEP output. Note that this is not the full block diagram for encrypt -- specifically, this scheme does NOT handle padding.
- See BigIntegerProblems for examples of how these issues can trip you up.
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 pratice.
When implementing OAEP, the PRF H can be seeded with any known value. Here, known means hard-coded into the .java files
For full credit, don't forget to pad the input to the OAEP algorithm if it is too short -- this is needed to guarantee security (otherwise the exponentiated message might be smaller than the modulus). This can be done using a padding scheme similar to that diagrammed above.The penalty for not padding will be very small (-2)! If you decide to attempt to implement padding, we recommend you write out a block diagram like in the hint about BigInteger/byte[] conversion issues above.
Your code should be written such that the .get() method in TrueRandomness is not called multiple times, no matter how many times the RSAKeyPair, RSAKey, or KeyExchange methods are called (including their constructors). One possible solution is to utilize a static PRGen. It is safe to assume that the client will not call TrueRandomness.
As in HW1, 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. Our reference solutions are 46, 168, and 84 lines of code (including everything, even comments, whitespace, brackets, etc.) for RSAKeyPair, RSAKey, and KeyExchange respectively.
If your solution to Homework 1 was flawed, you will want to correct these mistakes before testing your implementation of homework 2.
Oct 7, 3:10 PM - For maximum elegance in RSAKey, your message should only be in BigInteger format for the purposes of exponentiating and modulusing. In other words, when you're applying OAEP, padding, unOAEP, etc., it's much easier to deal with your input in terms of byte[].
Oct 7, 6:10 PM - For an example of how to properly initialize static variables, see StaticInitializationDemo, and this Piazza thread.

Submitting your solution. You should submit any code files that you modified or created. You don't need to submit any files that you did not modify. Please cite any sources you used when developing your code. You may submit any number of times. Only your most recent submission will be graded. Submit your code using this link.