//! Stage One proofs of concept — classic number-theoretic attacks, driven entirely
//! by `coprime::number`'s public surface at `u64` scale: the proved core composing
//! into real cryptography (scaling to production key sizes is the bignum layer's
//! job, not Stage One).
//!
//! Organization here is **code locality**, not genealogy: tests are grouped into
//! family modules (`dh`, `dlp`, `rsa`, `signatures`, `srp`) only to share setup
//! and imports. The actual lineage — the citation DAG of how each attack builds on
//! prior work, including the merge edges a module tree cannot show — is the map in
//! `ATTACKS.md` at the workspace root.
#![allow(clippy::many_single_char_names)] // p, q, n, e, d, m, g, h, x — canonical crypto names
#![allow(clippy::cast_possible_truncation)] // every u128→u64 cast here is a residue < n < 2^32

use coprime::number::Rng;

/// Deterministic LCG (Knuth MMIX constants) as a test [`Rng`] — reproducible,
/// not for secrets.
struct Lcg(u64);
impl Rng for Lcg {
    fn next_u64(&mut self) -> u64 {
        self.0 = self
            .0
            .wrapping_mul(6_364_136_223_846_793_005)
            .wrapping_add(1_442_695_040_888_963_407);
        self.0
    }
}

/// A non-cryptographic stand-in "hash" (FNV-style mixer) for the protocol POCs.
/// The challenges' real SHA is symmetric crypto — a later phase, not stage-1
/// number theory — so it is stubbed here; the number theory is what these tests
/// exercise. NOT secure; do not use for anything real.
fn mix(vals: &[u64]) -> u64 {
    vals.iter().fold(0xcbf2_9ce4_8422_2325, |acc, &v| {
        (acc ^ v).wrapping_mul(0x0000_0100_0000_01b3)
    })
}

/// **Diffie-Hellman, 1976** — the public-key key exchange (root of the whole
/// discrete-log world), then the two ways a tampered transcript collapses the
/// shared secret to a value the attacker already knows.
mod dh {
    use coprime::number::{modpow, primitive_root};

    /// **Key exchange** — Diffie & Hellman, 1976. Alice and Bob derive the same
    /// `g^(ab) mod p` from public `g^a`, `g^b` without exchanging their secrets.
    #[test]
    fn key_exchange() {
        let p = 1_000_000_007u64;
        let g = primitive_root(p).unwrap();
        for &(a, b) in &[(3u64, 5u64), (123_456, 789_012), (2, p - 2), (999_999, 1)] {
            let pub_a = modpow(g, a, p); // Alice publishes A = g^a
            let pub_b = modpow(g, b, p); // Bob publishes B = g^b
            assert_eq!(
                modpow(pub_a, b, p),
                modpow(pub_b, a, p),
                "DH shared secret disagreement (a={a} b={b})",
            );
        }
    }

    /// **MITM key-fixing** — challenge 34. A man-in-the-middle replaces both public
    /// values with `p` (≡ 0 mod p); each party computes `0^secret ≡ 0`, so the
    /// shared secret is `0` and known to the attacker with no private key.
    #[test]
    fn mitm_key_fixing() {
        let p = 1_000_000_007u64;
        let g = primitive_root(p).unwrap();
        let (a, b) = (123_456u64, 654_321u64);
        let _real_a = modpow(g, a, p); // honest A, dropped by the MITM
        let _real_b = modpow(g, b, p);
        let alice = modpow(p, a, p); // p^a ≡ 0
        let bob = modpow(p, b, p);
        assert_eq!(alice, 0);
        assert_eq!(bob, 0); // both derive 0; the attacker knows the key with no secret
    }

    /// **Malicious `g`** — challenge 35. A degenerate generator collapses the
    /// shared secret: `g = 1 ⇒ 1`, `g = p ⇒ 0`, `g = p−1 ≡ −1 ⇒ ±1`.
    #[test]
    fn malicious_g() {
        let p = 1_000_000_007u64;
        let (a, b) = (123_456u64, 654_321u64);
        assert_eq!(modpow(modpow(1, a, p), b, p), 1, "g=1 ⇒ secret 1");
        assert_eq!(modpow(modpow(p, a, p), b, p), 0, "g=p ⇒ secret 0");
        let s = modpow(modpow(p - 1, a, p), b, p);
        assert!(s == 1 || s == p - 1, "g=p-1 ⇒ secret ±1");
    }
}

/// **The discrete-log methods, 1978** — what an attacker runs against the DH
/// problem. Pohlig-Hellman factors a smooth group order into tiny per-subgroup
/// logs; Pollard's kangaroo searches a bounded interval; composing them recovers a
/// bounded secret in a partly-smooth group.
mod dlp {
    use coprime::number::{crt, factorize, is_prime, modpow, order, primitive_root};

