1package ed25519
  2
  3import (
  4	"crypto/subtle"
  5	"encoding/binary"
  6	"math/bits"
  7
  8	"github.com/cloudflare/circl/internal/conv"
  9	"github.com/cloudflare/circl/math"
 10	fp "github.com/cloudflare/circl/math/fp25519"
 11)
 12
 13var paramD = fp.Elt{
 14	0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
 15	0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
 16	0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
 17	0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52,
 18}
 19
 20// mLSBRecoding parameters.
 21const (
 22	fxT        = 257
 23	fxV        = 2
 24	fxW        = 3
 25	fx2w1      = 1 << (uint(fxW) - 1)
 26	numWords64 = (paramB * 8 / 64)
 27)
 28
 29// mLSBRecoding is the odd-only modified LSB-set.
 30//
 31// Reference:
 32//
 33//	"Efficient and secure algorithms for GLV-based scalar multiplication and
 34//	 their implementation on GLV–GLS curves" by (Faz-Hernandez et al.)
 35//	 http://doi.org/10.1007/s13389-014-0085-7.
 36func mLSBRecoding(L []int8, k []byte) {
 37	const ee = (fxT + fxW*fxV - 1) / (fxW * fxV)
 38	const dd = ee * fxV
 39	const ll = dd * fxW
 40	if len(L) == (ll + 1) {
 41		var m [numWords64 + 1]uint64
 42		for i := 0; i < numWords64; i++ {
 43			m[i] = binary.LittleEndian.Uint64(k[8*i : 8*i+8])
 44		}
 45		condAddOrderN(&m)
 46		L[dd-1] = 1
 47		for i := 0; i < dd-1; i++ {
 48			kip1 := (m[(i+1)/64] >> (uint(i+1) % 64)) & 0x1
 49			L[i] = int8(kip1<<1) - 1
 50		}
 51		{ // right-shift by d
 52			right := uint(dd % 64)
 53			left := uint(64) - right
 54			lim := ((numWords64+1)*64 - dd) / 64
 55			j := dd / 64
 56			for i := 0; i < lim; i++ {
 57				m[i] = (m[i+j] >> right) | (m[i+j+1] << left)
 58			}
 59			m[lim] = m[lim+j] >> right
 60		}
 61		for i := dd; i < ll; i++ {
 62			L[i] = L[i%dd] * int8(m[0]&0x1)
 63			div2subY(m[:], int64(L[i]>>1), numWords64)
 64		}
 65		L[ll] = int8(m[0])
 66	}
 67}
 68
 69// absolute returns always a positive value.
 70func absolute(x int32) int32 {
 71	mask := x >> 31
 72	return (x + mask) ^ mask
 73}
 74
 75// condAddOrderN updates x = x+order if x is even, otherwise x remains unchanged.
 76func condAddOrderN(x *[numWords64 + 1]uint64) {
 77	isOdd := (x[0] & 0x1) - 1
 78	c := uint64(0)
 79	for i := 0; i < numWords64; i++ {
 80		orderWord := binary.LittleEndian.Uint64(order[8*i : 8*i+8])
 81		o := isOdd & orderWord
 82		x0, c0 := bits.Add64(x[i], o, c)
 83		x[i] = x0
 84		c = c0
 85	}
 86	x[numWords64], _ = bits.Add64(x[numWords64], 0, c)
 87}
 88
 89// div2subY update x = (x/2) - y.
 90func div2subY(x []uint64, y int64, l int) {
 91	s := uint64(y >> 63)
 92	for i := 0; i < l-1; i++ {
 93		x[i] = (x[i] >> 1) | (x[i+1] << 63)
 94	}
 95	x[l-1] = (x[l-1] >> 1)
 96
 97	b := uint64(0)
 98	x0, b0 := bits.Sub64(x[0], uint64(y), b)
 99	x[0] = x0
100	b = b0
101	for i := 1; i < l-1; i++ {
102		x0, b0 := bits.Sub64(x[i], s, b)
103		x[i] = x0
104		b = b0
105	}
106	x[l-1], _ = bits.Sub64(x[l-1], s, b)
107}
108
109func (P *pointR1) fixedMult(scalar []byte) {
110	if len(scalar) != paramB {
111		panic("wrong scalar size")
112	}
113	const ee = (fxT + fxW*fxV - 1) / (fxW * fxV)
114	const dd = ee * fxV
115	const ll = dd * fxW
116
117	L := make([]int8, ll+1)
118	mLSBRecoding(L[:], scalar)
119	S := &pointR3{}
120	P.SetIdentity()
121	for ii := ee - 1; ii >= 0; ii-- {
122		P.double()
123		for j := 0; j < fxV; j++ {
124			dig := L[fxW*dd-j*ee+ii-ee]
125			for i := (fxW-1)*dd - j*ee + ii - ee; i >= (2*dd - j*ee + ii - ee); i = i - dd {
126				dig = 2*dig + L[i]
127			}
128			idx := absolute(int32(dig))
129			sig := L[dd-j*ee+ii-ee]
130			Tabj := &tabSign[fxV-j-1]
131			for k := 0; k < fx2w1; k++ {
132				S.cmov(&Tabj[k], subtle.ConstantTimeEq(int32(k), idx))
133			}
134			S.cneg(subtle.ConstantTimeEq(int32(sig), -1))
135			P.mixAdd(S)
136		}
137	}
138}
139
140const (
141	omegaFix = 7
142	omegaVar = 5
143)
144
145// doubleMult returns P=mG+nQ.
146func (P *pointR1) doubleMult(Q *pointR1, m, n []byte) {
147	nafFix := math.OmegaNAF(conv.BytesLe2BigInt(m), omegaFix)
148	nafVar := math.OmegaNAF(conv.BytesLe2BigInt(n), omegaVar)
149
150	if len(nafFix) > len(nafVar) {
151		nafVar = append(nafVar, make([]int32, len(nafFix)-len(nafVar))...)
152	} else if len(nafFix) < len(nafVar) {
153		nafFix = append(nafFix, make([]int32, len(nafVar)-len(nafFix))...)
154	}
155
156	var TabQ [1 << (omegaVar - 2)]pointR2
157	Q.oddMultiples(TabQ[:])
158	P.SetIdentity()
159	for i := len(nafFix) - 1; i >= 0; i-- {
160		P.double()
161		// Generator point
162		if nafFix[i] != 0 {
163			idxM := absolute(nafFix[i]) >> 1
164			R := tabVerif[idxM]
165			if nafFix[i] < 0 {
166				R.neg()
167			}
168			P.mixAdd(&R)
169		}
170		// Variable input point
171		if nafVar[i] != 0 {
172			idxN := absolute(nafVar[i]) >> 1
173			S := TabQ[idxN]
174			if nafVar[i] < 0 {
175				S.neg()
176			}
177			P.add(&S)
178		}
179	}
180}