// research/public-key-cryptography/verify.mjs
// The math behind the immersive page "The Lock That Locks Itself"
// (/strata/public-key-cryptography/). Exact integer arithmetic with BigInt —
// no crypto library, nothing approximated.
//
// What it proves, all exactly:
//   1. The canonical Wikipedia RSA worked example reproduces digit-for-digit
//      (p=61, q=53, n=3233, e=17, d=2753; 65 -> 2790 -> 65).
//   2. Encryption round-trips: for thousands of random toy keypairs and random
//      messages m in [0,n), dec(enc(m)) == m. (Euler's theorem made operable.)
//   3. The key really is the lock: decrypting with any *other* private key
//      almost never returns the message — the asymmetry is real, not asserted.
//   4. Sign/verify works, and a one-bit tamper of the signed value is caught.
//   5. Factoring n recovers the private key exactly — the whole secret is the
//      factorisation, and the work to find it grows like sqrt(n).
//
//   node research/public-key-cryptography/verify.mjs
'use strict';

// ---- exact integer RSA primitives (identical in spirit to the page's) ----
function modpow(base, exp, mod) {
  base %= mod; let r = 1n;
  while (exp > 0n) { if (exp & 1n) r = (r * base) % mod; base = (base * base) % mod; exp >>= 1n; }
  return r;
}
function egcd(a, b) { let [oldR, r] = [a, b], [oldS, s] = [1n, 0n], [oldT, t] = [0n, 1n];
  while (r !== 0n) { const q = oldR / r;
    [oldR, r] = [r, oldR - q * r]; [oldS, s] = [s, oldS - q * s]; [oldT, t] = [t, oldT - q * t]; }
  return { g: oldR, x: oldS, y: oldT };
}
function modInverse(a, m) { const { g, x } = egcd(((a % m) + m) % m, m);
  if (g !== 1n) return null; return ((x % m) + m) % m; }

// deterministic Miller-Rabin (these bases are a proof for all n < 3.3e24 — far
// past any toy key we generate here)
const MR_BASES = [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n];
function isPrime(n) {
  if (n < 2n) return false;
  for (const p of [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n])
    { if (n % p === 0n) return n === p; }
  let d = n - 1n, r = 0n; while ((d & 1n) === 0n) { d >>= 1n; r++; }
  for (const a of MR_BASES) {
    if (a % n === 0n) continue;
    let x = modpow(a, d, n); if (x === 1n || x === n - 1n) continue;
    let ok = false;
    for (let i = 0n; i < r - 1n; i++) { x = (x * x) % n; if (x === n - 1n) { ok = true; break; } }
    if (!ok) return false;
  }
  return true;
}

