1// Copyright 2013 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
5package elliptic
6
7import (
8	"crypto/internal/nistec"
9	"errors"
10	"math/big"
11)
12
13var p224 = &nistCurve[*nistec.P224Point]{
14	newPoint: nistec.NewP224Point,
15}
16
17func initP224() {
18	p224.params = &CurveParams{
19		Name:    "P-224",
20		BitSize: 224,
21		// FIPS 186-4, section D.1.2.2
22		P:  bigFromDecimal("26959946667150639794667015087019630673557916260026308143510066298881"),
23		N:  bigFromDecimal("26959946667150639794667015087019625940457807714424391721682722368061"),
24		B:  bigFromHex("b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4"),
25		Gx: bigFromHex("b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21"),
26		Gy: bigFromHex("bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"),
27	}
28}
29
30type p256Curve struct {
31	nistCurve[*nistec.P256Point]
32}
33
34var p256 = &p256Curve{nistCurve[*nistec.P256Point]{
35	newPoint: nistec.NewP256Point,
36}}
37
38func initP256() {
39	p256.params = &CurveParams{
40		Name:    "P-256",
41		BitSize: 256,
42		// FIPS 186-4, section D.1.2.3
43		P:  bigFromDecimal("115792089210356248762697446949407573530086143415290314195533631308867097853951"),
44		N:  bigFromDecimal("115792089210356248762697446949407573529996955224135760342422259061068512044369"),
45		B:  bigFromHex("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b"),
46		Gx: bigFromHex("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"),
47		Gy: bigFromHex("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"),
48	}
49}
50
51var p384 = &nistCurve[*nistec.P384Point]{
52	newPoint: nistec.NewP384Point,
53}
54
55func initP384() {
56	p384.params = &CurveParams{
57		Name:    "P-384",
58		BitSize: 384,
59		// FIPS 186-4, section D.1.2.4
60		P: bigFromDecimal("394020061963944792122790401001436138050797392704654" +
61			"46667948293404245721771496870329047266088258938001861606973112319"),
62		N: bigFromDecimal("394020061963944792122790401001436138050797392704654" +
63			"46667946905279627659399113263569398956308152294913554433653942643"),
64		B: bigFromHex("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088" +
65			"f5013875ac656398d8a2ed19d2a85c8edd3ec2aef"),
66		Gx: bigFromHex("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741" +
67			"e082542a385502f25dbf55296c3a545e3872760ab7"),
68		Gy: bigFromHex("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da31" +
69			"13b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f"),
70	}
71}
72
73var p521 = &nistCurve[*nistec.P521Point]{
74	newPoint: nistec.NewP521Point,
75}
76
77func initP521() {
78	p521.params = &CurveParams{
79		Name:    "P-521",
80		BitSize: 521,
81		// FIPS 186-4, section D.1.2.5
82		P: bigFromDecimal("68647976601306097149819007990813932172694353001433" +
83			"0540939446345918554318339765605212255964066145455497729631139148" +
84			"0858037121987999716643812574028291115057151"),
85		N: bigFromDecimal("68647976601306097149819007990813932172694353001433" +
86			"0540939446345918554318339765539424505774633321719753296399637136" +
87			"3321113864768612440380340372808892707005449"),
88		B: bigFromHex("0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8" +
89			"b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef" +
90			"451fd46b503f00"),
91		Gx: bigFromHex("00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f8" +
92			"28af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf9" +
93			"7e7e31c2e5bd66"),
94		Gy: bigFromHex("011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817" +
95			"afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088" +
96			"be94769fd16650"),
97	}
98}
99
100// nistCurve is a Curve implementation based on a nistec Point.
101//
102// It's a wrapper that exposes the big.Int-based Curve interface and encodes the
103// legacy idiosyncrasies it requires, such as invalid and infinity point
104// handling.
105//
106// To interact with the nistec package, points are encoded into and decoded from
107// properly formatted byte slices. All big.Int use is limited to this package.
108// Encoding and decoding is 1/1000th of the runtime of a scalar multiplication,
109// so the overhead is acceptable.
110type nistCurve[Point nistPoint[Point]] struct {
111	newPoint func() Point
112	params   *CurveParams
113}
114
115// nistPoint is a generic constraint for the nistec Point types.
116type nistPoint[T any] interface {
117	Bytes() []byte
118	SetBytes([]byte) (T, error)
119	Add(T, T) T
120	Double(T) T
121	ScalarMult(T, []byte) (T, error)
122	ScalarBaseMult([]byte) (T, error)
123}
124
125func (curve *nistCurve[Point]) Params() *CurveParams {
126	return curve.params
127}
128
129func (curve *nistCurve[Point]) IsOnCurve(x, y *big.Int) bool {
130	// IsOnCurve is documented to reject (0, 0), the conventional point at
131	// infinity, which however is accepted by pointFromAffine.
132	if x.Sign() == 0 && y.Sign() == 0 {
133		return false
134	}
135	_, err := curve.pointFromAffine(x, y)
136	return err == nil
137}
138
139func (curve *nistCurve[Point]) pointFromAffine(x, y *big.Int) (p Point, err error) {
140	// (0, 0) is by convention the point at infinity, which can't be represented
141	// in affine coordinates. See Issue 37294.
142	if x.Sign() == 0 && y.Sign() == 0 {
143		return curve.newPoint(), nil
144	}
145	// Reject values that would not get correctly encoded.
146	if x.Sign() < 0 || y.Sign() < 0 {
147		return p, errors.New("negative coordinate")
148	}
149	if x.BitLen() > curve.params.BitSize || y.BitLen() > curve.params.BitSize {
150		return p, errors.New("overflowing coordinate")
151	}
152	// Encode the coordinates and let SetBytes reject invalid points.
153	byteLen := (curve.params.BitSize + 7) / 8
154	buf := make([]byte, 1+2*byteLen)
155	buf[0] = 4 // uncompressed point
156	x.FillBytes(buf[1 : 1+byteLen])
157	y.FillBytes(buf[1+byteLen : 1+2*byteLen])
158	return curve.newPoint().SetBytes(buf)
159}
160
161func (curve *nistCurve[Point]) pointToAffine(p Point) (x, y *big.Int) {
162	out := p.Bytes()
163	if len(out) == 1 && out[0] == 0 {
164		// This is the encoding of the point at infinity, which the affine
165		// coordinates API represents as (0, 0) by convention.
166		return new(big.Int), new(big.Int)
167	}
168	byteLen := (curve.params.BitSize + 7) / 8
169	x = new(big.Int).SetBytes(out[1 : 1+byteLen])
170	y = new(big.Int).SetBytes(out[1+byteLen:])
171	return x, y
172}
173
174func (curve *nistCurve[Point]) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
175	p1, err := curve.pointFromAffine(x1, y1)
176	if err != nil {
177		panic("crypto/elliptic: Add was called on an invalid point")
178	}
179	p2, err := curve.pointFromAffine(x2, y2)
180	if err != nil {
181		panic("crypto/elliptic: Add was called on an invalid point")
182	}
183	return curve.pointToAffine(p1.Add(p1, p2))
184}
185
186func (curve *nistCurve[Point]) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
187	p, err := curve.pointFromAffine(x1, y1)
188	if err != nil {
189		panic("crypto/elliptic: Double was called on an invalid point")
190	}
191	return curve.pointToAffine(p.Double(p))
192}
193
194// normalizeScalar brings the scalar within the byte size of the order of the
195// curve, as expected by the nistec scalar multiplication functions.
196func (curve *nistCurve[Point]) normalizeScalar(scalar []byte) []byte {
197	byteSize := (curve.params.N.BitLen() + 7) / 8
198	if len(scalar) == byteSize {
199		return scalar
200	}
201	s := new(big.Int).SetBytes(scalar)
202	if len(scalar) > byteSize {
203		s.Mod(s, curve.params.N)
204	}
205	out := make([]byte, byteSize)
206	return s.FillBytes(out)
207}
208
209func (curve *nistCurve[Point]) ScalarMult(Bx, By *big.Int, scalar []byte) (*big.Int, *big.Int) {
210	p, err := curve.pointFromAffine(Bx, By)
211	if err != nil {
212		panic("crypto/elliptic: ScalarMult was called on an invalid point")
213	}
214	scalar = curve.normalizeScalar(scalar)
215	p, err = p.ScalarMult(p, scalar)
216	if err != nil {
217		panic("crypto/elliptic: nistec rejected normalized scalar")
218	}
219	return curve.pointToAffine(p)
220}
221
222func (curve *nistCurve[Point]) ScalarBaseMult(scalar []byte) (*big.Int, *big.Int) {
223	scalar = curve.normalizeScalar(scalar)
224	p, err := curve.newPoint().ScalarBaseMult(scalar)
225	if err != nil {
226		panic("crypto/elliptic: nistec rejected normalized scalar")
227	}
228	return curve.pointToAffine(p)
229}
230
231// CombinedMult returns [s1]G + [s2]P where G is the generator. It's used
232// through an interface upgrade in crypto/ecdsa.
233func (curve *nistCurve[Point]) CombinedMult(Px, Py *big.Int, s1, s2 []byte) (x, y *big.Int) {
234	s1 = curve.normalizeScalar(s1)
235	q, err := curve.newPoint().ScalarBaseMult(s1)
236	if err != nil {
237		panic("crypto/elliptic: nistec rejected normalized scalar")
238	}
239	p, err := curve.pointFromAffine(Px, Py)
240	if err != nil {
241		panic("crypto/elliptic: CombinedMult was called on an invalid point")
242	}
243	s2 = curve.normalizeScalar(s2)
244	p, err = p.ScalarMult(p, s2)
245	if err != nil {
246		panic("crypto/elliptic: nistec rejected normalized scalar")
247	}
248	return curve.pointToAffine(p.Add(p, q))
249}
250
251func (curve *nistCurve[Point]) Unmarshal(data []byte) (x, y *big.Int) {
252	if len(data) == 0 || data[0] != 4 {
253		return nil, nil
254	}
255	// Use SetBytes to check that data encodes a valid point.
256	_, err := curve.newPoint().SetBytes(data)
257	if err != nil {
258		return nil, nil
259	}
260	// We don't use pointToAffine because it involves an expensive field
261	// inversion to convert from Jacobian to affine coordinates, which we
262	// already have.
263	byteLen := (curve.params.BitSize + 7) / 8
264	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
265	y = new(big.Int).SetBytes(data[1+byteLen:])
266	return x, y
267}
268
269func (curve *nistCurve[Point]) UnmarshalCompressed(data []byte) (x, y *big.Int) {
270	if len(data) == 0 || (data[0] != 2 && data[0] != 3) {
271		return nil, nil
272	}
273	p, err := curve.newPoint().SetBytes(data)
274	if err != nil {
275		return nil, nil
276	}
277	return curve.pointToAffine(p)
278}
279
280func bigFromDecimal(s string) *big.Int {
281	b, ok := new(big.Int).SetString(s, 10)
282	if !ok {
283		panic("crypto/elliptic: internal error: invalid encoding")
284	}
285	return b
286}
287
288func bigFromHex(s string) *big.Int {
289	b, ok := new(big.Int).SetString(s, 16)
290	if !ok {
291		panic("crypto/elliptic: internal error: invalid encoding")
292	}
293	return b
294}
295