pohlig.js

// README: writeup @ https://blog.bithole.dev/blogposts/ctf-writeups/udctf-strong-primes/

// generate some small primes for trial division
const sieve = new Uint8Array(1e7);
const smallprimes = [];

for(let i = 2; i < sieve.length; i++) {
    if(!sieve[i]) {
        smallprimes.push(BigInt(i));
        for(let j = i; j < sieve.length; j += i) {
            sieve[j] = 1;
        }
    }
}

// efficient modular exponentiation
// ref: https://en.wikipedia.org/wiki/Modular_exponentiation 
const powMod = (base, exponent, modulus) => {
	let result = 1n;
	base = base % modulus;
	while(exponent > 0n) {
		if(exponent % 2n == 1n) {
			result = (result * base) % modulus;
		}
		exponent >>= 1n;
		base = (base * base) % modulus;
	}
	return result;
};

// crude sqrt approximation, returns smallest y so y*y > x
const sqrt = value => {
    let guess = 1n;
    while(guess * guess < value) { guess++; } 
    return guess + 1n;
};

// compute x so g^x mod p = y using the baby-step giant-step algorithm
// ref: https://en.wikipedia.org/wiki/Baby-step_giant-step
const discreteLog = (g, y, p, order) => {

    if(y==1n) return order;

    const m = sqrt(order);

    const arr = new Array(m);
    for(let j = 0n; j < m; j++) {
        arr[powMod(g, j, p)] = j; 
    }

    const c = powMod(g, m * (order - 1n), p);
    let gamma = y;
    for(let i = 0n; i < m; i++) {
        if(gamma in arr) {
            return i * m + arr[gamma];
        }
        gamma = (gamma * c) % p;
    }

};

// extended euclidean algorithm for computing modular inverses, we use this to solve the resulting system of congruences after solving DLP in the small subgroups
// ref: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
const inverse = (a, n) => {
	let t = 0n, newt = 1n;
	let r = n, newr = a;
	while(newr != 0n) {
		const quotient = r / newr;
		[t, newt] = [newt, t - quotient * newt];
		[r, newr] = [newr, r - quotient * newr];
    }
	if(r > 1n) 
		throw new Error("no inverse");
	if(t < 0n)
		t = t + n;
	return t;
};

// partially factorize `n`
const factorize = n => {
    for(const factor of smallprimes) {
        if(n % factor == 0) {
            return [factor, factorize(n / factor)].flat();
        }
    }
    return [n];
};

const log = require("fs").readFileSync("../dh/auth.log", "ascii").split("\n").map(JSON.parse);
const seenPrimes = [];

const g = 2n;
const map = {};

for(const entry of log) {

    const p = BigInt('0x' + entry.p),
          y = BigInt('0x' + entry.A);
        
    if(seenPrimes.includes(p)) {
        continue;
    }
    seenPrimes.push(p);

    // order of subgroup generated by g is divisible by order
    // so we can easily test which factors are *not* part of the subgroup order
    let order = p - 1n;
    const subgroupFactors = [];
    for(const factor of factorize(order)) {
        if(powMod(2n, order / factor, p) == 1n) {
            order /= factor;
        } else {
            subgroupFactors.push(factor);
        }
    }

    // remove last composite factor (too big)
    subgroupFactors.pop();

    // solve x mod r
    // ref: https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm
    for(const r of subgroupFactors) {

        // if we already know x mod r we don't need to compute it again
        if(map[r]) continue;

        const order = p - 1n;
        const gi = powMod(g, order / r, p); // this element has order r, use it as a generator 
        const yi = powMod(y, order / r, p); // gi^x mod r
    
        // solve gi^xi = yi mod p
        const xi = discreteLog(gi, yi, p, r);
        map[r] = xi;
            
    }

    // reconstruct secret
    // ref: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
    const factors = Object.keys(map).map(BigInt);
    let N = factors.reduce((a,c) => a*c, 1n);
    let ans = 0n;
    for(const factor of factors) {
        ans += map[factor] * (N / factor) * inverse(N / factor, factor);
    }
    ans %= N;

    // test if we have the full secret
    if(powMod(g, ans, p) == y) {
        console.log(ans);
        process.exit(0);
    }

}

// decrypt script
/*
import hashlib
from Crypto.Cipher import AES
from Crypto.Util import Padding

# fill in parameters from auth.log
# p = ...
# B = ...
# iv = bytes.fromhex('...')
# ct = bytes.fromhex('...')

g = 2
aliceSecret = ...
ss = pow(B,aliceSecret,p)
key = hashlib.sha256(ss.to_bytes(2048//8,'big')).digest()[:16]
cipher = AES.new(key,AES.MODE_CBC,iv)

print(Padding.unpad(cipher.decrypt(ct),AES.block_size).decode('utf-8'))
*/