secret-sharing-rs 0.5.1

//! Chor, Goldwasser, Micali, Awerbuch 1985, *Verifiable Secret Sharing
//! and Achieving Simultaneity in the Presence of Faults* — the
//! original computational VSS paper.
//!
//! The faithful 1985 protocol layers probabilistic encryption and zero-
//! knowledge interaction; for a self-contained Rust library that is a
//! lot of machinery for one bibliography entry. We implement the
//! discrete-log-commitment instantiation that became the standard
//! computational VSS template (and that Feldman 1987 later sharpened):
//!
//! 1. Public parameters: a prime `p`, a prime-order subgroup of order
//!    `q | (p − 1)`, and a generator `g` of that subgroup.
//! 2. Dealer samples a degree-`(k − 1)` polynomial `f(x) = a_0 + a_1 x
//!    + … + a_{k-1} x^{k-1}` over `GF(q)` with `a_0 = s`.
//! 3. Dealer broadcasts the *commitments* `c_i = g^{a_i} mod p` for
//!    `i = 0, …, k − 1`, and sends share `(j, f(j) mod q)` privately
//!    to player `j`.
//! 4. Player `j` accepts iff
//!    `g^{f(j)} ≡ ∏_{i=0}^{k-1} c_i^{j^i}  (mod p)`.
//! 5. Reconstruction is plain Shamir over `GF(q)` once shares pass
//!    verification.
//!
//! Security claim is **computational**: the dealer cannot lie about
//! `s` without breaking discrete log in the subgroup. Per-share secrecy
//! reduces to the IND-CPA security of the share channel (which is
//! caller-supplied; this module verifies, it does not encrypt).
//!
//! Group choice. The bundled [`rfc5114_modp_2048_256`] returns the
//! IETF-standard 2048-bit MODP group with a 256-bit prime-order
//! subgroup (RFC 5114 §2.3) — the canonical Schnorr-style group for
//! this scheme and the right default for new deployments. The
//! [`small_test_group`] `(p = 23, q = 11, g = 4)` is retained for
//! the unit tests where seconds-per-test would otherwise dominate
//! every CI run; it is **insecure** and must never be reached for
//! production code.
//!
//! Secret entropy. Because the dealer broadcasts `c_0 = g^s`, a low-
//! entropy secret can be brute-forced from `c_0` directly without
//! breaking discrete log: an attacker enumerates candidate `s'`,
//! computes `g^{s'}`, and compares. This is *not* a defect of the VSS
//! reduction — it follows from Feldman's leakage of `g^s` to all
//! parties — but callers must ensure `s` is drawn from a distribution
//! with entropy comparable to `log₂ q` (e.g. the secret IS a uniform
//! field element). Encrypt-then-share an arbitrary plaintext with a
//! random key and use the *key* as `s` if the underlying datum is
//! low-entropy.

use crate::bigint::{BigUint, MontgomeryCtx};
use crate::csprng::Csprng;
use crate::field::PrimeField;
use crate::poly::{horner, lagrange_eval};
use crate::primes::{is_probable_prime, random_below};
use crate::secure::Zeroizing;

/// A Schnorr-style discrete-log group: prime `p`, subgroup order `q`
/// (also prime), generator `g` of the subgroup.
#[derive(Clone, Debug)]
pub struct DlogGroup {
    p: BigUint,
    q: BigUint,
    g: BigUint,
    /// Montgomery context for `(Z/pZ)*` — enables `pow` without paying
    /// long-division-in-the-loop costs.
    mont: MontgomeryCtx,
}

