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