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 = []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 (&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 := []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 := []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 = (&big.Int{}).SetBytes(data[1 : 1+byteLen])
167 y = (&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 = (&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