impl DlogGroup {
    /// Wrap `(p, q, g)` after fully validating the Schnorr-group
    /// relations. Checks performed:
    ///
    /// - `p ≥ 3` and odd,
    /// - `p` is prime (Miller–Rabin via [`crate::primes::is_probable_prime`]),
    /// - `1 < q < p` and `q` is prime,
    /// - `q | (p − 1)`,
    /// - `g ≠ 0, 1 mod p`,
    /// - `g^q ≡ 1 mod p` — combined with `q` prime and `g ≠ 1`, this
    ///   pins the order of `g` to exactly `q`.
    ///
    /// Returns `None` if any check fails. The Miller–Rabin test is
    /// deterministic for `p, q < ~2^81` and probabilistic with
    /// false-positive rate `≤ 4^{-12}` above that.
    #[must_use]
    pub fn new(p: BigUint, q: BigUint, g: BigUint) -> Option<Self> {
        if p < BigUint::from_u64(3) {
            return None;
        }
        if !p.is_odd() {
            return None;
        }
        if !is_probable_prime(&p) {
            return None;
        }
        if q <= BigUint::one() || q >= p {
            return None;
        }
        if !is_probable_prime(&q) {
            return None;
        }
        // q | (p − 1) — verify by exact division, not by the weaker
        // 2q ≤ p − 1 plausibility test.
        let p_minus_1 = p.sub_ref(&BigUint::one());
        let (_, rem) = p_minus_1.div_rem(&q);
        if !rem.is_zero() {
            return None;
        }
        // Reduce g mod p BEFORE the identity check — `g = p + 1`
        // is not raw-one but reduces to 1 in (Z/pZ)*; accepting it
        // would let the dealer collapse every commitment to 1, killing
        // binding. The check must therefore be against the reduced
        // representative, not the raw input.
        let g = g.modulo(&p);
        if g.is_zero() || g == BigUint::one() {
            return None;
        }
        let mont = MontgomeryCtx::new(&p)?;
        // g^q ≡ 1 mod p AND q prime AND g ≠ 1 ⇒ ord(g) = q exactly.
        let one = mont.pow(&g, &q);
        if one != BigUint::one() {
            return None;
        }
        Some(Self { p, q, g, mont })
    }

    #[must_use]
    pub fn p(&self) -> &BigUint {
        &self.p
    }

    #[must_use]
    pub fn q(&self) -> &BigUint {
        &self.q
    }

    #[must_use]
    pub fn g(&self) -> &BigUint {
        &self.g
    }

    /// `base^exp mod p` via the Montgomery context.
    #[must_use]
    pub fn pow(&self, base: &BigUint, exp: &BigUint) -> BigUint {
        self.mont.pow(base, exp)
    }

    /// Multiplication in `(Z/pZ)*`, exposed for verification arithmetic.
    #[must_use]
    pub fn mul(&self, a: &BigUint, b: &BigUint) -> BigUint {
        BigUint::mod_mul(a, b, &self.p)
    }
}

/// One trustee's share: `(player_index, f(player_index) mod q)`.
#[derive(Clone, Eq, PartialEq)]
pub struct VssShare {
    pub player: usize,
    pub value: BigUint,
}

impl core::fmt::Debug for VssShare {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        // Secret-bearing: do not print field contents.
        f.write_str("VssShare(<elided>)")
    }
}

/// Public commitment vector `c = (g^{a_0}, g^{a_1}, …, g^{a_{k-1}})`
/// broadcast by the dealer.
#[derive(Clone, Eq, PartialEq)]
pub struct Commitments {
    pub c: Vec<BigUint>,
}

impl core::fmt::Debug for Commitments {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        // Secret-bearing: do not print field contents.
        f.write_str("Commitments(<elided>)")
    }
}

