keyshare.go

Documentation: github.com/cloudflare/circl/tss/rsa

     1  package rsa
     2  
     3  import (
     4  	"crypto/rand"
     5  	"crypto/rsa"
     6  	"encoding/binary"
     7  	"errors"
     8  	"fmt"
     9  	"io"
    10  	"math"
    11  	"math/big"
    12  	"sync"
    13  )
    14  
    15  // KeyShare represents a portion of the key. It can only be used to generate SignShare's. During the dealing phase (when Deal is called), one KeyShare is generated per player.
    16  type KeyShare struct {
    17  	si *big.Int
    18  
    19  	twoDeltaSi *big.Int // optional cached value, this value is used to marginally speed up SignShare generation in Sign. If nil, it will be generated when needed and then cached.
    20  	Index      uint     // When KeyShare's are generated they are each assigned an index sequentially
    21  
    22  	Players   uint
    23  	Threshold uint
    24  }
    25  
    26  func (kshare KeyShare) String() string {
    27  	return fmt.Sprintf("(t,n): (%v,%v) index: %v si: 0x%v",
    28  		kshare.Threshold, kshare.Players, kshare.Index, kshare.si.Text(16))
    29  }
    30  
    31  // MarshalBinary encodes a KeyShare into a byte array in a format readable by UnmarshalBinary.
    32  // Note: Only Index's up to math.MaxUint16 are supported
    33  func (kshare *KeyShare) MarshalBinary() ([]byte, error) {
    34  	// The encoding format is
    35  	// | Players: uint16 | Threshold: uint16 | Index: uint16 | siLen: uint16 | si: []byte | twoDeltaSiNil: bool | twoDeltaSiLen: uint16 | twoDeltaSi: []byte |
    36  	// with all values in big-endian.
    37  
    38  	if kshare.Players > math.MaxUint16 {
    39  		return nil, fmt.Errorf("rsa_threshold: keyshare marshall: Players is too big to fit in a uint16")
    40  	}
    41  
    42  	if kshare.Threshold > math.MaxUint16 {
    43  		return nil, fmt.Errorf("rsa_threshold: keyshare marshall: Threshold is too big to fit in a uint16")
    44  	}
    45  
    46  	if kshare.Index > math.MaxUint16 {
    47  		return nil, fmt.Errorf("rsa_threshold: keyshare marshall: Index is too big to fit in a uint16")
    48  	}
    49  
    50  	players := uint16(kshare.Players)
    51  	threshold := uint16(kshare.Threshold)
    52  	index := uint16(kshare.Index)
    53  
    54  	twoDeltaSiBytes := []byte(nil)
    55  	if kshare.twoDeltaSi != nil {
    56  		twoDeltaSiBytes = kshare.twoDeltaSi.Bytes()
    57  	}
    58  
    59  	twoDeltaSiLen := len(twoDeltaSiBytes)
    60  
    61  	if twoDeltaSiLen > math.MaxInt16 {
    62  		return nil, fmt.Errorf("rsa_threshold: keyshare marshall: twoDeltaSiBytes is too big to fit it's length in a uint16")
    63  	}
    64  
    65  	siBytes := kshare.si.Bytes()
    66  
    67  	siLength := len(siBytes)
    68  
    69  	if siLength == 0 {
    70  		siLength = 1
    71  		siBytes = []byte{0}
    72  	}
    73  
    74  	if siLength > math.MaxInt16 {
    75  		return nil, fmt.Errorf("rsa_threshold: keyshare marshall: siBytes is too big to fit it's length in a uint16")
    76  	}
    77  
    78  	blen := 2 + 2 + 2 + 2 + 2 + 1 + siLength + twoDeltaSiLen
    79  	out := make([]byte, blen)
    80  
    81  	binary.BigEndian.PutUint16(out[0:2], players)
    82  	binary.BigEndian.PutUint16(out[2:4], threshold)
    83  	binary.BigEndian.PutUint16(out[4:6], index)
    84  
    85  	binary.BigEndian.PutUint16(out[6:8], uint16(siLength)) // okay because of conditions checked above
    86  
    87  	copy(out[8:8+siLength], siBytes)
    88  
    89  	if twoDeltaSiBytes != nil {
    90  		out[8+siLength] = 1 // twoDeltaSiNil
    91  	}
    92  
    93  	binary.BigEndian.PutUint16(out[8+siLength+1:8+siLength+3], uint16(twoDeltaSiLen))
    94  
    95  	if twoDeltaSiBytes != nil {
    96  		copy(out[8+siLength+3:8+siLength+3+twoDeltaSiLen], twoDeltaSiBytes)
    97  	}
    98  
    99  	return out, nil
   100  }
   101  
   102  // UnmarshalBinary recovers a KeyShare from a slice of bytes, or returns an error if the encoding is invalid.
   103  func (kshare *KeyShare) UnmarshalBinary(data []byte) error {
   104  	// The encoding format is
   105  	// | Players: uint16 | Threshold: uint16 | Index: uint16 | siLen: uint16 | si: []byte | twoDeltaSiNil: bool | twoDeltaSiLen: uint16 | twoDeltaSi: []byte |
   106  	// with all values in big-endian.
   107  	if len(data) < 6 {
   108  		return fmt.Errorf("rsa_threshold: keyshare unmarshalKeyShareTest failed: data length was too short for reading Players, Threshold, Index")
   109  	}
   110  
   111  	players := binary.BigEndian.Uint16(data[0:2])
   112  	threshold := binary.BigEndian.Uint16(data[2:4])
   113  	index := binary.BigEndian.Uint16(data[4:6])
   114  
   115  	if len(data[6:]) < 2 {
   116  		return fmt.Errorf("rsa_threshold: keyshare unmarshalKeyShareTest failed: data length was too short for reading siLen length")
   117  	}
   118  
   119  	siLen := binary.BigEndian.Uint16(data[6:8])
   120  
   121  	if siLen == 0 {
   122  		return fmt.Errorf("rsa_threshold: keyshare unmarshalKeyShareTest failed: si is a required field but siLen was 0")
   123  	}
   124  
   125  	if uint16(len(data[8:])) < siLen {
   126  		return fmt.Errorf("rsa_threshold: keyshare unmarshalKeyShareTest failed: data length was too short for reading si, needed: %d found: %d", siLen, len(data[8:]))
   127  	}
   128  
   129  	si := new(big.Int).SetBytes(data[8 : 8+siLen])
   130  
   131  	if len(data[8+siLen:]) < 1 {
   132  		return fmt.Errorf("rsa_threshold: keyshare unmarshalKeyShareTest failed: data length was too short for reading twoDeltaSiNil")
   133  	}
   134  
   135  	isNil := data[8+siLen]
   136  
   137  	var twoDeltaSi *big.Int
   138  
   139  	if isNil != 0 {
   140  		if len(data[8+siLen+1:]) < 2 {
   141  			return fmt.Errorf("rsa_threshold: keyshare unmarshalKeyShareTest failed: data length was too short for reading twoDeltaSiLen length")
   142  		}
   143  
   144  		twoDeltaSiLen := binary.BigEndian.Uint16(data[8+siLen+1 : 8+siLen+3])
   145  
   146  		if uint16(len(data[8+siLen+3:])) < twoDeltaSiLen {
   147  			return fmt.Errorf("rsa_threshold: keyshare unmarshalKeyShareTest failed: data length was too short for reading twoDeltaSi, needed: %d found: %d", twoDeltaSiLen, len(data[8+siLen+2:]))
   148  		}
   149  
   150  		twoDeltaSi = new(big.Int).SetBytes(data[8+siLen+3 : 8+siLen+3+twoDeltaSiLen])
   151  	}
   152  
   153  	kshare.Players = uint(players)
   154  	kshare.Threshold = uint(threshold)
   155  	kshare.Index = uint(index)
   156  	kshare.si = si
   157  	kshare.twoDeltaSi = twoDeltaSi
   158  
   159  	return nil
   160  }
   161  
   162  // Returns the cached value in twoDeltaSi or if nil, generates 2∆s_i, stores it in twoDeltaSi, and returns it
   163  func (kshare *KeyShare) get2DeltaSi(players int64) *big.Int {
   164  	// use the cached value if it exists
   165  	if kshare.twoDeltaSi != nil {
   166  		return kshare.twoDeltaSi
   167  	}
   168  	delta := calculateDelta(players)
   169  	// 2∆s_i
   170  	// delta << 1 == delta * 2
   171  	delta.Lsh(delta, 1).Mul(delta, kshare.si)
   172  	kshare.twoDeltaSi = delta
   173  	return delta
   174  }
   175  
   176  // Sign msg using a KeyShare. msg MUST be padded and hashed. Call PadHash before this method.
   177  //
   178  // If rand is not nil then blinding will be used to avoid timing
   179  // side-channel attacks.
   180  //
   181  // parallel indicates whether the blinding operations should use go routines to operate in parallel.
   182  // If parallel is false, blinding will take about 2x longer than nonbinding, otherwise it will take about the same time
   183  // (see benchmarks). If randSource is nil, parallel has no effect. parallel should almost always be set to true.
   184  func (kshare *KeyShare) Sign(randSource io.Reader, pub *rsa.PublicKey, digest []byte, parallel bool) (SignShare, error) {
   185  	x := &big.Int{}
   186  	x.SetBytes(digest)
   187  
   188  	exp := kshare.get2DeltaSi(int64(kshare.Players))
   189  
   190  	var signShare SignShare
   191  	signShare.Players = kshare.Players
   192  	signShare.Threshold = kshare.Threshold
   193  	signShare.Index = kshare.Index
   194  
   195  	signShare.xi = &big.Int{}
   196  
   197  	if randSource != nil {
   198  		// Let's blind.
   199  		// We can't use traditional RSA blinding (as used in rsa.go) because we are exponentiating by exp and not d.
   200  		// As such, Euler's theorem doesn't apply ( exp * d != 0 (mod ϕ(n)) ).
   201  		// Instead, we will choose a random r and compute x^{exp+r} * x^{-r} = x^{exp}.
   202  		// This should (hopefully) prevent revealing information of the true value of exp, since with exp you can derive
   203  		// s_i, the secret key share.
   204  
   205  		r, err := rand.Int(randSource, pub.N)
   206  		if err != nil {
   207  			return SignShare{}, errors.New("rsa_threshold: unable to get random value for blinding")
   208  		}
   209  		expPlusr := big.Int{}
   210  		// exp + r
   211  		expPlusr.Add(exp, r)
   212  
   213  		var wg *sync.WaitGroup
   214  
   215  		// x^{|2∆s_i+r|}
   216  		if parallel {
   217  			wg = &sync.WaitGroup{}
   218  			wg.Add(1)
   219  			go func() {
   220  				signShare.xi.Exp(x, &expPlusr, pub.N)
   221  				wg.Done()
   222  			}()
   223  		} else {
   224  			signShare.xi.Exp(x, &expPlusr, pub.N)
   225  		}
   226  
   227  		xExpr := big.Int{}
   228  		// x^r
   229  		xExpr.Exp(x, r, pub.N)
   230  		// x^{-r}
   231  		res := xExpr.ModInverse(&xExpr, pub.N)
   232  
   233  		if res == nil {
   234  			// extremely unlikely, somehow x^r is p or q
   235  			return SignShare{}, errors.New("rsa_threshold: no mod inverse")
   236  		}
   237  
   238  		if wg != nil {
   239  			wg.Wait()
   240  		}
   241  
   242  		// x^{|2∆s_i+r|} * x^{-r} = x^{2∆s_i}
   243  		signShare.xi.Mul(signShare.xi, &xExpr)
   244  		signShare.xi.Mod(signShare.xi, pub.N)
   245  	} else {
   246  		// x^{2∆s_i}
   247  		signShare.xi = &big.Int{}
   248  		signShare.xi.Exp(x, exp, pub.N)
   249  	}
   250  
   251  	return signShare, nil
   252  }
   253
View as plain text