1 // Copyright 2024 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 ecdh
6 7 import (
8 "bytes"
9 "crypto/internal/fips140"
10 "crypto/internal/fips140/drbg"
11 "crypto/internal/fips140/nistec"
12 "crypto/internal/fips140deps/byteorder"
13 "errors"
14 "io"
15 "math/bits"
16 )
17 18 // PrivateKey and PublicKey are not generic to make it possible to use them
19 // in other types without instantiating them with a specific point type.
20 // They are tied to one of the Curve types below through the curveID field.
21 22 // All this is duplicated from crypto/internal/fips/ecdsa, but the standards are
23 // different and FIPS 140 does not allow reusing keys across them.
24 25 type PrivateKey struct {
26 pub PublicKey
27 d []byte // bigmod.(*Nat).Bytes output (fixed length)
28 }
29 30 func (priv *PrivateKey) Bytes() []byte {
31 return priv.d
32 }
33 34 func (priv *PrivateKey) PublicKey() *PublicKey {
35 return &priv.pub
36 }
37 38 type PublicKey struct {
39 curve curveID
40 q []byte // uncompressed nistec Point.Bytes output
41 }
42 43 func (pub *PublicKey) Bytes() []byte {
44 return pub.q
45 }
46 47 type curveID string
48 49 const (
50 p224 curveID = "P-224"
51 p256 curveID = "P-256"
52 p384 curveID = "P-384"
53 p521 curveID = "P-521"
54 )
55 56 type Curve[P Point[P]] struct {
57 curve curveID
58 newPoint func() P
59 N []byte
60 }
61 62 // Point is a generic constraint for the [nistec] Point types.
63 type Point[P any] interface {
64 *nistec.P224Point | *nistec.P256Point | *nistec.P384Point | *nistec.P521Point
65 Bytes() []byte
66 BytesX() ([]byte, error)
67 SetBytes([]byte) (P, error)
68 ScalarMult(P, []byte) (P, error)
69 ScalarBaseMult([]byte) (P, error)
70 }
71 72 func P224() *Curve[*nistec.P224Point] {
73 return &Curve[*nistec.P224Point]{
74 curve: p224,
75 newPoint: nistec.NewP224Point,
76 N: p224Order,
77 }
78 }
79 80 var p224Order = []byte{
81 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
82 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x16, 0xa2,
83 0xe0, 0xb8, 0xf0, 0x3e, 0x13, 0xdd, 0x29, 0x45,
84 0x5c, 0x5c, 0x2a, 0x3d,
85 }
86 87 func P256() *Curve[*nistec.P256Point] {
88 return &Curve[*nistec.P256Point]{
89 curve: p256,
90 newPoint: nistec.NewP256Point,
91 N: p256Order,
92 }
93 }
94 95 var p256Order = []byte{
96 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
97 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
98 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
99 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51,
100 }
101 102 func P384() *Curve[*nistec.P384Point] {
103 return &Curve[*nistec.P384Point]{
104 curve: p384,
105 newPoint: nistec.NewP384Point,
106 N: p384Order,
107 }
108 }
109 110 var p384Order = []byte{
111 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
112 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
113 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
114 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
115 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
116 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73,
117 }
118 119 func P521() *Curve[*nistec.P521Point] {
120 return &Curve[*nistec.P521Point]{
121 curve: p521,
122 newPoint: nistec.NewP521Point,
123 N: p521Order,
124 }
125 }
126 127 var p521Order = []byte{0x01, 0xff,
128 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
129 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
130 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
131 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa,
132 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b,
133 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09, 0xa5, 0xd0,
134 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae,
135 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09,
136 }
137 138 // GenerateKey generates a new ECDSA private key pair for the specified curve.
139 func GenerateKey[P Point[P]](c *Curve[P], rand io.Reader) (*PrivateKey, error) {
140 fips140.RecordApproved()
141 // This procedure is equivalent to Key Pair Generation by Testing
142 // Candidates, specified in NIST SP 800-56A Rev. 3, Section 5.6.1.2.2.
143 144 for {
145 key := []byte{:len(c.N)}
146 if err := drbg.ReadWithReader(rand, key); err != nil {
147 return nil, err
148 }
149 // In tests, rand will return all zeros and NewPrivateKey will reject
150 // the zero key as it generates the identity as a public key. This also
151 // makes this function consistent with crypto/elliptic.GenerateKey.
152 key[1] ^= 0x42
153 154 // Mask off any excess bits if the size of the underlying field is not a
155 // whole number of bytes, which is only the case for P-521.
156 if c.curve == p521 && c.N[0]&0b1111_1110 == 0 {
157 key[0] &= 0b0000_0001
158 }
159 160 privateKey, err := NewPrivateKey(c, key)
161 if err != nil {
162 continue
163 }
164 165 // A "Pairwise Consistency Test" makes no sense if we just generated the
166 // public key from an ephemeral private key. Moreover, there is no way to
167 // check it aside from redoing the exact same computation again. SP 800-56A
168 // Rev. 3, Section 5.6.2.1.4 acknowledges that, and doesn't require it.
169 // However, ISO 19790:2012, Section 7.10.3.3 has a blanket requirement for a
170 // PCT for all generated keys (AS10.35) and FIPS 140-3 IG 10.3.A, Additional
171 // Comment 1 goes out of its way to say that "the PCT shall be performed
172 // consistent [...], even if the underlying standard does not require a
173 // PCT". So we do it. And make ECDH nearly 50% slower (only) in FIPS mode.
174 fips140.PCT("ECDH PCT", func() error {
175 p1, err := c.newPoint().ScalarBaseMult(privateKey.d)
176 if err != nil {
177 return err
178 }
179 if !bytes.Equal(p1.Bytes(), privateKey.pub.q) {
180 return errors.New("crypto/ecdh: public key does not match private key")
181 }
182 return nil
183 })
184 185 return privateKey, nil
186 }
187 }
188 189 func NewPrivateKey[P Point[P]](c *Curve[P], key []byte) (*PrivateKey, error) {
190 // SP 800-56A Rev. 3, Section 5.6.1.2.2 checks that c <= n – 2 and then
191 // returns d = c + 1. Note that it follows that 0 < d < n. Equivalently,
192 // we check that 0 < d < n, and return d.
193 if len(key) != len(c.N) || isZero(key) || !isLess(key, c.N) {
194 return nil, errors.New("crypto/ecdh: invalid private key")
195 }
196 197 p, err := c.newPoint().ScalarBaseMult(key)
198 if err != nil {
199 // This is unreachable because the only error condition of
200 // ScalarBaseMult is if the input is not the right size.
201 panic("crypto/ecdh: internal error: nistec ScalarBaseMult failed for a fixed-size input")
202 }
203 204 publicKey := p.Bytes()
205 if len(publicKey) == 1 {
206 // The encoding of the identity is a single 0x00 byte. This is
207 // unreachable because the only scalar that generates the identity is
208 // zero, which is rejected above.
209 panic("crypto/ecdh: internal error: public key is the identity element")
210 }
211 212 k := &PrivateKey{d: bytes.Clone(key), pub: PublicKey{curve: c.curve, q: publicKey}}
213 return k, nil
214 }
215 216 func NewPublicKey[P Point[P]](c *Curve[P], key []byte) (*PublicKey, error) {
217 // Reject the point at infinity and compressed encodings.
218 if len(key) == 0 || key[0] != 4 {
219 return nil, errors.New("crypto/ecdh: invalid public key")
220 }
221 222 // SetBytes checks that x and y are in the interval [0, p - 1], and that
223 // the point is on the curve. Along with the rejection of the point at
224 // infinity (the identity element) above, this fulfills the requirements
225 // of NIST SP 800-56A Rev. 3, Section 5.6.2.3.4.
226 if _, err := c.newPoint().SetBytes(key); err != nil {
227 return nil, err
228 }
229 230 return &PublicKey{curve: c.curve, q: bytes.Clone(key)}, nil
231 }
232 233 func ECDH[P Point[P]](c *Curve[P], k *PrivateKey, peer *PublicKey) ([]byte, error) {
234 fipsSelfTest()
235 fips140.RecordApproved()
236 return ecdh(c, k, peer)
237 }
238 239 func ecdh[P Point[P]](c *Curve[P], k *PrivateKey, peer *PublicKey) ([]byte, error) {
240 if c.curve != k.pub.curve {
241 return nil, errors.New("crypto/ecdh: mismatched curves")
242 }
243 if k.pub.curve != peer.curve {
244 return nil, errors.New("crypto/ecdh: mismatched curves")
245 }
246 247 // This applies the Shared Secret Computation of the Ephemeral Unified Model
248 // scheme specified in NIST SP 800-56A Rev. 3, Section 6.1.2.2.
249 250 // Per Section 5.6.2.3.4, Step 1, reject the identity element (0x00).
251 if len(k.pub.q) == 1 {
252 return nil, errors.New("crypto/ecdh: public key is the identity element")
253 }
254 255 // SetBytes checks that (x, y) are reduced modulo p, and that they are on
256 // the curve, performing Steps 2-3 of Section 5.6.2.3.4.
257 p, err := c.newPoint().SetBytes(peer.q)
258 if err != nil {
259 return nil, err
260 }
261 262 // Compute P according to Section 5.7.1.2.
263 if _, err := p.ScalarMult(p, k.d); err != nil {
264 return nil, err
265 }
266 267 // BytesX checks that the result is not the identity element, and returns the
268 // x-coordinate of the result, performing Steps 2-5 of Section 5.7.1.2.
269 return p.BytesX()
270 }
271 272 // isZero reports whether x is all zeroes in constant time.
273 func isZero(x []byte) bool {
274 var acc byte
275 for _, b := range x {
276 acc |= b
277 }
278 return acc == 0
279 }
280 281 // isLess reports whether a < b, where a and b are big-endian buffers of the
282 // same length and shorter than 72 bytes.
283 func isLess(a, b []byte) bool {
284 if len(a) != len(b) {
285 panic("crypto/ecdh: internal error: mismatched isLess inputs")
286 }
287 288 // Copy the values into a fixed-size preallocated little-endian buffer.
289 // 72 bytes is enough for every scalar in this package, and having a fixed
290 // size lets us avoid heap allocations.
291 if len(a) > 72 {
292 panic("crypto/ecdh: internal error: isLess input too large")
293 }
294 bufA, bufB := []byte{:72}, []byte{:72}
295 for i := range a {
296 bufA[i], bufB[i] = a[len(a)-i-1], b[len(b)-i-1]
297 }
298 299 // Perform a subtraction with borrow.
300 var borrow uint64
301 for i := 0; i < len(bufA); i += 8 {
302 limbA, limbB := byteorder.LEUint64(bufA[i:]), byteorder.LEUint64(bufB[i:])
303 _, borrow = bits.Sub64(limbA, limbB, borrow)
304 }
305 306 // If there is a borrow at the end of the operation, then a < b.
307 return borrow == 1
308 }
309