I stumbled over this youtube video, Secret Sharing Explained Visually which links to this paper, How to Share a Secret (PDF) written by Adi Shamir.
The paper is going through a method for dividing a secret into n pieces in such a way that the secret can be easily reconstructed from any k pieces, while having complete knowledge of k-1 pieces reveals absolutely no information about the secret. Such a scheme is called a (k, n) threshold scheme.
Example: There are eight person, therefore the secret is divided into eight (n) pieces. For this secret it is decided that it will be enough if only three (k) persons (with their pieces) comes together to reproduce the complete secret. This would mean that two (k-1) persons would not be enough to gain any knowledge about the secret.
This technique is aimed at enabling the construction of robust key management schemes for cryptographic systems, allowing for secure sharing and storage of sensitive information.
Let see if we can express this algorithm in a F# script (based on this Python code). For purposes of keeping the code clearer, a prime field is used in the referenced Python code example. We start to define the main function to illustrate the helicopter view of what we want to do in our shamir.fsx script file.
let main () = // Pick a prime which is bigger than both the secret and n (12th Mersenne Prime). let prime = BigInteger.Pow(2I, 127) - 1I // The secret to share which is (or can be made) a number let secret = 1234I // Minimum number of pieces needed to recreate the secret let k = 3 // Total number of pieces to divide the secret in let n = 6 let pieces = splitSecretIntoPieces secret k n prime printfn "The secret is %A" secret printfn "Pieces:" pieces |> List.iter (fun (x, y) -> printfn "%A" (x, y)) let recoveredSecret = recoverSecret (pieces |> List.take 3) prime printfn "Recovered secret with 3 pieces: %A" recoveredSecret let recoveredSecretOnceMore = recoverSecret (pieces |> List.skip 3) prime printfn "Recovered secret with another set of 3 pieces: %A" recoveredSecretOnceMore main () The scheme of Shamir Secret Share (SSS) is based on polynomial interpolation. Therefore we need to be able to generate a random k-1 degree polynomial.
Where y on the point (0, y) equals the secret and points on the polynomial are pieces needed to recreate the secret.
The next code snippet is the random generator that we need, it has to be able to generate a number between 0 and less than the prime.
// Generate a random big integer in the range [0, prime) let randomBigInteger (prime: BigInteger) : BigInteger = let rnd = System.Random() let bytes = prime.ToByteArray() // Generate random bytes rnd.NextBytes(bytes) // Ensure the number is in the range [0, prime) BigInteger.Abs(new BigInteger(bytes)) % prime With that in place we can create the function splitSecretIntoPieces, which generates the points (pieces).
// Evaluates polynomial at x, used to generate a shamir pool let evaluatePolynomial (coefficients: BigInteger list) (x: BigInteger) (prime: BigInteger) : BigInteger = List.foldBack (fun c acc -> (acc * x + c) % prime) coefficients 0I // Create random pieces for the secret let splitSecretIntoPieces (secret: BigInteger) (k: int) (n: int) (prime: BigInteger) = if k > n then failwith "Pool secret would be irrecoverable." // Generate random coefficients for the polynomial let coefficients = secret :: [for _ in 1 .. k - 1 -> randomBigInteger prime] // Evaluate the polynomial for each piece and return a list of points [for x in 1 .. n -> (BigInteger(x), evaluatePolynomial coefficients (BigInteger(x)) prime)] Now we are halfway through, we have divided the secret in n pieces. Time to implement the process to combine k pieces to get the original secret value. The lagrange interpolation algorithm is used for this, however to implement that we will first need to build some building blocks, canonical modulo operation, extended GCD and modular division.
// Canonical modulo operation let (%%) a b = let c = a % b if (c < 0I && b > 0I) || (c > 0I && b < 0I) then c + b else c // Extended GCD algorithm let rec extendedGCD a b = let rec extendedGCD' a b x x' y y' = match b with | b' when b' = 0I -> x', y' | _ -> let quot = a / b extendedGCD' b (a %% b) (x' - quot * x) x (y' - quot * y) y extendedGCD' a b 0I 1I 1I 0I // Modular division (num / den) % p let modularDivision num den p = let (inv, _) = extendedGCD den p (num * inv) Next step is to implement the algorithm for Lagrange's Interpolation. As you can see it got pretty messy, but it works though.
// Find the y-value for the given x, given n (x, y) points; // k points will define a polynomial of up to kth order let lagrangeInterpolate x (pieces : (BigInteger * BigInteger) list) prime = let indexes = [0..pieces.Length-1] let calculateNum k = indexes |> List.map (fun j -> if k <> j then x - fst pieces.[j] else 1I) |> List.fold (*) 1I let calculateDen k = indexes |> List.map (fun j -> if k <> j then fst pieces.[k] - fst pieces.[j] else 1I) |> List.fold (*) 1I let nums = indexes |> List.map calculateNum let dens = indexes |> List.map calculateDen let den = List.fold (*) 1I dens let calculateTerm i = modularDivision ((nums.[i] * den * (snd pieces.[i])) %% prime) dens.[i] prime let num = indexes |> List.map calculateTerm |> List.fold (+) 0I (modularDivision num den prime) %% prime Finally we can create the last function, recoverSecret, which is very simple in it's nature.
// Recover the secret from pieces let recoverSecret (pieces: (BigInteger * BigInteger) list) (prime: BigInteger) : BigInteger = if List.length pieces < 3 then failwith "Need at least three pieces" lagrangeInterpolate 0I pieces prime Now we have everything in place and can run the script.
As you can see, it would be very hard to say anything about the secret if you just saw one piece.
The complete script looks like this in my shamir.fsx file.
open System open System.Numerics // Generate a random big integer in the range [0, prime) let randomBigInteger (prime: BigInteger) : BigInteger = let rnd = System.Random() let bytes = prime.ToByteArray() // Generate random bytes rnd.NextBytes(bytes) // Ensure the number is in the range [0, prime) BigInteger.Abs(new BigInteger(bytes)) % prime // Evaluates polynomial at x, used to generate a shamir pool let evaluatePolynomial (coefficients: BigInteger list) (x: BigInteger) (prime: BigInteger) : BigInteger = List.foldBack (fun c acc -> (acc * x + c) % prime) coefficients 0I // Create random pieces for the secret let splitSecretIntoPieces (secret: BigInteger) (k: int) (n: int) (prime: BigInteger) = if k > n then failwith "Pool secret would be irrecoverable." // Generate random coefficients for the polynomial let coefficients = secret :: [for _ in 1 .. k - 1 -> randomBigInteger prime] // Evaluate the polynomial for each piece and return a list of points [for x in 1 .. n -> (BigInteger(x), evaluatePolynomial coefficients (BigInteger(x)) prime)] // Canonical modulo operation let (%%) a b = let c = a % b if (c < 0I && b > 0I) || (c > 0I && b < 0I) then c + b else c // Extended GCD algorithm let rec extendedGCD a b = let rec extendedGCD' a b x x' y y' = match b with | b' when b' = 0I -> x', y' | _ -> let quot = a / b extendedGCD' b (a %% b) (x' - quot * x) x (y' - quot * y) y extendedGCD' a b 0I 1I 1I 0I // Modular division (num / den) % p let modularDivision num den p = let (inv, _) = extendedGCD den p (num * inv) // Find the y-value for the given x, given n (x, y) points; // k points will define a polynomial of up to kth order. let lagrangeInterpolate x (pieces : (BigInteger * BigInteger) list) prime = let indexes = [0..pieces.Length-1] let calculateNum k = indexes |> List.map (fun j -> if k <> j then x - fst pieces.[j] else 1I) |> List.fold (*) 1I let calculateDen k = indexes |> List.map (fun j -> if k <> j then fst pieces.[k] - fst pieces.[j] else 1I) |> List.fold (*) 1I let nums = indexes |> List.map calculateNum let dens = indexes |> List.map calculateDen let den = List.fold (*) 1I dens let calculateTerm i = modularDivision ((nums.[i] * den * (snd pieces.[i])) %% prime) dens.[i] prime let num = indexes |> List.map calculateTerm |> List.fold (+) 0I (modularDivision num den prime) %% prime // Recover the secret from pieces let recoverSecret (pieces: (BigInteger * BigInteger) list) (prime: BigInteger) : BigInteger = if List.length pieces < 3 then failwith "Need at least three pieces" lagrangeInterpolate 0I pieces prime let main () = // Pick a prime which is bigger than both the secret and n (12th Mersenne Prime). let prime = BigInteger.Pow(2I, 127) - 1I // The secret to share which is (or can be made) a number let secret = 1234I // Minimum number of pieces needed to recreate the secret let k = 3 // Total number of pieces to divide the secret in let n = 6 let pieces = splitSecretIntoPieces secret k n prime printfn "The secret is %A" secret printfn "Pieces:" pieces |> List.iter (fun (x, y) -> printfn "%A" (x, y)) let recoveredSecret = recoverSecret (pieces |> List.take 3) prime printfn "Recovered secret with 3 pieces: %A" recoveredSecret let recoveredSecretOnceMore = recoverSecret (pieces |> List.skip 3) prime printfn "Recovered secret with another set of 3 pieces: %A" recoveredSecretOnceMore main () Happy secret sharing!
Top comments (3)
good use of time to read this excellent work
If you would like to share 2FA, you could use 2FA app like ente, export it to file, and share via ProtonMail.
really interesting, thanks for sharing