Assignment One: Pseudo-Random Generator and Stream Cipher

In this assignment, you will implement your own pseudo-random number generator and stream cipher in Java. 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
PRF.java This is a fully implemented pseudo-random function. You should use it as a building block for all of the cryptographic functionality you need in this assignment. As discussed in lecture, this pseudo-random function is the only cryptography primitive that you need. You may not use any other cryptographic primitives, even those provided by standard Java libraries.
PRGen.java This is a partially implemented pseudo-random generator. 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.
StreamCipher.java This is a partially implemented stream cipher. 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.

PRGen.java

Your pseudo-random generator class will implement the following API:

public class PRGen extends java.util.Random {
    public PRGen(byte[] key);       // generates a new PRGen
    protected int next(int bits);   // generates the next pseudo-random number
}

Your pseudo-random generator class extends the java.util.Random class, but you will only be overriding the constructor and the next() method. Your next() method must implement 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), the returned int will have a pseudo-random value between 0 and 15 (the range of a 4-bit unsigned integer). If you call next(31), the returned int will have a pseudo-random value between 0 and 2,147,483,647 (the range of a 31-bit unsigned integer). However, since the int primitive is a signed data type, when you call next(32), the returned int will have a pseudo-random value between -2,147,483,648 and 2,147,483,647 (the range of a 32-bit signed integer).

In addition to implementing this behavior, your pseudo-random generator class must also obey the following security properties:

  1. It must be pseudo-random: there is no (known) way to distinguish its output from that of a truly random generator, unless you know the key.
  2. It must be deterministic: if two programs create generators with the same key (or “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.
  3. It must be forward-secret: an adversary, who observes the full internal state of the generator at any point in time, cannot reconstruct any output that was produced by previous calls to the generator.

StreamCipher.java

Your stream cipher class will implement the following API:

public class StreamCipher {
    public StreamCipher(byte[] key, byte[] nonceArr, int nonceOffset);
    public StreamCipher(byte[] key, byte[] nonce);

    public byte cryptByte(byte in);
    public void cryptBytes(byte[] inBuf, int inOffset, byte[] outBuf, int outOffset, int numBytes);
}

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

  • Review the properties of pseudo-random functions (PRFs) and consider how you can use the provided PRF.java class to deterministically generate pseudo-random values.
  • 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 Requirements

Submit the following files to Gradescope:

  • PRGen.java - Source code file containing your fully implemented pseudo-random generator class.
  • StreamCipher.java - Source code file containing your fully implemented stream cipher class.