libgo/go/crypto/elliptic/elliptic.go

   1 // Copyright 2010 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Package elliptic implements several standard elliptic curves over prime
   6 // fields.
   7 package elliptic
   8
   9 // This package operates, internally, on Jacobian coordinates. For a given
  10 // (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1)
  11 // where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole
  12 // calculation can be performed within the transform (as in ScalarMult and
  13 // ScalarBaseMult). But even for Add and Double, it's faster to apply and
  14 // reverse the transform than to operate in affine coordinates.
  15
  16 import (
  17         "io"
  18         "math/big"
  19         "sync"
  20 )
  21
  22 // A Curve represents a short-form Weierstrass curve with a=-3.
  23 // See http://www.hyperelliptic.org/EFD/g1p/auto-shortw.html
  24 type Curve interface {
  25         // Params returns the parameters for the curve.
  26         Params() *CurveParams
  27         // IsOnCurve returns true if the given (x,y) lies on the curve.
  28         IsOnCurve(x, y *big.Int) bool
  29         // Add returns the sum of (x1,y1) and (x2,y2)
  30         Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
  31         // Double returns 2*(x,y)
  32         Double(x1, y1 *big.Int) (x, y *big.Int)
  33         // ScalarMult returns k*(Bx,By) where k is a number in big-endian form.
  34         ScalarMult(x1, y1 *big.Int, scalar []byte) (x, y *big.Int)
  35         // ScalarBaseMult returns k*G, where G is the base point of the group and k
  36         // is an integer in big-endian form.
  37         ScalarBaseMult(scalar []byte) (x, y *big.Int)
  38 }
  39
  40 // CurveParams contains the parameters of an elliptic curve and also provides
  41 // a generic, non-constant time implementation of Curve.
  42 type CurveParams struct {
  43         P       *big.Int // the order of the underlying field
  44         N       *big.Int // the order of the base point
  45         B       *big.Int // the constant of the curve equation
  46         Gx, Gy  *big.Int // (x,y) of the base point
  47         BitSize int      // the size of the underlying field
  48 }
  49
  50 func (curve *CurveParams) Params() *CurveParams {
  51         return curve
  52 }
  53
  54 func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
  55         // y² = x³ - 3x + b
  56         y2 := new(big.Int).Mul(y, y)
  57         y2.Mod(y2, curve.P)
  58
  59         x3 := new(big.Int).Mul(x, x)
  60         x3.Mul(x3, x)
  61
  62         threeX := new(big.Int).Lsh(x, 1)
  63         threeX.Add(threeX, x)
  64
  65         x3.Sub(x3, threeX)
  66         x3.Add(x3, curve.B)
  67         x3.Mod(x3, curve.P)
  68
  69         return x3.Cmp(y2) == 0
  70 }
  71
  72 // affineFromJacobian reverses the Jacobian transform. See the comment at the
  73 // top of the file.
  74 func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
  75         zinv := new(big.Int).ModInverse(z, curve.P)
  76         zinvsq := new(big.Int).Mul(zinv, zinv)
  77
  78         xOut = new(big.Int).Mul(x, zinvsq)
  79         xOut.Mod(xOut, curve.P)
  80         zinvsq.Mul(zinvsq, zinv)
  81         yOut = new(big.Int).Mul(y, zinvsq)
  82         yOut.Mod(yOut, curve.P)
  83         return
  84 }
  85
  86 func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
  87         z := new(big.Int).SetInt64(1)
  88         return curve.affineFromJacobian(curve.addJacobian(x1, y1, z, x2, y2, z))
  89 }
  90
  91 // addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and
  92 // (x2, y2, z2) and returns their sum, also in Jacobian form.
  93 func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
  94         // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl
  95         z1z1 := new(big.Int).Mul(z1, z1)
  96         z1z1.Mod(z1z1, curve.P)
  97         z2z2 := new(big.Int).Mul(z2, z2)
  98         z2z2.Mod(z2z2, curve.P)
  99
 100         u1 := new(big.Int).Mul(x1, z2z2)
 101         u1.Mod(u1, curve.P)
 102         u2 := new(big.Int).Mul(x2, z1z1)
 103         u2.Mod(u2, curve.P)
 104         h := new(big.Int).Sub(u2, u1)
 105         if h.Sign() == -1 {
 106                 h.Add(h, curve.P)
 107         }
 108         i := new(big.Int).Lsh(h, 1)
 109         i.Mul(i, i)
 110         j := new(big.Int).Mul(h, i)
 111
 112         s1 := new(big.Int).Mul(y1, z2)
 113         s1.Mul(s1, z2z2)
 114         s1.Mod(s1, curve.P)
 115         s2 := new(big.Int).Mul(y2, z1)
 116         s2.Mul(s2, z1z1)
 117         s2.Mod(s2, curve.P)
 118         r := new(big.Int).Sub(s2, s1)
 119         if r.Sign() == -1 {
 120                 r.Add(r, curve.P)
 121         }
 122         r.Lsh(r, 1)
 123         v := new(big.Int).Mul(u1, i)
 124
 125         x3 := new(big.Int).Set(r)
 126         x3.Mul(x3, x3)
 127         x3.Sub(x3, j)
 128         x3.Sub(x3, v)
 129         x3.Sub(x3, v)
 130         x3.Mod(x3, curve.P)
 131
 132         y3 := new(big.Int).Set(r)
 133         v.Sub(v, x3)
 134         y3.Mul(y3, v)
 135         s1.Mul(s1, j)
 136         s1.Lsh(s1, 1)
 137         y3.Sub(y3, s1)
 138         y3.Mod(y3, curve.P)
 139
 140         z3 := new(big.Int).Add(z1, z2)
 141         z3.Mul(z3, z3)
 142         z3.Sub(z3, z1z1)
 143         if z3.Sign() == -1 {
 144                 z3.Add(z3, curve.P)
 145         }
 146         z3.Sub(z3, z2z2)
 147         if z3.Sign() == -1 {
 148                 z3.Add(z3, curve.P)
 149         }
 150         z3.Mul(z3, h)
 151         z3.Mod(z3, curve.P)
 152
 153         return x3, y3, z3
 154 }
 155
 156 func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
 157         z1 := new(big.Int).SetInt64(1)
 158         return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
 159 }
 160
 161 // doubleJacobian takes a point in Jacobian coordinates, (x, y, z), and
 162 // returns its double, also in Jacobian form.
 163 func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
 164         // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
 165         delta := new(big.Int).Mul(z, z)
 166         delta.Mod(delta, curve.P)
 167         gamma := new(big.Int).Mul(y, y)
 168         gamma.Mod(gamma, curve.P)
 169         alpha := new(big.Int).Sub(x, delta)
 170         if alpha.Sign() == -1 {
 171                 alpha.Add(alpha, curve.P)
 172         }
 173         alpha2 := new(big.Int).Add(x, delta)
 174         alpha.Mul(alpha, alpha2)
 175         alpha2.Set(alpha)
 176         alpha.Lsh(alpha, 1)
 177         alpha.Add(alpha, alpha2)
 178
 179         beta := alpha2.Mul(x, gamma)
 180
 181         x3 := new(big.Int).Mul(alpha, alpha)
 182         beta8 := new(big.Int).Lsh(beta, 3)
 183         x3.Sub(x3, beta8)
 184         for x3.Sign() == -1 {
 185                 x3.Add(x3, curve.P)
 186         }
 187         x3.Mod(x3, curve.P)
 188
 189         z3 := new(big.Int).Add(y, z)
 190         z3.Mul(z3, z3)
 191         z3.Sub(z3, gamma)
 192         if z3.Sign() == -1 {
 193                 z3.Add(z3, curve.P)
 194         }
 195         z3.Sub(z3, delta)
 196         if z3.Sign() == -1 {
 197                 z3.Add(z3, curve.P)
 198         }
 199         z3.Mod(z3, curve.P)
 200
 201         beta.Lsh(beta, 2)
 202         beta.Sub(beta, x3)
 203         if beta.Sign() == -1 {
 204                 beta.Add(beta, curve.P)
 205         }
 206         y3 := alpha.Mul(alpha, beta)
 207
 208         gamma.Mul(gamma, gamma)
 209         gamma.Lsh(gamma, 3)
 210         gamma.Mod(gamma, curve.P)
 211
 212         y3.Sub(y3, gamma)
 213         if y3.Sign() == -1 {
 214                 y3.Add(y3, curve.P)
 215         }
 216         y3.Mod(y3, curve.P)
 217
 218         return x3, y3, z3
 219 }
 220
 221 func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
 222         // We have a slight problem in that the identity of the group (the
 223         // point at infinity) cannot be represented in (x, y) form on a finite
 224         // machine. Thus the standard add/double algorithm has to be tweaked
 225         // slightly: our initial state is not the identity, but x, and we
 226         // ignore the first true bit in |k|.  If we don't find any true bits in
 227         // |k|, then we return nil, nil, because we cannot return the identity
 228         // element.
 229
 230         Bz := new(big.Int).SetInt64(1)
 231         x := Bx
 232         y := By
 233         z := Bz
 234
 235         seenFirstTrue := false
 236         for _, byte := range k {
 237                 for bitNum := 0; bitNum < 8; bitNum++ {
 238                         if seenFirstTrue {
 239                                 x, y, z = curve.doubleJacobian(x, y, z)
 240                         }
 241                         if byte&0x80 == 0x80 {
 242                                 if !seenFirstTrue {
 243                                         seenFirstTrue = true
 244                                 } else {
 245                                         x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
 246                                 }
 247                         }
 248                         byte <<= 1
 249                 }
 250         }
 251
 252         if !seenFirstTrue {
 253                 return nil, nil
 254         }
 255
 256         return curve.affineFromJacobian(x, y, z)
 257 }
 258
 259 func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
 260         return curve.ScalarMult(curve.Gx, curve.Gy, k)
 261 }
 262
 263 var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
 264
 265 // GenerateKey returns a public/private key pair. The private key is
 266 // generated using the given reader, which must return random data.
 267 func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
 268         bitSize := curve.Params().BitSize
 269         byteLen := (bitSize + 7) >> 3
 270         priv = make([]byte, byteLen)
 271
 272         for x == nil {
 273                 _, err = io.ReadFull(rand, priv)
 274                 if err != nil {
 275                         return
 276                 }
 277                 // We have to mask off any excess bits in the case that the size of the
 278                 // underlying field is not a whole number of bytes.
 279                 priv[0] &= mask[bitSize%8]
 280                 // This is because, in tests, rand will return all zeros and we don't
 281                 // want to get the point at infinity and loop forever.
 282                 priv[1] ^= 0x42
 283                 x, y = curve.ScalarBaseMult(priv)
 284         }
 285         return
 286 }
 287
 288 // Marshal converts a point into the form specified in section 4.3.6 of ANSI X9.62.
 289 func Marshal(curve Curve, x, y *big.Int) []byte {
 290         byteLen := (curve.Params().BitSize + 7) >> 3
 291
 292         ret := make([]byte, 1+2*byteLen)
 293         ret[0] = 4 // uncompressed point
 294
 295         xBytes := x.Bytes()
 296         copy(ret[1+byteLen-len(xBytes):], xBytes)
 297         yBytes := y.Bytes()
 298         copy(ret[1+2*byteLen-len(yBytes):], yBytes)
 299         return ret
 300 }
 301
 302 // Unmarshal converts a point, serialized by Marshal, into an x, y pair. On error, x = nil.
 303 func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
 304         byteLen := (curve.Params().BitSize + 7) >> 3
 305         if len(data) != 1+2*byteLen {
 306                 return
 307         }
 308         if data[0] != 4 { // uncompressed form
 309                 return
 310         }
 311         x = new(big.Int).SetBytes(data[1 : 1+byteLen])
 312         y = new(big.Int).SetBytes(data[1+byteLen:])
 313         return
 314 }
 315
 316 var initonce sync.Once
 317 var p256 *CurveParams
 318 var p384 *CurveParams
 319 var p521 *CurveParams
 320
 321 func initAll() {
 322         initP224()
 323         initP256()
 324         initP384()
 325         initP521()
 326 }
 327
 328 func initP256() {
 329         // See FIPS 186-3, section D.2.3
 330         p256 = new(CurveParams)
 331         p256.P, _ = new(big.Int).SetString("115792089210356248762697446949407573530086143415290314195533631308867097853951", 10)
 332         p256.N, _ = new(big.Int).SetString("115792089210356248762697446949407573529996955224135760342422259061068512044369", 10)
 333         p256.B, _ = new(big.Int).SetString("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16)
 334         p256.Gx, _ = new(big.Int).SetString("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16)
 335         p256.Gy, _ = new(big.Int).SetString("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16)
 336         p256.BitSize = 256
 337 }
 338
 339 func initP384() {
 340         // See FIPS 186-3, section D.2.4
 341         p384 = new(CurveParams)
 342         p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)
 343         p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
 344         p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
 345         p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)
 346         p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)
 347         p384.BitSize = 384
 348 }
 349
 350 func initP521() {
 351         // See FIPS 186-3, section D.2.5
 352         p521 = new(CurveParams)
 353         p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)
 354         p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
 355         p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)
 356         p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)
 357         p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)
 358         p521.BitSize = 521
 359 }
 360
 361 // P256 returns a Curve which implements P-256 (see FIPS 186-3, section D.2.3)
 362 func P256() Curve {
 363         initonce.Do(initAll)
 364         return p256
 365 }
 366
 367 // P384 returns a Curve which implements P-384 (see FIPS 186-3, section D.2.4)
 368 func P384() Curve {
 369         initonce.Do(initAll)
 370         return p384
 371 }
 372
 373 // P256 returns a Curve which implements P-521 (see FIPS 186-3, section D.2.5)
 374 func P521() Curve {
 375         initonce.Do(initAll)
 376         return p521
 377 }