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
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 ( "fmt" "os" "strconv" "github.com/btcsuite/btcd/btcec" "github.com/coinbase/kryptology/pkg/core/curves" v1 "github.com/coinbase/kryptology/pkg/sharing/v1" "github.com/coinbase/kryptology/pkg/tecdsa/gg20/dealer" ) func getParams(t, n *uint32) { argCount := len(os.Args[1:]) if argCount > 0 { val, _ := strconv.Atoi(os.Args[1]) *t = uint32(val) } if argCount > 1 { val, _ := strconv.Atoi(os.Args[2]) *n = uint32(val) } } func main() { tshare := uint32(2) nshare := uint32(3) getParams(&tshare, &nshare) curve := btcec.S256() ikm, _ := dealer.NewSecret(curve) pk, sharesMap, _ := dealer.NewDealerShares(curve, tshare, nshare, ikm) fmt.Printf("Random secret: (%x)\n\n", ikm) fmt.Printf("Public key: (%s %s)\n\n", pk.X, pk.Y) // derivedPublicKey, _ := dealer.DerivePublicKey(curve, ikm) // fmt.Printf("Derived public key: (%s %s)\n", derivedPublicKey.X, derivedPublicKey.Y) for _, s := range sharesMap { x, y := curve.ScalarMult(curve.Gx, curve.Gy, s.ShamirShare.Value.Bytes()) fmt.Printf("Share: (%x)\n", s.ShamirShare.Value.Bytes()) fmt.Printf("Share as point: (%s %s)\n", x, y) } n := curves.NewField(curve.N) combiner, _ := v1.NewShamir(int(tshare), int(nshare), n) sShareArray := make([]*v1.ShamirShare, len(sharesMap)) for i, s := range sharesMap { // sharesMap[0] is always nil sShareArray[i-1] = s.ShamirShare } sk, _ := combiner.Combine(sShareArray...) pkx, pky := curve.ScalarBaseMult(sk) fmt.Printf("\n\nRecovered secret key: %x\n", sk) fmt.Printf("Public key: (%s %s)\n", pkx, pky) }
A sample run:
Sharing scheme: Any 3 from 4 Random secret: (3f03387da2b720028c8e8a87d4debd069692df72936e5f2d741bdf6f549e2937) Public key: (63324817329544191920864355152841420909669555317858139069678368003636027042462 91316442273205495929655849218247612848996446799476141603428447915021603620058) Share: (29e366fd96b698e4b0b38c25e25d3e8bfddb52cfa3e3d14b834cd0c054a1ea64) Share as point: (73951959257439151272639719145704178603278291516591348844944173000750066545333 15122150400853369898367568031781190769621389198080363724921070004792771090979) Share: (86b7637c0e174b72fa03ad9de7a27a1aa1620ca9782ea1e6f1b7e9b468c77a69) Share as point: (31129860827362772172840680364268349696939429058403711300716875803083499337232 50195007101891776622277303700342449568419997586060624656131059812013891372190) Share: (d3234e242e634cbf68278f8696965cdc51457cfdef6bf776ba13f8abef9d69a2) Share as point: (55006324122835899718672202177944073618348920550856463405393682968035071462336 78474555725098760224118369128628641645282017332886812628289753290014325302013) Share: (bca758a8c84135148c372b1e86c6aa2f21602c5721d425e02ea50c5c8362fad4) Share as point: (39132846206968063573279640112874747049988157460648972577989390220531368987197 9199869872386411663111466621092006958968416274623657828196791579289728419283) Recovered secret key: 3f03387da2b720028c8e8a87d4debd069692df72936e5f2d741bdf6f549e2937 Public key: (63324817329544191920864355152841420909669555317858139069678368003636027042462 91316442273205495929655849218247612848996446799476141603428447915021603620058)
References
[1] Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613 [here].