Rsa.java
The instructor's program with my changes marked // HW5.
Download it as Rsa.java.txt and drop the .txt;
then javac Rsa.java and java Rsa. Jump to make_plot.py.
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();
}
}
}
make_plot.py
Reads the program's bits ms output and draws the plots: the required
linear one, a log-scale one with a “doubles every bit” guide, and the all-points one
for the extra credit. It also prints the per-bit growth and the estimates for bigger keys.
Download: make_plot.py.txt.
"""
CSC 482 HW5 - plot the RSA cracking times.
Reads the program's own output (a header line, then "bits ms" lines) and draws
bit length on the x axis and crack time in seconds on the y axis, like the
assignment asks. A second plot uses a log y axis, because the time roughly
doubles every bit and a straight line on a log scale is the easy way to see that.
If an extra-credit file is given too, a third plot puts every point on linear
axes: the 16..28 points go flat next to the 32-bit one, which is exponential
growth in one picture.
Usage:
python make_plot.py results/average-results-16-28.txt [results/extra-credit-29-32.txt] [--runs=3]
--runs only sets the legend text ("average of 3 runs"); the program's output has no run count in it.
Only matplotlib and the standard library (same as HW3's make_plot.py).
Written with help from Claude (Anthropic).
"""
import math
import os
import subprocess
import sys
import matplotlib
matplotlib.use("Agg") # draw to a file, no window
import matplotlib.pyplot as plt
from matplotlib.ticker import FuncFormatter
BLUE, ORANGE = "#2b6cb0", "#c05621"
def read_results(path):
"""Return [(bits, ms), ...] from a "Results:"/"Average results:" file."""
rows = []
with open(path, encoding="utf-8") as f:
for line in f:
parts = line.split()
if len(parts) == 2 and parts[0].isdigit() and parts[1].lstrip("-").isdigit():
rows.append((int(parts[0]), int(parts[1])))
return rows
def cpu_name():
try:
out = subprocess.run(
["powershell.exe", "-NoProfile", "-Command",
"(Get-CimInstance Win32_Processor).Name.Trim()"],
capture_output=True, text=True, timeout=20).stdout.strip()
return out or "unknown CPU"
except Exception:
return "unknown CPU"
def seconds_fmt(y, _pos=None):
"""Tick or label text for a time in seconds: 850 ms, 2.5 s, 37.8 min, 2.1 h."""
if y <= 0:
return "0"
if y >= 3600:
return f"{y/3600:.3g} h"
if y >= 60:
return f"{y/60:.3g} min"
if y >= 1:
return f"{y:.3g} s"
return f"{y*1000:.3g} ms"
def log_tick_fmt(y, _pos=None):
"""Decade ticks on the log axis: 100 ms, 1 s, 10 s, 100 s, 1000 s, 2.8 h."""
if y >= 3600:
return f"{y/3600:.3g} h"
if y >= 1:
return f"{y:.4g} s"
return f"{y*1000:.3g} ms"
def long_time(sec):
"""Text for an estimate: minutes, hours, days or years."""
if sec < 3600:
return f"{sec/60:.1f} minutes"
if sec < 86400 * 2:
return f"{sec/3600:.1f} hours"
if sec < 86400 * 365 * 2:
return f"{sec/86400:.1f} days"
return f"{sec/86400/365.25:,.0f} years"
def geo_mean(values):
return math.exp(sum(math.log(v) for v in values) / len(values))
def main():
if len(sys.argv) < 2:
print(__doc__)
sys.exit(1)
runs = 3 # the program's default; --runs=N for a file made with another count
paths = [a for a in sys.argv[1:] if not a.startswith("--runs=")]
for arg in sys.argv[1:]:
if arg.startswith("--runs="):
runs = int(arg.split("=", 1)[1])
if not paths:
print(__doc__)
sys.exit(1)
main_path = paths[0]
extra_path = paths[1] if len(paths) > 1 else None
out_dir = os.path.dirname(os.path.abspath(main_path))
main_rows = read_results(main_path)
extra_rows = read_results(extra_path) if extra_path and os.path.exists(extra_path) else []
if not main_rows:
print("no 'bits ms' rows found in", main_path)
sys.exit(1)
cpu = cpu_name()
label_main = f"average of {runs} runs" if "verage" in open(main_path, encoding="utf-8").readline() else "one run"
all_rows = main_rows + extra_rows
# ---- growth table: how much longer does each extra bit take? ----
print(f"{'bits':>4} {'ms':>10} {'time':>10} {'x prev bit':>10}")
prev = None
ratios_main, ratios_all = [], []
for idx, (bits, ms) in enumerate(all_rows):
is_extra = idx >= len(main_rows)
ratio = (ms / prev) if prev else float("nan")
if prev and prev >= 1000 and ms >= 1000: # only trust ratios once both times are past 1 s
ratios_all.append(ratio)
if not is_extra:
ratios_main.append(ratio)
tag = " (extra credit, one run)" if is_extra else ""
print(f"{bits:>4} {ms:>10,} {seconds_fmt(ms/1000):>10} {ratio:>10.2f}{tag}")
prev = ms
if ratios_all:
g_all = geo_mean(ratios_all)
first_bits = next(b for b, ms in all_rows if ms >= 1000)
print(f"\ngeometric-mean growth per bit, {first_bits}..{all_rows[-1][0]} bits (rows >= 1 s): x{g_all:.2f}")
if extra_rows and ratios_main:
print(f" same for the required {main_rows[0][0]}..{main_rows[-1][0]} range only: x{geo_mean(ratios_main):.2f}")
print(" (a search range that doubles every bit would give x2.00)")
last_bits, last_ms = all_rows[-1]
print(f"\nestimates from the {last_bits}-bit time ({seconds_fmt(last_ms/1000)}):")
head_g = f"at x{g_all:.2f}/bit"
print(f"{'bits':>6} {head_g:>18} {'at x2.00/bit':>18}")
for b in (32, 36, 40, 48, 64):
if b <= last_bits:
continue
est = last_ms / 1000 * g_all ** (b - last_bits)
est2 = last_ms / 1000 * 2.0 ** (b - last_bits)
print(f"{b:>6} {long_time(est):>18} {long_time(est2):>18}")
xs = [b for b, _ in main_rows]
ys = [ms / 1000 for _, ms in main_rows]
ex = [b for b, _ in extra_rows]
ey = [ms / 1000 for _, ms in extra_rows]
def add_extra(ax, log=False):
"""Dashed orange line from the last required point through the extra-credit points."""
if not extra_rows:
return
px = [xs[-1]] + ex
py = [max(ys[-1], 1e-3)] + ([max(v, 1e-3) for v in ey] if log else ey)
plot = ax.semilogy if log else ax.plot
plot(px, py, marker="s", markevery=list(range(1, len(px))), color=ORANGE,
linewidth=2, linestyle="--", label="extra credit (one run)")
# ---- plot 1: linear axes, 16..28 only, as the assignment asks ----
fig, ax = plt.subplots(figsize=(9, 5.5))
ax.plot(xs, ys, marker="o", color=BLUE, linewidth=2, label=f"crack time ({label_main})")
ax.set_xlabel("RSA key bit length (bits in each prime; n has twice as many)")
ax.set_ylabel("time to crack (seconds)")
ax.set_title(f"HW5 - Multithreaded RSA cracking, Rsa.java\n{cpu}")
ax.set_xticks(xs)
ax.grid(True, alpha=0.3)
ax.legend()
for b, s in zip(xs, ys):
if s >= 1:
ax.annotate(f"{s:.1f}s", (b, s), textcoords="offset points", xytext=(0, 7), ha="center", fontsize=8)
fig.tight_layout()
out1 = os.path.join(out_dir, "HW5-plot.png")
fig.savefig(out1, dpi=150)
print("\nwrote", out1)
# ---- plot 2: log y axis, where "doubles every bit" shows up as a straight line ----
fig, ax = plt.subplots(figsize=(9, 5.5))
ax.semilogy(xs, [max(v, 1e-3) for v in ys], marker="o", color=BLUE,
linewidth=2, label=f"crack time ({label_main})")
add_extra(ax, log=True)
# guide line: doubling every bit, anchored at the last required point
b0, ms0 = main_rows[-1]
guide_x = list(range(main_rows[0][0], all_rows[-1][0] + 1))
ax.semilogy(guide_x, [ms0 / 1000 * 2 ** (b - b0) for b in guide_x], color="gray",
linestyle=":", label="doubles every bit (guide)")
ax.yaxis.set_major_formatter(FuncFormatter(log_tick_fmt))
ax.set_xlabel("RSA key bit length")
ax.set_ylabel("time to crack (log scale)")
ax.set_title(f"HW5 - same data, log scale\n{cpu}")
ax.set_xticks(guide_x)
ax.grid(True, which="both", alpha=0.3)
ax.legend()
fig.tight_layout()
out2 = os.path.join(out_dir, "HW5-plot-log.png")
fig.savefig(out2, dpi=150)
print("wrote", out2)
# ---- plot 3 (extra credit only): every point on linear axes ----
if extra_rows:
fig, ax = plt.subplots(figsize=(9, 5.5))
ax.plot(xs, ys, marker="o", color=BLUE, linewidth=2, label=f"crack time ({label_main})")
add_extra(ax)
ax.set_yticks(range(0, int(max(ey)) + 300, 300)) # a tick every 5 minutes
ax.yaxis.set_major_formatter(FuncFormatter(seconds_fmt))
ax.set_xlabel("RSA key bit length")
ax.set_ylabel("time to crack")
ax.set_title(f"HW5 - extra credit, {xs[0]}..{ex[-1]} bits on linear axes\n{cpu}")
ax.set_xticks(xs + ex)
ax.grid(True, alpha=0.3)
ax.legend(loc="upper left")
for b, s in zip(xs[-1:] + ex, ys[-1:] + ey):
ax.annotate(seconds_fmt(s), (b, s), textcoords="offset points", xytext=(-6, 6), ha="right", fontsize=8)
fig.tight_layout()
out3 = os.path.join(out_dir, "HW5-plot-extra.png")
fig.savefig(out3, dpi=150)
print("wrote", out3)
if __name__ == "__main__":
main()