go.crypto/curve25519: add package.
This consists of ~2000 lines of amd64 assembly and a, much slower,
generic Go version in curve25519.go. The assembly has been ported from
djb's public domain sources and the only semantic alterations are to
deal with Go's split stacks.
R=rsc
CC=golang-dev
https://golang.org/cl/5786045
diff --git a/curve25519/curve25519.go b/curve25519/curve25519.go
new file mode 100644
index 0000000..23c6516
--- /dev/null
+++ b/curve25519/curve25519.go
@@ -0,0 +1,136 @@
+// Copyright 2012 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package curve25519
+
+// We have a implementation in amd64 assembly so this code is only run on
+// non-amd64 platforms.
+// +build !amd64
+
+import (
+ "math/big"
+)
+
+// p is the prime order of the underlying field: 2^255-19
+var p *big.Int
+
+// pMinus2 is p-2
+var pMinus2 *big.Int
+
+// a is a parameter of the elliptic curve: 486662
+var a *big.Int
+
+func init() {
+ p, _ = new(big.Int).SetString("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", 16)
+ pMinus2, _ = new(big.Int).SetString("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeb", 16)
+ a = new(big.Int).SetInt64(486662)
+}
+
+// context contains state shared throughout the computation, including scratch
+// variables to save on allocation.
+type context struct {
+ tmp1, tmp2, tmp3, tmp4 *big.Int
+ x1 *big.Int
+}
+
+// add sets (outx, outz) to the sum of two points in the elliptic curve group.
+// See http://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#diffadd-dadd-1987-m
+// outx and outz should not alias any of the other inputs.
+func (c *context) add(outx, outz, xn, zn, xm, zm *big.Int) {
+ // x₃ = 4(x·x′ - z·z′)² · z1
+ // (z1 == 1 here)
+ c.tmp1.Mul(xn, xm)
+ c.tmp2.Mul(zn, zm)
+ c.tmp3.Sub(c.tmp1, c.tmp2)
+ outx.Mul(c.tmp3, c.tmp3)
+ outx.Lsh(outx, 2)
+ outx.Mod(outx, p)
+
+ // z₃ = 4(x·z′ - z·x′)² · x1
+ // (x1 == 1 here)
+ c.tmp1.Mul(xm, zn)
+ c.tmp2.Mul(zm, xn)
+ c.tmp3.Sub(c.tmp1, c.tmp2)
+ outz.Mul(c.tmp3, c.tmp3)
+ outz.Mul(outz, c.x1)
+ outz.Lsh(outz, 2)
+ outz.Mod(outz, p)
+
+ return
+}
+
+// double sets (outx, outz) to 2*(x,z) in the elliptic curve group. See
+// http://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#doubling-dbl-1987-m
+// outx and outz should not alias any of the other inputs.
+func (c *context) double(outx, outz, x, z *big.Int) {
+ // x₂ = (x² - z²)²
+ c.tmp1.Mul(x, x)
+ c.tmp2.Mul(z, z)
+ c.tmp3.Sub(c.tmp1, c.tmp2)
+ outx.Mul(c.tmp3, c.tmp3)
+ outx.Mod(outx, p)
+
+ // z₂ = 4xz·(x² + Axz + z²)
+ c.tmp3.Add(c.tmp1, c.tmp2)
+ c.tmp1.Mul(x, z)
+ c.tmp2.Mul(c.tmp1, a)
+ outz.Add(c.tmp3, c.tmp2)
+ c.tmp2.Lsh(c.tmp1, 2)
+ outz.Mul(outz, c.tmp2)
+ outz.Mod(outz, p)
+
+ return
+}
+
+func scalarMult(out, in, base *[32]byte) {
+ var baseReversed, inCopy [32]byte
+ for i := 0; i < 32; i++ {
+ baseReversed[31-i] = base[i]
+ inCopy[i] = in[i]
+ }
+
+ inCopy[31] &= 127
+ inCopy[31] |= 64
+ inCopy[0] &= 248
+
+ c := &context{new(big.Int), new(big.Int), new(big.Int), new(big.Int), nil}
+ c.x1 = new(big.Int).SetBytes(baseReversed[:])
+
+ x1 := new(big.Int).SetInt64(1)
+ z1 := new(big.Int)
+ x2 := new(big.Int).Set(c.x1)
+ z2 := new(big.Int).SetInt64(1)
+ outx := new(big.Int)
+ outz := new(big.Int)
+
+ for i := 0; i < 32; i++ {
+ b := inCopy[31-i]
+ for j := 0; j < 8; j++ {
+ if b&0x80 != 0 {
+ c.add(outx, outz, x1, z1, x2, z2)
+ x1, z1, outx, outz = outx, outz, x1, z1
+ c.double(outx, outz, x2, z2)
+ x2, z2, outx, outz = outx, outz, x2, z2
+ } else {
+ c.add(outx, outz, x1, z1, x2, z2)
+ x2, z2, outx, outz = outx, outz, x2, z2
+ c.double(outx, outz, x1, z1)
+ x1, z1, outx, outz = outx, outz, x1, z1
+ }
+ b <<= 1
+ }
+ }
+
+ c.tmp1.Exp(z1, pMinus2, p)
+ c.tmp2.Mul(x1, c.tmp1)
+ c.tmp3.Mod(c.tmp2, p)
+
+ outReversed := c.tmp3.Bytes()
+ for i := 0; i < len(outReversed); i++ {
+ out[i] = outReversed[len(outReversed)-(1+i)]
+ }
+ for i := len(outReversed); i < 32; i++ {
+ out[i] = 0
+ }
+}