    /// **Pohlig-Hellman** — Pohlig & Hellman, 1978. The discrete log in a group of
    /// smooth order, recovered one prime-power factor at a time then CRT'd. Here
    /// `p-1 = 2²·3·5·7·11` is smooth, so each per-subgroup log is a tiny search.
    #[test]
    fn pohlig_hellman() {
        let p = 4621u64; // prime; p-1 = 4620 = 2²·3·5·7·11 (smooth)
        assert!(is_prime(p));
        let g = primitive_root(p).unwrap();
        let n = p - 1;
        assert_eq!(order(g, p), Some(n)); // g generates the whole group

        for &secret in &[1u64, 2, 1234, 4619, 777, 3000] {
            let x = secret % n;
            let h = modpow(g, x, p); // the public value h = g^x
            let mut congruences: Vec<(u64, u64)> = Vec::new();
            for &(q, e) in factorize(n).as_slice() {
                let qe = q.pow(e);
                let exp = n / qe; // project into the order-q^e subgroup
                let gi = modpow(g, exp, p);
                let hi = modpow(h, exp, p);
                let mut xi = 0u64; // least xi in [0, q^e) with gi^xi = hi
                while modpow(gi, xi, p) != hi {
                    xi += 1;
                }
                congruences.push((xi, qe)); // x ≡ xi (mod q^e)
            }
            assert_eq!(
                crt(&congruences),
                Some(x),
                "Pohlig-Hellman recovered the wrong discrete log (x={x})",
            );
        }
    }

    /// **Pollard's kangaroo** — Pollard, 1978. The discrete log of `h = g^x` with
    /// `x` in a known interval `[0, W]`, found by a tame kangaroo laying a trail of
    /// footprints and a wild kangaroo hopping until it lands on one.
    #[test]
    fn kangaroo() {
        use std::collections::HashMap;
        let p = 1_000_003u64;
        let g = primitive_root(p).unwrap();
        let width = 4_000u64; // x in [0, W]
        let x_secret = 1_337u64 % (width + 1);
        let h = modpow(g, x_secret, p);

        let jumps: [u64; 16] = std::array::from_fn(|i| 1u64 << (i % 7));
        let jump = |elt: u64| jumps[(elt % 16) as usize];
        let mut trail: HashMap<u64, u64> = HashMap::new();
        let mut tame = modpow(g, width, p);
        let mut dt = 0u64;
        for _ in 0..3_000 {
            trail.insert(tame, dt);
            let j = jump(tame);
            tame = tame * modpow(g, j, p) % p;
            dt += j;
        }
        trail.insert(tame, dt);
        let mut wild = h;
        let mut dw = 0u64;
        let mut recovered = None;
        for _ in 0..20_000 {
            if let Some(&dtame) = trail.get(&wild) {
                recovered = Some(width + dtame - dw); // g^(x+dw)=g^(W+dtame)
                break;
            }
            let j = jump(wild);
            wild = wild * modpow(g, j, p) % p;
            dw += j;
        }
        assert_eq!(
            recovered,
            Some(x_secret),
            "kangaroo did not recover the discrete log",
        );
    }

    /// **Confinement → kangaroo** — challenge 58 (combined). Recover a bounded
    /// discrete log by first pinning `x mod (smooth part)` with Pohlig-Hellman,
    /// then finishing the small residual `t` with the kangaroo: `x = x_smooth +
    /// smooth·t`, where `t = dlog(h·g^(−x_smooth))` to base `g^smooth`.
    #[test]
    fn confinement_then_kangaroo() {
        use std::collections::HashMap;
        let smooth = 2u64 * 3 * 5 * 7 * 11; // 2310
        let qq = (1_048_576u64..1_100_000)
            .find(|&q| is_prime(q) && is_prime(smooth * q + 1))
            .unwrap();
        let p = smooth * qq + 1; // < 2^32
        let g = primitive_root(p).unwrap();
        let ord = p - 1; // = smooth · qq
        let span = 1_000u64; // the secret is bounded: x < smooth · span ≤ ord
        let secret = 723_457u64 % (smooth * span);
        let hpub = modpow(g, secret, p);

        // (1) Pohlig-Hellman on the smooth factors → x mod smooth.
        let mut congr: Vec<(u64, u64)> = Vec::new();
        for &(r, e) in factorize(smooth).as_slice() {
            let re = r.pow(e);
            let gi = modpow(g, ord / re, p);
            let hi = modpow(hpub, ord / re, p);
            let mut xi = 0u64;
            while modpow(gi, xi, p) != hi {
                xi += 1;
            }
            congr.push((xi, re));
        }
        let x_smooth = crt(&congr).unwrap();

        // (2) residual t in [0, span): kangaroo on the order-qq subgroup.
        let g_sub = modpow(g, smooth, p);
        let h_sub = hpub * modpow(g, ord - x_smooth % ord, p) % p; // = g_sub^t
        let jumps: [u64; 16] = std::array::from_fn(|i| 1u64 << (i % 8));
        let jump = |elt: u64| jumps[(elt % 16) as usize];
        let mut trail: HashMap<u64, u64> = HashMap::new();
        let mut tame = modpow(g_sub, span, p);
        let mut dt = 0u64;
        for _ in 0..8_000 {
            trail.insert(tame, dt);
            let j = jump(tame);
            tame = tame * modpow(g_sub, j, p) % p;
            dt += j;
        }
        trail.insert(tame, dt);
        let mut wild = h_sub;
        let mut dw = 0u64;
        let mut t = None;
        for _ in 0..200_000 {
            if let Some(&dtame) = trail.get(&wild) {
                t = Some(span + dtame - dw);
                break;
            }
            let j = jump(wild);
            wild = wild * modpow(g_sub, j, p) % p;
            dw += j;
        }
        let x_full = x_smooth + smooth * t.unwrap(); // x = x_smooth + smooth·t
        assert_eq!(
            x_full, secret,
            "combined confinement→kangaroo recovery failed"
        );
    }
}

