vendor/github.com/btcsuite/btcd/btcec/gensecp256k1.go

   1 // Copyright (c) 2014-2015 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 // This file is ignored during the regular build due to the following build tag.
   6 // This build tag is set during go generate.
   7 // +build gensecp256k1
   8
   9 package btcec
  10
  11 // References:
  12 //   [GECC]: Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone)
  13
  14 import (
  15         "encoding/binary"
  16         "math/big"
  17 )
  18
  19 // secp256k1BytePoints are dummy points used so the code which generates the
  20 // real values can compile.
  21 var secp256k1BytePoints = ""
  22
  23 // getDoublingPoints returns all the possible G^(2^i) for i in
  24 // 0..n-1 where n is the curve's bit size (256 in the case of secp256k1)
  25 // the coordinates are recorded as Jacobian coordinates.
  26 func (curve *KoblitzCurve) getDoublingPoints() [][3]fieldVal {
  27         doublingPoints := make([][3]fieldVal, curve.BitSize)
  28
  29         // initialize px, py, pz to the Jacobian coordinates for the base point
  30         px, py := curve.bigAffineToField(curve.Gx, curve.Gy)
  31         pz := new(fieldVal).SetInt(1)
  32         for i := 0; i < curve.BitSize; i++ {
  33                 doublingPoints[i] = [3]fieldVal{*px, *py, *pz}
  34                 // P = 2*P
  35                 curve.doubleJacobian(px, py, pz, px, py, pz)
  36         }
  37         return doublingPoints
  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 // secp256k1.go.
  43 func (curve *KoblitzCurve) SerializedBytePoints() []byte {
  44         doublingPoints := curve.getDoublingPoints()
  45
  46         // Segregate the bits into byte-sized windows
  47         serialized := make([]byte, curve.byteSize*256*3*10*4)
  48         offset := 0
  49         for byteNum := 0; byteNum < curve.byteSize; byteNum++ {
  50                 // Grab the 8 bits that make up this byte from doublingPoints.
  51                 startingBit := 8 * (curve.byteSize - byteNum - 1)
  52                 computingPoints := doublingPoints[startingBit : startingBit+8]
  53
  54                 // Compute all points in this window and serialize them.
  55                 for i := 0; i < 256; i++ {
  56                         px, py, pz := new(fieldVal), new(fieldVal), new(fieldVal)
  57                         for j := 0; j < 8; j++ {
  58                                 if i>>uint(j)&1 == 1 {
  59                                         curve.addJacobian(px, py, pz, &computingPoints[j][0],
  60                                                 &computingPoints[j][1], &computingPoints[j][2], px, py, pz)
  61                                 }
  62                         }
  63                         for i := 0; i < 10; i++ {
  64                                 binary.LittleEndian.PutUint32(serialized[offset:], px.n[i])
  65                                 offset += 4
  66                         }
  67                         for i := 0; i < 10; i++ {
  68                                 binary.LittleEndian.PutUint32(serialized[offset:], py.n[i])
  69                                 offset += 4
  70                         }
  71                         for i := 0; i < 10; i++ {
  72                                 binary.LittleEndian.PutUint32(serialized[offset:], pz.n[i])
  73                                 offset += 4
  74                         }
  75                 }
  76         }
  77
  78         return serialized
  79 }
  80
  81 // sqrt returns the square root of the provided big integer using Newton's
  82 // method.  It's only compiled and used during generation of pre-computed
  83 // values, so speed is not a huge concern.
  84 func sqrt(n *big.Int) *big.Int {
  85         // Initial guess = 2^(log_2(n)/2)
  86         guess := big.NewInt(2)
  87         guess.Exp(guess, big.NewInt(int64(n.BitLen()/2)), nil)
  88
  89         // Now refine using Newton's method.
  90         big2 := big.NewInt(2)
  91         prevGuess := big.NewInt(0)
  92         for {
  93                 prevGuess.Set(guess)
  94                 guess.Add(guess, new(big.Int).Div(n, guess))
  95                 guess.Div(guess, big2)
  96                 if guess.Cmp(prevGuess) == 0 {
  97                         break
  98                 }
  99         }
 100         return guess
 101 }
 102
 103 // EndomorphismVectors runs the first 3 steps of algorithm 3.74 from [GECC] to
 104 // generate the linearly independent vectors needed to generate a balanced
 105 // length-two representation of a multiplier such that k = k1 + k2λ (mod N) and
 106 // returns them.  Since the values will always be the same given the fact that N
 107 // and λ are fixed, the final results can be accelerated by storing the
 108 // precomputed values with the curve.
 109 func (curve *KoblitzCurve) EndomorphismVectors() (a1, b1, a2, b2 *big.Int) {
 110         bigMinus1 := big.NewInt(-1)
 111
 112         // This section uses an extended Euclidean algorithm to generate a
 113         // sequence of equations:
 114         //  s[i] * N + t[i] * λ = r[i]
 115
 116         nSqrt := sqrt(curve.N)
 117         u, v := new(big.Int).Set(curve.N), new(big.Int).Set(curve.lambda)
 118         x1, y1 := big.NewInt(1), big.NewInt(0)
 119         x2, y2 := big.NewInt(0), big.NewInt(1)
 120         q, r := new(big.Int), new(big.Int)
 121         qu, qx1, qy1 := new(big.Int), new(big.Int), new(big.Int)
 122         s, t := new(big.Int), new(big.Int)
 123         ri, ti := new(big.Int), new(big.Int)
 124         a1, b1, a2, b2 = new(big.Int), new(big.Int), new(big.Int), new(big.Int)
 125         found, oneMore := false, false
 126         for u.Sign() != 0 {
 127                 // q = v/u
 128                 q.Div(v, u)
 129
 130                 // r = v - q*u
 131                 qu.Mul(q, u)
 132                 r.Sub(v, qu)
 133
 134                 // s = x2 - q*x1
 135                 qx1.Mul(q, x1)
 136                 s.Sub(x2, qx1)
 137
 138                 // t = y2 - q*y1
 139                 qy1.Mul(q, y1)
 140                 t.Sub(y2, qy1)
 141
 142                 // v = u, u = r, x2 = x1, x1 = s, y2 = y1, y1 = t
 143                 v.Set(u)
 144                 u.Set(r)
 145                 x2.Set(x1)
 146                 x1.Set(s)
 147                 y2.Set(y1)
 148                 y1.Set(t)
 149
 150                 // As soon as the remainder is less than the sqrt of n, the
 151                 // values of a1 and b1 are known.
 152                 if !found && r.Cmp(nSqrt) < 0 {
 153                         // When this condition executes ri and ti represent the
 154                         // r[i] and t[i] values such that i is the greatest
 155                         // index for which r >= sqrt(n).  Meanwhile, the current
 156                         // r and t values are r[i+1] and t[i+1], respectively.
 157
 158                         // a1 = r[i+1], b1 = -t[i+1]
 159                         a1.Set(r)
 160                         b1.Mul(t, bigMinus1)
 161                         found = true
 162                         oneMore = true
 163
 164                         // Skip to the next iteration so ri and ti are not
 165                         // modified.
 166                         continue
 167
 168                 } else if oneMore {
 169                         // When this condition executes ri and ti still
 170                         // represent the r[i] and t[i] values while the current
 171                         // r and t are r[i+2] and t[i+2], respectively.
 172
 173                         // sum1 = r[i]^2 + t[i]^2
 174                         rSquared := new(big.Int).Mul(ri, ri)
 175                         tSquared := new(big.Int).Mul(ti, ti)
 176                         sum1 := new(big.Int).Add(rSquared, tSquared)
 177
 178                         // sum2 = r[i+2]^2 + t[i+2]^2
 179                         r2Squared := new(big.Int).Mul(r, r)
 180                         t2Squared := new(big.Int).Mul(t, t)
 181                         sum2 := new(big.Int).Add(r2Squared, t2Squared)
 182
 183                         // if (r[i]^2 + t[i]^2) <= (r[i+2]^2 + t[i+2]^2)
 184                         if sum1.Cmp(sum2) <= 0 {
 185                                 // a2 = r[i], b2 = -t[i]
 186                                 a2.Set(ri)
 187                                 b2.Mul(ti, bigMinus1)
 188                         } else {
 189                                 // a2 = r[i+2], b2 = -t[i+2]
 190                                 a2.Set(r)
 191                                 b2.Mul(t, bigMinus1)
 192                         }
 193
 194                         // All done.
 195                         break
 196                 }
 197
 198                 ri.Set(r)
 199                 ti.Set(t)
 200         }
 201
 202         return a1, b1, a2, b2
 203 }