mlsbset.go

Documentation: github.com/cloudflare/circl/math/mlsbset

     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
     7  package mlsbset
     8  
     9  import (
    10  	"errors"
    11  	"fmt"
    12  	"math/big"
    13  
    14  	"github.com/cloudflare/circl/internal/conv"
    15  )
    16  
    17  // EltG is a group element.
    18  type EltG interface{}
    19  
    20  // EltP is a precomputed group element.
    21  type EltP interface{}
    22  
    23  // Group defines the operations required by MLSBSet exponentiation method.
    24  type 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.
    34  type 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.
    44  type Encoder struct{ p Params }
    45  
    46  // New produces an encoder of the MLSBSet algorithm.
    47  func 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.
    58  func (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.
    87  func (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.
    98  func (m Encoder) GetParams() Params { return m.p }
    99  
   100  // tableSize returns the size of each table.
   101  func (m Encoder) tableSize() uint { return 1 << (m.p.W - 1) }
   102  
   103  // Elts returns the total number of elements that must be precomputed.
   104  func (m Encoder) Elts() uint { return m.p.V * m.tableSize() }
   105  
   106  // IsExtended returns true if the element x^(2^(wd)) must be calculated.
   107  func (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.
   110  func (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  
   119  func (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  }
   123
View as plain text