Assignment 1: Pseudo-Random Generator

• Download Files ⇓
• Submit Files ⇑

Introduction

In this project, you will implement your own pseudo-random number generator (PRG) in Java. 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.

PRF.java: This is a fully implemented code file which we are giving you. You should use it as a building block for all of the crypto functionality you need to do this assignment. The file gives you access to a pseudo-random function, as described in lecture. This is the only crypto primitive you are allowed to use any other crypto you use must be built (by you) on top of this file. Specifically, you may not use any other crypto libraries, not even the ones that are part of the standard Java libraries.

Your task is to implement two cryptographic algorithms, by modifying two Java code files as described below.

PRGen.java is a partially implemented file for a pseudo-random generator class. 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 indicating IMPLEMENT THIS everywhere that you have to supply code.

StreamCipher.java is a partially implemented file for a stream cipher. 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 indicating IMPLEMENT THIS everywhere that you have to supply code.

Objectives of this assignment

• Learn the common mistakes made in PRG design and implementation.
• Understand the risks of insecure PRGs.
• Gain experience writing cryptographic programs.

PRGen.java

Your PRGen class should implement the following API:

public class PRGen extends Random {
   public PRGen(byte[] key)     // creates a new PRGen
   protected int next(int bits) // generates the next pseudorandom number      

Your PRGen class will extend the java.util.Random class, but you should only implement the constructor and "next" method specified above. Your "next" method should follow the same behavior as the java.util.Random.next method. The Java documentation says, "The general contract of next is that it returns an int value and if the argument bits is between 1 and 32 (inclusive), then that many low-order bits of the returned value will be (approximately) independently chosen bit values, each of which is (approximately) equally likely to be 0 or 1." For example, if you call next(4), it will return a pseudo-random int between 0 and 15 (the range of 4-bit unsigned number). If you call next(31), it will return a pseudo-random int between 0 and 2,147,483,647 (the range of an unsigned 31-bit number). If you call next(32), it will return a pseudo-random int between -2,147,483,648 and 2,147,483,647 (the range of a signed 32-bit number).

Your PRGen class must also obey the following three properties:

• It must be pseudorandom, meaning that there is no (known) way to distinguish its output from that of a truly random generator, unless you know the key.
• It must be deterministic, meaning that if two programs create generators with the same seed, and then the two programs make the same sequence of calls to their generators, they should receive the same return values from all of those calls.
• It must be forward-secure, meaning that if an adversary is able to observe the full state of the generator at some point in time, that adversary cannot reconstruct any of the output that was produced by previous calls to the generator. Note that the .next method in java.util.Random is not forward-secure.

StreamCipher.java

Your StreamCipher class should implement the following API:

public class StreamCipher {
   public StreamCipher(byte[] key, byte[] nonceArr, int nonceOffset)   // constructor 
   public StreamCipher(byte[] key, byte[] nonce)                       // constructor 
   public byte cryptByte(byte in)                                      // encrypts the next byte
   public void cryptBytes(byte[] inBuf, int inOffset,                  // encrypts next numBytes
                          byte[] outBuf, int outOffset,                // in the inBuf, writing
                          int numBytes)                                // results to the outBuf
}      

This class encrypts or decrypts a stream of bytes, using a stream cipher. (Recall that for a stream cipher, encryption and decryption are the same operation.)

Getting Started

• Download the starting code here.
• Make sure you understand what a PRF (pseudo-random function) is, and how you can use the provided PRF.java class to deterministically generate pseudo-random values. See the comments in PRF.java for examples.
• The specification is deliberately vague regarding how you should accomplish each task. There is a significant design component to each problem.
• The bulk of the work for this assignment will be in the design, not the implementation. It shouldn’t take many additional lines of code to complete the classes.
• Advice on testing crypto code: As always, it is important to test your code. But you should be aware that crypto code presents different testing issues than other code does. Testing can sanity- check your code, but it can’t verify that your code has the desired security properties. For example, if your code is encrypting data for confidentiality, you can test whether the ciphertext is the right size, and you can test whether the ciphertext looks kind of randomish, and you can test whether different plaintexts yield different ciphertexts. But you cannot test whether there is a way for an adversary to recover the plaintext. So by all means test your code — if you do not, it’s almost certain not to work — but remember that passing the tests is not enough.

Submission Checklist

Submit your files to Gradescope: