// Privacy Pass in the page: the client of RFC 9577's `PrivateToken` HTTP authentication
// scheme and of RFC 9578's publicly verifiable issuance (§6, token type 0x0002, blind RSA of
// RFC 9474), for a room that admits by age (WAI age-assurance §5.6).
//
// - parseChallenges: the `WWW-Authenticate` challenges an origin sends (RFC 9577 §2.1.2),
//   each a TokenChallenge (§2.1.1) and the issuer's key;
// - acceptable: RFC 9577 §2.1.3's checks of a challenge, its origin_info holding the page's
//   own server name;
// - issue: the client of RFC 9578 §6.1 to §6.3. It blinds the token input under the issuer's
//   key (RFC 9474 §4.2: EMSA-PSS with SHA-384, MGF1 with SHA-384, a salt of 48 bytes, then
//   m·r^e mod n), sends the TokenRequest to the issuer's request URL (from its directory,
//   RFC 9578 §4), unblinds the answer (RFC 9474 §4.4: s = z·r^−1 mod n), verifies it, and
//   returns the token. The issuer signs blindly, so it never sees the token, the challenge or
//   the room; the origin sees the token and never the issuance.
// - authorization: the `Authorization: PrivateToken token="…"` field (RFC 9577 §2.2.2).
//
// The arithmetic is BigInt's; SHA-256 and SHA-384 are WebCrypto's. Nothing here is a secret
// the page keeps: a token is spent once, and the blind is forgotten once the token is made.

const TOKEN_TYPE = 0x0002;
const NK = 256; // RSA-2048
const SALT_LEN = 48;
const H_LEN = 48;

const cat = (...parts) => {
  const out = new Uint8Array(parts.reduce((n, p) => n + p.length, 0));
  let at = 0;
  for (const p of parts) { out.set(p, at); at += p.length; }
  return out;
};
const sha = async (alg, b) => new Uint8Array(await crypto.subtle.digest(alg, b));
const eq = (a, b) => a.length === b.length && a.every((x, i) => x === b[i]);

// ---- base64url (RFC 4648 §5), with padding as RFC 9577 writes it ----

const B64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";

export function b64url(b) {
  let s = "";
  for (let i = 0; i < b.length; i += 3) {
    const n = (b[i] << 16) | ((b[i + 1] || 0) << 8) | (b[i + 2] || 0);
    const k = Math.min(3, b.length - i);
    for (let j = 0; j < 4; j++) s += j <= k ? B64[(n >> (18 - 6 * j)) & 63] : "=";
  }
  return s;
}

export function unb64url(s) {
  const t = s.replace(/=+$/, "");
  if (t.length % 4 === 1) throw new Error("not base64url");
  const out = [];
  for (let i = 0; i < t.length; i += 4) {
    let n = 0;
    const c = t.slice(i, i + 4);
    for (let j = 0; j < c.length; j++) {
      const v = B64.indexOf(c[j]);
      if (v < 0) throw new Error("not base64url");
      n |= v << (18 - 6 * j);
    }
    out.push((n >> 16) & 255);
    if (c.length > 2) out.push((n >> 8) & 255);
    if (c.length > 3) out.push(n & 255);
  }
  return new Uint8Array(out);
}

// ---- RFC 9577: challenges and the token's field ----

// The challenges of `WWW-Authenticate` field values (one or more fields, each one or more
// challenges): those of the scheme `PrivateToken`, each its TokenChallenge, its issuer key and
// its max-age.
export function parseChallenges(values) {
  const out = [];
  for (const v of [].concat(values || [])) {
    for (const part of String(v).split(/(?=PrivateToken\s)/)) {
      const m = part.match(/^PrivateToken\s+(.*)$/s);
      if (!m) continue;
      const params = {};
      for (const p of m[1].matchAll(/([A-Za-z-]+)\s*=\s*("([^"]*)"|[^,\s]+)/g)) params[p[1].toLowerCase()] = p[3] !== undefined ? p[3] : p[2];
      if (!params.challenge) continue;
      out.push({
        challenge: unb64url(params.challenge),
        tokenKey: params["token-key"] ? unb64url(params["token-key"]) : null,
        maxAge: params["max-age"] ? Number(params["max-age"]) : null,
      });
    }
  }
  return out;
}

// RFC 9577 §2.1.1: a TokenChallenge, or null.
export function readChallenge(b) {
  if (b.length < 4) return null;
  const tokenType = (b[0] << 8) | b[1];
  const nl = (b[2] << 8) | b[3];
  let i = 4 + nl;
  if (nl < 1 || i >= b.length) return null;
  const issuerName = new TextDecoder().decode(b.subarray(4, i));
  const cl = b[i];
  if (cl !== 0 && cl !== 32) return null;
  const redemptionContext = b.subarray(i + 1, i + 1 + cl);
  i += 1 + cl;
  if (i + 2 > b.length) return null;
  const ol = (b[i] << 8) | b[i + 1];
  if (i + 2 + ol !== b.length) return null;
  return { tokenType, issuerName, redemptionContext, originInfo: new TextDecoder().decode(b.subarray(i + 2)) };
}

// RFC 9577 §2.1.3: a challenge a client may act on, for the origin `host`: a token type it
// supports (0x0002), well formed, and an origin_info that is empty or lists `host`, compared
// without regard to ASCII case.
export function acceptable(c, host) {
  if (!c || c.tokenType !== TOKEN_TYPE) return false;
  return c.originInfo === "" || c.originInfo.split(",").some((n) => n.toLowerCase() === String(host).toLowerCase());
}

export function authorization(token) {
  return `PrivateToken token="${b64url(token)}"`;
}

// ---- RSA (RFC 8017) in BigInt ----

const big = (b) => b.reduce((n, x) => (n << 8n) | BigInt(x), 0n);
function bytes(n, len) {
  const out = new Uint8Array(len);
  for (let i = len - 1; i >= 0; i--) { out[i] = Number(n & 255n); n >>= 8n; }
  if (n !== 0n) throw new Error("integer too large");
  return out;
}
export function modpow(b, e, m) {
  let r = 1n;
  b %= m;
  while (e > 0n) {
    if (e & 1n) r = (r * b) % m;
    b = (b * b) % m;
    e >>= 1n;
  }
  return r;
}
function gcd(a, b) {
  while (b) [a, b] = [b, a % b];
  return a;
}
function inverse(a, m) {
  let [r0, r1, s0, s1] = [m, a % m, 0n, 1n];
  while (r1) {
    const q = r0 / r1;
    [r0, r1] = [r1, r0 - q * r1];
    [s0, s1] = [s1, s0 - q * s1];
  }
  if (r0 !== 1n) throw new Error("blinding error");
  return ((s0 % m) + m) % m;
}
const bitLength = (n) => n.toString(2).length;

// One DER element at `i`: [tag, start of contents, end].
function der(b, i) {
  const tag = b[i];
  let len = b[i + 1];
  let at = i + 2;
  if (len & 0x80) {
    const k = len & 0x7f;
    len = 0;
    for (let j = 0; j < k; j++) len = len * 256 + b[at + j];
    at += k;
  }
  return [tag, at, at + len];
}

// RFC 9578 §6.5's SubjectPublicKeyInfo: its modulus and exponent.
export function readSpki(spki) {
  const [, s0] = der(spki, 0);
  const [, , algEnd] = der(spki, s0);
  const [bt, bs, be] = der(spki, algEnd);
  if (bt !== 0x03 || spki[bs] !== 0) throw new Error("not a SubjectPublicKeyInfo");
  const [, k0] = der(spki, bs + 1);
  const [nt, ns, ne] = der(spki, k0);
  const [et, es, ee] = der(spki, ne);
  if (nt !== 2 || et !== 2 || ee > be) throw new Error("not an RSA key");
  return { n: big(spki.subarray(ns, ne)), e: big(spki.subarray(es, ee)) };
}

async function mgf1(seed, len) {
  const out = [];
  for (let c = 0; out.length < len; c++) out.push(...(await sha("SHA-384", cat(seed, new Uint8Array([c >>> 24, (c >>> 16) & 255, (c >>> 8) & 255, c & 255])))));
  return new Uint8Array(out.slice(0, len));
}

// RFC 8017 §9.1.1, EMSA-PSS-ENCODE with SHA-384, MGF1 with SHA-384 and `salt`.
async function pssEncode(m, emBits, salt) {
  const emLen = Math.ceil(emBits / 8);
  const mHash = await sha("SHA-384", m);
  const h = await sha("SHA-384", cat(new Uint8Array(8), mHash, salt));
  const db = cat(new Uint8Array(emLen - salt.length - H_LEN - 2), new Uint8Array([1]), salt);
  const mask = await mgf1(h, emLen - H_LEN - 1);
  const masked = db.map((x, i) => x ^ mask[i]);
  masked[0] &= 0xff >> (8 * emLen - emBits);
  return cat(masked, h, new Uint8Array([0xbc]));
}

// RFC 8017 §8.1.2 and §9.1.2: RSASSA-PSS-VERIFY with SHA-384 and a salt of 48 bytes.
export async function pssVerify(key, m, sig) {
  const modBits = bitLength(key.n);
  if (sig.length !== Math.ceil(modBits / 8)) return false;
  const s = big(sig);
  if (s >= key.n) return false;
  const emBits = modBits - 1;
  const emLen = Math.ceil(emBits / 8);
  const em = bytes(modpow(s, key.e, key.n), emLen);
  if (em[emLen - 1] !== 0xbc) return false;
  const masked = em.subarray(0, emLen - H_LEN - 1);
  const h = em.subarray(emLen - H_LEN - 1, emLen - 1);
  if (masked[0] & ~(0xff >> (8 * emLen - emBits)) & 0xff) return false;
  const mask = await mgf1(h, masked.length);
  const db = masked.map((x, i) => x ^ mask[i]);
  db[0] &= 0xff >> (8 * emLen - emBits);
  const ps = emLen - H_LEN - SALT_LEN - 2;
  if (!db.subarray(0, ps).every((x) => x === 0) || db[ps] !== 1) return false;
  const salt = db.subarray(ps + 1);
  return eq(await sha("SHA-384", cat(new Uint8Array(8), await sha("SHA-384", m), salt)), h);
}

function randomBytes(n) {
  return crypto.getRandomValues(new Uint8Array(n));
}

function randomBelow(n) {
  for (;;) {
    const r = big(randomBytes(Math.ceil(bitLength(n) / 8))) % (1n << BigInt(bitLength(n)));
    if (r > 0n && r < n) return r;
  }
}

// ---- RFC 9578 §6: issuance ----

// The TokenRequest for `challenge` under `tokenKey` (§6.1), and how to finalize the issuer's
// answer into a token (§6.3). `nonce`, `blind` and `salt` are drawn here unless given (the
// tests give RFC 9578 Appendix A.2's).
export async function tokenRequest({ challenge, tokenKey, nonce, blind, salt }) {
  const key = readSpki(tokenKey);
  nonce = nonce || randomBytes(32);
  salt = salt || randomBytes(SALT_LEN);
  const keyId = await sha("SHA-256", tokenKey);
  const input = cat(new Uint8Array([0, TOKEN_TYPE]), nonce, await sha("SHA-256", challenge), keyId);
  const m = big(await pssEncode(input, bitLength(key.n) - 1, salt));
  if (gcd(m, key.n) !== 1n) throw new Error("invalid input");
  const r = blind ? big(blind) : randomBelow(key.n);
  const inv = inverse(r, key.n);
  const blinded = (m * modpow(r, key.e, key.n)) % key.n;
  const request = cat(new Uint8Array([0, TOKEN_TYPE, keyId[31]]), bytes(blinded, NK));
  const finalize = async (response) => {
    if (response.length !== NK) throw new Error("unexpected input size");
    const sig = bytes((big(response) * inv) % key.n, NK);
    if (!(await pssVerify(key, input, sig))) throw new Error("invalid signature");
    return cat(input, sig);
  };
  return { request, finalize };
}

// A token for `challenge` from its issuer, whose directory (RFC 9578 §4) is at `directory`:
// the TokenRequest sent to the directory's request URL, the answer finalized. `fetchFn` is
// the page's fetch.
export async function issue({ challenge, tokenKey, directory, fetchFn = fetch }) {
  const d = await fetchFn(directory, { cache: "no-store" });
  if (!d.ok) throw new Error(`the issuer's directory answered ${d.status}`);
  const dir = await d.json();
  const listed = (dir["token-keys"] || []).some((k) => k["token-type"] === TOKEN_TYPE && eq(unb64url(k["token-key"]), tokenKey));
  if (!listed) throw new Error("the issuer does not list the challenge's key");
  const url = new URL(dir["issuer-request-uri"], directory).toString();
  const { request, finalize } = await tokenRequest({ challenge, tokenKey });
  const r = await fetchFn(url, { method: "POST", headers: { "content-type": "application/private-token-request", accept: "application/private-token-response" }, body: request, cache: "no-store" });
  if (r.status !== 200) throw new Error(`the issuer answered ${r.status}`);
  return finalize(new Uint8Array(await r.arrayBuffer()));
}

// The directory of `issuerName` (RFC 9578 §4): at its well-known URI, or under `base` where
// the page is told one (`?issuer_directory=`), at `<base>/<issuer name>/.well-known/…`.
export function directoryOf(issuerName, base) {
  const path = "/.well-known/private-token-issuer-directory";
  return base ? `${base.replace(/\/$/, "")}/${encodeURIComponent(issuerName)}${path}` : `https://${issuerName}${path}`;
}