/// **RSA, 1977** — the modulus root, then its attack lineage: keygen-weakness
/// factorizations (shared-prime batch GCD, Fermat close-primes), the multiplicative
/// homomorphism (blinding), the low public exponent (e=3 broadcast → Bleichenbacher
/// e=3), and one-bit decryption oracles (parity → the PKCS#1 padding oracle).
mod rsa {
    use super::Lcg;
    use coprime::number::{
        carmichael, continued_fraction, crt, gcd, iroot, isqrt, modinv, modpow, next_prime,
        random_prime,
    };

    /// **RSA** — Rivest, Shamir & Adleman, 1977. Keygen, encryption, decryption:
    /// `n = p·q`, `e` coprime to `λ(n)`, `d ≡ e⁻¹`; `m^(ed) ≡ m` (n squarefree).
    #[test]
    fn keygen_encrypt_decrypt() {
        let mut rng = Lcg(0x9E37_79B9_7F4A_7C15);
        for _ in 0..20 {
            let p = random_prime(&mut rng, 16).unwrap();
            let mut q = random_prime(&mut rng, 16).unwrap();
            while q == p {
                q = random_prime(&mut rng, 16).unwrap();
            }
            let n = p * q; // distinct 16-bit primes ⇒ n < 2^32, squarefree
            let lambda = carmichael(n).unwrap(); // λ(n) = lcm(p-1, q-1)
            let e = (3u64..lambda).find(|&e| gcd(e, lambda) == 1).unwrap();
            let d = modinv(e, lambda).unwrap();
            for m in [0u64, 1, 2, 42, 1234, n / 2, n - 1] {
                let c = modpow(m, e, n);
                assert_eq!(modpow(c, d, n), m, "RSA: decrypt∘encrypt ≠ id (m={m})");
            }
        }
    }

    /// **Unpadded-RSA recovery via blinding** — RSA homomorphism + Chaum's blinding,
    /// 1983. An oracle refusing `c` still leaks `m`: query `c' = sᵉ·c`, get `s·m`,
    /// divide by `s`.
    #[test]
    fn unpadded_blinding_recovery() {
        let mut rng = Lcg(0xACED_1983_C0FF_EE01);
        let p = random_prime(&mut rng, 16).unwrap();
        let mut q = random_prime(&mut rng, 16).unwrap();
        while q == p {
            q = random_prime(&mut rng, 16).unwrap();
        }
        let n = p * q;
        let lambda = carmichael(n).unwrap();
        let e = (3u64..lambda).find(|&e| gcd(e, lambda) == 1).unwrap();
        let d = modinv(e, lambda).unwrap();
        let decrypt = |c: u64| modpow(c, d, n); // the oracle — needs the secret d

        let m = 31_337 % n;
        let c = modpow(m, e, n);
        let s = 2u64; // blinding factor; gcd(s, n) = 1 since n is odd
        let c_blinded = modpow(s, e, n) * c % n; // sᵉ·c mod n
        let m_blinded = decrypt(c_blinded); // = s·m mod n
        let m_recovered = m_blinded * modinv(s, n).unwrap() % n; // ·s⁻¹ mod n
        assert_eq!(m_recovered, m, "blinding recovery failed");
    }

    /// **e=3 broadcast, identical plaintext** — the elementary low-exponent
    /// broadcast: the *same* `m` under `e=3` to three coprime moduli gives `m³ mod
    /// nᵢ`, and CRT reconstructs `m³` exactly (since `m³ < n₁n₂n₃`), then an integer
    /// cube root recovers `m`. This degenerate no-padding case needs no lattice
    /// work; Håstad's theorem proper (1988) handles *polynomially-related* padded
    /// messages and needs Coppersmith / lattice reduction — the Stage Two layer this
    /// crate does not have.
    #[test]
    fn hastad_broadcast_e3() {
        let mut rng = Lcg(0x4A57_AD19_8500_0001);
        let mut primes: Vec<u64> = Vec::new();
        while primes.len() < 6 {
            let pr = random_prime(&mut rng, 10).unwrap();
            if !primes.contains(&pr) {
                primes.push(pr);
            }
        }
        let n: Vec<u64> = (0..3).map(|i| primes[2 * i] * primes[2 * i + 1]).collect();
        let m = 999u64; // m < min(n_i) and m³ < ∏ n_i
        assert!(n.iter().all(|&ni| m < ni));
        let cts: Vec<(u64, u64)> = n.iter().map(|&ni| (modpow(m, 3, ni), ni)).collect();
        let m_cubed = crt(&cts).unwrap(); // = m³ exactly
        assert_eq!(iroot(m_cubed, 3), m, "e=3 broadcast recovery failed");
    }

