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. 8package curve25519 // import "golang.org/x/crypto/curve25519" 9 10import ( 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. 22func 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. 79func ScalarBaseMult(dst, scalar *[32]byte) { 80 ScalarMult(dst, scalar, &basePoint) 81} 82 83const ( 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. 91var Basepoint []byte 92 93var 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 95func init() { Basepoint = basePoint[:] } 96 97func 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. 117func 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 124func 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