RSA Threshold Signatures

In 1979, Adi Shamir (who represents the “S” in RSA) created a secret sharing algorithm that allows a secret to be split into parts, and…

RSA Threshold Signatures

In 1979, Adi Shamir (who represents the “S” in RSA) created a secret sharing algorithm that allows a secret to be split into parts, and only when a number of them are added together, we will be able to recover the secret (paper):

In this article, I will outline how Lagrange interpretation constants — and named after Joseph-Louis Lagrange — are used to recreate the secret, and will use a simple example. These Lagrange polynomial values are used for polynomial interpolation, and where we can derive a polynomial from a given number of points on the curve.

To explain the basics, let’s say that there are six generals who have control over firing a missile, and there are three bases, with two generals on each base. Unfortunately, we are worried that one of the generals might make a rash decision, so we agree that the generals will not get the secret password to fire the missile. We are also worried that a base could be taken over by a malicious force, so we agree that no two generals will be able to gain the password. So to overcome these problems we decide that a least three generals must agree together to generate the correct password to fire the missile.

In Shamir’s scheme, the number of generals can be represented by the number of shares (n), and the number of generals who are required to generate the secret is represented by the threshold (t). Thus, in this example, we have a share value of six and a threshold value of three. So we give out one of the shares to each of the generals so that none of them has the same one. We will then require three generals to put together their shares in order for them to generate the password for the missile. To solve this problem and generate the shares (and also check the answer), I’ve created this Web page [here]:

So for a password of “Fire The Missile”, with a share of six, and a threshold of three we get:

000if30kGfSjyDNilwU0Tyz5awf2uk=
001PoYDi8eMEoMI6Zkbkn2n1GABoas=
002HxjSfFEEakXLqUnfGolr27XG3Ws=
003qGMlZ/Fa9+YOyozQWch/6nnYpik=
004RHyZDtPQP9/yXgv4cojC6Zg6Ets=
0058wduFXOOonw3Pc73McnW2FQkaZk=

for which each of these can be distributed to each of the generals. Notice, that there is a “000”, “001”, “002”, “003”, “004” and “005” values at the start of the shares. These values are important, for reasons we will see later. When one, two or three of them combine their codes, the result will be:

Trying a share of 1: ‰ýôgҏ ÍŠ\Ñ<³å¬Úé
Trying a share of 2: ?D·CümQFH¤Ú¼A7™r¹Ì
Trying a share of 3: Fire The Missile

Shamir’s secret sharing method generates a number of shares, of which a threshold defines the number of shares which can be used to re-build the message. In this case we will have a number of entities (p) and which use a threshold of t.

RSA key generation

An RSA key can then be created with a private key of (d,N), and where the decryption exponent is shared between the parties. These shares can then be used to sign a message, and where at least t shares are required to generate a valid RSA signature.

In this case, we have pl players and a threshold of t. First we start with two prime numbers (p and q). The modulus N is equal to:

N=p.q

and:

φ=(p−1)(q−1)

d=e^{−1} (mod φ)

The method for this will be explained in the following sections.

Basic theory

The basic theory relates to the number of points within a mathematical equation, that are required to reveal what the equation is (and thus determine the secret). For example, if we have a secret of 15, and can only be revealed when two people combine their information. For this, we thus need a linear equation, such as:

y=2x + 15

The two pieces of information that could be generated to reveal the equation would thus be two points on this line, such as:

(0,15) and (1,17)

If we only know one point, such as (1,17), we cannot determine the equation of the line, but knowing two points we can determine the gradient:

m = (17–15)/(1–0) =2

and from here we can determine the point it cuts the y-axis ©:

c = y -mx = 17- 2×1 = 15

and thus we have the equation (y = 2x + 15), where the secret is 15. In this example, we have only two shares, but if we require three shares we need a parabola, such as:

y = 2x² + 5x + 15

and share three points on the equation to generate the secret. If we require four shares then a cubic curve is required, and so on.

