1extern crate rand;
  2extern crate num;
  3extern crate num_bigint;
  4extern crate num_traits;
  5
  6use num_bigint::RandBigInt;
  7use num::pow::pow;
  8
  9
 10use num_bigint::{BigInt, ToBigInt};
 11use num_traits::{Zero, One};
 12
 13fn modulus(a: &BigInt, m: &BigInt) -> BigInt {
 14    ((a%m) + m) % m
 15}
 16
 17pub fn create(t: u32, n: u32,p: &BigInt, k: &BigInt) -> Vec<[BigInt;2]> {
 18    // t: number of secrets needed
 19    // n: number of shares
 20    // p: random point
 21    // k: secret to share
 22    if k>p {
 23        println!("\nERROR: need k<p\n");
 24    }
 25
 26    // generate base_polynomial
 27    let mut base_polynomial: Vec<BigInt> = Vec::new();
 28    base_polynomial.push(k.clone());
 29    for _ in 0..t as usize-1 {
 30        let mut rng = rand::thread_rng();
 31        let a = rng.gen_bigint(1024);
 32        base_polynomial.push(a);
 33    }
 34
 35    // calculate shares, based on the base_polynomial
 36    let mut shares: Vec<BigInt> = Vec::new();
 37    for i in 1..n+1 {
 38        let mut p_res: BigInt = Zero::zero();
 39        let mut x = 0;
 40        for pol_elem in &base_polynomial {
 41            if x==0 {
 42                p_res = p_res + pol_elem;
 43            } else {
 44                let i_pow = pow(i, x);
 45                let curr_elem = i_pow * pol_elem;
 46                p_res = p_res + curr_elem;
 47                p_res = modulus(&p_res, p);
 48            }
 49            x = x+1;
 50        }
 51        shares.push(p_res);
 52    }
 53    pack_shares(shares)
 54}
 55
 56fn pack_shares(shares: Vec<BigInt>) -> Vec<[BigInt;2]> {
 57    let mut r: Vec<[BigInt;2]> = Vec::new();
 58    for i in 0..shares.len() {
 59        let curr: [BigInt;2] = [shares[i].clone(), (i+1).to_bigint().unwrap()];
 60        r.push(curr);
 61    }
 62    r
 63}
 64
 65fn unpack_shares(s: Vec<[BigInt;2]>) -> (Vec<BigInt>, Vec<BigInt>) {
 66    let mut shares: Vec<BigInt> = Vec::new();
 67    let mut is: Vec<BigInt> = Vec::new();
 68    for i in 0..s.len() {
 69        shares.push(s[i][0].clone());
 70        is.push(s[i][1].clone());
 71    }
 72    (shares, is)
 73}
 74
 75fn mod_inverse(a: BigInt, module: BigInt) -> BigInt {
 76    // TODO search biguint impl of mod_inv
 77    let mut mn = (module.clone(), a);
 78    let mut xy: (BigInt, BigInt) = (Zero::zero(), One::one());
 79
 80    let big_zero: BigInt = Zero::zero();
 81    while mn.1 != big_zero {
 82        xy = (xy.1.clone(), xy.0 - (mn.0.clone() / mn.1.clone()) * xy.1);
 83        mn = (mn.1.clone(), modulus(&mn.0, &mn.1));
 84    }
 85
 86    while xy.0 < Zero::zero() {
 87        xy.0 += module.clone();
 88    }
 89    xy.0
 90}
 91
 92pub fn lagrange_interpolation(p: &BigInt, shares_packed: Vec<[BigInt;2]>) -> BigInt {
 93    let mut res_n: BigInt = Zero::zero();
 94    let mut res_d: BigInt = Zero::zero();
 95    let (shares, sh_i) = unpack_shares(shares_packed);
 96
 97    for i in 0..shares.len() {
 98        let mut lagrange_numerator: BigInt = One::one();
 99        let mut lagrange_denominator: BigInt = One::one();
100        for j in 0..shares.len() {
101            if shares[i] != shares[j] {
102                let curr_l_numerator = &sh_i[j];
103                let curr_l_denominator = &sh_i[j] - &sh_i[i];
104                lagrange_numerator = lagrange_numerator * curr_l_numerator;
105                lagrange_denominator = lagrange_denominator * curr_l_denominator;
106            }
107        }
108        let numerator: BigInt = &shares[i] * &lagrange_numerator;
109
110        let quo: BigInt = (&numerator / &lagrange_denominator) + (&lagrange_denominator ) % &lagrange_denominator;
111        if quo != Zero::zero() {
112            res_n = res_n + quo;
113        } else {
114            let res_n_mul_lagrange_den = res_n * &lagrange_denominator;
115            res_n = res_n_mul_lagrange_den + numerator;
116            res_d = res_d + lagrange_denominator;
117        }
118    }
119    let modinv_mul: BigInt;
120    if res_d != Zero::zero() {
121        let modinv = mod_inverse(res_d, p.clone());
122        modinv_mul = res_n * modinv;
123    } else {
124        modinv_mul = res_n;
125    }
126    let r = modulus(&modinv_mul, &p);
127    r
128}
129
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134
135    #[test]
136    fn test_create_and_lagrange_interpolation() {
137        let mut rng = rand::thread_rng();
138        let p = rng.gen_biguint(1024).to_bigint().unwrap();
139        println!("p: {:?}", p);
140        let k = BigInt::parse_bytes(b"123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", 10).unwrap();
141
142        let s = create(3, 6, &p, &k);
143        // println!("s: {:?}", s);
144
145        let mut shares_to_use: Vec<[BigInt;2]> = Vec::new();
146        shares_to_use.push(s[2].clone());
147        shares_to_use.push(s[1].clone());
148        shares_to_use.push(s[0].clone());
149        let r = lagrange_interpolation(&p, shares_to_use);
150        println!("recovered secret: {:?}", r.to_string());
151        println!("original secret: {:?}", k.to_string());
152        assert_eq!(k, r);
153    }
154}