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