rsa_threshold_test.go

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

     1  package rsa
     2  
     3  import (
     4  	"bytes"
     5  	"crypto"
     6  	"crypto/rand"
     7  	"crypto/rsa"
     8  	_ "crypto/sha256"
     9  	"errors"
    10  	"fmt"
    11  	"io"
    12  	"math/big"
    13  	"testing"
    14  
    15  	"github.com/cloudflare/circl/internal/test"
    16  )
    17  
    18  var ONE = big.NewInt(1)
    19  
    20  func TestGenerateKey(t *testing.T) {
    21  	// [Warning]: this is only for tests, use a secure bitlen above 2048 bits.
    22  	bitlen := 128
    23  	key, err := GenerateKey(rand.Reader, bitlen)
    24  	test.CheckNoErr(t, err, "failed to create key")
    25  	test.CheckOk(key.Validate() == nil, fmt.Sprintf("key is not valid: %v", key), t)
    26  }
    27  
    28  func createPrivateKey(p, q *big.Int, e int) *rsa.PrivateKey {
    29  	return &rsa.PrivateKey{
    30  		PublicKey: rsa.PublicKey{
    31  			E: e,
    32  		},
    33  		D:           nil,
    34  		Primes:      []*big.Int{p, q},
    35  		Precomputed: rsa.PrecomputedValues{},
    36  	}
    37  }
    38  
    39  func TestCalcN(t *testing.T) {
    40  	TWO := big.NewInt(2)
    41  	n := calcN(ONE, TWO)
    42  	if n.Cmp(TWO) != 0 {
    43  		t.Fatal("calcN failed: (1, 2)")
    44  	}
    45  	n = calcN(TWO, big.NewInt(4))
    46  	if n.Cmp(big.NewInt(8)) != 0 {
    47  		t.Fatal("calcN failed: (2, 4)")
    48  	}
    49  }
    50  
    51  func TestComputePolynomial(t *testing.T) {
    52  	m := big.NewInt(11)
    53  	const k = 5
    54  	a := make([]*big.Int, k)
    55  	for i := 0; i < k; i++ {
    56  		a[i] = big.NewInt(int64(i + 1))
    57  	}
    58  	// a = {1, 2, 3, 4, 5}
    59  
    60  	x := uint(3)
    61  	out := computePolynomial(k, a, x, m)
    62  	// 1 * 3^0 = 1  = 1
    63  	// 2 * 3^1 = 6  = 6
    64  	// 3 * 3^2 = 27 = 5
    65  	// 4 * 3^3 = 108 = 9
    66  	// 5 * 3^4 = 405 = 9
    67  	// 1 + 6 + 5 + 9 + 9 = 30 = 8
    68  	if out.Cmp(big.NewInt(8)) != 0 {
    69  		t.Fatal("compute polynomial failed")
    70  	}
    71  }
    72  
    73  func TestComputeLambda(t *testing.T) {
    74  	// shares = {1, 2, 3, 4, 5}
    75  	// i = 0
    76  	// ∆ = 5! = 120
    77  	// j = 3
    78  	//
    79  	// num = (0 - 1) * (0 - 2) * (0 - 4) * (0 - 5) = 40
    80  	// dem = (3 - 1) * (3 - 2) * (3 - 4) * (3 - 5) = 4
    81  	// num/dev = 40/4 = 10
    82  	// ∆ * 10 = 120 * 10 = 1200
    83  	shares := make([]SignShare, 5)
    84  	for i := uint(1); i <= 5; i++ {
    85  		shares[i-1].Index = i
    86  	}
    87  	i := int64(0)
    88  	delta := int64(120)
    89  	j := int64(3)
    90  
    91  	lambda, err := computeLambda(big.NewInt(delta), shares, i, j)
    92  
    93  	if err != nil || lambda.Cmp(big.NewInt(1200)) != 0 {
    94  		t.Fatal("computeLambda failed")
    95  	}
    96  }
    97  
    98  func TestDeal(t *testing.T) {
    99  	// Players = 3
   100  	// Threshold = 2
   101  	// e = 3
   102  	// p' = 11
   103  	// q' = 5
   104  	// p = 2(11) + 1 = 23
   105  	// q = 2(5) + 1 = 11
   106  	// n = 253
   107  	// m = 55
   108  	// d = 37
   109  	//
   110  	// a[0] = 37
   111  	// a[1] = 33
   112  	//
   113  	//
   114  	// Index = 1
   115  	// computePolynomial(k: 2, a: {37, 33}, x: 1, m: 55) :
   116  	//  	37 * 1^0 = 37 * 1 = 37
   117  	//  	33 * 1^1 = 33 * 1 = 33
   118  	//      37 + 33 = 70 = 15
   119  	//
   120  	// shares[0].si = 15
   121  	// shares[0].Index  = 1
   122  	//
   123  	// Index = 2
   124  	// computePolynomial(k: 2, a: {37, 33}, x: 2, m: 55) :
   125  	//  	37 * 2^0 = 37 * 1 = 37
   126  	//  	33 * 2^1 = 33 * 2 = 66 = 11
   127  	//      37 + 11 = 48
   128  	//
   129  	// shares[1].si = 48
   130  	// shares[1].Index  = 2
   131  	//
   132  	//
   133  	// Index = 3
   134  	// computePolynomial(k: 2, a: {37, 33}, x: 3, m: 55) :
   135  	//  	37 * 3^0 = 37 * 1 = 37
   136  	//  	33 * 3^1 = 33 * 3 = 99 = 44
   137  	//      37 + 44 = 81 = 26
   138  	//
   139  	// shares[2].si = 26
   140  	// shares[2].Index  = 3
   141  	//
   142  	//
   143  	//
   144  	r := bytes.NewReader([]byte{33, 17})
   145  	players := uint(3)
   146  	threshold := uint(2)
   147  	p := int64(23)
   148  	q := int64(11)
   149  	e := 3
   150  
   151  	key := createPrivateKey(big.NewInt(p), big.NewInt(q), e)
   152  
   153  	share, err := Deal(r, players, threshold, key, false)
   154  	if err != nil {
   155  		t.Fatal(err)
   156  	}
   157  	if share[0].si.Cmp(big.NewInt(15)) != 0 {
   158  		t.Fatalf("share[0].si should have been 15 but was %d", share[0].si)
   159  	}
   160  	if share[1].si.Cmp(big.NewInt(48)) != 0 {
   161  		t.Fatalf("share[1].si should have been 48 but was %d", share[1].si)
   162  	}
   163  	if share[2].si.Cmp(big.NewInt(26)) != 0 {
   164  		t.Fatalf("share[2].si should have been 26 but was %d", share[2].si)
   165  	}
   166  }
   167  
   168  const (
   169  	PKS1v15 = 0
   170  	PSS     = 1
   171  )
   172  
   173  func testIntegration(t *testing.T, algo crypto.Hash, priv *rsa.PrivateKey, threshold uint, keys []KeyShare, padScheme int) {
   174  	msg := []byte("hello")
   175  	pub := &priv.PublicKey
   176  
   177  	var padder Padder
   178  	if padScheme == PKS1v15 {
   179  		padder = &PKCS1v15Padder{}
   180  	} else if padScheme == PSS {
   181  		padder = &PSSPadder{
   182  			Rand: rand.Reader,
   183  			Opts: nil,
   184  		}
   185  	} else {
   186  		t.Fatal(errors.New("unknown padScheme"))
   187  	}
   188  
   189  	msgPH, err := PadHash(padder, algo, pub, msg)
   190  	if err != nil {
   191  		t.Fatal(err)
   192  	}
   193  
   194  	signshares := make([]SignShare, threshold)
   195  
   196  	for i := uint(0); i < threshold; i++ {
   197  		signshares[i], err = keys[i].Sign(rand.Reader, pub, msgPH, true)
   198  		if err != nil {
   199  			t.Fatal(err)
   200  		}
   201  	}
   202  
   203  	sig, err := CombineSignShares(pub, signshares, msgPH)
   204  	if err != nil {
   205  		t.Fatal(err)
   206  	}
   207  	if len(sig) != pub.Size() {
   208  		t.Fatal("bad signature size")
   209  	}
   210  
   211  	h := algo.New()
   212  	h.Write(msg)
   213  	hashed := h.Sum(nil)
   214  
   215  	if padScheme == PKS1v15 {
   216  		err = rsa.VerifyPKCS1v15(pub, algo, hashed, sig)
   217  	} else if padScheme == PSS {
   218  		err = rsa.VerifyPSS(pub, algo, hashed, sig, padder.(*PSSPadder).Opts)
   219  	} else {
   220  		panic("logical error")
   221  	}
   222  
   223  	if err != nil {
   224  		t.Logf("d: %v p: %v q: %v\n", priv.D.Text(16), priv.Primes[0].Text(16), priv.Primes[1].Text(16))
   225  		for i, k := range keys {
   226  			t.Logf("keys[%v]: %v\n", i, k)
   227  		}
   228  		for i, s := range signshares {
   229  			t.Logf("signShares[%v]: %v\n", i, s)
   230  		}
   231  		t.Logf("sig: %x\n", sig)
   232  		t.Fatal(err)
   233  	}
   234  }
   235  
   236  func TestIntegrationStdRsaKeyGenerationPKS1v15(t *testing.T) {
   237  	const players = 3
   238  	const threshold = 2
   239  	const bits = 2048
   240  	const algo = crypto.SHA256
   241  
   242  	key, err := rsa.GenerateKey(rand.Reader, bits)
   243  	if err != nil {
   244  		t.Fatal(err)
   245  	}
   246  	keys, err := Deal(rand.Reader, players, threshold, key, false)
   247  	if err != nil {
   248  		t.Fatal(err)
   249  	}
   250  	testIntegration(t, algo, key, threshold, keys, PKS1v15)
   251  }
   252  
   253  func TestIntegrationStdRsaKeyGenerationPSS(t *testing.T) {
   254  	const players = 3
   255  	const threshold = 2
   256  	const bits = 2048
   257  	const algo = crypto.SHA256
   258  
   259  	key, err := rsa.GenerateKey(rand.Reader, bits)
   260  	if err != nil {
   261  		t.Fatal(err)
   262  	}
   263  	keys, err := Deal(rand.Reader, players, threshold, key, false)
   264  	if err != nil {
   265  		t.Fatal(err)
   266  	}
   267  	testIntegration(t, algo, key, threshold, keys, PSS)
   268  }
   269  
   270  // nolint: unparam
   271  func benchmarkSignCombineHelper(randSource io.Reader, parallel bool, b *testing.B, players, threshold uint, bits int, algo crypto.Hash, padScheme int) {
   272  	key, err := rsa.GenerateKey(rand.Reader, bits)
   273  	pub := key.PublicKey
   274  	if err != nil {
   275  		panic(err)
   276  	}
   277  
   278  	keys, err := Deal(rand.Reader, players, threshold, key, true)
   279  	if err != nil {
   280  		b.Fatal(err)
   281  	}
   282  
   283  	msg := []byte("hello")
   284  	var padder Padder
   285  	if padScheme == PKS1v15 {
   286  		padder = &PKCS1v15Padder{}
   287  	} else if padScheme == PSS {
   288  		padder = &PSSPadder{
   289  			Rand: rand.Reader,
   290  			Opts: nil,
   291  		}
   292  	} else {
   293  		b.Fatal(errors.New("unknown padScheme"))
   294  	}
   295  	msgPH, err := PadHash(padder, algo, &pub, msg)
   296  	if err != nil {
   297  		b.Fatal(err)
   298  	}
   299  
   300  	signshares := make([]SignShare, threshold)
   301  	b.ResetTimer()
   302  	for i := 0; i < b.N; i++ {
   303  		for i := uint(0); i < threshold; i++ {
   304  			signshares[i], err = keys[i].Sign(randSource, &pub, msgPH, parallel)
   305  			if err != nil {
   306  				b.Fatal(err)
   307  			}
   308  		}
   309  		_, err = CombineSignShares(&pub, signshares, msgPH)
   310  		if err != nil {
   311  			b.Fatal(err)
   312  		}
   313  	}
   314  	b.StopTimer()
   315  }
   316  
   317  func BenchmarkBaselineRSA_SHA256_4096(b *testing.B) {
   318  	const bits = 4096
   319  	const algo = crypto.SHA256
   320  
   321  	key, err := rsa.GenerateKey(rand.Reader, bits)
   322  	if err != nil {
   323  		b.Fatal(err)
   324  	}
   325  	h := algo.New()
   326  
   327  	msg := []byte("hello")
   328  
   329  	h.Write(msg)
   330  	d := h.Sum(nil)
   331  	b.ResetTimer()
   332  	for i := 0; i < b.N; i++ {
   333  		_, err = rsa.SignPKCS1v15(rand.Reader, key, algo, d)
   334  		if err != nil {
   335  			b.Fatal(err)
   336  		}
   337  	}
   338  	b.StopTimer()
   339  }
   340  
   341  func BenchmarkBaselineRSA_SHA256_2048(b *testing.B) {
   342  	const bits = 2048
   343  	const algo = crypto.SHA256
   344  
   345  	key, err := rsa.GenerateKey(rand.Reader, bits)
   346  	if err != nil {
   347  		b.Fatal(err)
   348  	}
   349  	h := algo.New()
   350  
   351  	msg := []byte("hello")
   352  
   353  	h.Write(msg)
   354  	d := h.Sum(nil)
   355  	b.ResetTimer()
   356  	for i := 0; i < b.N; i++ {
   357  		_, err = rsa.SignPKCS1v15(rand.Reader, key, algo, d)
   358  		if err != nil {
   359  			b.Fatal(err)
   360  		}
   361  	}
   362  	b.StopTimer()
   363  }
   364  
   365  func BenchmarkSignCombine_SHA256_4096_3_2_Scheme(b *testing.B) {
   366  	const players = 3
   367  	const threshold = 2
   368  	const bits = 4096
   369  	const algo = crypto.SHA256
   370  	benchmarkSignCombineHelper(nil, false, b, players, threshold, bits, algo, PKS1v15)
   371  }
   372  
   373  func BenchmarkSignCombine_SHA256_4096_3_2_Scheme_Blind(b *testing.B) {
   374  	const players = 3
   375  	const threshold = 2
   376  	const bits = 4096
   377  	const algo = crypto.SHA256
   378  	benchmarkSignCombineHelper(rand.Reader, false, b, players, threshold, bits, algo, PKS1v15)
   379  }
   380  
   381  func BenchmarkSignCombine_SHA256_4096_3_2_Scheme_BlindParallel(b *testing.B) {
   382  	const players = 3
   383  	const threshold = 2
   384  	const bits = 4096
   385  	const algo = crypto.SHA256
   386  	benchmarkSignCombineHelper(rand.Reader, true, b, players, threshold, bits, algo, PKS1v15)
   387  }
   388  
   389  func BenchmarkSignCombine_SHA256_2048_3_2_Scheme(b *testing.B) {
   390  	const players = 3
   391  	const threshold = 2
   392  	const bits = 2048
   393  	const algo = crypto.SHA256
   394  	benchmarkSignCombineHelper(nil, false, b, players, threshold, bits, algo, PKS1v15)
   395  }
   396  
   397  func BenchmarkSignCombine_SHA256_2048_3_2_Scheme_Blind(b *testing.B) {
   398  	const players = 3
   399  	const threshold = 2
   400  	const bits = 2048
   401  	const algo = crypto.SHA256
   402  	benchmarkSignCombineHelper(rand.Reader, false, b, players, threshold, bits, algo, PKS1v15)
   403  }
   404  
   405  func BenchmarkSignCombine_SHA256_2048_3_2_Scheme_BlindParallel(b *testing.B) {
   406  	const players = 3
   407  	const threshold = 2
   408  	const bits = 2048
   409  	const algo = crypto.SHA256
   410  	benchmarkSignCombineHelper(rand.Reader, true, b, players, threshold, bits, algo, PKS1v15)
   411  }
   412  
   413  func BenchmarkSignCombine_SHA256_1024_3_2_Scheme(b *testing.B) {
   414  	const players = 3
   415  	const threshold = 2
   416  	const bits = 1024
   417  	const algo = crypto.SHA256
   418  	benchmarkSignCombineHelper(nil, false, b, players, threshold, bits, algo, PKS1v15)
   419  }
   420  
   421  func BenchmarkDealGeneration(b *testing.B) {
   422  	const players = 3
   423  	const threshold = 2
   424  	const bits = 2048
   425  	key, err := rsa.GenerateKey(rand.Reader, bits)
   426  	if err != nil {
   427  		b.Fatal("could not generate key")
   428  	}
   429  	b.ResetTimer()
   430  	for i := 0; i < b.N; i++ {
   431  		_, err := Deal(rand.Reader, players, threshold, key, false)
   432  		if err != nil {
   433  			b.Fatal(err)
   434  		}
   435  	}
   436  }
   437
View as plain text