1// Copyright 2010 The Go Authors. All rights reserved. 2// Copyright 2011 ThePiachu. All rights reserved. 3// Copyright 2015 Jeffrey Wilcke, Felix Lange, Gustav Simonsson. All rights reserved. 4// 5// Redistribution and use in source and binary forms, with or without 6// modification, are permitted provided that the following conditions are 7// met: 8// 9// * Redistributions of source code must retain the above copyright 10// notice, this list of conditions and the following disclaimer. 11// * Redistributions in binary form must reproduce the above 12// copyright notice, this list of conditions and the following disclaimer 13// in the documentation and/or other materials provided with the 14// distribution. 15// * Neither the name of Google Inc. nor the names of its 16// contributors may be used to endorse or promote products derived from 17// this software without specific prior written permission. 18// * The name of ThePiachu may not be used to endorse or promote products 19// derived from this software without specific prior written permission. 20// 21// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 33package secp256k1 34 35import ( 36 "crypto/elliptic" 37 "math/big" 38) 39 40const ( 41 // number of bits in a big.Word 42 wordBits = 32 << (uint64(^big.Word(0)) >> 63) 43 // number of bytes in a big.Word 44 wordBytes = wordBits / 8 45) 46 47// readBits encodes the absolute value of bigint as big-endian bytes. Callers 48// must ensure that buf has enough space. If buf is too short the result will 49// be incomplete. 50func readBits(bigint *big.Int, buf []byte) { 51 i := len(buf) 52 for _, d := range bigint.Bits() { 53 for j := 0; j < wordBytes && i > 0; j++ { 54 i-- 55 buf[i] = byte(d) 56 d >>= 8 57 } 58 } 59} 60 61// This code is from https://github.com/ThePiachu/GoBit and implements 62// several Koblitz elliptic curves over prime fields. 63// 64// The curve methods, internally, on Jacobian coordinates. For a given 65// (x, y) position on the curve, the Jacobian coordinates are (x1, y1, 66// z1) where x = x1/z1² and y = y1/z1³. The greatest speedups come 67// when the whole calculation can be performed within the transform 68// (as in ScalarMult and ScalarBaseMult). But even for Add and Double, 69// it's faster to apply and reverse the transform than to operate in 70// affine coordinates. 71 72// A BitCurve represents a Koblitz Curve with a=0. 73// See http://www.hyperelliptic.org/EFD/g1p/auto-shortw.html 74type BitCurve struct { 75 P *big.Int // the order of the underlying field 76 N *big.Int // the order of the base point 77 B *big.Int // the constant of the BitCurve equation 78 Gx, Gy *big.Int // (x,y) of the base point 79 BitSize int // the size of the underlying field 80} 81 82func (BitCurve *BitCurve) Params() *elliptic.CurveParams { 83 return &elliptic.CurveParams{ 84 P: BitCurve.P, 85 N: BitCurve.N, 86 B: BitCurve.B, 87 Gx: BitCurve.Gx, 88 Gy: BitCurve.Gy, 89 BitSize: BitCurve.BitSize, 90 } 91} 92 93// IsOnCurve returns true if the given (x,y) lies on the BitCurve. 94func (BitCurve *BitCurve) IsOnCurve(x, y *big.Int) bool { 95 // y² = x³ + b 96 y2 := new(big.Int).Mul(y, y) //y² 97 y2.Mod(y2, BitCurve.P) //y²%P 98 99 x3 := new(big.Int).Mul(x, x) //x² 100 x3.Mul(x3, x) //x³ 101 102 x3.Add(x3, BitCurve.B) //x³+B 103 x3.Mod(x3, BitCurve.P) //(x³+B)%P 104 105 return x3.Cmp(y2) == 0 106} 107 108//TODO: double check if the function is okay 109// affineFromJacobian reverses the Jacobian transform. See the comment at the 110// top of the file. 111func (BitCurve *BitCurve) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) { 112 if z.Sign() == 0 { 113 return new(big.Int), new(big.Int) 114 } 115 116 zinv := new(big.Int).ModInverse(z, BitCurve.P) 117 zinvsq := new(big.Int).Mul(zinv, zinv) 118 119 xOut = new(big.Int).Mul(x, zinvsq) 120 xOut.Mod(xOut, BitCurve.P) 121 zinvsq.Mul(zinvsq, zinv) 122 yOut = new(big.Int).Mul(y, zinvsq) 123 yOut.Mod(yOut, BitCurve.P) 124 return 125} 126 127// Add returns the sum of (x1,y1) and (x2,y2) 128func (BitCurve *BitCurve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) { 129 // If one point is at infinity, return the other point. 130 // Adding the point at infinity to any point will preserve the other point. 131 if x1.Sign() == 0 && y1.Sign() == 0 { 132 return x2, y2 133 } 134 if x2.Sign() == 0 && y2.Sign() == 0 { 135 return x1, y1 136 } 137 z := new(big.Int).SetInt64(1) 138 if x1.Cmp(x2) == 0 && y1.Cmp(y2) == 0 { 139 return BitCurve.affineFromJacobian(BitCurve.doubleJacobian(x1, y1, z)) 140 } 141 return BitCurve.affineFromJacobian(BitCurve.addJacobian(x1, y1, z, x2, y2, z)) 142} 143 144// addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and 145// (x2, y2, z2) and returns their sum, also in Jacobian form. 146func (BitCurve *BitCurve) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) { 147 // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl 148 z1z1 := new(big.Int).Mul(z1, z1) 149 z1z1.Mod(z1z1, BitCurve.P) 150 z2z2 := new(big.Int).Mul(z2, z2) 151 z2z2.Mod(z2z2, BitCurve.P) 152 153 u1 := new(big.Int).Mul(x1, z2z2) 154 u1.Mod(u1, BitCurve.P) 155 u2 := new(big.Int).Mul(x2, z1z1) 156 u2.Mod(u2, BitCurve.P) 157 h := new(big.Int).Sub(u2, u1) 158 if h.Sign() == -1 { 159 h.Add(h, BitCurve.P) 160 } 161 i := new(big.Int).Lsh(h, 1) 162 i.Mul(i, i) 163 j := new(big.Int).Mul(h, i) 164 165 s1 := new(big.Int).Mul(y1, z2) 166 s1.Mul(s1, z2z2) 167 s1.Mod(s1, BitCurve.P) 168 s2 := new(big.Int).Mul(y2, z1) 169 s2.Mul(s2, z1z1) 170 s2.Mod(s2, BitCurve.P) 171 r := new(big.Int).Sub(s2, s1) 172 if r.Sign() == -1 { 173 r.Add(r, BitCurve.P) 174 } 175 r.Lsh(r, 1) 176 v := new(big.Int).Mul(u1, i) 177 178 x3 := new(big.Int).Set(r) 179 x3.Mul(x3, x3) 180 x3.Sub(x3, j) 181 x3.Sub(x3, v) 182 x3.Sub(x3, v) 183 x3.Mod(x3, BitCurve.P) 184 185 y3 := new(big.Int).Set(r) 186 v.Sub(v, x3) 187 y3.Mul(y3, v) 188 s1.Mul(s1, j) 189 s1.Lsh(s1, 1) 190 y3.Sub(y3, s1) 191 y3.Mod(y3, BitCurve.P) 192 193 z3 := new(big.Int).Add(z1, z2) 194 z3.Mul(z3, z3) 195 z3.Sub(z3, z1z1) 196 if z3.Sign() == -1 { 197 z3.Add(z3, BitCurve.P) 198 } 199 z3.Sub(z3, z2z2) 200 if z3.Sign() == -1 { 201 z3.Add(z3, BitCurve.P) 202 } 203 z3.Mul(z3, h) 204 z3.Mod(z3, BitCurve.P) 205 206 return x3, y3, z3 207} 208 209// Double returns 2*(x,y) 210func (BitCurve *BitCurve) Double(x1, y1 *big.Int) (*big.Int, *big.Int) { 211 z1 := new(big.Int).SetInt64(1) 212 return BitCurve.affineFromJacobian(BitCurve.doubleJacobian(x1, y1, z1)) 213} 214 215// doubleJacobian takes a point in Jacobian coordinates, (x, y, z), and 216// returns its double, also in Jacobian form. 217func (BitCurve *BitCurve) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) { 218 // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l 219 220 a := new(big.Int).Mul(x, x) //X1² 221 b := new(big.Int).Mul(y, y) //Y1² 222 c := new(big.Int).Mul(b, b) //B² 223 224 d := new(big.Int).Add(x, b) //X1+B 225 d.Mul(d, d) //(X1+B)² 226 d.Sub(d, a) //(X1+B)²-A 227 d.Sub(d, c) //(X1+B)²-A-C 228 d.Mul(d, big.NewInt(2)) //2*((X1+B)²-A-C) 229 230 e := new(big.Int).Mul(big.NewInt(3), a) //3*A 231 f := new(big.Int).Mul(e, e) //E² 232 233 x3 := new(big.Int).Mul(big.NewInt(2), d) //2*D 234 x3.Sub(f, x3) //F-2*D 235 x3.Mod(x3, BitCurve.P) 236 237 y3 := new(big.Int).Sub(d, x3) //D-X3 238 y3.Mul(e, y3) //E*(D-X3) 239 y3.Sub(y3, new(big.Int).Mul(big.NewInt(8), c)) //E*(D-X3)-8*C 240 y3.Mod(y3, BitCurve.P) 241 242 z3 := new(big.Int).Mul(y, z) //Y1*Z1 243 z3.Mul(big.NewInt(2), z3) //3*Y1*Z1 244 z3.Mod(z3, BitCurve.P) 245 246 return x3, y3, z3 247} 248 249// ScalarBaseMult returns k*G, where G is the base point of the group and k is 250// an integer in big-endian form. 251func (BitCurve *BitCurve) ScalarBaseMult(k []byte) (*big.Int, *big.Int) { 252 return BitCurve.ScalarMult(BitCurve.Gx, BitCurve.Gy, k) 253} 254 255// Marshal converts a point into the form specified in section 4.3.6 of ANSI 256// X9.62. 257func (BitCurve *BitCurve) Marshal(x, y *big.Int) []byte { 258 byteLen := (BitCurve.BitSize + 7) >> 3 259 ret := make([]byte, 1+2*byteLen) 260 ret[0] = 4 // uncompressed point flag 261 readBits(x, ret[1:1+byteLen]) 262 readBits(y, ret[1+byteLen:]) 263 return ret 264} 265 266// Unmarshal converts a point, serialised by Marshal, into an x, y pair. On 267// error, x = nil. 268func (BitCurve *BitCurve) Unmarshal(data []byte) (x, y *big.Int) { 269 byteLen := (BitCurve.BitSize + 7) >> 3 270 if len(data) != 1+2*byteLen { 271 return 272 } 273 if data[0] != 4 { // uncompressed form 274 return 275 } 276 x = new(big.Int).SetBytes(data[1 : 1+byteLen]) 277 y = new(big.Int).SetBytes(data[1+byteLen:]) 278 return 279} 280 281var theCurve = new(BitCurve) 282 283func init() { 284 // See SEC 2 section 2.7.1 285 // curve parameters taken from: 286 // http://www.secg.org/sec2-v2.pdf 287 theCurve.P, _ = new(big.Int).SetString("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 0) 288 theCurve.N, _ = new(big.Int).SetString("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 0) 289 theCurve.B, _ = new(big.Int).SetString("0x0000000000000000000000000000000000000000000000000000000000000007", 0) 290 theCurve.Gx, _ = new(big.Int).SetString("0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 0) 291 theCurve.Gy, _ = new(big.Int).SetString("0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 0) 292 theCurve.BitSize = 256 293} 294 295// S256 returns a BitCurve which implements secp256k1. 296func S256() *BitCurve { 297 return theCurve 298} 299