shamirsecretsharing/shamirsecretsharing-rs/src/lib.rs
shamirsecretsharing-rs/src/lib.rsRaw
1extern crate rand;
2extern crate num;
3extern crate num_bigint;
4extern crate num_traits;
5
6use std::str::FromStr;
7
8use num_bigint::RandBigInt;
9use num::pow::pow;
10use num::Integer;
11
12
13use num_bigint::{BigInt, ToBigInt};
14use num_traits::{Zero, One};
15
16fn modulus(a: &BigInt, m: &BigInt) -> BigInt {
17 ((a%m) + m) % m
18}
19
20pub fn create(t: u32, n: u32,p: &BigInt, k: &BigInt) -> Vec<[BigInt;2]> {
21 // t: number of secrets needed
22 // n: number of shares
23 // p: random point
24 // k: secret to share
25 if k>p {
26 println!("\nERROR: need k<p\n");
27 }
28
29 // generate base_polynomial
30 let mut base_polynomial: Vec<BigInt> = Vec::new();
31 base_polynomial.push(k.clone());
32 for _ in 0..t as usize-1 {
33 let mut rng = rand::thread_rng();
34 let a = rng.gen_bigint(1024);
35 base_polynomial.push(a);
36 }
37
38 // calculate shares, based on the base_polynomial
39 let mut shares: Vec<BigInt> = Vec::new();
40 for i in 1..n+1 {
41 let mut p_res: BigInt = Zero::zero();
42 let mut x = 0;
43 for pol_elem in &base_polynomial {
44 if x==0 {
45 p_res = p_res + pol_elem;
46 } else {
47 let i_pow = pow(i, x);
48 let curr_elem = i_pow * pol_elem;
49 p_res = p_res + curr_elem;
50 p_res = modulus(&p_res, p);
51 }
52 x = x+1;
53 }
54 shares.push(p_res);
55 }
56 pack_shares(shares)
57}
58
59fn pack_shares(shares: Vec<BigInt>) -> Vec<[BigInt;2]> {
60 let mut r: Vec<[BigInt;2]> = Vec::new();
61 for i in 0..shares.len() {
62 let curr: [BigInt;2] = [shares[i].clone(), (i+1).to_bigint().unwrap()];
63 r.push(curr);
64 }
65 r
66}
67
68fn unpack_shares(s: Vec<[BigInt;2]>) -> (Vec<BigInt>, Vec<BigInt>) {
69 let mut shares: Vec<BigInt> = Vec::new();
70 let mut is: Vec<BigInt> = Vec::new();
71 for i in 0..s.len() {
72 shares.push(s[i][0].clone());
73 is.push(s[i][1].clone());
74 }
75 (shares, is)
76}
77
78fn mod_inverse(a: BigInt, module: BigInt) -> BigInt {
79 // TODO search biguint impl of mod_inv
80 let mut mn = (module.clone(), a);
81 let mut xy: (BigInt, BigInt) = (Zero::zero(), One::one());
82
83 let big_zero: BigInt = Zero::zero();
84 while mn.1 != big_zero {
85 xy = (xy.1.clone(), xy.0 - (mn.0.clone() / mn.1.clone()) * xy.1);
86 mn = (mn.1.clone(), modulus(&mn.0, &mn.1));
87 }
88
89 while xy.0 < Zero::zero() {
90 xy.0 += module.clone();
91 }
92 xy.0
93}
94
95/// Compute `a^-1 (mod l)` using the the Kalinski implementation
96/// of the Montgomery Modular Inverse algorithm.
97/// B. S. Kaliski Jr. - The Montgomery inverse and its applica-tions.
98/// IEEE Transactions on Computers, 44(8):1064–1065, August-1995
99pub fn kalinski_inv(a: &BigInt, modulo: &BigInt) -> BigInt {
100 // This Phase I indeed is the Binary GCD algorithm , a version o Stein's algorithm
101 // which tries to remove the expensive division operation away from the Classical
102 // Euclidean GDC algorithm replacing it for Bit-shifting, subtraction and comparaison.
103 //
104 // Output = `a^(-1) * 2^k (mod l)` where `k = log2(modulo) == Number of bits`.
105 //
106 // Stein, J.: Computational problems associated with Racah algebra.J. Comput. Phys.1, 397–405 (1967).
107 let phase1 = |a: &BigInt| -> (BigInt, u64) {
108 assert!(a != &BigInt::zero());
109 let p = modulo;
110 let mut u = modulo.clone();
111 let mut v = a.clone();
112 let mut r = BigInt::zero();
113 let mut s = BigInt::one();
114 let two = BigInt::from(2u64);
115 let mut k = 0u64;
116
117 while v > BigInt::zero() {
118 match(u.is_even(), v.is_even(), u > v, v >= u) {
119 // u is even
120 (true, _, _, _) => {
121
122 u = u >> 1;
123 s = &s * &two;
124 },
125 // u isn't even but v is even
126 (false, true, _, _) => {
127
128 v = v >> 1;
129 r = &r * &two;
130 },
131 // u and v aren't even and u > v
132 (false, false, true, _) => {
133
134 u = &u - &v;
135 u = u >> 1;
136 r = &r + &s;
137 s = &s * &two;
138 },
139 // u and v aren't even and v > u
140 (false, false, false, true) => {
141
142 v = &v - &u;
143 v = v >> 1;
144 s = &r + &s;
145 r = &r * &two;
146 },
147 (false, false, false, false) => panic!("Unexpected error has ocurred."),
148 }
149 k += 1;
150 }
151 if &r > p {
152 r = &r - p;
153 }
154 ((p - &r), k)
155 };
156
157 // Phase II performs some adjustments to obtain
158 // the Montgomery inverse.
159 //
160 // We implement it as a clousure to be able to grap the
161 // kalinski_inv scope to get `modulo` variable.
162 let phase2 = |r: &BigInt, k: &u64| -> BigInt {
163 let mut rr = r.clone();
164 let _p = modulo;
165
166 for _i in 0..(k - modulo.bits() as u64) {
167 match rr.is_even() {
168 true => {
169 rr = rr >> 1;
170 },
171 false => {
172 rr = (rr + modulo) >> 1;
173 }
174 }
175 }
176 rr
177 };
178
179 let (r, z) = phase1(&a.clone());
180
181 phase2(&r, &z)
182}
183
184pub fn lagrange_interpolation(p: &BigInt, shares_packed: Vec<[BigInt;2]>) -> BigInt {
185 let mut res_n: BigInt = Zero::zero();
186 let mut res_d: BigInt = Zero::zero();
187 let (shares, sh_i) = unpack_shares(shares_packed);
188
189 for i in 0..shares.len() {
190 let mut lagrange_numerator: BigInt = One::one();
191 let mut lagrange_denominator: BigInt = One::one();
192 for j in 0..shares.len() {
193 if shares[i] != shares[j] {
194 let curr_l_numerator = &sh_i[j];
195 let curr_l_denominator = &sh_i[j] - &sh_i[i];
196 lagrange_numerator = lagrange_numerator * curr_l_numerator;
197 lagrange_denominator = lagrange_denominator * curr_l_denominator;
198 }
199 }
200 let numerator: BigInt = &shares[i] * &lagrange_numerator;
201
202 let quo: BigInt = (&numerator / &lagrange_denominator) + (&lagrange_denominator ) % &lagrange_denominator;
203 if quo != Zero::zero() {
204 res_n = res_n + quo;
205 } else {
206 let res_n_mul_lagrange_den = res_n * &lagrange_denominator;
207 res_n = res_n_mul_lagrange_den + numerator;
208 res_d = res_d + lagrange_denominator;
209 }
210 }
211 let modinv_mul: BigInt;
212 if res_d != Zero::zero() {
213 let modinv = mod_inverse(res_d, p.clone());
214 modinv_mul = res_n * modinv;
215 } else {
216 modinv_mul = res_n;
217 }
218 let r = modulus(&modinv_mul, &p);
219 r
220}
221
222
223#[cfg(test)]
224mod tests {
225 use super::*;
226 use std::str::FromStr;
227
228 #[test]
229 fn test_create_and_lagrange_interpolation() {
230 let mut rng = rand::thread_rng();
231 let p = rng.gen_biguint(1024).to_bigint().unwrap();
232 println!("p: {:?}", p);
233 let k = BigInt::parse_bytes(b"123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890", 10).unwrap();
234
235 let s = create(3, 6, &p, &k);
236 // println!("s: {:?}", s);
237
238 let mut shares_to_use: Vec<[BigInt;2]> = Vec::new();
239 shares_to_use.push(s[2].clone());
240 shares_to_use.push(s[1].clone());
241 shares_to_use.push(s[0].clone());
242 let r = lagrange_interpolation(&p, shares_to_use);
243 println!("recovered secret: {:?}", r.to_string());
244 println!("original secret: {:?}", k.to_string());
245 assert_eq!(k, r);
246 }
247
248 #[test]
249 fn kalinski_modular_inverse() {
250 let modul1 = BigInt::from(127u64);
251
252 let a = BigInt::from(79u64);
253 let res1 = kalinski_inv(&a, &modul1);
254 let expected1 = BigInt::from(82u64);
255 assert_eq!(res1, expected1);
256
257 let b = BigInt::from(50u64);
258 let res2 = kalinski_inv(&b, &modul1);
259 let expected2 = BigInt::from(94u64);
260 assert_eq!(res2, expected2);
261
262 // Big numbers testing.
263 // C = 19.
264 // modul2 = 2^255 - 19.
265 let modul2 = BigInt::from_str("57896044618658097711785492504343953926634992332820282019728792003956564819949").unwrap();
266 let c = BigInt::from_str("19").unwrap();
267 let res3 = kalinski_inv(&c, &modul2);
268 let expected3 = BigInt::from_str("1").unwrap();
269 assert_eq!(res3, expected3);
270
271 /*// D = 182687704666362864775460604089535377456991567872.
272 // modul3 = 2^252 + 27742317777372353535851937790883648493.
273 let modul3 = BigInt::from_str("7237005577332262213973186563042994240857116359379907606001950938285454250989").unwrap();
274 let d = BigInt::from_str("182687704666362864775460604089535377456991567872").unwrap();
275 let res4 = kalinski_inv(&d, &modul3);
276 println!("RES ON IMPL: {}", res4);
277 let expected4 = BigInt::from_str("7155219595916845557842258654134856828180378438239419449390401977965479867845").unwrap();
278 assert_eq!(expected4, res4);*/
279 }
280}