How to share a secret

Stefan Alfbo - Feb 24 - - Dev Community

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.

k vs n

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 ()
Enter fullscreen mode Exit fullscreen mode

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.

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
Enter fullscreen mode Exit fullscreen mode

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)]
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Now we have everything in place and can run the script.

run fsharp 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 ()
Enter fullscreen mode Exit fullscreen mode

Happy secret sharing!

Image
Are Coffee Drip Machine The Best Thing There Ever Was?
Image
10 Mobile Apps That Are The Best For Replace Lost Car Key
Image
Comprehensive List of Trie-Based Questions

datastructures, algorithms, interview, programming
Image
Callback Functions

callbackfunctions, beginners, javascript, explainlikeimfive
Image
How to use Eslint and Prettier together for your Node.js Project
Image
20 Things That Only The Most Devoted How To Repair Broken Car Key Fans Understand
Image
10 Websites To Help You Become An Expert In Drip Coffee
Image
The Role of AI and Machine Learning in Contemporary App Development
Image
What Is The Average Settlement For Asbestos Claim: 11 Things You've Forgotten To Do
Image
Why We Enjoy Drip Pot Coffee Maker (And You Should, Too!)
Image
Jak stworzyć idealne mieszkanie: Przewodnik po aranżacji i dekoracji
Image
situs slots online bonus new peserta yang baik
Image
What Is Attorneys For Asbestos Exposure? And How To Use It
Image
teknik raih jekpot di dalam permainan slots online
Image
1minDocker #2 - Get Docker

docker, beginners, tutorial, devops
Image
LazyHGrid Grid Layout in iOS 18 - #30DaysOfSwift

beginners, tutorial, swift, swiftui
Image
The Next Big Trend In The Asbestosis Lawsuit Settlements Industry
Image
Custom Toggle Button in iOS 18 - #30DaysOfSwift

beginners, tutorial, swift, swiftui
Image
The Big Refactoring - Chapter 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .