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