Skip to content

Instantly share code, notes, and snippets.

@adrian154
Last active October 30, 2023 01:41
Show Gist options
  • Save adrian154/089bb15f8890cb30457eb5429e10f098 to your computer and use it in GitHub Desktop.
Save adrian154/089bb15f8890cb30457eb5429e10f098 to your computer and use it in GitHub Desktop.
// 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'))
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment