shamir_algorithm/

lib.rs

/// # Shamir Secret Sharing Library
///
/// This library implements Shamir's Secret Sharing algorithm, allowing a secret to be split into multiple shares
/// such that a minimum number of shares are required to reconstruct the original secret.
/// The implementation uses Galois Field arithmetic over GF(256) for the polynomial operations.
///
/// # Example
///
/// ```rust
/// use shamir_algorithm::ShamirSS;
/// use std::collections::BTreeMap;
///
/// let secret = b"Hello, world!";
/// let n = 5;
/// let k = 3;
///
/// let shares = ShamirSS::split(n, k, secret.to_vec()).unwrap();
/// // Use at least k shares to reconstruct
/// let mut parts = BTreeMap::new();
/// for i in 1..=k {
///     parts.insert(i, shares[&i].clone());
/// }
/// let reconstructed = ShamirSS::join(parts).unwrap();
/// assert_eq!(reconstructed, secret);
/// ```

use std::{
    collections::{BTreeMap, HashSet},
    fmt::Debug,
};

/// Shamir Secret Sharing implementation.
/// This struct provides static methods for splitting and joining secrets using Shamir's algorithm.
#[derive(Debug, Clone)]
pub struct ShamirSS;

/// Implementation of Shamir's Secret Sharing methods.
impl ShamirSS {

    /// Splits a secret into `n` shares, requiring at least `k` shares to reconstruct the secret.
    ///
    /// The secret is treated as a sequence of bytes, and each byte is split independently using
    /// polynomial interpolation over GF(256).
    ///
    /// # Arguments
    ///
    /// * `n` - The total number of shares to generate. Must be between `k` and 255.
    /// * `k` - The minimum number of shares required to reconstruct the secret. Must be greater than 1.
    /// * `secret` - The secret data as a vector of bytes.
    ///
    /// # Returns
    ///
    /// A `Result` containing a `BTreeMap` where keys are share indices (1 to n) and values are the share data,
    /// or an error string if the parameters are invalid.
    ///
    /// # Errors
    ///
    /// Returns an error if `k <= 1`, `n < k`, or `n > 255`.
    pub fn split(n: i32, k: i32, secret: Vec<u8>) -> Result<BTreeMap<i32, Vec<u8>>, String> {
        if !(k > 1) {
            return Err("Not k > 1".to_string());
        }
        if !(n >= k) {
            return Err("Not n >= k".to_string());
        }
        if !(n <= 255) {
            return Err("Not n <= 255".to_string());
        }

        let seclen = secret.len();
        let mut values: Vec<Vec<u8>> = vec![vec![0u8; seclen]; n as usize];
        let degree = k - 1;
        for i in 0..=secret.len() - 1 {
            let p = GFC256::generate(degree, secret[i]);
            for x in 1..=n {
                let index = x - 1;
                let element = GFC256::eval(p.clone(), x as u8);
                values[index as usize][i] = element;
            }
        }
        let mut parts: BTreeMap<i32, Vec<u8>> = BTreeMap::new();
        for i in 0..=n - 1 {
            let mut tmp = vec![0u8; secret.len()];

            for ii in 0..=secret.len() - 1 {
                tmp[ii] = values[i as usize][ii as usize];
            }
            parts.insert(i + 1, tmp);
        }

        Ok(parts)
    }

    /// Reconstructs the original secret from a set of shares.
    ///
    /// At least `k` shares (where `k` is the threshold used in `split`) are required to successfully
    /// reconstruct the secret. Providing fewer shares or invalid shares will result in an error.
    ///
    /// # Arguments
    ///
    /// * `parts` - A `BTreeMap` containing share indices as keys and share data as values.
    ///   The indices should correspond to those generated by `split`.
    ///
    /// # Returns
    ///
    /// A `Result` containing the reconstructed secret as a vector of bytes, or an error string.
    ///
    /// # Errors
    ///
    /// Returns an error if no parts are provided or if the parts have inconsistent lengths.
    pub fn join(parts: BTreeMap<i32, Vec<u8>>) -> Result<Vec<u8>, String> {
        let p = parts.clone();

        if !(parts.len() > 0) {
            return Err("No parts provided".to_string());
        }
        let mut h = HashSet::new();
        for value in p.values() {
            let l = value.clone().len();
            if l != 0 {
                h.insert(l);
            }
        }
        if h.len() != 1 {
            return Err("Varying lengths of part values".to_string());
        }
        let len = h.iter().next().unwrap();
        let partslen = parts.len();
        let mut secret = vec![0u8; len.clone()];

        for i in 0..=secret.len() - 1 {
            let mut points = vec![vec![0u8; 2]; partslen as usize];
            let mut j = 0;

            let mut iter = parts.iter();

            while let Some(item) = iter.next() {
                //println!("{}", item.0);
                points[j][0] = *item.0 as u8;
                points[j][1] = item.1[i];

                j = j + 1;
            }

            secret[i] = GFC256::interpolate(points);
        }

        Ok(secret.clone())
    }
}