    /// **Bleichenbacher low-exponent (e=3) forgery** — Bleichenbacher, 2006. With
    /// only the high-order structure of `s³` checked, a forger picks `s ≈ ∛target`
    /// so `s³` reproduces it. `iroot` is what makes finding `s` possible.
    #[test]
    fn bleichenbacher_e3_forgery() {
        let prefix = 0xABCDu64; // stands in for 00 01 FF…FF 00 ‖ ASN.1 ‖ Hash
        let shift = 40u32;
        let target = prefix << shift;
        let s = iroot(target, 3) + 1;
        let cube = s.checked_pow(3).unwrap();
        assert!(cube >= target);
        assert_eq!(cube >> shift, prefix, "forged s³ lost the checked prefix");
    }

    /// **RSA parity / LSB oracle** — challenge 46. An oracle on the low bit of each
    /// decryption recovers the message by binary search: `c·2^(ie)` reveals whether
    /// `2^i·m` wrapped mod `n`, halving the interval each step.
    #[test]
    fn parity_oracle() {
        let mut rng = Lcg(0x0AB1_7E46_0000_0001);
        let p = random_prime(&mut rng, 16).unwrap();
        let mut q = random_prime(&mut rng, 16).unwrap();
        while q == p {
            q = random_prime(&mut rng, 16).unwrap();
        }
        let n = p * q;
        let lambda = carmichael(n).unwrap();
        let e = (3u64..lambda).find(|&e| gcd(e, lambda) == 1).unwrap();
        let d = modinv(e, lambda).unwrap();
        let oracle = |cc: u64| modpow(cc, d, n) & 1; // low bit of the decryption

        let m = 0x12_345u64 % n;
        let c = modpow(m, e, n);
        let two_e = modpow(2, e, n);
        let mut c_cur = c;
        let (mut lo, mut hi): (u128, u128) = (0, u128::from(n));
        for _ in 0..(64 - n.leading_zeros()) {
            c_cur = c_cur * two_e % n; // decrypts to 2·(previous) mod n
            let mid = lo.midpoint(hi);
            if oracle(c_cur) == 0 {
                hi = mid; // even ⇒ no wrap ⇒ m in the lower half
            } else {
                lo = mid;
            }
        }
        let recovered = (lo.saturating_sub(2)..=hi + 2)
            .find(|&cand| modpow(cand as u64, e, n) == c)
            .unwrap();
        assert_eq!(recovered as u64, m, "parity-oracle recovery failed");
    }

