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

View as plain text