1package goldilocks
  2
  3import (
  4	"crypto/subtle"
  5	"math/bits"
  6
  7	"github.com/cloudflare/circl/internal/conv"
  8	"github.com/cloudflare/circl/math"
  9	fp "github.com/cloudflare/circl/math/fp448"
 10)
 11
 12// twistCurve is -x^2+y^2=1-39082x^2y^2 and is 4-isogenous to Goldilocks.
 13type twistCurve struct{}
 14
 15// Identity returns the identity point.
 16func (twistCurve) Identity() *twistPoint {
 17	return &twistPoint{
 18		y: fp.One(),
 19		z: fp.One(),
 20	}
 21}
 22
 23// subYDiv16 update x = (x - y) / 16.
 24func subYDiv16(x *scalar64, y int64) {
 25	s := uint64(y >> 63)
 26	x0, b0 := bits.Sub64((*x)[0], uint64(y), 0)
 27	x1, b1 := bits.Sub64((*x)[1], s, b0)
 28	x2, b2 := bits.Sub64((*x)[2], s, b1)
 29	x3, b3 := bits.Sub64((*x)[3], s, b2)
 30	x4, b4 := bits.Sub64((*x)[4], s, b3)
 31	x5, b5 := bits.Sub64((*x)[5], s, b4)
 32	x6, _ := bits.Sub64((*x)[6], s, b5)
 33	x[0] = (x0 >> 4) | (x1 << 60)
 34	x[1] = (x1 >> 4) | (x2 << 60)
 35	x[2] = (x2 >> 4) | (x3 << 60)
 36	x[3] = (x3 >> 4) | (x4 << 60)
 37	x[4] = (x4 >> 4) | (x5 << 60)
 38	x[5] = (x5 >> 4) | (x6 << 60)
 39	x[6] = (x6 >> 4)
 40}
 41
 42func recodeScalar(d *[113]int8, k *Scalar) {
 43	var k64 scalar64
 44	k64.fromScalar(k)
 45	for i := 0; i < 112; i++ {
 46		d[i] = int8((k64[0] & 0x1f) - 16)
 47		subYDiv16(&k64, int64(d[i]))
 48	}
 49	d[112] = int8(k64[0])
 50}
 51
 52// ScalarMult returns kP.
 53func (e twistCurve) ScalarMult(k *Scalar, P *twistPoint) *twistPoint {
 54	var TabP [8]preTwistPointProy
 55	var S preTwistPointProy
 56	var d [113]int8
 57
 58	var isZero int
 59	if k.IsZero() {
 60		isZero = 1
 61	}
 62	subtle.ConstantTimeCopy(isZero, k[:], order[:])
 63
 64	minusK := *k
 65	isEven := 1 - int(k[0]&0x1)
 66	minusK.Neg()
 67	subtle.ConstantTimeCopy(isEven, k[:], minusK[:])
 68	recodeScalar(&d, k)
 69
 70	P.oddMultiples(TabP[:])
 71	Q := e.Identity()
 72	for i := 112; i >= 0; i-- {
 73		Q.Double()
 74		Q.Double()
 75		Q.Double()
 76		Q.Double()
 77		mask := d[i] >> 7
 78		absDi := (d[i] + mask) ^ mask
 79		inx := int32((absDi - 1) >> 1)
 80		sig := int((d[i] >> 7) & 0x1)
 81		for j := range TabP {
 82			S.cmov(&TabP[j], uint(subtle.ConstantTimeEq(inx, int32(j))))
 83		}
 84		S.cneg(sig)
 85		Q.mixAdd(&S)
 86	}
 87	Q.cneg(uint(isEven))
 88	return Q
 89}
 90
 91const (
 92	omegaFix = 7
 93	omegaVar = 5
 94)
 95
 96// CombinedMult returns mG+nP.
 97func (e twistCurve) CombinedMult(m, n *Scalar, P *twistPoint) *twistPoint {
 98	nafFix := math.OmegaNAF(conv.BytesLe2BigInt(m[:]), omegaFix)
 99	nafVar := math.OmegaNAF(conv.BytesLe2BigInt(n[:]), omegaVar)
100
101	if len(nafFix) > len(nafVar) {
102		nafVar = append(nafVar, make([]int32, len(nafFix)-len(nafVar))...)
103	} else if len(nafFix) < len(nafVar) {
104		nafFix = append(nafFix, make([]int32, len(nafVar)-len(nafFix))...)
105	}
106
107	var TabQ [1 << (omegaVar - 2)]preTwistPointProy
108	P.oddMultiples(TabQ[:])
109	Q := e.Identity()
110	for i := len(nafFix) - 1; i >= 0; i-- {
111		Q.Double()
112		// Generator point
113		if nafFix[i] != 0 {
114			idxM := absolute(nafFix[i]) >> 1
115			R := tabVerif[idxM]
116			if nafFix[i] < 0 {
117				R.neg()
118			}
119			Q.mixAddZ1(&R)
120		}
121		// Variable input point
122		if nafVar[i] != 0 {
123			idxN := absolute(nafVar[i]) >> 1
124			S := TabQ[idxN]
125			if nafVar[i] < 0 {
126				S.neg()
127			}
128			Q.mixAdd(&S)
129		}
130	}
131	return Q
132}
133
134// absolute returns always a positive value.
135func absolute(x int32) int32 {
136	mask := x >> 31
137	return (x + mask) ^ mask
138}