/// Deal `n` Shamir shares of `secret` over `GF(q)` together with
/// Feldman commitments to the polynomial coefficients.
///
/// # Panics
/// - `k < 2`,
/// - `n < k`,
/// - `n ≥ q` (every player needs a distinct nonzero abscissa in
///   `GF(q)`).
#[must_use]
pub fn deal<R: Csprng>(
    group: &DlogGroup,
    rng: &mut R,
    secret: &BigUint,
    k: usize,
    n: usize,
) -> (Vec<VssShare>, Commitments) {
    assert!(k >= 2, "k must be at least 2");
    assert!(n >= k, "n must be at least k");
    assert!(
        BigUint::from_u64(n as u64) < *group.q(),
        "subgroup order must exceed n",
    );
    assert!(secret < group.q(), "secret must be < q");

    let q_field = PrimeField::new_unchecked(group.q().clone());
    // Polynomial f(x) = a_0 + a_1 x + … + a_{k-1} x^{k-1} over GF(q),
    // with a_0 = secret. Wrap in `Zeroizing` so the secret coefficient
    // and the random pad are volatile-zeroed on function exit.
    let mut coeffs = Zeroizing::new(Vec::<BigUint>::with_capacity(k));
    coeffs.push(secret.clone());
    for _ in 1..k {
        let v = random_below(rng, group.q()).expect("q > 0");
        coeffs.push(v);
    }
    let commitments = Commitments {
        c: coeffs.iter().map(|a| group.pow(group.g(), a)).collect(),
    };
    let shares: Vec<VssShare> = (1..=n)
        .map(|j| {
            let x = BigUint::from_u64(j as u64);
            let y = horner(&q_field, &coeffs, &x);
            VssShare {
                player: j,
                value: y,
            }
        })
        .collect();
    (shares, commitments)
}

/// Verify a single share against the dealer's commitments.
/// Returns `true` iff `g^{share.value} ≡ ∏_i c_i^{j^i} mod p` and
/// every `c_i` lies in the order-`q` subgroup (i.e. `c_i^q ≡ 1 mod p`).
/// The subgroup-membership step is necessary for the discrete-log
/// security reduction: a malicious dealer who broadcasts a `c_i`
/// outside the subgroup escapes the binding argument.
#[must_use]
pub fn verify_share(group: &DlogGroup, commits: &Commitments, share: &VssShare) -> bool {
    if share.player == 0 {
        return false;
    }
    // Player abscissa must fit in GF(q); at j ≡ 0 mod q the share lies
    // on the secret abscissa and reconstruction would alias to the
    // secret directly.
    let j_big = BigUint::from_u64(share.player as u64);
    if j_big >= *group.q() {
        return false;
    }
    // Subgroup membership: a commitment outside ⟨g⟩ escapes the
    // discrete-log binding argument, so reject before applying the
    // verification equation.
    for c_i in &commits.c {
        if c_i.is_zero() {
            return false;
        }
        if group.pow(c_i, group.q()) != BigUint::one() {
            return false;
        }
    }
    let lhs = group.pow(group.g(), &share.value);
    // RHS: ∏ c_i^{j^i}. Since the polynomial is over GF(q), the
    // exponents `j^i` are taken mod q (the subgroup order).
    let q = group.q();
    let j = BigUint::from_u64(share.player as u64);
    let mut rhs = BigUint::one();
    let mut pow_j = BigUint::one(); // j^0
    for c_i in &commits.c {
        let term = group.pow(c_i, &pow_j);
        rhs = group.mul(&rhs, &term);
        pow_j = BigUint::mod_mul(&pow_j, &j, q);
    }
    lhs == rhs
}

/// Reconstruct the secret from any `k` (or more) verified shares by
/// Lagrange interpolation in `GF(q)` evaluated at `x = 0`.
///
/// Returns `None` if fewer than `k` are supplied or `x`-coordinates
/// collide. Callers should run [`verify_share`] on every share *before*
/// invoking this — `reconstruct` does not re-check commitments.
#[must_use]
pub fn reconstruct(group: &DlogGroup, shares: &[VssShare], k: usize) -> Option<BigUint> {
    if k < 2 || shares.len() < k {
        return None;
    }
    let q_field = PrimeField::new_unchecked(group.q().clone());
    for s in shares {
        if s.player == 0 {
            return None;
        }
        // Reject players whose abscissa would alias the secret slot
        // (≡ 0 mod q) or any larger collision with another player.
        let j_big = BigUint::from_u64(s.player as u64);
        if j_big >= *group.q() {
            return None;
        }
    }
    for i in 0..shares.len() {
        for j in (i + 1)..shares.len() {
            if shares[i].player == shares[j].player {
                return None;
            }
        }
    }
    let pts: Vec<(BigUint, BigUint)> = shares
        .iter()
        .take(k)
        .map(|s| (BigUint::from_u64(s.player as u64), s.value.clone()))
        .collect();
    lagrange_eval(&q_field, &pts, &BigUint::zero())
}

