How to share a secret

#100daystooffload #cryptography #shamir #fsharp

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 ()