// PRNG seeded for reproducibility (mulberry32 -> BigInt of `bits` bits)
function mulberry32(a) { return function () {
  a |= 0; a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
function randBits(rnd, bits) { let v = 0n;
  for (let i = 0; i < bits; i++) v = (v << 1n) | (rnd() < 0.5 ? 0n : 1n);
  v |= 1n; v |= (1n << BigInt(bits - 1)); return v; } // odd, top bit set
function randPrime(rnd, bits) { for (;;) { const c = randBits(rnd, bits); if (isPrime(c)) return c; } }

function keygen(rnd, bits) {
  let p, q;
  do { p = randPrime(rnd, bits); q = randPrime(rnd, bits); } while (p === q);
  const n = p * q, phi = (p - 1n) * (q - 1n);
  let e = 0n;
  for (const cand of [65537n, 257n, 17n, 5n, 3n]) { if (cand < phi && egcd(cand, phi).g === 1n) { e = cand; break; } }
  if (e === 0n) { e = 3n; while (egcd(e, phi).g !== 1n) e += 2n; }
  const d = modInverse(e, phi);
  return { p, q, n, phi, e, d };
}

// trial-division factoriser: work ~ sqrt(n) (the whole point of the wall)
function factor(n) { if (n % 2n === 0n) return 2n;
  for (let i = 3n; i * i <= n; i += 2n) if (n % i === 0n) return i; return n; }

let fails = 0;
const ok = (name, cond, extra = '') => { if (!cond) fails++; console.log(`${cond ? '  ok  ' : 'FAIL  '}${name}${extra ? '   ' + extra : ''}`); };

// ---- 1. The canonical Wikipedia worked example, exact ----
{
  const p = 61n, q = 53n, n = p * q, phi = (p - 1n) * (q - 1n), e = 17n;
  const d = modInverse(e, phi);
  ok('Wikipedia example: n = 61·53 = 3233', n === 3233n, String(n));
  ok('Wikipedia example: φ(n) = 3120', phi === 3120n, String(phi));
  ok('Wikipedia example: d = 17⁻¹ mod 3120 = 2753', d === 2753n, String(d));
  const c = modpow(65n, e, n);
  ok('Wikipedia example: encrypt 65 → 2790', c === 2790n, String(c));
  ok('Wikipedia example: decrypt 2790 → 65', modpow(c, d, n) === 65n, String(modpow(c, d, n)));
}

// ---- 2. round-trip over many random toy keys × messages ----
{
  const rnd = mulberry32(12345);
  let trials = 0, allRoundTrip = true;
  for (let k = 0; k < 400; k++) {
    const { n, e, d } = keygen(rnd, 12); // ~24-bit n
    for (let j = 0; j < 30; j++) {
      const m = randBits(rnd, 11) % n; // m < n
      const c = modpow(m, e, n), back = modpow(c, d, n);
      trials++; if (back !== m) allRoundTrip = false;
    }
  }
  ok(`encryption round-trips on every trial (${trials} of them)`, allRoundTrip, `${trials} trials`);
}

// ---- 3. exhaustive round-trip on a tiny key: EVERY m in [0,n) survives ----
{
  // p=61,q=53 -> n=3233. Encrypt then decrypt all 3233 residues.
  const p = 61n, q = 53n, n = p * q, e = 17n, d = modInverse(e, (p - 1n) * (q - 1n));
  let allBack = true;
  for (let m = 0n; m < n; m++) if (modpow(modpow(m, e, n), d, n) !== m) { allBack = false; break; }
  ok('exhaustive: all 3233 messages round-trip under (n=3233,e=17,d=2753)', allBack);
}

// ---- 4. the asymmetry: a DIFFERENT private key does not invert ----
{
  const rnd = mulberry32(999);
  let leaks = 0, total = 0;
  for (let k = 0; k < 300; k++) {
    const A = keygen(rnd, 12);
    // a foreign private exponent (another valid key for the SAME modulus would be
    // identical, so use a different modulus's d applied here — it must fail).
    const B = keygen(rnd, 12);
    const m = randBits(rnd, 10) % A.n;
    const c = modpow(m, A.e, A.n);
    const wrong = modpow(c, B.d, A.n); // decrypt A's ciphertext with B's secret
    total++; if (wrong === m) leaks++;
  }
  ok('a foreign private key recovers the message ~never', leaks === 0, `${leaks}/${total} accidental recoveries`);
}

// ---- 5. sign / verify, and tampering is caught ----
{
  const rnd = mulberry32(2024);
  let good = 0, caughtTamper = 0, T = 0;
  for (let k = 0; k < 300; k++) {
    const { n, e, d } = keygen(rnd, 12);
    const m = randBits(rnd, 10) % n;
    const sig = modpow(m, d, n);          // sign with PRIVATE
    const check = modpow(sig, e, n);      // verify with PUBLIC
    if (check === m) good++;
    // tamper: change the message by 1, signature no longer verifies
    const m2 = (m + 1n) % n;
    if (modpow(sig, e, n) !== m2) caughtTamper++;
    T++;
  }
  ok('a private-key signature verifies with the public key (all)', good === T, `${good}/${T}`);
  ok('tampering with the signed message is caught (all)', caughtTamper === T, `${caughtTamper}/${T}`);
}

// ---- 6. factoring n recovers the private key exactly ----
{
  const rnd = mulberry32(7);
  let recovered = 0, T = 0;
  for (let k = 0; k < 50; k++) {
    const key = keygen(rnd, 14); // ~28-bit n, factor in well under a ms
    const f = factor(key.n);     // attacker sees only (n,e); finds a factor
    const p2 = f, q2 = key.n / f;
    const phi2 = (p2 - 1n) * (q2 - 1n);
    const dRecovered = modInverse(key.e, phi2);
    T++;
    if (dRecovered === key.d && p2 * q2 === key.n) recovered++;
  }
  ok('factoring n recovers d exactly (the whole secret is the factorisation)', recovered === T, `${recovered}/${T}`);
}

// ---- the wall: work to factor grows like sqrt(n) ----
{
  // timing sanity — purely illustrative, not a pass/fail claim.
  const sizes = [20, 28, 36];
  console.log('  ·   factoring work scales like √n (trial division):');
  const rnd = mulberry32(55);
  for (const bits of sizes) {
    const key = keygen(rnd, bits / 2);
    const t0 = process.hrtime.bigint();
    factor(key.n);
    const us = Number(process.hrtime.bigint() - t0) / 1000;
    console.log(`        n≈2^${bits} (${key.n})  factored in ${us.toFixed(0)} µs  (√n ≈ ${Math.round(Math.sqrt(Number(key.n)))} steps)`);
  }
}

console.log(fails ? `\n${fails} FAILED` : '\nAll checks passed.');
process.exit(fails ? 1 : 0);
