Last active
October 30, 2023 01:41
-
-
Save adrian154/089bb15f8890cb30457eb5429e10f098 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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