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