wnaf.go

Documentation: github.com/cloudflare/circl/math

     1  // Package math provides some utility functions for big integers.
     2  package math
     3  
     4  import "math/big"
     5  
     6  // SignedDigit obtains the signed-digit recoding of n and returns a list L of
     7  // digits such that n = sum( L[i]*2^(i*(w-1)) ), and each L[i] is an odd number
     8  // in the set {±1, ±3, ..., ±2^(w-1)-1}. The third parameter ensures that the
     9  // output has ceil(l/(w-1)) digits.
    10  //
    11  // Restrictions:
    12  //   - n is odd and n > 0.
    13  //   - 1 < w < 32.
    14  //   - l >= bit length of n.
    15  //
    16  // References:
    17  //   - Alg.6 in "Exponent Recoding and Regular Exponentiation Algorithms"
    18  //     by Joye-Tunstall. http://doi.org/10.1007/978-3-642-02384-2_21
    19  //   - Alg.6 in "Selecting Elliptic Curves for Cryptography: An Efficiency and
    20  //     Security Analysis" by Bos et al. http://doi.org/10.1007/s13389-015-0097-y
    21  func SignedDigit(n *big.Int, w, l uint) []int32 {
    22  	if n.Sign() <= 0 || n.Bit(0) == 0 {
    23  		panic("n must be non-zero, odd, and positive")
    24  	}
    25  	if w <= 1 || w >= 32 {
    26  		panic("Verify that 1 < w < 32")
    27  	}
    28  	if uint(n.BitLen()) > l {
    29  		panic("n is too big to fit in l digits")
    30  	}
    31  	lenN := (l + (w - 1) - 1) / (w - 1) // ceil(l/(w-1))
    32  	L := make([]int32, lenN+1)
    33  	var k, v big.Int
    34  	k.Set(n)
    35  
    36  	var i uint
    37  	for i = 0; i < lenN; i++ {
    38  		words := k.Bits()
    39  		value := int32(words[0] & ((1 << w) - 1))
    40  		value -= int32(1) << (w - 1)
    41  		L[i] = value
    42  		v.SetInt64(int64(value))
    43  		k.Sub(&k, &v)
    44  		k.Rsh(&k, w-1)
    45  	}
    46  	L[i] = int32(k.Int64())
    47  	return L
    48  }
    49  
    50  // OmegaNAF obtains the window-w Non-Adjacent Form of a positive number n and
    51  // 1 < w < 32. The returned slice L holds n = sum( L[i]*2^i ).
    52  //
    53  // Reference:
    54  //   - Alg.9 "Efficient arithmetic on Koblitz curves" by Solinas.
    55  //     http://doi.org/10.1023/A:1008306223194
    56  func OmegaNAF(n *big.Int, w uint) (L []int32) {
    57  	if n.Sign() < 0 {
    58  		panic("n must be positive")
    59  	}
    60  	if w <= 1 || w >= 32 {
    61  		panic("Verify that 1 < w < 32")
    62  	}
    63  
    64  	L = make([]int32, n.BitLen()+1)
    65  	var k, v big.Int
    66  	k.Set(n)
    67  
    68  	i := 0
    69  	for ; k.Sign() > 0; i++ {
    70  		value := int32(0)
    71  		if k.Bit(0) == 1 {
    72  			words := k.Bits()
    73  			value = int32(words[0] & ((1 << w) - 1))
    74  			if value >= (int32(1) << (w - 1)) {
    75  				value -= int32(1) << w
    76  			}
    77  			v.SetInt64(int64(value))
    78  			k.Sub(&k, &v)
    79  		}
    80  		L[i] = value
    81  		k.Rsh(&k, 1)
    82  	}
    83  	return L[:i]
    84  }
    85
View as plain text