curve25519.go

     1  // Copyright 2019 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 curve25519 provides an implementation of the X25519 function, which
     6  // performs scalar multiplication on the elliptic curve known as Curve25519.
     7  // See RFC 7748.
     8  package curve25519 // import "golang.org/x/crypto/curve25519"
     9  
    10  import (
    11  	"crypto/subtle"
    12  	"fmt"
    13  
    14  	"golang.org/x/crypto/curve25519/internal/field"
    15  )
    16  
    17  // ScalarMult sets dst to the product scalar * point.
    18  //
    19  // Deprecated: when provided a low-order point, ScalarMult will set dst to all
    20  // zeroes, irrespective of the scalar. Instead, use the X25519 function, which
    21  // will return an error.
    22  func ScalarMult(dst, scalar, point *[32]byte) {
    23  	var e [32]byte
    24  
    25  	copy(e[:], scalar[:])
    26  	e[0] &= 248
    27  	e[31] &= 127
    28  	e[31] |= 64
    29  
    30  	var x1, x2, z2, x3, z3, tmp0, tmp1 field.Element
    31  	x1.SetBytes(point[:])
    32  	x2.One()
    33  	x3.Set(&x1)
    34  	z3.One()
    35  
    36  	swap := 0
    37  	for pos := 254; pos >= 0; pos-- {
    38  		b := e[pos/8] >> uint(pos&7)
    39  		b &= 1
    40  		swap ^= int(b)
    41  		x2.Swap(&x3, swap)
    42  		z2.Swap(&z3, swap)
    43  		swap = int(b)
    44  
    45  		tmp0.Subtract(&x3, &z3)
    46  		tmp1.Subtract(&x2, &z2)
    47  		x2.Add(&x2, &z2)
    48  		z2.Add(&x3, &z3)
    49  		z3.Multiply(&tmp0, &x2)
    50  		z2.Multiply(&z2, &tmp1)
    51  		tmp0.Square(&tmp1)
    52  		tmp1.Square(&x2)
    53  		x3.Add(&z3, &z2)
    54  		z2.Subtract(&z3, &z2)
    55  		x2.Multiply(&tmp1, &tmp0)
    56  		tmp1.Subtract(&tmp1, &tmp0)
    57  		z2.Square(&z2)
    58  
    59  		z3.Mult32(&tmp1, 121666)
    60  		x3.Square(&x3)
    61  		tmp0.Add(&tmp0, &z3)
    62  		z3.Multiply(&x1, &z2)
    63  		z2.Multiply(&tmp1, &tmp0)
    64  	}
    65  
    66  	x2.Swap(&x3, swap)
    67  	z2.Swap(&z3, swap)
    68  
    69  	z2.Invert(&z2)
    70  	x2.Multiply(&x2, &z2)
    71  	copy(dst[:], x2.Bytes())
    72  }
    73  
    74  // ScalarBaseMult sets dst to the product scalar * base where base is the
    75  // standard generator.
    76  //
    77  // It is recommended to use the X25519 function with Basepoint instead, as
    78  // copying into fixed size arrays can lead to unexpected bugs.
    79  func ScalarBaseMult(dst, scalar *[32]byte) {
    80  	ScalarMult(dst, scalar, &basePoint)
    81  }
    82  
    83  const (
    84  	// ScalarSize is the size of the scalar input to X25519.
    85  	ScalarSize = 32
    86  	// PointSize is the size of the point input to X25519.
    87  	PointSize = 32
    88  )
    89  
    90  // Basepoint is the canonical Curve25519 generator.
    91  var Basepoint []byte
    92  
    93  var basePoint = [32]byte{9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    94  
    95  func init() { Basepoint = basePoint[:] }
    96  
    97  func checkBasepoint() {
    98  	if subtle.ConstantTimeCompare(Basepoint, []byte{
    99  		0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   100  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   101  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   102  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   103  	}) != 1 {
   104  		panic("curve25519: global Basepoint value was modified")
   105  	}
   106  }
   107  
   108  // X25519 returns the result of the scalar multiplication (scalar * point),
   109  // according to RFC 7748, Section 5. scalar, point and the return value are
   110  // slices of 32 bytes.
   111  //
   112  // scalar can be generated at random, for example with crypto/rand. point should
   113  // be either Basepoint or the output of another X25519 call.
   114  //
   115  // If point is Basepoint (but not if it's a different slice with the same
   116  // contents) a precomputed implementation might be used for performance.
   117  func X25519(scalar, point []byte) ([]byte, error) {
   118  	// Outline the body of function, to let the allocation be inlined in the
   119  	// caller, and possibly avoid escaping to the heap.
   120  	var dst [32]byte
   121  	return x25519(&dst, scalar, point)
   122  }
   123  
   124  func x25519(dst *[32]byte, scalar, point []byte) ([]byte, error) {
   125  	var in [32]byte
   126  	if l := len(scalar); l != 32 {
   127  		return nil, fmt.Errorf("bad scalar length: %d, expected %d", l, 32)
   128  	}
   129  	if l := len(point); l != 32 {
   130  		return nil, fmt.Errorf("bad point length: %d, expected %d", l, 32)
   131  	}
   132  	copy(in[:], scalar)
   133  	if &point[0] == &Basepoint[0] {
   134  		checkBasepoint()
   135  		ScalarBaseMult(dst, &in)
   136  	} else {
   137  		var base, zero [32]byte
   138  		copy(base[:], point)
   139  		ScalarMult(dst, &in, &base)
   140  		if subtle.ConstantTimeCompare(dst[:], zero[:]) == 1 {
   141  			return nil, fmt.Errorf("bad input point: low order point")
   142  		}
   143  	}
   144  	return dst[:], nil
   145  }
   146
View as plain text