import java.math.BigInteger; import java.util.*; import java.util.concurrent.*; /* CSC 482 - Homework 5 - Multithreaded RSA cracking Charleigh Roberts Starting point: Rsa.java from the course page (J. Hastings). It makes a random RSA modulus n = p*q for a given bit length and brute-forces the factors with a ForkJoin pool, starting at sqrt(n) and stepping through probable primes. My changes are marked // HW5: - main loops over the bit lengths (16..28 by default) instead of cracking one key; the body of the old main became the crack() method so the loop can call it - each bit length is cracked RUNS times and only the average time prints - one ForkJoinPool for the whole program instead of a new one per key - the thread that finds a factor now also remembers it (endCont(currentPrime)), and every crack checks that the factor really divides n and is p or q before the time counts (lesson from HW3: verify every run before trusting the time) - the chatty output is commented out so only "bits ms" prints The original already stops the other threads through the shared "cont" flag (its System.exit(0) and the constructor's initCont() were commented out), so the loop works without touching the thread coordination. Written with help from Claude (Anthropic), per the course AI policy. Compile: javac Rsa.java Run: java Rsa -> bits 16..28, 3 runs each, prints "Average results:" java Rsa 16 28 1 -> one run each, prints "Results:" java Rsa 29 32 1 -> extra credit, one run each (took 67 min) */ public class Rsa { static final BigInteger TWO = new BigInteger("2"); public static void main (String [] args) { int minBits = 16, maxBits = 28, runs = 3; // HW5: the assignment's range and run count try { if (args.length >= 1) minBits = Integer.parseInt(args[0]); if (args.length >= 2) maxBits = Integer.parseInt(args[1]); if (args.length >= 3) runs = Integer.parseInt(args[2]); if (args.length > 3 || minBits < 2 || maxBits < minBits || runs < 1) throw new Exception(); } catch (Exception e) { System.out.println("Correct usage: java Rsa [min-bits] [max-bits] [runs]"); System.exit(0); } Random r = new Random(); // should only ever be called once in a Java program! // HW5: one pool for the whole program instead of a new one per key ForkJoinPool fjPool = new ForkJoinPool(); System.out.println(runs == 1 ? "Results:" : "Average results:"); // LOOP OVER THE BIT LENGTH HERE for (int bitLength = minBits; bitLength <= maxBits; bitLength++) { long total = 0; for (int run = 0; run < runs; run++) total += crack(bitLength, r, fjPool); System.out.println(bitLength + " " + (total / runs)); // HW5: only the average prints } fjPool.shutdown(); } // HW5: the body of the original main, moved into a method so the loop can call it. // Returns the crack time in ms. Inside it is the original code; only the prints changed. static long crack(int bitLength, Random r, ForkJoinPool fjPool) { // Produce two random primes up to the specified bit length BigInteger n = BigInteger.ONE; BigInteger p = null, q = null; int calcBitLength = 0; do { p = BigInteger.probablePrime(bitLength, r); q = BigInteger.probablePrime(bitLength, r); n = p.multiply(q); //System.out.println("p="+p+" q="+q+" n="+n); // recalculate the bit length based on the produced value of n // it could be less than bitLength. We want it to be the same. calcBitLength = n.bitLength()/2; } while (calcBitLength != bitLength); // calculate the upper value of the search range. // max is maximum value for the given bit length. It's likely overly large. Can it be smaller? BigInteger max = TWO.pow(calcBitLength+1).subtract(BigInteger.ONE); //System.out.println("bitLength="+calcBitLength+", max="+max); // attempt to factor n. start at the sqrt of n and work up. BigInteger i = n.sqrt(); //System.out.println("initial i="+i); // Try to invoke the garbage collector before cracking so that it is less likely to happen // during cracking. Java might listen. System.gc(); long startTime = System.currentTimeMillis(); // if you had an idea that the solution was within a certain range of numbers, // e.g., close to the sqrt of n, you would want to adjust the search to concentrate on this area // rather than creating an initial set of thread tasks that span the entire range from the sqrt of n // up to max ForkJoinRsaTask forkJoinRsaTask = new ForkJoinRsaTask(n, i, max); ForkJoinRsaTask.initCont(); // this really should be done internal to the class fjPool.invoke(forkJoinRsaTask); long endTime = System.currentTimeMillis(); //System.out.println("Elapsed time: " + (endTime-startTime) + "ms"); // HW5: don't trust the time unless the crack really worked BigInteger found = ForkJoinRsaTask.getFound(); if (found == null || !n.mod(found).equals(BigInteger.ZERO) || !(found.equals(p) || found.equals(q))) { System.out.println("CRACK FAILED at " + bitLength + " bits: n=" + n + " p=" + p + " q=" + q + " found=" + found); System.exit(1); } return endTime - startTime; } } class ForkJoinRsaTask extends RecursiveAction { BigInteger min, n, max; private static final BigInteger THRESHOLD = new BigInteger("1000"); // This variable will tell threads whether they should continue factoring. // It must be protected through synchronization because // ALL threads may try to access it simultaneously!!!! static boolean cont = true; // should all threads continue? static BigInteger found = null; // HW5: the factor a thread found, so main can check it // Synchronized methods to protect access to "cont". Only one static // synchronized method for a class can be running at a time!!! static synchronized boolean getCont() { return cont; } static synchronized void initCont() { cont = true; found = null; } static synchronized void endCont() { cont = false; } static synchronized void endCont(BigInteger f) { cont = false; found = f; } // HW5 static synchronized BigInteger getFound() { return found; } // HW5 public ForkJoinRsaTask(BigInteger n, BigInteger min, BigInteger max) { this.min = min; this.n=n; this.max=max; //initCont(); // (already commented out in the original: every subtask runs this constructor, // so it would flip cont back to true mid-search; main calls initCont() once per crack) } @Override protected void compute() { BigInteger diff = max.subtract(min); // once the search is sufficiently small, just loop through it if (diff.compareTo(THRESHOLD)<0) { BigInteger currentPrime = min; // loop through each prime less than max and see if any divide n. If so, print the found value, and do a // system exit to end all threads each time through the loop, select the next value to test by using the // BigInteger nextProbablePrime method do { if (n.mod(currentPrime).equals(BigInteger.ZERO)) { //System.out.println("Keys (p,q): " + currentPrime+", " + // n.divide(currentPrime)); // iF this was a "home run" hack trying to just exit as soon as a factor was found, // we could do that right here. Otherwise, we have to coordinate with the threads // through the "cont" variable so they know they need to exit. //System.exit(0); endCont(currentPrime); // HW5: was endCont(); now also remembers the factor break; } else currentPrime = currentPrime.nextProbablePrime(); } while (getCont() && currentPrime.compareTo(max) <= 0); } else if (getCont() ) { // Cut the list in half, and call ForkJoinRsaTask for the two halves (similar to multithreaded quicksort) BigInteger mid = (max.add(min)).divide(BigInteger.TWO); ForkJoinRsaTask taskA = new ForkJoinRsaTask(n,min,mid); ForkJoinRsaTask taskB = new ForkJoinRsaTask(n,mid.add(BigInteger.ONE),max); taskA.fork(); taskB.compute(); taskA.join(); } } }