x25519.go

     1  // Copyright 2022 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/edwards25519/field"
    10  	"crypto/internal/fips140only"
    11  	"crypto/internal/randutil"
    12  	"errors"
    13  	"io"
    14  )
    15  
    16  var (
    17  	x25519PublicKeySize    = 32
    18  	x25519PrivateKeySize   = 32
    19  	x25519SharedSecretSize = 32
    20  )
    21  
    22  // X25519 returns a [Curve] which implements the X25519 function over Curve25519
    23  // (RFC 7748, Section 5).
    24  //
    25  // Multiple invocations of this function will return the same value, so it can
    26  // be used for equality checks and switch statements.
    27  func X25519() Curve { return x25519 }
    28  
    29  var x25519 = &x25519Curve{}
    30  
    31  type x25519Curve struct{}
    32  
    33  func (c *x25519Curve) String() string {
    34  	return "X25519"
    35  }
    36  
    37  func (c *x25519Curve) GenerateKey(rand io.Reader) (*PrivateKey, error) {
    38  	if fips140only.Enabled {
    39  		return nil, errors.New("crypto/ecdh: use of X25519 is not allowed in FIPS 140-only mode")
    40  	}
    41  	key := make([]byte, x25519PrivateKeySize)
    42  	randutil.MaybeReadByte(rand)
    43  	if _, err := io.ReadFull(rand, key); err != nil {
    44  		return nil, err
    45  	}
    46  	return c.NewPrivateKey(key)
    47  }
    48  
    49  func (c *x25519Curve) NewPrivateKey(key []byte) (*PrivateKey, error) {
    50  	if fips140only.Enabled {
    51  		return nil, errors.New("crypto/ecdh: use of X25519 is not allowed in FIPS 140-only mode")
    52  	}
    53  	if len(key) != x25519PrivateKeySize {
    54  		return nil, errors.New("crypto/ecdh: invalid private key size")
    55  	}
    56  	publicKey := make([]byte, x25519PublicKeySize)
    57  	x25519Basepoint := [32]byte{9}
    58  	x25519ScalarMult(publicKey, key, x25519Basepoint[:])
    59  	// We don't check for the all-zero public key here because the scalar is
    60  	// never zero because of clamping, and the basepoint is not the identity in
    61  	// the prime-order subgroup(s).
    62  	return &PrivateKey{
    63  		curve:      c,
    64  		privateKey: bytes.Clone(key),
    65  		publicKey:  &PublicKey{curve: c, publicKey: publicKey},
    66  	}, nil
    67  }
    68  
    69  func (c *x25519Curve) NewPublicKey(key []byte) (*PublicKey, error) {
    70  	if fips140only.Enabled {
    71  		return nil, errors.New("crypto/ecdh: use of X25519 is not allowed in FIPS 140-only mode")
    72  	}
    73  	if len(key) != x25519PublicKeySize {
    74  		return nil, errors.New("crypto/ecdh: invalid public key")
    75  	}
    76  	return &PublicKey{
    77  		curve:     c,
    78  		publicKey: bytes.Clone(key),
    79  	}, nil
    80  }
    81  
    82  func (c *x25519Curve) ecdh(local *PrivateKey, remote *PublicKey) ([]byte, error) {
    83  	out := make([]byte, x25519SharedSecretSize)
    84  	x25519ScalarMult(out, local.privateKey, remote.publicKey)
    85  	if isZero(out) {
    86  		return nil, errors.New("crypto/ecdh: bad X25519 remote ECDH input: low order point")
    87  	}
    88  	return out, nil
    89  }
    90  
    91  func x25519ScalarMult(dst, scalar, point []byte) {
    92  	var e [32]byte
    93  
    94  	copy(e[:], scalar[:])
    95  	e[0] &= 248
    96  	e[31] &= 127
    97  	e[31] |= 64
    98  
    99  	var x1, x2, z2, x3, z3, tmp0, tmp1 field.Element
   100  	x1.SetBytes(point[:])
   101  	x2.One()
   102  	x3.Set(&x1)
   103  	z3.One()
   104  
   105  	swap := 0
   106  	for pos := 254; pos >= 0; pos-- {
   107  		b := e[pos/8] >> uint(pos&7)
   108  		b &= 1
   109  		swap ^= int(b)
   110  		x2.Swap(&x3, swap)
   111  		z2.Swap(&z3, swap)
   112  		swap = int(b)
   113  
   114  		tmp0.Subtract(&x3, &z3)
   115  		tmp1.Subtract(&x2, &z2)
   116  		x2.Add(&x2, &z2)
   117  		z2.Add(&x3, &z3)
   118  		z3.Multiply(&tmp0, &x2)
   119  		z2.Multiply(&z2, &tmp1)
   120  		tmp0.Square(&tmp1)
   121  		tmp1.Square(&x2)
   122  		x3.Add(&z3, &z2)
   123  		z2.Subtract(&z3, &z2)
   124  		x2.Multiply(&tmp1, &tmp0)
   125  		tmp1.Subtract(&tmp1, &tmp0)
   126  		z2.Square(&z2)
   127  
   128  		z3.Mult32(&tmp1, 121666)
   129  		x3.Square(&x3)
   130  		tmp0.Add(&tmp0, &z3)
   131  		z3.Multiply(&x1, &z2)
   132  		z2.Multiply(&tmp1, &tmp0)
   133  	}
   134  
   135  	x2.Swap(&x3, swap)
   136  	z2.Swap(&z3, swap)
   137  
   138  	z2.Invert(&z2)
   139  	x2.Multiply(&x2, &z2)
   140  	copy(dst[:], x2.Bytes())
   141  }
   142  
   143  // isZero reports whether x is all zeroes in constant time.
   144  func isZero(x []byte) bool {
   145  	var acc byte
   146  	for _, b := range x {
   147  		acc |= b
   148  	}
   149  	return acc == 0
   150  }
   151
View as plain text