x25519.mx raw

   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 := []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 := []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 := []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