Adi Shamir published "How to share a secret" [1] in the Communications of the ACM in 1979 and it has since become a classic method in cryptography. With secret sharing we take a secret value and then share it with others. For example we might have a share for Bob, Alice, Carol and Dave and then for three of them to come together to bring their shares together. For an any 3-from-4, we can use a quadratic equation, such as \(f(x)=20 x^2 - 2 x + 10\), and where the value of 10 is the secret. Bob then gets the value of \(f(x)\) when \(x=0\). This can be defined as \(f(1)\). Carol gets \(f(2)\), Dave gets \(f(3)\) and Alice gets \(f(4)\). The secret value is thus \(f(0)\). They then each know a point on the quadratic equation, and three of them can bring then back to recover the secret. In this case we will generate a random polynomial of \(a x^2 + b x + secret\), and then distribute the shares to Bob, Alice, Carol and Dave. Finally we will recover the secret from three of these shares (Bob, Carol and Dave). In this case we will investigate the main elements of sharing a secret using the Krytology library.
The Details of Shamir Secret Sharing Scheme using Kryptology |
Coding
Background
With secret sharing we take a secret value and then share it with others. For example we might have a share for Bob, Alice, Carol and Dave and then for three of them to come together to bring their shares together. For this we define a threshold (t) and a number of shares (n). We reconstruct the shares we need at least t shares to come together to reveal the secret. If we have (t-1) shares it should be impossible to reconstruct the secret.
For an any 3-from-4, we can use a quadratic equation, such as \(f(x)=20 x^2 - 2 x + 10\), and where the value of 10 is the secret. Bob then gets the value of \(f(x)\) when \(x=0\) - and which is defined as \(f(1)\). Carol gets \(f(2)\), Dave gets \(f(3)\) and Alice gets \(f(4)\). The secret value is thus \(f(0)\). They then each know a y-co-ordinate point on the quadratic equation. When they want to bring the value back, we can curve fit the gathered points. Thus if we have \(f(1)\), \(f(2)\) and \(f(3)\) we can regenerate the quadratic equation and thus determine \(f(0)\). We, of course, need to remember the x co-ordinate values for each share, so we give each share an ID of 1, 2, 3, and so on. Here we have three sample shares from an any 2-from-3 share, and notice that we have the x-co-ordinate value, so that when we reconstruct, we know the \(x\)-co-ordinate for the share:
== Secret shares == 2 from 3 === 00000001a971463eae26ff1dc6dd19db77f209643fe72ee384101f6e2bd6e97674ef630c 000000022faa84e5c3a2756b3b3accdbabe548eb67ea81283296913ae9d0fdd45ca25a0d 00000003b5e2c28cd91eecb8b0967edcdfd8877290edd46ddf1b0407a7cb11334555510e =================
These days we often use elliptic curves to perform efficient operations. With this we start with a secret (\(s\)) and then take the base point of the curve (\(G\)) and produce a secret of \(sG\). Next we convert \(sG\) into a number of polynomial factors for a given threshold \(t\) and with \(n\) shares. First we will take the share point and then split it into a number of polynomial values, and where the point that we cut the y-axis will recover the share. Initially we will fit a polynomial to the secret with:
\(P(x)=p_0 + p_1 x + p_2 x^2 + ...\)
and where \(p_0\), \(p_1\) and so on, are co-efficients of the required polynomial. Then we will create the shares for \(P(1)\), \(P(2)\), and so on. These are the points when \(x=1\), \(x=2\) and so on. These shares can then be distributed to the entities that will store the shares. When required, we gather back at least \(t\) shares to recreate the secret (\(sG)\). For example we may use \(P(0)\), \(P(1)\) ... \(P(t-1)\) and use a curve fitting method to find \(P(0)\) and which is the point of the polynomial where \(x=0\). The value we recover for \(P(0)\) is then covered back into an elliptic curve point to give \(sG\):
Let's look at the detail of the shares. We first need to create a number of random polynomial terms. This will equal the threshold value (\(t\)). So if we need any 3 from 5, we will create a polynomial of the form:
\(P(x)=a_0 + a_1 x + a_2 x^2 + a_3 x^3 \)
If we have any 4 from 10, the polynomial will be:
\(P(x)=a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 \)
Initially we create our curve and then generate the secret:
curve := curves.ED25519() secret := curve.NewScalar().Hash([]byte(msg))
Next we generate the order of the polynomial and random polynomial factors (apart from \(a_0\) and which is the secret value):
poly := new(sharing.Polynomial).Init(secret, t, crand.Reader)
We now need to create \(n\) shares and determine the polynomial output for \(x=1\), \(x=2\) and so on:
shares := make([]*sharing.ShamirShare, n) for i := range shares { x := curve.Scalar.New(i + 1) value := poly.Evaluate(x).Bytes() shares[i] = &sharing.ShamirShare{ Id: uint32(i + 1), Value: poly.Evaluate(x).Bytes(), } }
The Evaluate method thus calculates for the differing \(x\) values. Finally we reconstruct the shares as point values on the curve, and then use interolation to recover the polynomial and thus the secret (for \(a_0=1\):
dups := make(map[uint32]bool, len(shares)) xs := make([]curves.Scalar, len(shares)) ys := make([]curves.Scalar, len(shares)) for i, share := range shares { dups[share.Id] = true ys[i], _ = curve.Scalar.SetBytes(share.Value) xs[i] = curve.Scalar.New(int(share.Id)) } rtn, _ := interpolate(curve, xs, ys) fmt.Printf("\n\nRecovered secret: %x\n", rtn.Bytes()) } func interpolate(curve *curves.Curve, xs, ys []curves.Scalar) (curves.Scalar, error) { result := curve.Scalar.Zero() for i, xi := range xs { num := curve.Scalar.One() den := curve.Scalar.One() for j, xj := range xs { if i == j { continue } num = num.Mul(xj) den = den.Mul(xj.Sub(xi)) } if den.IsZero() { return nil, fmt.Errorf("divide by zero") } result = result.Add(ys[i].Mul(num.Div(den))) } return result, nil }
Coding
We can use the Kryptology library developed by Coinbase to implement Felman Verifiable Shamir Secret (VSS) Shares. In this case we will define \(t\) for the threshold and \(n\) for the number of shares:
package main import ( crand "crypto/rand" "fmt" "os" "strconv" curves "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/sharing" ) func main() { curve := curves.ED25519() t := uint32(4) n := uint32(7) msg := "hello" argCount := len(os.Args[1:]) if argCount > 0 { msg = os.Args[1] } if argCount > 1 { val, err := strconv.Atoi(os.Args[2]) if err == nil { t = uint32(val) } } if argCount > 2 { val, err := strconv.Atoi(os.Args[3]) if err == nil { n = uint32(val) } } secret := curve.NewScalar().Hash([]byte(msg)) poly := new(sharing.Polynomial).Init(secret, t, crand.Reader) shares := make([]*sharing.ShamirShare, n) fmt.Printf("Message: %x\n", msg) fmt.Printf("Secret: %x\n", secret.Bytes()) fmt.Print("=== Polynomial === ") fmt.Printf("\nf(x)=a_0: %x", poly.Coefficients[0].Bytes()) for i := 1; i < int(t); i++ { fmt.Printf("+a_%d %x x^%d ", i, poly.Coefficients[i].Bytes(), i) } fmt.Printf("\n\n") for i := range shares { x := curve.Scalar.New(i + 1) value := poly.Evaluate(x).Bytes() fmt.Printf("[f(%d) = %x]\n", i+1, value) shares[i] = &sharing.ShamirShare{ Id: uint32(i + 1), Value: poly.Evaluate(x).Bytes(), } } fmt.Print("\n=== Regenerating secret === ") dups := make(map[uint32]bool, len(shares)) xs := make([]curves.Scalar, len(shares)) ys := make([]curves.Scalar, len(shares)) for i, share := range shares { dups[share.Id] = true ys[i], _ = curve.Scalar.SetBytes(share.Value) xs[i] = curve.Scalar.New(int(share.Id)) } rtn, _ := interpolate(curve, xs, ys) fmt.Printf("\n\nRecovered secret: %x\n", rtn.Bytes()) } func interpolate(curve *curves.Curve, xs, ys []curves.Scalar) (curves.Scalar, error) { result := curve.Scalar.Zero() for i, xi := range xs { num := curve.Scalar.One() den := curve.Scalar.One() for j, xj := range xs { if i == j { continue } num = num.Mul(xj) den = den.Mul(xj.Sub(xi)) } if den.IsZero() { return nil, fmt.Errorf("divide by zero") } result = result.Add(ys[i].Mul(num.Div(den))) } return result, nil }
A sample run:
Message: hello Secret: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f === Polynomial === f(x)=b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f + 439ec3a8268e124f4609aff29da3cd9c5b745e19b409263aab8f7262a706650e x^1 + bb52af3da563710bc2e4ed42d0aa6258075864b1f7567b957378a8a20abaad0e x^2 + 2e8249b0f081b57c04f3bd22f4f7f5bbea6e8839f96f76f0dc06d2c1c027500f x^3 [f(1) = 1a7e9ec2a1ccad6662814294901147fd058a6db0df22c09fb742f884058c890b] [f(2) = a188e2f72ad14078d8204942bbc061e1e10eb4704b41952dc86b221c12d72801] [f(3) = aa6371900a0f5c58fc93777388ae554bcc762846554dee2b1bd8750e3d73e50b] [f(4) = e17c55c61179ad3236a684e0bbdbeefb445bfd89d4e6913ddeb0dee60a4fa007] [f(5) = b9bd7aea602b1a3b71f90d2bb53696f2cb556595a0ad46053f1f493000593a00] [f(6) = a50fcd4d184287a5982fb1f4d3adb42ee1ff92c19041d3256b4ca175a17f9401] [f(7) = 2b8842e43d76c74dc14d143c9935d49a04f3b8677c42fe419061d34173b18f07] [f(8) = d13cd1a1d780ad0f0059ddff85c27e21b6c809e13a508efcdb87cb1ffadc0c0e] [f(9) = 306f791dd1b7f96e93b9ba9b3c4f5f98751ab886a30a4af87be8759abaf0ec00] [f(10) = 95b012627ffdb54f134b39f7d9bd9c28c381f6b18d11f8d79dacbe3c39db100c] === Regenerating secret === Recovered secret: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f
References
[1] Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613 [here].