    /// **Bleichenbacher PKCS#1 v1.5 padding oracle** — Bleichenbacher, 1998. An
    /// oracle revealing only PKCS conformance (`2B ≤ m < 3B`) recovers the whole
    /// message by adaptive interval narrowing. The "padding" is a high-bits check,
    /// not a hash — pure number theory.
    #[test]
    fn bleichenbacher_pkcs1_oracle() {
        let mut rng = Lcg(0xB1EC_4BAC_0000_0001);
        let p = random_prime(&mut rng, 16).unwrap();
        let mut q = random_prime(&mut rng, 16).unwrap();
        while q == p {
            q = random_prime(&mut rng, 16).unwrap();
        }
        let n = p * q; // 4-byte modulus (~2^32)
        let lambda = carmichael(n).unwrap();
        let e = (3u64..lambda).find(|&e| gcd(e, lambda) == 1).unwrap();
        let d = modinv(e, lambda).unwrap();
        let nn = u128::from(n);
        let bb = 1u128 << 16; // B = 2^(8·(k-2)) for k = 4 bytes

        let conforming = |c: u64| {
            let m = u128::from(modpow(c, d, n));
            2 * bb <= m && m < 3 * bb
        };
        let c0 = {
            let m0 = 2 * bb + 12_345; // a conforming plaintext in [2B, 3B)
            modpow(m0 as u64, e, n)
        };
        let cs = |s: u128| modpow((s % nn) as u64, e, n) * c0 % n; // c0 · s^e mod n
        let ceil = |a: u128, b: u128| a.div_ceil(b);
        let floor = |a: u128, b: u128| a / b;
        assert!(conforming(c0));

        let mut intervals: Vec<(u128, u128)> = vec![(2 * bb, 3 * bb - 1)];
        let mut s = ceil(nn, 3 * bb); // step 2a start
        while !conforming(cs(s)) {
            s += 1;
        }
        let recovered = loop {
            // step 3: narrow the interval set
            let mut next: Vec<(u128, u128)> = Vec::new();
            for &(a, b) in &intervals {
                let r_lo = ceil(a * s - (3 * bb - 1), nn);
                let r_hi = floor(b * s - 2 * bb, nn);
                let mut r = r_lo;
                while r <= r_hi {
                    let na = a.max(ceil(2 * bb + r * nn, s));
                    let nb = b.min(floor(3 * bb - 1 + r * nn, s));
                    if na <= nb {
                        next.push((na, nb));
                    }
                    r += 1;
                }
            }
            next.sort_unstable();
            let mut merged: Vec<(u128, u128)> = Vec::new();
            for (a, b) in next {
                match merged.last_mut() {
                    Some(last) if a <= last.1 + 1 => last.1 = last.1.max(b),
                    _ => merged.push((a, b)),
                }
            }
            intervals = merged;

            // step 4: done when a single point remains
            if intervals.len() == 1 && intervals[0].0 == intervals[0].1 {
                break intervals[0].0;
            }
            // step 2b / 2c: find the next multiplier s
            if intervals.len() > 1 {
                s += 1;
                while !conforming(cs(s)) {
                    s += 1;
                }
            } else {
                let (a, b) = intervals[0];
                let mut r = ceil(2 * (b * s - 2 * bb), nn);
                'search: loop {
                    let mut ss = ceil(2 * bb + r * nn, b);
                    let s_hi = floor(3 * bb - 1 + r * nn, a);
                    while ss <= s_hi {
                        if conforming(cs(ss)) {
                            s = ss;
                            break 'search;
                        }
                        ss += 1;
                    }
                    r += 1;
                }
            }
        };
        assert_eq!(
            recovered,
            2 * bb + 12_345,
            "Bleichenbacher recovered wrong m"
        );
    }

    /// **Batch-GCD shared-prime factorization** — Heninger, Durumeric, Wustrow &
    /// Halderman, "Mining Your Ps and Qs" (2012); independently Lenstra et al. the
    /// same year. When low-entropy keygen makes two RSA moduli share *one* prime, a
    /// single `gcd(n₁, n₂)` factors *both* — no other information needed. The crate
    /// is named for exactly this relation.
    #[test]
    fn batch_gcd_shared_prime() {
        let mut rng = Lcg(0x900D_5EED_C0DE_0001);
        // Five distinct 16-bit primes; `shared` is reused across two of the keys.
        let mut primes: Vec<u64> = Vec::new();
        while primes.len() < 5 {
            let pr = random_prime(&mut rng, 16).unwrap();
            if !primes.contains(&pr) {
                primes.push(pr);
            }
        }
        let shared = primes[0];
        let moduli = [
            shared * primes[1],    // n₀ ┐ share `shared`
            shared * primes[2],    // n₁ ┘
            primes[3] * primes[4], // n₂ independent
        ];

        // Pairwise GCD across the keyset: the only nontrivial gcd is the collision.
        let mut hit = None;
        for (i, &ni) in moduli.iter().enumerate() {
            for (j, &nj) in moduli.iter().enumerate().skip(i + 1) {
                let g = gcd(ni, nj);
                if g != 1 {
                    hit = Some((i, j, g));
                }
            }
        }
        let (i, j, p) = hit.expect("batch-GCD found no shared factor");
        assert_eq!((i, j), (0, 1), "shared factor surfaced in the wrong pair");
        assert_eq!(p, shared, "recovered the wrong shared prime");

        // That one gcd factors both moduli completely; the private keys follow.
        for &n in &moduli[0..2] {
            let q = n / p;
            assert_eq!(p * q, n, "p ∤ n — not a clean factorization");
            let lambda = carmichael(n).unwrap();
            let e = (3u64..lambda).find(|&e| gcd(e, lambda) == 1).unwrap();
            let d = modinv(e, lambda).unwrap();
            let m = 31_337 % n;
            assert_eq!(
                modpow(modpow(m, e, n), d, n),
                m,
                "recovered key fails to decrypt",
            );
        }
    }

    /// **Fermat factorization (close primes)** — Fermat, 17th century; the standard
    /// caution against RSA primes chosen too near each other. If `|p − q|` is small,
    /// `n = p·q = a² − b²` with `a = ⌈√n⌉` only a few steps above the root, so
    /// `isqrt` peels `n` apart without searching the key space.
    #[test]
    fn fermat_close_primes() {
        let p = next_prime(50_000).unwrap();
        let q = next_prime(p + 1).unwrap(); // q just past p ⇒ |p − q| tiny
        let n = p * q;
        let mut a = isqrt(n);
        if a * a < n {
            a += 1; // a = ⌈√n⌉
        }
        let (mut pf, mut qf) = (0u64, 0u64);
        for _ in 0..10_000 {
            let b2 = a * a - n;
            let b = isqrt(b2);
            if b * b == b2 {
                (pf, qf) = (a - b, a + b); // n = (a − b)(a + b)
                break;
            }
            a += 1;
        }
        assert_eq!(pf * qf, n, "Fermat did not factor n");
        assert_eq!(
            (pf.min(qf), pf.max(qf)),
            (p.min(q), p.max(q)),
            "Fermat recovered the wrong factors",
        );
    }

    /// **Wiener small-`d` attack** — Wiener, 1990. A *small* private exponent
    /// (`d < ⅓·N^(1/4)`) is recoverable from the public `(N, e)` alone: since
    /// `e·d = k·φ(N) + 1` and `φ(N) ≈ N`, the unknown `k/d` is one of the
    /// continued-fraction convergents of `e/N`. Walk them; for each `(t, dʹ)`
    /// reconstruct `φ = (e·dʹ − 1)/t`, hence the candidate `p + q = N − φ + 1`,
    /// and accept when `x² − (p+q)x + N` has a perfect-square discriminant —
    /// that convergent's denominator is `d`, and `N` is factored.
    #[test]
    fn wiener_small_d() {
        // RSA key with a deliberately tiny private exponent.
        let p = next_prime(12_345_678).unwrap();
        let q = next_prime(23_456_789).unwrap();
        let n = p * q; // ~2^48, so N^(1/4) ~ 4100
        let phi = (p - 1) * (q - 1);
        // a small d in the Wiener-vulnerable range, coprime to φ
        let d = (1_000u64..1_380).find(|&d| gcd(d, phi) == 1).unwrap();
        assert!(
            3 * d < iroot(n, 4),
            "d must satisfy Wiener's bound d < ⅓·N^¼"
        );
        let e = modinv(d, phi).unwrap(); // the (large) public exponent

        // The attacker knows only (n, e). Recover d from the convergents of e/N.
        let recovered = continued_fraction(e, n)
            .convergents()
            .find_map(|(t, d_guess)| {
                // φ = (e·d − 1)/t must be a positive integer with N − φ + 1 = p+q
                let ed = e.checked_mul(d_guess)?;
                if t == 0 || (ed - 1) % t != 0 {
                    return None;
                }
                let phi_guess = (ed - 1) / t;
                let s = (n + 1).checked_sub(phi_guess)?; // candidate p + q
                let disc = s.checked_mul(s)?.checked_sub(4 * n)?; // (p − q)²
                let r = isqrt(disc);
                (r * r == disc).then_some(d_guess)
            })
            .unwrap();
        assert_eq!(
            recovered, d,
            "Wiener did not recover the small private exponent"
        );
    }
}