/// A toy `(p = 23, q = 11, g = 4)` group used for the unit tests.
/// Insecure: discrete log is trivial here. **Do not use in production.**
#[must_use]
pub fn small_test_group() -> DlogGroup {
    DlogGroup::new(
        BigUint::from_u64(23),
        BigUint::from_u64(11),
        BigUint::from_u64(4),
    )
    .expect("hand-validated toy group")
}

/// RFC 5114 §2.3 — 2048-bit MODP group with a 256-bit prime-order
/// subgroup. Standardised Schnorr-style group; the 2048-bit `p` and
/// 256-bit `q` give roughly 112-bit symmetric-equivalent security per
/// NIST SP 800-57. The same `(p, q, g)` are used by the IETF IKE and
/// TLS profiles that pre-date RFC 7919, and remain a reasonable
/// floor for new Schnorr-VSS deployments where modular-exponent cost
/// is the budget concern. For ≥128-bit security move to a 3072/256
/// FIPS 186-4 group, an EC group, or RFC 7919 FFDHE3072 (no prime-
/// order subgroup, so unsuited to plain Feldman).
///
/// Validated through [`DlogGroup::new`] on every call — a failure
/// would mean the bundled hex constants were corrupted in transit.
#[must_use]
pub fn rfc5114_modp_2048_256() -> DlogGroup {
    // RFC 5114 §2.3, hex digits stripped of whitespace.
    const P_HEX: &str = "\
        87A8E61DB4B6663CFFBBD19C651959998CEEF608660DD0F2\
        5D2CEED4435E3B00E00DF8F1D61957D4FAF7DF4561B2AA30\
        16C3D91134096FAA3BF4296D830E9A7C209E0C6497517ABD\
        5A8A9D306BCF67ED91F9E6725B4758C022E0B1EF4275BF7B\
        6C5BFC11D45F9088B941F54EB1E59BB8BC39A0BF12307F5C\
        4FDB70C581B23F76B63ACAE1CAA6B7902D52526735488A0E\
        F13C6D9A51BFA4AB3AD8347796524D8EF6A167B5A41825D9\
        67E144E5140564251CCACB83E6B486F6B3CA3F7971506026\
        C0B857F689962856DED4010ABD0BE621C3A3960A54E710C3\
        75F26375D7014103A4B54330C198AF126116D2276E11715F\
        693877FAD7EF09CADB094AE91E1A1597";
    const Q_HEX: &str =
        "8CF83642A709A097B447997640129DA299B1A47D1EB3750BA308B0FE64F5FBD3";
    const G_HEX: &str = "\
        3FB32C9B73134D0B2E77506660EDBD484CA7B18F21EF205407F4793A1A0BA125\
        10DBC15077BE463FFF4FED4AAC0BB555BE3A6C1B0C6B47B1BC3773BF7E8C6F62\
        901228F8C28CBB18A55AE31341000A650196F931C77A57F2DDF463E5E9EC144B\
        777DE62AAAB8A8628AC376D282D6ED3864E67982428EBC831D14348F6F2F9193\
        B5045AF2767164E1DFC967C1FB3F2E55A4BD1BFFE83B9C80D052B985D182EA0A\
        DB2A3B7313D3FE14C8484B1E052588B9B7D2BBD2DF016199ECD06E1557CD0915\
        B3353BBB64E0EC377FD028370DF92B52C7891428CDC67EB6184B523D1DB246C3\
        2F63078490F00EF8D647D148D47954515E2327CFEF98C582664B4C0F6CC41659";
    DlogGroup::new(hex_to_biguint(P_HEX), hex_to_biguint(Q_HEX), hex_to_biguint(G_HEX))
        .expect("RFC 5114 §2.3 group is well-formed")
}

