BBS.java

package crypto;

import java.math.BigInteger;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.Scanner;

/**
 * Blum-Blum-Shub (BBS) pseudorandom number generator in pure Java.
 * 
 * @author Chris Lattman
 */
public class BBS {

    /**
     * The Blum-Blum-Shub (BBS) pseudorandom number generator.
     * 
     * @param args not used
     * @throws NoSuchAlgorithmException non-issue
     */
    public static void main(String[] args) throws NoSuchAlgorithmException {
        /*
         * 2048-bit primes p and q are chosen such that they are of the form
         * 4k + 3, which means that the two rightmost (lowest-order) bits
         * should be set to 1.
         */
        SecureRandom random = SecureRandom.getInstanceStrong();
        BigInteger p = BigInteger.probablePrime(2048, random);
        BigInteger q = BigInteger.probablePrime(2048, random);
        while (!p.testBit(0) || !p.testBit(1)) {
            p = BigInteger.probablePrime(2048, random);
        }
        while (p.equals(q) || !q.testBit(0) || !q.testBit(1)) {
            q = BigInteger.probablePrime(2048, random);
        }
        
        /*
         * n = p * q is computed
         * 
         * x must be relatively prime to n
         * 
         * Since x must be invertible under multiplication mod n, it suffices
         * to choose x to be a random number less than n not equal to p or q.
         */
        BigInteger n = p.multiply(q);
        BigInteger x = new BigInteger(4096, random);
        while (x.compareTo(n) >= 0 || x.equals(p) || x.equals(q)) {
            x = new BigInteger(4096, random);
        }
        
        /*
         * Ask user how many random bits are desired.
         */
        Scanner scanner = new Scanner(System.in);
        int bits = 0;
        while (true) {
            try {
                System.out.print("Enter how many random bits ");
                System.out.print("you would like (enter q to quit): ");
                String bitsString = scanner.next();
                if (bitsString.contains("q")) {
                    break;
                }
                bitsString = bitsString.replaceAll("[^0-9]", "");
                bits = Integer.parseInt(bitsString);
                break;
            }
            catch (Exception e) {
                System.out.println("Invalid input.");
            }
        }
        scanner.close();
        
        /*
         * The BBS algorithm. Bits, stored in b, are generated by squaring x
         * mod n, isolating the lowest-order bit of x, and setting b's 
         * current index bit to x's isolated bit value.
         * 
         * Note: it is possible to calculate the ith bit directly due to
         * Euler's theorem:
         * 
         * x_i = x_0^(2^i mod L(n)) mod n
         * 
         * where L is the Carmichael function:
         * 
         * L(n) = L(p * q) = lcm(p - 1, q - 1)
         * 
         * (lcm is the Least Common Multiple function)
         * 
         * Therefore, the cycle length of BBS is phi(L(n)), where phi is
         * Euler's totient function.
         */
        BigInteger b = BigInteger.ZERO;
        for (int i = 0; i < bits; i++) {
            x = x.modPow(BigInteger.TWO, n);
            if (x.testBit(0)) {
                b = b.setBit(i);
            }
        }
        
        if (bits > 0) {
            System.out.println("Random number (in hex): " + b.toString(16));
        }
    }
}