/// **El Gamal, 1985** — Taher El Gamal's discrete-log public-key cryptosystem,
/// Diffie–Hellman turned into encryption. The round-trip, then the ephemeral-key
/// reuse that degrades it to a two-time pad: one repeated `k` lets a *known*
/// plaintext unmask an *unknown* one, with the private key never touched.
mod elgamal {
    use coprime::number::{modinv, modpow, primitive_root};

    /// **Keygen / encrypt / decrypt** — public key `h = g^x`; encrypt `m` under a
    /// fresh ephemeral `k` as `(c₁, c₂) = (g^k, m·h^k)`; decrypt by stripping the
    /// shared mask `s = c₁^x = h^k`, i.e. `m = c₂·s⁻¹`.
    #[test]
    fn keygen_encrypt_decrypt() {
        let p = 1_000_000_007u64;
        let g = primitive_root(p).unwrap();
        let x = 424_242u64 % (p - 1); // recipient's private key
        let h = modpow(g, x, p); // published public key h = g^x
        for (m, k) in [(2u64, 7u64), (123_456, 99), (p - 1, 555), (1, 1)] {
            let c1 = modpow(g, k, p); // ephemeral public g^k
            let c2 = m * modpow(h, k, p) % p; // plaintext masked by h^k
            let s = modpow(c1, x, p); // recipient recovers the mask = h^k
            let m_back = c2 * modinv(s, p).unwrap() % p;
            assert_eq!(m_back, m, "ElGamal round-trip failed (m={m} k={k})");
        }
    }

    /// **Ephemeral-key reuse** — the El Gamal analogue of DSA nonce reuse.
    /// Reusing `k` repeats the mask `s = h^k`, so `c₁` is identical across the
    /// two ciphertexts (reuse is *detectable*) and
    /// `c₂/c₂' = m/m'`. A known plaintext `m₁` then yields the secret
    /// `m₂ = m₁·c₂'·c₂⁻¹` — the private key `x` never enters.
    #[test]
    fn ephemeral_reuse_recovery() {
        let p = 1_000_000_007u64;
        let g = primitive_root(p).unwrap();
        let x = 0x00C0_FFEEu64 % (p - 1);
        let h = modpow(g, x, p);

        let k = 0x0001_2345u64 % (p - 1); // the reused ephemeral
        let (m1, m2) = (111_111u64, 987_654u64); // m1 known to the attacker; m2 secret
        let enc = |m: u64| (modpow(g, k, p), m * modpow(h, k, p) % p);
        let (c1a, c2a) = enc(m1);
        let (c1b, c2b) = enc(m2);
        assert_eq!(c1a, c1b, "reuse must leave c₁ identical — the tell");

        // attacker holds m1 and both ciphertexts: m2 = m1 · c2' · c2⁻¹
        let m2_rec = m1 * c2b % p * modinv(c2a, p).unwrap() % p;
        assert_eq!(m2_rec, m2, "ephemeral-reuse recovery failed");
    }
}

