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