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) [article][article].
Shamir Secret Shares with Kryptology |
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\):
Coding
Now we can use the Kryptology library developed by Coinbase to implement Shamir Secret Shares. In this case we will define \(t\) for the threshold and \(n\) for the number of shares. In this case we will use Ed25519 for our curve, and hash a message to this curve (mysecret):
package main import ( crand "crypto/rand" "fmt" "os" "strconv" "strings" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/sharing" ) func getCurve(t string) *curves.Curve { s := strings.ToLower(t) if s == "ed25519" { return (curves.ED25519()) } else if s == "k256" { return (curves.K256()) } else if s == "p256" { return (curves.P256()) } else if s == "pallas" { return (curves.PALLAS()) } return curves.ED25519() } func main() { msg := "Hello" var t uint32 = uint32(2) var n uint32 = uint32(3) argCount := len(os.Args[1:]) curve := curves.ED25519() 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) } } if argCount > 3 { curvetype := os.Args[4] curve = getCurve(curvetype) } scheme, _ := sharing.NewShamir(t, n, curve) shares, _ := scheme.Split(curve.NewScalar().Hash([]byte(msg)), crand.Reader) fmt.Printf("== Shamir Secret Shares ===\n") fmt.Printf("Curve: %s\n", curve.Name) fmt.Printf("== Secret shares == %d from %d ===\n", t, n) for _, s := range shares { fmt.Printf("%x\n", s.Bytes()) } fmt.Printf("\n=================\n") mysecret := curve.NewScalar().Hash([]byte(msg)) fmt.Printf("Message: %s\n", msg) fmt.Printf("\nOriginal Hash: %x\n\n", mysecret.Bytes()) secret, err := scheme.Combine(shares...) if err == nil { fmt.Printf("Recorded Hash with all the shares: %x\n", secret.Bytes()) } else { fmt.Printf("Cannot recover with all shares\n") } secret, err = scheme.Combine(shares[0]) if err == nil { fmt.Printf("Recorded Hash with one share: %x\n", secret.Bytes()) } else { fmt.Printf("Cannot recover with one share\n") } secret, err = scheme.Combine(shares[0], shares[1]) if err == nil { fmt.Printf("Recorded Hash with two shares: %x\n", secret.Bytes()) } else { fmt.Printf("Cannot recover with two shares\n") } }
A sample run:
== Shamir Secret Shares === Curve: ed25519 == Secret shares == 3 from 4 === 00000001b35d5b4e0c7f6319f844f75b19b5cd1d2f5d567b8ba3e19d47a48b21912aac0c 00000002543ba570bd631d352ab26b9a16067117d30df3d06c0979d02e7816c263c61707 0000000385f396066293eb42455b2383a0a5868ca460f8acde836e7771afab9f0a77690e 000000046cde4456c547a9929c062fd0f99f5053a355660fe112c2920f4a4bba853ca102 ================= Message: hello Original Hash: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f Recorded Hash with all the shares: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f Cannot recover with one share Cannot recover with two shares
Coding
Presentation
The following is an outline presentation [here]:
References
[1] Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613 [here].