/// **DSA, 1991** — the discrete-log signature (Kravitz / NIST FIPS-186), and the
/// two classic key-recovery routes: a tampered generator, and a reused nonce
/// (whose partial-leak generalization is the HNP lattice attack — against DSA and
/// ECDSA — of Stage Two).
mod signatures {
    use super::Lcg;
    use coprime::number::{is_prime, modinv, modpow, random_prime};

    /// **Repeated-nonce key recovery** — challenge 43/44. Reusing `k` across two
    /// signatures `(r, s₁)`, `(r, s₂)` on `H₁ ≠ H₂` gives `k = (H₁−H₂)(s₁−s₂)⁻¹`,
    /// then `x = (s₁k − H₁)r⁻¹`, all mod `q`. (Famously a 2010 game-console break.)
    #[test]
    fn dsa_repeated_nonce() {
        let mut rng = Lcg(0xD5A0_2010_5037_0001);
        let q = random_prime(&mut rng, 16).unwrap(); // 16-bit subgroup order
        let p = (2u64..10_000)
            .map(|t| t * q + 1)
            .find(|&p| is_prime(p))
            .unwrap();
        let g = (2u64..p)
            .map(|h| modpow(h, (p - 1) / q, p))
            .find(|&g| g != 1)
            .unwrap();

        let x = 12_345 % q; // private key
        let k = 9_999 % q; // the reused nonce
        let r = modpow(g, k, p) % q;
        assert_ne!(r, 0);
        let kinv = modinv(k, q).unwrap();
        let sign = |h: u64| kinv * ((h + x * r % q) % q) % q; // s = k⁻¹(H + x·r)
        let (h1, h2) = (111u64, 222u64);
        let (s1, s2) = (sign(h1), sign(h2));

        let k_rec = (h1 + q - h2) % q * modinv((s1 + q - s2) % q, q).unwrap() % q;
        let x_rec = (s1 * k_rec % q + q - h1) % q * modinv(r, q).unwrap() % q;
        assert_eq!(k_rec, k, "DSA nonce not recovered");
        assert_eq!(x_rec, x, "DSA private key not recovered");
    }

    /// **`g ≡ 1` magic signature** — challenge 45. With `g = p+1 ≡ 1 (mod p)` the
    /// public key is `y = 1` and one `(r, s)` verifies for *every* message hash.
    #[test]
    fn dsa_magic_signature() {
        let mut rng = Lcg(0xD5A0_0045_1100_0001);
        let q = random_prime(&mut rng, 16).unwrap();
        let p = (2u64..10_000)
            .map(|t| t * q + 1)
            .find(|&p| is_prime(p))
            .unwrap();
        let g = 1u64; // g = p+1 ≡ 1 (mod p)
        let x = 12_345 % q;
        let y = modpow(g, x, p); // = 1
        let z = 7u64;
        let r = modpow(y, z, p) % q; // = 1
        let s = r * modinv(z, q).unwrap() % q;
        assert_ne!(s, 0);
        for &hh in &[42u64, 1_000, 999_999] {
            let w = modinv(s, q).unwrap();
            let u1 = hh % q * w % q;
            let u2 = r * w % q;
            let v = (modpow(g, u1, p) * modpow(y, u2, p) % p) % q;
            assert_eq!(v, r, "magic signature did not verify for H={hh}");
        }
    }

    /// **Weak-nonce key recovery by brute force** — challenge 43. A *single*
    /// signature whose nonce `k` was drawn from too small a range leaks the key:
    /// brute-force `k`, and for each candidate recover `x = (s·k − H)·r⁻¹ mod q`,
    /// keeping the one whose `g^x` reproduces the public key. (Distinct from the
    /// repeated-nonce route above, which is algebraic over *two* signatures and
    /// needs no search.)
    #[test]
    fn dsa_weak_nonce_bruteforce() {
        let mut rng = Lcg(0xD5A0_0043_BEEF_0001);
        let q = random_prime(&mut rng, 16).unwrap();
        let p = (2u64..10_000)
            .map(|t| t * q + 1)
            .find(|&p| is_prime(p))
            .unwrap();
        let g = (2u64..p)
            .map(|h| modpow(h, (p - 1) / q, p))
            .find(|&g| g != 1)
            .unwrap();

        let x = 31_337 % q; // private key
        let y = modpow(g, x, p); // public key
        let k = 1_009 % q; // weak nonce — small, brute-forceable range
        let r = modpow(g, k, p) % q;
        assert_ne!(r, 0);
        let hh = 8_675_309 % q; // message hash
        let s = modinv(k, q).unwrap() * ((hh + x * r % q) % q) % q; // s = k⁻¹(H + x·r)

        // attacker sees (r, s), H, and the public key — brute the small nonce
        let rinv = modinv(r, q).unwrap();
        let recovered = (1..(1u64 << 16))
            .map(|cand| (s * cand % q + q - hh % q) % q * rinv % q) // x = (s·k − H)·r⁻¹
            .find(|&x_cand| modpow(g, x_cand, p) == y)
            .unwrap();
        assert_eq!(recovered, x, "DSA weak-nonce key not recovered");
    }
}

