nx_vault_shamir.nx source

1// nx_vault_shamir.nx -- sovereign SHAMIR threshold secret sharing (HashiCorp Vault "Shamir seal/unseal" gap 2// from vault_capability_census.tsv) -- the iconic multi-operator unseal: split a master key into N shares; 3// ANY K reconstruct it; K-1 shares reveal a WRONG value (no quorum -> no unseal). Real finite-field math 4// over GF(p), p = 2^31-1 (Mersenne prime): products of two field elements stay < 2^62 so they fit i64 with 5// no overflow. Shares = poly(1..N); reconstruct = Lagrange interpolation at x=0. license_tier: ORIGINAL 6import "nx_syscalls.nx" 7 8const SH_P: i64 = 2147483647 // 2^31 - 1 (Mersenne prime); secrets must be < SH_P 9 10func sh_mod(x: i64) -> i64 { var r: i64 = x % SH_P; if r < 0 { r = r + SH_P } return r } 11func sh_add(a: i64, b: i64) -> i64 { return sh_mod(a + b) } 12func sh_sub(a: i64, b: i64) -> i64 { return sh_mod(a - b) } 13func sh_mul(a: i64, b: i64) -> i64 { return sh_mod(a * b) } // a,b < 2^31 -> a*b < 2^62, fits i64 14 15// modular inverse via extended Euclid (a^{-1} mod p). 16func sh_inv(a: i64) -> i64 { 17 var t: i64 = 0 18 var newt: i64 = 1 19 var r: i64 = SH_P 20 var newr: i64 = sh_mod(a) 21 while newr != 0 { 22 let q: i64 = r / newr 23 let t2: i64 = t - q * newt 24 t = newt; newt = t2 25 let r2: i64 = r - q * newr 26 r = newr; newr = r2 27 } 28 if t < 0 { t = t + SH_P } 29 return t 30} 31 32// evaluate the share polynomial at x (Horner). coeffs[0]=secret, coeffs[1..k-1]=random; degree k-1. 33func sh_eval(coeffs: *i64, k: i64, x: i64) -> i64 { 34 var acc: i64 = 0 35 var i: i64 = k - 1 36 while i >= 0 { acc = sh_add(sh_mul(acc, x), coeffs[i]); i = i - 1 } 37 return acc 38} 39 40// reconstruct the secret = poly(0) from k shares (xs[],ys[]) via Lagrange interpolation at x=0. 41func sh_reconstruct(xs: *i64, ys: *i64, k: i64) -> i64 { 42 var secret: i64 = 0 43 var j: i64 = 0 44 while j < k { 45 var num: i64 = 1 46 var den: i64 = 1 47 var m: i64 = 0 48 while m < k { 49 if m != j { 50 num = sh_mul(num, sh_sub(0, xs[m])) // (0 - x_m) 51 den = sh_mul(den, sh_sub(xs[j], xs[m])) // (x_j - x_m) 52 } 53 m = m + 1 54 } 55 let basis: i64 = sh_mul(num, sh_inv(den)) 56 secret = sh_add(secret, sh_mul(ys[j], basis)) 57 j = j + 1 58 } 59 return secret 60}