genprecomps.go

Documentation: github.com/decred/dcrd/dcrec/secp256k1/v4

     1  // Copyright 2015 The btcsuite developers
     2  // Copyright (c) 2015-2022 The Decred developers
     3  // Use of this source code is governed by an ISC
     4  // license that can be found in the LICENSE file.
     5  
     6  // This file is ignored during the regular build due to the following build tag.
     7  // It is called by go generate and used to automatically generate pre-computed
     8  // tables used to accelerate operations.
     9  //go:build ignore
    10  // +build ignore
    11  
    12  package main
    13  
    14  // References:
    15  //   [GECC]: Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone)
    16  
    17  import (
    18  	"bytes"
    19  	"compress/zlib"
    20  	"encoding/base64"
    21  	"fmt"
    22  	"log"
    23  	"math/big"
    24  	"os"
    25  
    26  	"github.com/decred/dcrd/dcrec/secp256k1/v4"
    27  )
    28  
    29  // curveParams houses the secp256k1 curve parameters for convenient access.
    30  var curveParams = secp256k1.Params()
    31  
    32  // bigAffineToJacobian takes an affine point (x, y) as big integers and converts
    33  // it to Jacobian point with Z=1.
    34  func bigAffineToJacobian(x, y *big.Int, result *secp256k1.JacobianPoint) {
    35  	result.X.SetByteSlice(x.Bytes())
    36  	result.Y.SetByteSlice(y.Bytes())
    37  	result.Z.SetInt(1)
    38  }
    39  
    40  // serializedBytePoints returns a serialized byte slice which contains all of
    41  // the possible points per 8-bit window.  This is used to when generating
    42  // compressedbytepoints.go.
    43  func serializedBytePoints() []byte {
    44  	// Calculate G^(2^i) for i in 0..255.  These are used to avoid recomputing
    45  	// them for each digit of the 8-bit windows.
    46  	doublingPoints := make([]secp256k1.JacobianPoint, curveParams.BitSize)
    47  	var q secp256k1.JacobianPoint
    48  	bigAffineToJacobian(curveParams.Gx, curveParams.Gy, &q)
    49  	for i := 0; i < curveParams.BitSize; i++ {
    50  		// Q = 2*Q.
    51  		doublingPoints[i] = q
    52  		secp256k1.DoubleNonConst(&q, &q)
    53  	}
    54  
    55  	// Separate the bits into byte-sized windows.
    56  	curveByteSize := curveParams.BitSize / 8
    57  	serialized := make([]byte, curveByteSize*256*2*32)
    58  	offset := 0
    59  	for byteNum := 0; byteNum < curveByteSize; byteNum++ {
    60  		// Grab the 8 bits that make up this byte from doubling points.
    61  		startingBit := 8 * (curveByteSize - byteNum - 1)
    62  		windowPoints := doublingPoints[startingBit : startingBit+8]
    63  
    64  		// Compute all points in this window, convert them to affine, and
    65  		// serialize them.
    66  		for i := 0; i < 256; i++ {
    67  			var point secp256k1.JacobianPoint
    68  			for bit := 0; bit < 8; bit++ {
    69  				if i>>uint(bit)&1 == 1 {
    70  					secp256k1.AddNonConst(&point, &windowPoints[bit], &point)
    71  				}
    72  			}
    73  			point.ToAffine()
    74  
    75  			point.X.PutBytesUnchecked(serialized[offset:])
    76  			offset += 32
    77  			point.Y.PutBytesUnchecked(serialized[offset:])
    78  			offset += 32
    79  		}
    80  	}
    81  
    82  	return serialized
    83  }
    84  
    85  // sqrt returns the square root of the provided big integer using Newton's
    86  // method.  It's only compiled and used during generation of pre-computed
    87  // values, so speed is not a huge concern.
    88  func sqrt(n *big.Int) *big.Int {
    89  	// Initial guess = 2^(log_2(n)/2)
    90  	guess := big.NewInt(2)
    91  	guess.Exp(guess, big.NewInt(int64(n.BitLen()/2)), nil)
    92  
    93  	// Now refine using Newton's method.
    94  	big2 := big.NewInt(2)
    95  	prevGuess := big.NewInt(0)
    96  	for {
    97  		prevGuess.Set(guess)
    98  		guess.Add(guess, new(big.Int).Div(n, guess))
    99  		guess.Div(guess, big2)
   100  		if guess.Cmp(prevGuess) == 0 {
   101  			break
   102  		}
   103  	}
   104  	return guess
   105  }
   106  
   107  // endomorphismParams houses the parameters needed to make use of the secp256k1
   108  // endomorphism.
   109  type endomorphismParams struct {
   110  	lambda *big.Int
   111  	beta   *big.Int
   112  	a1, b1 *big.Int
   113  	a2, b2 *big.Int
   114  	z1, z2 *big.Int
   115  }
   116  
   117  // endomorphismVectors runs the first 3 steps of algorithm 3.74 from [GECC] to
   118  // generate the linearly independent vectors needed to generate a balanced
   119  // length-two representation of a multiplier such that k = k1 + k2λ (mod N) and
   120  // returns them.  Since the values will always be the same given the fact that N
   121  // and λ are fixed, the final results can be accelerated by storing the
   122  // precomputed values.
   123  func endomorphismVectors(lambda *big.Int) (a1, b1, a2, b2 *big.Int) {
   124  	// This section uses an extended Euclidean algorithm to generate a
   125  	// sequence of equations:
   126  	//  s[i] * N + t[i] * λ = r[i]
   127  
   128  	nSqrt := sqrt(curveParams.N)
   129  	u, v := new(big.Int).Set(curveParams.N), new(big.Int).Set(lambda)
   130  	x1, y1 := big.NewInt(1), big.NewInt(0)
   131  	x2, y2 := big.NewInt(0), big.NewInt(1)
   132  	q, r := new(big.Int), new(big.Int)
   133  	qu, qx1, qy1 := new(big.Int), new(big.Int), new(big.Int)
   134  	s, t := new(big.Int), new(big.Int)
   135  	ri, ti := new(big.Int), new(big.Int)
   136  	a1, b1, a2, b2 = new(big.Int), new(big.Int), new(big.Int), new(big.Int)
   137  	found, oneMore := false, false
   138  	for u.Sign() != 0 {
   139  		// q = v/u
   140  		q.Div(v, u)
   141  
   142  		// r = v - q*u
   143  		qu.Mul(q, u)
   144  		r.Sub(v, qu)
   145  
   146  		// s = x2 - q*x1
   147  		qx1.Mul(q, x1)
   148  		s.Sub(x2, qx1)
   149  
   150  		// t = y2 - q*y1
   151  		qy1.Mul(q, y1)
   152  		t.Sub(y2, qy1)
   153  
   154  		// v = u, u = r, x2 = x1, x1 = s, y2 = y1, y1 = t
   155  		v.Set(u)
   156  		u.Set(r)
   157  		x2.Set(x1)
   158  		x1.Set(s)
   159  		y2.Set(y1)
   160  		y1.Set(t)
   161  
   162  		// As soon as the remainder is less than the sqrt of n, the
   163  		// values of a1 and b1 are known.
   164  		if !found && r.Cmp(nSqrt) < 0 {
   165  			// When this condition executes ri and ti represent the
   166  			// r[i] and t[i] values such that i is the greatest
   167  			// index for which r >= sqrt(n).  Meanwhile, the current
   168  			// r and t values are r[i+1] and t[i+1], respectively.
   169  
   170  			// a1 = r[i+1], b1 = -t[i+1]
   171  			a1.Set(r)
   172  			b1.Neg(t)
   173  			found = true
   174  			oneMore = true
   175  
   176  			// Skip to the next iteration so ri and ti are not
   177  			// modified.
   178  			continue
   179  
   180  		} else if oneMore {
   181  			// When this condition executes ri and ti still
   182  			// represent the r[i] and t[i] values while the current
   183  			// r and t are r[i+2] and t[i+2], respectively.
   184  
   185  			// sum1 = r[i]^2 + t[i]^2
   186  			rSquared := new(big.Int).Mul(ri, ri)
   187  			tSquared := new(big.Int).Mul(ti, ti)
   188  			sum1 := new(big.Int).Add(rSquared, tSquared)
   189  
   190  			// sum2 = r[i+2]^2 + t[i+2]^2
   191  			r2Squared := new(big.Int).Mul(r, r)
   192  			t2Squared := new(big.Int).Mul(t, t)
   193  			sum2 := new(big.Int).Add(r2Squared, t2Squared)
   194  
   195  			// if (r[i]^2 + t[i]^2) <= (r[i+2]^2 + t[i+2]^2)
   196  			if sum1.Cmp(sum2) <= 0 {
   197  				// a2 = r[i], b2 = -t[i]
   198  				a2.Set(ri)
   199  				b2.Neg(ti)
   200  			} else {
   201  				// a2 = r[i+2], b2 = -t[i+2]
   202  				a2.Set(r)
   203  				b2.Neg(t)
   204  			}
   205  
   206  			// All done.
   207  			break
   208  		}
   209  
   210  		ri.Set(r)
   211  		ti.Set(t)
   212  	}
   213  
   214  	return a1, b1, a2, b2
   215  }
   216  
   217  // deriveEndomorphismParams calculates and returns parameters needed to make use
   218  // of the secp256k1 endomorphism.
   219  func deriveEndomorphismParams() [2]endomorphismParams {
   220  	// roots returns the solutions of the characteristic polynomial of the
   221  	// secp256k1 endomorphism.
   222  	//
   223  	// The characteristic polynomial for the endomorphism is:
   224  	//
   225  	// X^2 + X + 1 ≡ 0 (mod n).
   226  	//
   227  	// Solving for X:
   228  	//
   229  	// 4X^2 + 4X + 4 ≡ 0 (mod n)       | (*4, possible because gcd(4, n) = 1)
   230  	// (2X + 1)^2 + 3 ≡ 0 (mod n)      | (factor by completing the square)
   231  	// (2X + 1)^2 ≡ -3 (mod n)         | (-3)
   232  	// (2X + 1) ≡ ±sqrt(-3) (mod n)    | (sqrt)
   233  	// 2X ≡ ±sqrt(-3) - 1 (mod n)      | (-1)
   234  	// X ≡ (±sqrt(-3)-1)*2^-1 (mod n)  | (*2^-1)
   235  	//
   236  	// So, the roots are:
   237  	// X1 ≡ (-(sqrt(-3)+1)*2^-1 (mod n)
   238  	// X2 ≡ (sqrt(-3)-1)*2^-1 (mod n)
   239  	//
   240  	// It is also worth noting that X is a cube root of unity, meaning
   241  	// X^3 - 1 ≡ 0 (mod n), hence it can be factored as (X - 1)(X^2 + X + 1) ≡ 0
   242  	// and (X1)^2 ≡ X2 (mod n) and (X2)^2 ≡ X1 (mod n).
   243  	roots := func(prime *big.Int) [2]big.Int {
   244  		var result [2]big.Int
   245  		one := big.NewInt(1)
   246  		twoInverse := new(big.Int).ModInverse(big.NewInt(2), prime)
   247  		negThree := new(big.Int).Neg(big.NewInt(3))
   248  		sqrtNegThree := new(big.Int).ModSqrt(negThree, prime)
   249  		sqrtNegThreePlusOne := new(big.Int).Add(sqrtNegThree, one)
   250  		negSqrtNegThreePlusOne := new(big.Int).Neg(sqrtNegThreePlusOne)
   251  		result[0].Mul(negSqrtNegThreePlusOne, twoInverse)
   252  		result[0].Mod(&result[0], prime)
   253  		sqrtNegThreeMinusOne := new(big.Int).Sub(sqrtNegThree, one)
   254  		result[1].Mul(sqrtNegThreeMinusOne, twoInverse)
   255  		result[1].Mod(&result[1], prime)
   256  		return result
   257  	}
   258  
   259  	// Find the λ's and β's which are the solutions for the characteristic
   260  	// polynomial of the secp256k1 endomorphism modulo the curve order and
   261  	// modulo the field order, respectively.
   262  	lambdas := roots(curveParams.N)
   263  	betas := roots(curveParams.P)
   264  
   265  	// Ensure the calculated roots are actually the roots of the characteristic
   266  	// polynomial.
   267  	checkRoots := func(foundRoots [2]big.Int, prime *big.Int) {
   268  		// X^2 + X + 1 ≡ 0 (mod p)
   269  		one := big.NewInt(1)
   270  		for i := 0; i < len(foundRoots); i++ {
   271  			root := &foundRoots[i]
   272  			result := new(big.Int).Mul(root, root)
   273  			result.Add(result, root)
   274  			result.Add(result, one)
   275  			result.Mod(result, prime)
   276  			if result.Sign() != 0 {
   277  				panic(fmt.Sprintf("%[1]x^2 + %[1]x + 1 != 0 (mod %x)", root,
   278  					prime))
   279  			}
   280  		}
   281  	}
   282  	checkRoots(lambdas, curveParams.N)
   283  	checkRoots(betas, curveParams.P)
   284  
   285  	// checkVectors ensures the passed vectors satisfy the equation:
   286  	// a + b*λ ≡ 0 (mod n)
   287  	checkVectors := func(a, b *big.Int, lambda *big.Int) {
   288  		result := new(big.Int).Mul(b, lambda)
   289  		result.Add(result, a)
   290  		result.Mod(result, curveParams.N)
   291  		if result.Sign() != 0 {
   292  			panic(fmt.Sprintf("%x + %x*lambda != 0 (mod %x)", a, b,
   293  				curveParams.N))
   294  		}
   295  	}
   296  
   297  	var endoParams [2]endomorphismParams
   298  	for i := 0; i < 2; i++ {
   299  		// Calculate the linearly independent vectors needed to generate a
   300  		// balanced length-two representation of a scalar such that
   301  		// k = k1 + k2*λ (mod n) for each of the solutions.
   302  		lambda := &lambdas[i]
   303  		a1, b1, a2, b2 := endomorphismVectors(lambda)
   304  
   305  		// Ensure the derived vectors satisfy the required equation.
   306  		checkVectors(a1, b1, lambda)
   307  		checkVectors(a2, b2, lambda)
   308  
   309  		// Calculate the precomputed estimates also used when generating the
   310  		// aforementioned decomposition.
   311  		//
   312  		// z1 = floor(b2<<320 / n)
   313  		// z2 = floor(((-b1)%n)<<320) / n)
   314  		const shift = 320
   315  		z1 := new(big.Int).Lsh(b2, shift)
   316  		z1.Div(z1, curveParams.N)
   317  		z2 := new(big.Int).Neg(b1)
   318  		z2.Lsh(z2, shift)
   319  		z2.Div(z2, curveParams.N)
   320  
   321  		params := &endoParams[i]
   322  		params.lambda = lambda
   323  		params.beta = &betas[i]
   324  		params.a1 = a1
   325  		params.b1 = b1
   326  		params.a2 = a2
   327  		params.b2 = b2
   328  		params.z1 = z1
   329  		params.z2 = z2
   330  	}
   331  
   332  	return endoParams
   333  }
   334  
   335  func main() {
   336  	fi, err := os.Create("compressedbytepoints.go")
   337  	if err != nil {
   338  		log.Fatal(err)
   339  	}
   340  	defer fi.Close()
   341  
   342  	// Compress the serialized byte points.
   343  	serialized := serializedBytePoints()
   344  	var compressed bytes.Buffer
   345  	w := zlib.NewWriter(&compressed)
   346  	if _, err := w.Write(serialized); err != nil {
   347  		fmt.Println(err)
   348  		os.Exit(1)
   349  	}
   350  	w.Close()
   351  
   352  	// Encode the compressed byte points with base64.
   353  	encoded := make([]byte, base64.StdEncoding.EncodedLen(compressed.Len()))
   354  	base64.StdEncoding.Encode(encoded, compressed.Bytes())
   355  
   356  	fmt.Fprintln(fi, "// Copyright (c) 2015 The btcsuite developers")
   357  	fmt.Fprintln(fi, "// Copyright (c) 2015-2022 The Decred developers")
   358  	fmt.Fprintln(fi, "// Use of this source code is governed by an ISC")
   359  	fmt.Fprintln(fi, "// license that can be found in the LICENSE file.")
   360  	fmt.Fprintln(fi)
   361  	fmt.Fprintln(fi, "package secp256k1")
   362  	fmt.Fprintln(fi)
   363  	fmt.Fprintln(fi, "// Auto-generated file (see genprecomps.go)")
   364  	fmt.Fprintln(fi, "// DO NOT EDIT")
   365  	fmt.Fprintln(fi)
   366  	fmt.Fprintf(fi, "var compressedBytePoints = %q\n", string(encoded))
   367  	fmt.Fprintln(fi)
   368  	fmt.Fprintln(fi, "// Set accessor to a real function.")
   369  	fmt.Fprintln(fi, "func init() {")
   370  	fmt.Fprintln(fi, "	compressedBytePointsFn = func() string {")
   371  	fmt.Fprintln(fi, "		return compressedBytePoints")
   372  	fmt.Fprintln(fi, "	}")
   373  	fmt.Fprintln(fi, "}")
   374  
   375  	printParams := func(p *endomorphismParams) {
   376  		fmt.Printf("lambda: %x\n", p.lambda)
   377  		fmt.Printf("  beta: %x\n", p.beta)
   378  		fmt.Printf("    a1: %x\n", p.a1)
   379  		fmt.Printf("    b1: %x\n", p.b1)
   380  		fmt.Printf("    a2: %x\n", p.a2)
   381  		fmt.Printf("    b2: %x\n", p.b2)
   382  		fmt.Printf("    z1: %x\n", p.z1)
   383  		fmt.Printf("    z2: %x\n", p.z2)
   384  	}
   385  	endoParams := deriveEndomorphismParams()
   386  	fmt.Println("The following are the computed values to make use of the " +
   387  		"secp256k1 endomorphism.\nThey consist of the lambda and beta " +
   388  		"values along with the associated linearly independent vectors " +
   389  		"(a1, b1, a2, b2) and estimates (z1, z2) used when decomposing " +
   390  		"scalars:")
   391  	printParams(&endoParams[0])
   392  	fmt.Println()
   393  
   394  	fmt.Println("Alternatively, the following parameters are valid as well:")
   395  	printParams(&endoParams[1])
   396  }
   397
View as plain text