/// **SRP, 1998** — the Secure Remote Password handshake (Wu), and the zero-key
/// bypass that logs in with no password by sending `A = 0`.
mod srp {
    use super::mix;
    use coprime::number::modpow;

    /// **Login** — challenge 36. Client and server derive the same session value
    /// from the verifier without the password crossing the wire.
    #[test]
    fn login() {
        let n = 2_147_483_647u64; // N: prime (2^31 − 1)
        let g = 2u64;
        let kk = mix(&[n, g]) % n;
        let (salt, password) = (0xBEEFu64, 0x5337u64);
        let x = mix(&[salt, password]) % n;
        let v = modpow(g, x, n); // the stored verifier v = g^x
        let (a, b) = (0x11u64, 0x22u64);
        let aa = modpow(g, a, n); // client A = g^a
        let bb = (kk * v % n + modpow(g, b, n)) % n; // server B = k·v + g^b
        let u = mix(&[aa, bb]) % n;
        // client S = (B − k·v)^(a + u·x) = g^(b·(a+ux))
        let base_c = (bb + n - kk * v % n) % n; // = g^b
        let exp_c = ((u128::from(a) + u128::from(u) * u128::from(x)) % u128::from(n - 1)) as u64;
        let s_client = modpow(base_c, exp_c, n);
        // server S = (A · v^u)^b = g^((a+ux)·b)
        let s_server = modpow(aa * modpow(v, u, n) % n, b, n);
        assert_eq!(s_client, s_server, "SRP session values disagree");
    }

    /// **Zero-key bypass** — challenge 37. A client sending `A = 0` makes the
    /// server's `S = (A·v^u)^b ≡ 0` regardless of the password, so the attacker
    /// logs in knowing the session key is `H(0)`.
    #[test]
    fn zero_key_bypass() {
        let n = 2_147_483_647u64;
        let g = 2u64;
        let kk = mix(&[n, g]) % n;
        let v = modpow(g, mix(&[0xBEEF, 0x5337]) % n, n); // server's stored verifier
        let b = 0x22u64;
        let aa = 0u64; // the attacker sends A = 0 (no password)
        let bb = (kk * v % n + modpow(g, b, n)) % n;
        let u = mix(&[aa, bb]) % n;
        let s_server = modpow(aa * modpow(v, u, n) % n, b, n); // (0·v^u)^b = 0
        assert_eq!(s_server, 0);
        assert_eq!(
            mix(&[s_server]),
            mix(&[0]),
            "attacker key = H(0) w/o password"
        );
    }

    /// **Simplified-SRP offline dictionary attack** — challenge 38. Dropping the
    /// `k·v` term so `B = g^b` decouples the server's value from the verifier: a
    /// malicious server that captured one login proof can now try passwords
    /// *offline*, because `S = (A·v^u)^b` is computable from `A`, `b`, `u` and a
    /// *guessed* verifier `v`. (Full SRP's `B = k·v + g^b` ties `B` to `v`,
    /// which is exactly what blocks this.)
    #[test]
    fn simplified_dictionary_attack() {
        let n = 2_147_483_647u64; // N = 2^31 − 1, prime
        let g = 2u64;
        let salt = 0xBEEFu64;
        let real_password = 0x6D65_696Eu64; // "mein"

        // honest client logs in to the malicious server (simplified: B = g^b)
        let xc = mix(&[salt, real_password]) % (n - 1); // password exponent x = H(salt‖pw)
        let a = 0x0246_8ACEu64 % (n - 1);
        let a_pub = modpow(g, a, n); // A = g^a
        let b = 0x33u64;
        let b_pub = modpow(g, b, n); // B = g^b — no k·v term
        let u = mix(&[a_pub, b_pub]) % n;
        // client S = B^(a + u·x) = g^(b·(a + u·x))
        let exp = ((u128::from(a) + u128::from(u) * u128::from(xc)) % u128::from(n - 1)) as u64;
        let client_proof = mix(&[modpow(b_pub, exp, n), salt]);

        // the malicious server brute-forces the password offline
        let dictionary = [
            0x7177_6572u64,
            0x6472_676Eu64,
            0x6D65_696Eu64,
            0x6C6F_7665u64,
        ];
        let cracked = dictionary.iter().copied().find(|&pw| {
            let v = modpow(g, mix(&[salt, pw]) % (n - 1), n); // verifier for the guess
            let s = modpow(a_pub * modpow(v, u, n) % n, b, n); // S = (A · v^u)^b
            mix(&[s, salt]) == client_proof
        });
        assert_eq!(
            cracked,
            Some(real_password),
            "offline dictionary attack failed"
        );
    }
}
