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 cryptographic 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 cryptographic primitive you are allowed to use; any other cryptographic code you use must be built (by you) on top of this file. Specifically, you may not use any other cryptographic 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 describes this behavior as follows: "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."

The higher order bits beyond the number of bits specified by the argument must be zero. 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 (in the form of byte arrays), using a stream cipher with the properties discussed in lecture. Recall that encryption and decryption are the same operation for a stream cipher. You must not use any cryptographic primitives other than the pseudo-random function we provided and pseudo-random generator you implemented.

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.
• Start with a design that you understand before you start coding. Each component of this assignment is primarily a design challenge, which will be relatively easy to code once you understand a correct design.
• Test your code extensively for correctness, beyond the tests provided by our Autograder.
• Thoroughly review your design and implementation for security properties. Passing correctness tests will not guarantee a secure design. For example, if your code is encrypting data for confidentiality, you can test whether the ciphertext is the right size, you can test whether the ciphertext has equal distribution of ones and zeros, and you can test whether different plaintexts yield different ciphertexts. This does not guarantee that an adversary cannot recover the plaintext, so you must rely on the cryptographic theory behind your design.

Submission Checklist

Submit your files to Gradescope: