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