qualia_client_core/
shamir_recovery.rs

1//! **Shamir Secret Sharing over GF(2⁸)** — the primitive for *social recovery* of a key without the owner.
2//!
3//! A secret (e.g. a payload's data-encryption key, or a recovery key) is split into `n` shares such that any
4//! `k` of them reconstruct it and any `k-1` reveal **nothing** (information-theoretic). The shares are handed
5//! to chosen friends/trustees; after death or incapacity, a quorum of `k` of them combine their shares and
6//! recover the key — **the owner's key is never needed** (this is what the dead-man / incapacity switches
7//! need for true friend-side enactment, which key-release-on-enact could not do while it depended on the
8//! owner's derived key).
9//!
10//! This is not a cipher and not a simulation: it is the standard Shamir scheme — a degree-`(k-1)` polynomial
11//! per secret byte over the AES field GF(2⁸) (modulus `x⁸+x⁴+x³+x+1` = `0x11b`), evaluated at `x = 1..=n` for
12//! the shares and Lagrange-interpolated at `x = 0` to recover the constant term (the secret byte). Field
13//! multiplication uses carry-less multiply with reduction; the inverse is `a^254` (Fermat in GF(2⁸)). Fully
14//! deterministic and testable.
15
16use serde::{Deserialize, Serialize};
17
18/// GF(2⁸) multiplication (AES field, modulus `0x11b`).
19fn gf_mul(mut a: u8, mut b: u8) -> u8 {
20    let mut p = 0u8;
21    for _ in 0..8 {
22        if b & 1 != 0 {
23            p ^= a;
24        }
25        let hi = a & 0x80;
26        a <<= 1;
27        if hi != 0 {
28            a ^= 0x1b; // reduce by the low bits of 0x11b (the x⁸ term is the shifted-out bit)
29        }
30        b >>= 1;
31    }
32    p
33}
34
35/// GF(2⁸) multiplicative inverse via Fermat: `a^(2⁸-2) = a^254 = a⁻¹` (for `a != 0`). `inv(0)` is defined as
36/// `0` (never used — division only ever divides by a nonzero `x_i ^ x_j`).
37fn gf_inv(a: u8) -> u8 {
38    if a == 0 {
39        return 0;
40    }
41    let mut result = 1u8;
42    let mut base = a;
43    let mut exp = 254u32;
44    while exp > 0 {
45        if exp & 1 == 1 {
46            result = gf_mul(result, base);
47        }
48        base = gf_mul(base, base);
49        exp >>= 1;
50    }
51    result
52}
53
54fn gf_div(a: u8, b: u8) -> u8 {
55    gf_mul(a, gf_inv(b))
56}
57
58/// A single Shamir share: the evaluation point `x` (`1..=n`, distinct, nonzero) and the per-byte evaluations.
59#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
60pub struct Share {
61    /// The evaluation abscissa (never 0 — 0 is the secret).
62    pub x: u8,
63    /// One field evaluation per secret byte.
64    pub y: Vec<u8>,
65}
66
67/// A random field element (four is overkill for one byte, but keep it simple — one draw per coefficient).
68fn random_byte() -> u8 {
69    rand::random::<u8>()
70}
71
72/// **Split** `secret` into `n` shares, any `k` of which reconstruct it. `k` in `1..=n`, `n` in `1..=255`.
73/// Each secret byte gets an independent random degree-`(k-1)` polynomial with that byte as the constant term.
74pub fn split(secret: &[u8], k: usize, n: usize) -> Result<Vec<Share>, String> {
75    if k == 0 || n == 0 {
76        return Err("k and n must be >= 1".into());
77    }
78    if k > n {
79        return Err(format!("threshold k={k} cannot exceed shares n={n}"));
80    }
81    if n > 255 {
82        return Err("n must be <= 255 (distinct nonzero abscissae in GF(2^8))".into());
83    }
84    // Per-byte coefficients: coeff[byte][0] = secret byte; coeff[byte][1..k] = random.
85    let coeffs: Vec<Vec<u8>> = secret
86        .iter()
87        .map(|&s| {
88            let mut c = Vec::with_capacity(k);
89            c.push(s);
90            for _ in 1..k {
91                c.push(random_byte());
92            }
93            c
94        })
95        .collect();
96
97    let mut shares = Vec::with_capacity(n);
98    for x in 1..=(n as u8) {
99        let y: Vec<u8> = coeffs.iter().map(|c| eval_poly(c, x)).collect();
100        shares.push(Share { x, y });
101    }
102    Ok(shares)
103}
104
105/// Evaluate a polynomial (Horner) at `x` in GF(2⁸).
106fn eval_poly(coeffs: &[u8], x: u8) -> u8 {
107    let mut acc = 0u8;
108    for &c in coeffs.iter().rev() {
109        acc = gf_mul(acc, x) ^ c;
110    }
111    acc
112}
113
114/// **Reconstruct** the secret from a set of shares via Lagrange interpolation at `x = 0`. Requires at least
115/// the original `k` shares (fewer under-determines the polynomial and yields a wrong secret); all shares must
116/// have equal-length `y` and distinct `x`. Providing more than `k` is fine (consistent, overdetermined).
117pub fn reconstruct(shares: &[Share]) -> Result<Vec<u8>, String> {
118    if shares.is_empty() {
119        return Err("no shares".into());
120    }
121    let len = shares[0].y.len();
122    if shares.iter().any(|s| s.y.len() != len) {
123        return Err("shares have differing secret lengths".into());
124    }
125    // Distinct abscissae check.
126    for i in 0..shares.len() {
127        if shares[i].x == 0 {
128            return Err("share abscissa 0 is invalid".into());
129        }
130        for j in (i + 1)..shares.len() {
131            if shares[i].x == shares[j].x {
132                return Err("duplicate share abscissa".into());
133            }
134        }
135    }
136
137    let mut secret = vec![0u8; len];
138    for byte in 0..len {
139        let mut acc = 0u8;
140        for i in 0..shares.len() {
141            // Lagrange basis L_i(0) = prod_{j!=i} (0 - x_j) / (x_i - x_j) = prod x_j / (x_i ^ x_j).
142            let xi = shares[i].x;
143            let mut num = 1u8;
144            let mut den = 1u8;
145            for j in 0..shares.len() {
146                if i == j {
147                    continue;
148                }
149                let xj = shares[j].x;
150                num = gf_mul(num, xj);
151                den = gf_mul(den, xi ^ xj);
152            }
153            let l0 = gf_div(num, den);
154            acc ^= gf_mul(shares[i].y[byte], l0);
155        }
156        secret[byte] = acc;
157    }
158    Ok(secret)
159}
160
161#[cfg(test)]
162mod tests {
163    use super::*;
164
165    #[test]
166    fn gf_field_axioms() {
167        // 1 is the identity; every nonzero element has an inverse; multiplication is associative-ish spot check.
168        for a in 1u8..=255 {
169            assert_eq!(gf_mul(a, 1), a);
170            assert_eq!(gf_mul(a, gf_inv(a)), 1, "a * a^-1 == 1 for a={a}");
171        }
172        assert_eq!(gf_mul(0, 5), 0);
173        // Distributivity spot-check: a*(b^c) == a*b ^ a*c.
174        assert_eq!(gf_mul(7, 9 ^ 13), gf_mul(7, 9) ^ gf_mul(7, 13));
175    }
176
177    #[test]
178    fn any_k_of_n_reconstructs_the_secret() {
179        let secret = b"a 32-byte data-encryption key!!!".to_vec();
180        let shares = split(&secret, 3, 5).unwrap();
181        assert_eq!(shares.len(), 5);
182        // Several distinct 3-subsets all recover the exact secret.
183        for subset in [[0usize, 1, 2], [0, 2, 4], [1, 3, 4], [2, 3, 4]] {
184            let chosen: Vec<Share> = subset.iter().map(|&i| shares[i].clone()).collect();
185            assert_eq!(
186                reconstruct(&chosen).unwrap(),
187                secret,
188                "subset {subset:?} recovers"
189            );
190        }
191        // More than k (all 5) also recovers.
192        assert_eq!(reconstruct(&shares).unwrap(), secret);
193    }
194
195    #[test]
196    fn fewer_than_k_shares_do_not_recover_the_secret() {
197        let secret = b"top secret payload key".to_vec();
198        let shares = split(&secret, 3, 5).unwrap();
199        // With only 2 of the 3 required shares, the interpolated value is not the secret.
200        let two: Vec<Share> = vec![shares[0].clone(), shares[1].clone()];
201        assert_ne!(
202            reconstruct(&two).unwrap(),
203            secret,
204            "k-1 shares must not reveal the secret"
205        );
206    }
207
208    #[test]
209    fn threshold_equals_n_and_threshold_one() {
210        let secret = b"edge".to_vec();
211        // k == n: every share needed.
212        let all = split(&secret, 4, 4).unwrap();
213        assert_eq!(reconstruct(&all).unwrap(), secret);
214        assert_ne!(reconstruct(&all[..3]).unwrap(), secret);
215        // k == 1: any single share is the secret (degree-0 polynomial).
216        let ones = split(&secret, 1, 3).unwrap();
217        assert_eq!(reconstruct(&ones[1..2]).unwrap(), secret);
218    }
219
220    #[test]
221    fn bad_parameters_are_rejected() {
222        assert!(split(b"x", 0, 3).is_err());
223        assert!(split(b"x", 4, 3).is_err(), "k > n");
224        assert!(split(b"x", 1, 300).is_err(), "n > 255");
225        assert!(reconstruct(&[]).is_err());
226        let s = split(b"xy", 2, 3).unwrap();
227        // Duplicate abscissa rejected.
228        let dup = vec![s[0].clone(), s[0].clone()];
229        assert!(reconstruct(&dup).is_err());
230    }
231
232    #[test]
233    fn serde_round_trips() {
234        let shares = split(b"round trip", 2, 3).unwrap();
235        let json = serde_json::to_string(&shares).unwrap();
236        let back: Vec<Share> = serde_json::from_str(&json).unwrap();
237        assert_eq!(shares, back);
238        assert_eq!(reconstruct(&back[..2]).unwrap(), b"round trip");
239    }
240}
qualia_client_core/shamir_recovery.rs

qualia_client_core/
shamir_recovery.rs
