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 the standard NIST P-224, P-256, P-384, and P-521 6 // elliptic curves over prime fields. 7 package elliptic 8 9 import ( 10 "io" 11 "math/big" 12 "sync" 13 ) 14 15 // A Curve represents a short-form Weierstrass curve with a=-3. 16 // 17 // The behavior of Add, Double, and ScalarMult when the input is not a point on 18 // the curve is undefined. 19 // 20 // Note that the conventional point at infinity (0, 0) is not considered on the 21 // curve, although it can be returned by Add, Double, ScalarMult, or 22 // ScalarBaseMult (but not the Unmarshal or UnmarshalCompressed functions). 23 type Curve interface { 24 // Params returns the parameters for the curve. 25 Params() *CurveParams 26 // IsOnCurve reports whether the given (x,y) lies on the curve. 27 IsOnCurve(x, y *big.Int) bool 28 // Add returns the sum of (x1,y1) and (x2,y2) 29 Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int) 30 // Double returns 2*(x,y) 31 Double(x1, y1 *big.Int) (x, y *big.Int) 32 // ScalarMult returns k*(Bx,By) where k is a number in big-endian form. 33 ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int) 34 // ScalarBaseMult returns k*G, where G is the base point of the group 35 // and k is an integer in big-endian form. 36 ScalarBaseMult(k []byte) (x, y *big.Int) 37 } 38 39 var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f} 40 41 // GenerateKey returns a public/private key pair. The private key is 42 // generated using the given reader, which must return random data. 43 func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) { 44 N := curve.Params().N 45 bitSize := N.BitLen() 46 byteLen := (bitSize + 7) / 8 47 priv = make([]byte, byteLen) 48 49 for x == nil { 50 _, err = io.ReadFull(rand, priv) 51 if err != nil { 52 return 53 } 54 // We have to mask off any excess bits in the case that the size of the 55 // underlying field is not a whole number of bytes. 56 priv[0] &= mask[bitSize%8] 57 // This is because, in tests, rand will return all zeros and we don't 58 // want to get the point at infinity and loop forever. 59 priv[1] ^= 0x42 60 61 // If the scalar is out of range, sample another random number. 62 if new(big.Int).SetBytes(priv).Cmp(N) >= 0 { 63 continue 64 } 65 66 x, y = curve.ScalarBaseMult(priv) 67 } 68 return 69 } 70 71 // Marshal converts a point on the curve into the uncompressed form specified in 72 // SEC 1, Version 2.0, Section 2.3.3. If the point is not on the curve (or is 73 // the conventional point at infinity), the behavior is undefined. 74 func Marshal(curve Curve, x, y *big.Int) []byte { 75 panicIfNotOnCurve(curve, x, y) 76 77 byteLen := (curve.Params().BitSize + 7) / 8 78 79 ret := make([]byte, 1+2*byteLen) 80 ret[0] = 4 // uncompressed point 81 82 x.FillBytes(ret[1 : 1+byteLen]) 83 y.FillBytes(ret[1+byteLen : 1+2*byteLen]) 84 85 return ret 86 } 87 88 // MarshalCompressed converts a point on the curve into the compressed form 89 // specified in SEC 1, Version 2.0, Section 2.3.3. If the point is not on the 90 // curve (or is the conventional point at infinity), the behavior is undefined. 91 func MarshalCompressed(curve Curve, x, y *big.Int) []byte { 92 panicIfNotOnCurve(curve, x, y) 93 byteLen := (curve.Params().BitSize + 7) / 8 94 compressed := make([]byte, 1+byteLen) 95 compressed[0] = byte(y.Bit(0)) | 2 96 x.FillBytes(compressed[1:]) 97 return compressed 98 } 99 100 // unmarshaler is implemented by curves with their own constant-time Unmarshal. 101 // 102 // There isn't an equivalent interface for Marshal/MarshalCompressed because 103 // that doesn't involve any mathematical operations, only FillBytes and Bit. 104 type unmarshaler interface { 105 Unmarshal([]byte) (x, y *big.Int) 106 UnmarshalCompressed([]byte) (x, y *big.Int) 107 } 108 109 // Assert that the known curves implement unmarshaler. 110 var _ = []unmarshaler{p224, p256, p384, p521} 111 112 // Unmarshal converts a point, serialized by Marshal, into an x, y pair. It is 113 // an error if the point is not in uncompressed form, is not on the curve, or is 114 // the point at infinity. On error, x = nil. 115 func Unmarshal(curve Curve, data []byte) (x, y *big.Int) { 116 if c, ok := curve.(unmarshaler); ok { 117 return c.Unmarshal(data) 118 } 119 120 byteLen := (curve.Params().BitSize + 7) / 8 121 if len(data) != 1+2*byteLen { 122 return nil, nil 123 } 124 if data[0] != 4 { // uncompressed form 125 return nil, nil 126 } 127 p := curve.Params().P 128 x = new(big.Int).SetBytes(data[1 : 1+byteLen]) 129 y = new(big.Int).SetBytes(data[1+byteLen:]) 130 if x.Cmp(p) >= 0 || y.Cmp(p) >= 0 { 131 return nil, nil 132 } 133 if !curve.IsOnCurve(x, y) { 134 return nil, nil 135 } 136 return 137 } 138 139 // UnmarshalCompressed converts a point, serialized by MarshalCompressed, into 140 // an x, y pair. It is an error if the point is not in compressed form, is not 141 // on the curve, or is the point at infinity. On error, x = nil. 142 func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) { 143 if c, ok := curve.(unmarshaler); ok { 144 return c.UnmarshalCompressed(data) 145 } 146 147 byteLen := (curve.Params().BitSize + 7) / 8 148 if len(data) != 1+byteLen { 149 return nil, nil 150 } 151 if data[0] != 2 && data[0] != 3 { // compressed form 152 return nil, nil 153 } 154 p := curve.Params().P 155 x = new(big.Int).SetBytes(data[1:]) 156 if x.Cmp(p) >= 0 { 157 return nil, nil 158 } 159 // y² = x³ - 3x + b 160 y = curve.Params().polynomial(x) 161 y = y.ModSqrt(y, p) 162 if y == nil { 163 return nil, nil 164 } 165 if byte(y.Bit(0)) != data[0]&1 { 166 y.Neg(y).Mod(y, p) 167 } 168 if !curve.IsOnCurve(x, y) { 169 return nil, nil 170 } 171 return 172 } 173 174 func panicIfNotOnCurve(curve Curve, x, y *big.Int) { 175 // (0, 0) is the point at infinity by convention. It's ok to operate on it, 176 // although IsOnCurve is documented to return false for it. See Issue 37294. 177 if x.Sign() == 0 && y.Sign() == 0 { 178 return 179 } 180 181 if !curve.IsOnCurve(x, y) { 182 panic("crypto/elliptic: attempted operation on invalid point") 183 } 184 } 185 186 var initonce sync.Once 187 188 func initAll() { 189 initP224() 190 initP256() 191 initP384() 192 initP521() 193 } 194 195 // P224 returns a Curve which implements NIST P-224 (FIPS 186-3, section D.2.2), 196 // also known as secp224r1. The CurveParams.Name of this Curve is "P-224". 197 // 198 // Multiple invocations of this function will return the same value, so it can 199 // be used for equality checks and switch statements. 200 // 201 // The cryptographic operations are implemented using constant-time algorithms. 202 func P224() Curve { 203 initonce.Do(initAll) 204 return p224 205 } 206 207 // P256 returns a Curve which implements NIST P-256 (FIPS 186-3, section D.2.3), 208 // also known as secp256r1 or prime256v1. The CurveParams.Name of this Curve is 209 // "P-256". 210 // 211 // Multiple invocations of this function will return the same value, so it can 212 // be used for equality checks and switch statements. 213 // 214 // The cryptographic operations are implemented using constant-time algorithms. 215 func P256() Curve { 216 initonce.Do(initAll) 217 return p256 218 } 219 220 // P384 returns a Curve which implements NIST P-384 (FIPS 186-3, section D.2.4), 221 // also known as secp384r1. The CurveParams.Name of this Curve is "P-384". 222 // 223 // Multiple invocations of this function will return the same value, so it can 224 // be used for equality checks and switch statements. 225 // 226 // The cryptographic operations are implemented using constant-time algorithms. 227 func P384() Curve { 228 initonce.Do(initAll) 229 return p384 230 } 231 232 // P521 returns a Curve which implements NIST P-521 (FIPS 186-3, section D.2.5), 233 // also known as secp521r1. The CurveParams.Name of this Curve is "P-521". 234 // 235 // Multiple invocations of this function will return the same value, so it can 236 // be used for equality checks and switch statements. 237 // 238 // The cryptographic operations are implemented using constant-time algorithms. 239 func P521() Curve { 240 initonce.Do(initAll) 241 return p521 242 } 243