edwards25519/unsafe.go

package edwards25519

// UnsafeVarTimeScalarMult sets v = x * q, and returns v., and returns v. Execution time depends on the inputs.
// Deprecated: Unsafe for private operations
func (v *Point) UnsafeVarTimeScalarMult(x *Scalar, q *Point) *Point {
	checkInitialized(q)

	// Build lookup table for point q
	var table nafLookupTable5
	table.FromP3(q)
	// Compute a NAF for scalar x
	naf := x.nonAdjacentForm(5)

	multiple := &projCached{}
	tmp1 := &projP1xP1{}
	tmp2 := &projP2{}
	tmp2.Zero()

	// Skip the trailing zeroes
	i := 255
	for ; i >= 0; i-- {
		if naf[i] != 0 {
			break
		}
	}

	if i == -1 {
		v.fromP2(tmp2)
		return v
	}

	// Move from high to low bits, doubling the accumulator
	// at each iteration and checking whether there is a nonzero
	// coefficient to look up a multiple of.
	//
	// Skip trying to find the first nonzero coefficent, because
	// searching might be more work than a few extra doublings.
	for ; i >= 0; i-- {
		tmp1.Double(tmp2)
		if naf[i] > 0 {
			v.fromP1xP1(tmp1)
			table.SelectInto(multiple, naf[i])
			tmp1.Add(v, multiple)
		} else if naf[i] < 0 {
			v.fromP1xP1(tmp1)
			table.SelectInto(multiple, -naf[i])
			tmp1.Sub(v, multiple)
		}

		tmp2.FromP1xP1(tmp1)
	}

	v.fromP2(tmp2)
	return v
}

// UnsafeVarTimeScalarBaseMult sets v = x * B, where B is the canonical generator, and returns v. Execution time depends on the inputs.
// Deprecated: Unsafe for private operations
func (v *Point) UnsafeVarTimeScalarBaseMult(x *Scalar) *Point {
	basepointTable := basepointTable()

	// Write x = sum(x_i * 16^i) so  x*B = sum( B*x_i*16^i )
	// as described in the Ed25519 paper
	//
	// Group even and odd coefficients
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
	//         + x_1*16^1*B + x_3*16^3*B + ... + x_63*16^63*B
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
	//    + 16*( x_1*16^0*B + x_3*16^2*B + ... + x_63*16^62*B)
	//
	// We use a lookup table for each i to get x_i*16^(2*i)*B
	// and do four doublings to multiply by 16.
	digits := x.signedRadix16()

	multiple := &affineCached{}
	tmp1 := &projP1xP1{}
	tmp2 := &projP2{}

	// Accumulate the odd components first
	v.Set(NewIdentityPoint())
	for i := 1; i < 64; i += 2 {
		basepointTable[i/2].UnsafeVarTimeSelectInto(multiple, digits[i])
		tmp1.AddAffine(v, multiple)
		v.fromP1xP1(tmp1)
	}

	// Multiply by 16
	tmp2.FromP3(v)       // tmp2 =    v in P2 coords
	tmp1.Double(tmp2)    // tmp1 =  2*v in P1xP1 coords
	tmp2.FromP1xP1(tmp1) // tmp2 =  2*v in P2 coords
	tmp1.Double(tmp2)    // tmp1 =  4*v in P1xP1 coords
	tmp2.FromP1xP1(tmp1) // tmp2 =  4*v in P2 coords
	tmp1.Double(tmp2)    // tmp1 =  8*v in P1xP1 coords
	tmp2.FromP1xP1(tmp1) // tmp2 =  8*v in P2 coords
	tmp1.Double(tmp2)    // tmp1 = 16*v in P1xP1 coords
	v.fromP1xP1(tmp1)    // now v = 16*(odd components)

	// Accumulate the even components
	for i := 0; i < 64; i += 2 {
		basepointTable[i/2].UnsafeVarTimeSelectInto(multiple, digits[i])
		tmp1.AddAffine(v, multiple)
		v.fromP1xP1(tmp1)
	}

	return v
}

// UnsafeVarTimeScalarMultPrecomputed sets v = x * q, and returns v., and returns v. Execution time depends on the inputs.
// Deprecated: Unsafe for private operations
func (v *Point) UnsafeVarTimeScalarMultPrecomputed(x *Scalar, table *PrecomputedTable) *Point {
	// Write x = sum(x_i * 16^i) so  x*B = sum( B*x_i*16^i )
	// as described in the Ed25519 paper
	//
	// Group even and odd coefficients
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
	//         + x_1*16^1*B + x_3*16^3*B + ... + x_63*16^63*B
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
	//    + 16*( x_1*16^0*B + x_3*16^2*B + ... + x_63*16^62*B)
	//
	// We use a lookup table for each i to get x_i*16^(2*i)*B
	// and do four doublings to multiply by 16.
	digits := x.signedRadix16()

	multiple := &affineCached{}
	tmp1 := &projP1xP1{}
	tmp2 := &projP2{}

	// Accumulate the odd components first
	v.Set(NewIdentityPoint())
	for i := 1; i < 64; i += 2 {
		table[i/2].UnsafeVarTimeSelectInto(multiple, digits[i])
		tmp1.AddAffine(v, multiple)
		v.fromP1xP1(tmp1)
	}

	// Multiply by 16
	tmp2.FromP3(v)       // tmp2 =    v in P2 coords
	tmp1.Double(tmp2)    // tmp1 =  2*v in P1xP1 coords
	tmp2.FromP1xP1(tmp1) // tmp2 =  2*v in P2 coords
	tmp1.Double(tmp2)    // tmp1 =  4*v in P1xP1 coords
	tmp2.FromP1xP1(tmp1) // tmp2 =  4*v in P2 coords
	tmp1.Double(tmp2)    // tmp1 =  8*v in P1xP1 coords
	tmp2.FromP1xP1(tmp1) // tmp2 =  8*v in P2 coords
	tmp1.Double(tmp2)    // tmp1 = 16*v in P1xP1 coords
	v.fromP1xP1(tmp1)    // now v = 16*(odd components)

	// Accumulate the even components
	for i := 0; i < 64; i += 2 {
		table[i/2].UnsafeVarTimeSelectInto(multiple, digits[i])
		tmp1.AddAffine(v, multiple)
		v.fromP1xP1(tmp1)
	}

	return v
}

// Set dest to x*Q, where -8 <= x <= 8, in variable time.
// Deprecated: Unsafe for private operations
func (v *affineLookupTable) UnsafeVarTimeSelectInto(dest *affineCached, x int8) {
	if x == 0 {
		dest.Zero()
		return
	}

	// Compute xabs = |x|
	xmask := x >> 7
	xabs := uint8((x + xmask) ^ xmask)

	// Set dest = j*Q
	*dest = v.points[xabs-1]

	// Now dest = |x|*Q, conditionally negate to get x*Q
	if (xmask & 1) > 0 {
		dest.YplusX, dest.YminusX = dest.YminusX, dest.YplusX
		dest.T2d.Negate(&dest.T2d)
	}
}