/// Decode a (possibly whitespace-padded) hex string to a `BigUint`.
/// Used only by the standardised-group constructors. Panics on a
/// malformed input — the constants are compile-time literals, so a
/// runtime panic would mean a transcription error to fix at the call
/// site.
fn hex_to_biguint(hex: &str) -> BigUint {
    let mut bytes = Vec::with_capacity(hex.len() / 2);
    let cleaned: Vec<u8> = hex.bytes().filter(|b| !b.is_ascii_whitespace()).collect();
    assert!(cleaned.len().is_multiple_of(2), "hex literal must have even length");
    for chunk in cleaned.chunks_exact(2) {
        let hi = nibble(chunk[0]);
        let lo = nibble(chunk[1]);
        bytes.push((hi << 4) | lo);
    }
    BigUint::from_be_bytes(&bytes)
}

fn nibble(b: u8) -> u8 {
    match b {
        b'0'..=b'9' => b - b'0',
        b'a'..=b'f' => b - b'a' + 10,
        b'A'..=b'F' => b - b'A' + 10,
        _ => panic!("non-hex character in literal: {b:#x}"),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::csprng::ChaCha20Rng;

    fn rng() -> ChaCha20Rng {
        ChaCha20Rng::from_seed(&[0xC9u8; 32])
    }

    #[test]
    fn round_trip_3_of_5() {
        let group = small_test_group();
        let mut r = rng();
        let secret = BigUint::from_u64(7); // < q = 11
        let (shares, commits) = deal(&group, &mut r, &secret, 3, 5);
        assert_eq!(shares.len(), 5);
        assert_eq!(commits.c.len(), 3);
        for s in &shares {
            assert!(verify_share(&group, &commits, s), "player {} verifies", s.player);
        }
        assert_eq!(reconstruct(&group, &shares[..3], 3), Some(secret.clone()));
        assert_eq!(reconstruct(&group, &shares[2..5], 3), Some(secret));
    }

    #[test]
    fn tampered_share_fails_verification() {
        let group = small_test_group();
        let mut r = rng();
        let secret = BigUint::from_u64(3);
        let (mut shares, commits) = deal(&group, &mut r, &secret, 3, 5);
        // +1 mod q lands on a different residue class, which is the
        // smallest perturbation that breaks the Feldman equation.
        let q = BigUint::from_u64(11);
        shares[2].value = shares[2].value.add_ref(&BigUint::one()).modulo(&q);
        assert!(!verify_share(&group, &commits, &shares[2]));
        for s in shares.iter().filter(|s| s.player != 3) {
            assert!(verify_share(&group, &commits, s));
        }
    }

    #[test]
    fn verify_rejects_oversized_player() {
        // Player abscissa j ≥ q aliases mod q (j ≡ 0 mod q lands on
        // the secret slot itself); verify_share must refuse before the
        // equation could spuriously pass.
        let group = small_test_group();
        let mut r = rng();
        let secret = BigUint::from_u64(2);
        let (_shares, commits) = deal(&group, &mut r, &secret, 3, 5);
        let bad = VssShare {
            player: 11,
            value: BigUint::zero(),
        };
        assert!(!verify_share(&group, &commits, &bad));
    }

    #[test]
    fn verify_rejects_non_subgroup_commitment() {
        // A malicious dealer can broadcast c_i outside the order-q
        // subgroup, escaping the discrete-log binding argument.
        // Verification must reject before that reduction even applies.
        let group = small_test_group();
        let mut r = rng();
        let secret = BigUint::from_u64(2);
        let (shares, mut commits) = deal(&group, &mut r, &secret, 3, 5);
        // 5 has order 22 in (Z/23)*, so it lies outside the order-11
        // subgroup that legitimate commitments must occupy.
        commits.c[0] = BigUint::from_u64(5);
        for s in &shares {
            assert!(!verify_share(&group, &commits, s));
        }
    }

    #[test]
    fn tampered_commitment_breaks_all_shares() {
        let group = small_test_group();
        let mut r = rng();
        let secret = BigUint::from_u64(5);
        let (shares, mut commits) = deal(&group, &mut r, &secret, 3, 5);
        // c_0 is the commitment to the secret coefficient; perturbing
        // it shifts the constant term of every verification equation.
        commits.c[0] = group.mul(&commits.c[0], &BigUint::from_u64(2));
        for s in &shares {
            assert!(!verify_share(&group, &commits, s));
        }
    }

    #[test]
    fn below_threshold_reconstruct_returns_none() {
        let group = small_test_group();
        let mut r = rng();
        let secret = BigUint::from_u64(8);
        let (shares, _) = deal(&group, &mut r, &secret, 3, 5);
        assert!(reconstruct(&group, &shares[..2], 3).is_none());
    }

    #[test]
    fn duplicate_player_in_reconstruct_returns_none() {
        let group = small_test_group();
        let mut r = rng();
        let secret = BigUint::from_u64(2);
        let (shares, _) = deal(&group, &mut r, &secret, 3, 5);
        let dup = vec![shares[0].clone(), shares[0].clone(), shares[1].clone()];
        assert!(reconstruct(&group, &dup, 3).is_none());
    }

    #[test]
    fn larger_group_round_trip() {
        // (p, q) = (167, 83): a Schnorr group large enough to exercise
        // multi-block exponentiation but small enough for round-trip
        // tests. g = 4 generates the order-83 subgroup (since 83 is
        // prime, any element ≠ 1 with g^q = 1 has order exactly q).
        let group = DlogGroup::new(
            BigUint::from_u64(167),
            BigUint::from_u64(83),
            BigUint::from_u64(4),
        )
        .expect("p=167, q=83 is a valid Schnorr group with g=4");
        let mut r = rng();
        let secret = BigUint::from_u64(42);
        let (shares, commits) = deal(&group, &mut r, &secret, 4, 7);
        for s in &shares {
            assert!(verify_share(&group, &commits, s));
        }
        assert_eq!(reconstruct(&group, &shares[..4], 4), Some(secret));
    }

    #[test]
    fn rejects_identity_generator_after_reduction() {
        // `g = p + 1` reduces to 1 in (Z/pZ)*. Accepting it would let
        // the dealer collapse every commitment to 1 and break Feldman
        // binding — so the identity check must run after `g mod p`.
        let bad = DlogGroup::new(
            BigUint::from_u64(23),
            BigUint::from_u64(11),
            BigUint::from_u64(24), // 24 mod 23 == 1
        );
        assert!(bad.is_none());
    }

    #[test]
    fn rejects_non_subgroup_generator() {
        // 5 generates all of (Z/23)* (order 22), so it cannot lie in
        // the order-11 subgroup; new() must reject it.
        let bad = DlogGroup::new(
            BigUint::from_u64(23),
            BigUint::from_u64(11),
            BigUint::from_u64(5),
        );
        assert!(bad.is_none());
    }

    #[test]
    fn rejects_even_modulus() {
        let bad = DlogGroup::new(
            BigUint::from_u64(22),
            BigUint::from_u64(11),
            BigUint::from_u64(4),
        );
        assert!(bad.is_none());
    }

    #[test]
    fn rejects_q_too_large() {
        // q ≥ p makes "q | p − 1" unsatisfiable (any divisor of p − 1
        // is < p), so the constructor must refuse.
        let bad = DlogGroup::new(
            BigUint::from_u64(23),
            BigUint::from_u64(23),
            BigUint::from_u64(4),
        );
        assert!(bad.is_none());
    }
}