In most situations, it would be too processor intense to encrypt data with the secret share method, especially if we had a complete equation (such as using any 8 from 10 shares), so we often use symmetric encryption (such as for AES or ChaCha) to encrypt the data, and then create a share of the key. For example, if we had an 8 from 10 secret share policy, we would generate a 256-bit encryption key and then encrypt the data. Next, we would then take the 256-bit AES key and create a secret share where 8 of the 10 shares can come together to recreate the key.

https://asecuritysite.com/shares/go_sss

Lagrange interpretation constants

Shamir’s secret sharing method generates a number of shares, of which a threshold defines the number of shares which can be used to re-build the message. With this, we define a threshold value (t) and where we have n shares. For a threshold of 3, we create a polynomial which is in the form of:

f(x)=a+bx+cx² (mod p)

The secret is a . With three parties involved we then create shares for the split with f(x=1), f(x=2) and f(x=3), and where f(x=0) is the secret. With these shares, we use Lagrange interpretation constants to rebuild the secret value (f(x=0)). For each party this is computed with:

And where i is the node identifier, and n is the number of parties involved. So, for f(x)=a+bx+cx² (mod p), if we have shares of φ_1, φ_2 and φ_3, and coefficients of γ_1, γ_2 and γ_2, the secret share becomes:

For a three party share and for f(x)=7+19x+21x² (mod 31) , we get shares of φ_1=16, φ_2=5 and φ_3=5, have Lagrange interpretation constants of γ_1=3, γ_2=−3.0 and γ_3=1, we get:

Polnomial:
    2
21 x + 19 x + 7
Prime: 31
Shares: f_1=16, f_2=5, f_3=5
Lagrange Interpolation constants:
c_1=3.0, c_2=-3.0, c_3=1.0
Recovered secret: f_0 (secret)=7
Successful recovery

Here are some examples:

  • f(x)=7+19x+21x² (mod31) Try
  • f(x)=21+19x+21x² (mod31) Try
  • f(x)=500+499x+78x² (mod997) Try
  • f(x)=9999+7654x+501x² (mod 65537) Try

For f(x)=a+bx+cx² (mod p), we make a_0=d (the decryption exponent).

Coding

The following figure shows an example of spliting an RSA key into three shares for Bob, Peggy and Victor. If we do an any 2–from-3 approach, then Bob and Peggy can sign for a message with their key share, and then we can merge the signatures to produce the correct signature — as it if was signed by d.

The following is an outline of the code [here]:

package main
import (
 "crypto/rand"
 "crypto/rsa"
 _ "crypto/sha256"
 "fmt"
 "crypto"
 "math/big"
 "os"
 "strconv"
 tssrsa "github.com/cloudflare/circl/tss/rsa"
)
func createPrivateKey(p, q *big.Int, e int) *rsa.PrivateKey {
 return &rsa.PrivateKey{
  PublicKey: rsa.PublicKey{
   E: e,
  },
  D:           nil,
  Primes:      []*big.Int{p, q},
  Precomputed: rsa.PrecomputedValues{},
 }
}
func main() {
 m := "Hello"
 players := 3
 threshold := 2
 bits := 512
 const algo = crypto.SHA256
 argCount := len(os.Args[1:])
 if argCount > 0 {
  m = os.Args[1]
 }
 if argCount > 1 {
  players, _ = strconv.Atoi(os.Args[2])
 }
 if argCount > 2 {
  threshold, _ = strconv.Atoi(os.Args[3])
 }
 if argCount > 3 {
  bits, _ = strconv.Atoi(os.Args[4])
 }
 if players < threshold {
  fmt.Printf("Threshold greater than parties")
  return
 }
 key, _ := rsa.GenerateKey(rand.Reader, bits)
 keys, _ := tssrsa.Deal(rand.Reader, uint(players), uint(threshold), key, false)
 msg := []byte(m)
 pub := &key.PublicKey
 var padder tssrsa.Padder
 padder = &tssrsa.PKCS1v15Padder{}
 // fmt.Printf("Here 6")
 // If we use PSS:
 /*
  padder = &tssrsa.PSSPadder{
   Rand: rand.Reader,
   Opts: nil,
  } */
 msgPH, _ := tssrsa.PadHash(padder, algo, pub, msg)
 signshares := make([]tssrsa.SignShare, threshold)
 for i := uint(0); i < uint(threshold); i++ {
  signshares[i], _ = keys[i].Sign(rand.Reader, pub, msgPH, true)
 }
 sig, _ := tssrsa.CombineSignShares(pub, signshares, msgPH)
 if len(sig) != pub.Size() {
  fmt.Printf("bad signature size")
 }
 h := algo.New()
 h.Write(msg)
 hashed := h.Sum(nil)
 err := rsa.VerifyPKCS1v15(pub, algo, hashed, sig)
 fmt.Printf("Share %d from %d for message [%s]\n\n", threshold, players, m)
 if err == nil {
  fmt.Printf("Excellent: Signature verifies\n\n")
 } else {
  fmt.Printf("Bad luck. Signature does NOT verify: %s\n\n", err)
 }
 fmt.Printf("Signature: %x\n", sig)
 fmt.Printf("RSA Private key: N=%s\n", key.N)
 fmt.Printf("RSA Private key: D=%s\n", key.D)
 fmt.Printf("RSA Public key: E=%d\n\n", key.E)
 for i, k := range keys {
  fmt.Printf("Keys[%v]: %v\n", i, k)
 }
 for i, s := range signshares {
  fmt.Printf("SignShares[%v]: %v\n", i, s)
 }
 /* If PSS
 err = rsa.VerifyPSS(pub, algo, hashed, sig, padder.(*PSSPadder).Opts)
 */
}