/// Galois Field operations over GF(256) for polynomial arithmetic in Shamir's algorithm.
struct GFC256;

/// Implementation of Galois Field arithmetic operations.
impl GFC256 {
    fn add(a: u8, b: u8) -> u8 {
        a ^ b
    }
    fn sub(a: u8, b: u8) -> u8 {
        Self::add(a, b)
    }
    fn mul(a: u8, b: u8) -> u8 {
        if a == 0 || b == 0 {
            return 0;
        }

        let exp = LOG[a as usize] as i32 + LOG[b as usize] as i32;

        EXP[exp as usize]
    }
    fn div(a: u8, b: u8) -> u8 {
        Self::mul(a, EXP[255 - LOG[b as usize] as usize])
    }

    /// Evaluates a polynomial at a given point using Horner's method.
    fn eval(p: Vec<u8>, x: u8) -> u8 {
        let mut result: u8 = 0u8;

        // Horner's method
        for i in (0..=p.len() - 1).rev() {
            let val = p[i];
            result = Self::add(Self::mul(result, x), val);
        }

        result
    }
    fn degree(p: Vec<u8>) -> i32 {
        let to = p.len() - 1;

        for i in (1..=to).rev() {
            if p[i] != 0 {
                return i as i32;
            }
        }
        return 0;
    }
    fn generate(degree: i32, x: u8) -> Vec<u8> {
        let d: i32 = degree + 1;
        let mut p: Vec<u8>;

        loop {
            p = (0..d).map(|_| rand::random::<u8>()).collect();
            let dg = Self::degree(p.clone());
            if dg == degree {
                break;
            }
        }
        p[0] = x;

        p
    }

    /// Performs Lagrange interpolation to find the y-value at x=0 given a set of points.
    fn interpolate(points: Vec<Vec<u8>>) -> u8 {
        let x: u8 = 0;
        let mut y: u8 = 0;
        let len = points.len() - 1;
        for i in 0..=len {
            let ax: u8 = points[i][0];
            let ay: u8 = points[i][1];
            let mut li: u8 = 1;
            for j in 0..=len {
                let bx = points[j][0];
                if i != j {
                    li = Self::mul(li, Self::div(Self::sub(x, bx), Self::sub(ax, bx)));
                }
            }
            let mul = Self::mul(li, ay);
            y = Self::add(y, mul);
        }
        y
    }
}

static LOG: [u8; 256] = [
    0xff, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03,
    0x64, 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1,
    0x7d, 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78,
    0x65, 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e,
    0x96, 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38,
    0x66, 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10,
    0x7e, 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba,
    0x2b, 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57,
    0xaf, 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8,
    0x2c, 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0,
    0x7f, 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7,
    0xcc, 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d,
    0x97, 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1,
    0x53, 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab,
    0x44, 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5,
    0x67, 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07,
];

static EXP: [u8; 510] = [
    0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
    0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
    0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
    0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
    0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
    0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
    0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
    0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
    0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
    0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
    0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
    0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
    0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
    0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
    0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
    0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01,
    0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35, 0x5f,
    0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa, 0xe5,
    0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31, 0x53,
    0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd, 0x4c,
    0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88, 0x83,
    0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a, 0xb5,
    0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3, 0xfe,
    0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0, 0xfb,
    0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41, 0xc3,
    0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75, 0x9f,
    0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80, 0x9b,
    0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54, 0xfc,
    0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca, 0x45,
    0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e, 0x12,
    0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17, 0x39,
    0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6,
];

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

    #[test]
    fn it_works() {
        let secret = b"Hello Shamir Shared Secret!!!!!";
        let numparts = 5;
        let miniumparts = 3;



        let keys = ShamirSS::split(numparts, miniumparts, secret.to_vec());
        assert!(keys.is_ok());
        let keys = keys.unwrap();
        let mut parts:BTreeMap<i32,Vec<u8>>=BTreeMap::new();
        for (key, value) in &keys {
            // Copy only entries with keys less than or equal to 3
            if *key <= miniumparts {
                parts.insert(*key, value.clone());
            }
        }
        let nshared = ShamirSS::join(parts);
        assert!(nshared.is_ok());
        let shared = nshared.unwrap();
        assert_eq!(shared, secret.to_vec());

    }
}