# 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
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.
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
```

View as plain text