A sample run is [here]:

Share 3 from 4 for message [Hello]
Excellent: Signature verifies
Signature: 0ad2ccfed402cfe9380a73c9c42c5ba474838860425272b988edd19c9c5fe5fd567f4ebcfb2966acf1c8cfab65c37268cf49d573845d4a84043ce52db9547fce
RSA Private key: N=9711573066217625488374098079500494722118336214998594909653327985774700483271586524716135623271991767275410105140718110142001110771587781847900483181430887
RSA Private key: D=4135831732885758081397089848465123635416982220129251932929862277537450455286394529552490856682226612788571826183770472662293015695711653083934576613969873
RSA Public key: E=65537

Keys[0]: (t,n): (3,4) index: 1 si: 0x284735702f95cb745adec6f15f233759d7c4b843965c6634cff5771e968ed3651c501efafb7aaf347f75c2d25593d13cd32daa26b8e2976997ba09ff031eec4e
Keys[1]: (t,n): (3,4) index: 2 si: 0xeaebbdc18c96d6f11148e3da0d6744c84667fc257c0602f9c90c1449f42428d21ac40523c6bf07f394df3626c7826cddd9449c85103a950c8ab81a7954630dd
Keys[2]: (t,n): (3,4) index: 3 si: 0x22e19833df4d9299b2a1dce09c7dc1a3aa2410280c0b5a29305c0f5f98cd8a795f1714eca034d58e1602e7a6df709cf3e997018262a65d10a9e85ff6d5c9d7e
Keys[3]: (t,n): (3,4) index: 4 si: 0x2c54e659f180ea3f91f75a299f76ec2fa77fc04115d668db3547632a56e95b4791fb1f0a440c5c177ac741a5a107a40f63d1d163856ccea5d9317068b623231

SignShares[0]: (t,n): (3,4) index: 1 xi: 0x3f38051247d1ebc04530c6cec7e4e7fb56409c4894c83f62019959dfa2e8a63498f3792fea1496a5fdb7d326d048d594671f337c7a2ce706c49913e4f1eb2a07
SignShares[1]: (t,n): (3,4) index: 2 xi: 0x7ccee9c99409a248f9c1de42393493f525e2f066abcd917e64e8dd947299810f97c9aedfe3c3e7728de42f8191918b230b1b5d012ef26b1fa0c2cfae8b6b008e
SignShares[2]: (t,n): (3,4) index: 3 xi: 0x7f34d8f8ae196f715c9dbd6d1b46149fb962720ec606c2c22e719e9795fe5acad0cfd256965e085d3b6fecf63971066807a6052bd87ffcd810e7653daebe761a