1// Package mlsbset provides a constant-time exponentiation method with precomputation.
  2//
  3// References: "Efficient and secure algorithms for GLV-based scalar
  4// multiplication and their implementation on GLV–GLS curves" by (Faz-Hernandez et al.)
  5//   - https://doi.org/10.1007/s13389-014-0085-7
  6//   - https://eprint.iacr.org/2013/158
  7package mlsbset
  8
  9import (
 10	"errors"
 11	"fmt"
 12	"math/big"
 13
 14	"github.com/cloudflare/circl/internal/conv"
 15)
 16
 17// EltG is a group element.
 18type EltG interface{}
 19
 20// EltP is a precomputed group element.
 21type EltP interface{}
 22
 23// Group defines the operations required by MLSBSet exponentiation method.
 24type Group interface {
 25	Identity() EltG                    // Returns the identity of the group.
 26	Sqr(x EltG)                        // Calculates x = x^2.
 27	Mul(x EltG, y EltP)                // Calculates x = x*y.
 28	NewEltP() EltP                     // Returns an arbitrary precomputed element.
 29	ExtendedEltP() EltP                // Returns the precomputed element x^(2^(w*d)).
 30	Lookup(a EltP, v uint, s, u int32) // Sets a = s*T[v][u].
 31}
 32
 33// Params contains the parameters of the encoding.
 34type Params struct {
 35	T uint // T is the maximum size (in bits) of exponents.
 36	V uint // V is the number of tables.
 37	W uint // W is the window size.
 38	E uint // E is the number of digits per table.
 39	D uint // D is the number of digits in total.
 40	L uint // L is the length of the code.
 41}
 42
 43// Encoder allows to convert integers into valid powers.
 44type Encoder struct{ p Params }
 45
 46// New produces an encoder of the MLSBSet algorithm.
 47func New(t, v, w uint) (Encoder, error) {
 48	if !(t > 1 && v >= 1 && w >= 2) {
 49		return Encoder{}, errors.New("t>1, v>=1, w>=2")
 50	}
 51	e := (t + w*v - 1) / (w * v)
 52	d := e * v
 53	l := d * w
 54	return Encoder{Params{t, v, w, e, d, l}}, nil
 55}
 56
 57// Encode converts an odd integer k into a valid power for exponentiation.
 58func (m Encoder) Encode(k []byte) (*Power, error) {
 59	if len(k) == 0 {
 60		return nil, errors.New("empty slice")
 61	}
 62	if !(len(k) <= int(m.p.L+7)>>3) {
 63		return nil, errors.New("k too big")
 64	}
 65	if k[0]%2 == 0 {
 66		return nil, errors.New("k must be odd")
 67	}
 68	ap := int((m.p.L+7)/8) - len(k)
 69	k = append(k, make([]byte, ap)...)
 70	s := m.signs(k)
 71	b := make([]int32, m.p.L-m.p.D)
 72	c := conv.BytesLe2BigInt(k)
 73	c.Rsh(c, m.p.D)
 74	var bi big.Int
 75	for i := m.p.D; i < m.p.L; i++ {
 76		c0 := int32(c.Bit(0))
 77		b[i-m.p.D] = s[i%m.p.D] * c0
 78		bi.SetInt64(int64(b[i-m.p.D] >> 1))
 79		c.Rsh(c, 1)
 80		c.Sub(c, &bi)
 81	}
 82	carry := int(c.Int64())
 83	return &Power{m, s, b, carry}, nil
 84}
 85
 86// signs calculates the set of signs.
 87func (m Encoder) signs(k []byte) []int32 {
 88	s := make([]int32, m.p.D)
 89	s[m.p.D-1] = 1
 90	for i := uint(1); i < m.p.D; i++ {
 91		ki := int32((k[i>>3] >> (i & 0x7)) & 0x1)
 92		s[i-1] = 2*ki - 1
 93	}
 94	return s
 95}
 96
 97// GetParams returns the complementary parameters of the encoding.
 98func (m Encoder) GetParams() Params { return m.p }
 99
100// tableSize returns the size of each table.
101func (m Encoder) tableSize() uint { return 1 << (m.p.W - 1) }
102
103// Elts returns the total number of elements that must be precomputed.
104func (m Encoder) Elts() uint { return m.p.V * m.tableSize() }
105
106// IsExtended returns true if the element x^(2^(wd)) must be calculated.
107func (m Encoder) IsExtended() bool { q := m.p.T / (m.p.V * m.p.W); return m.p.T == q*m.p.V*m.p.W }
108
109// Ops returns the number of squares and multiplications executed during an exponentiation.
110func (m Encoder) Ops() (S uint, M uint) {
111	S = m.p.E
112	M = m.p.E * m.p.V
113	if m.IsExtended() {
114		M++
115	}
116	return
117}
118
119func (m Encoder) String() string {
120	return fmt.Sprintf("T: %v W: %v V: %v e: %v d: %v l: %v wv|t: %v",
121		m.p.T, m.p.W, m.p.V, m.p.E, m.p.D, m.p.L, m.IsExtended())
122}