mult.go

Documentation: github.com/cloudflare/circl/sign/ed25519

     1  package ed25519
     2  
     3  import (
     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  
    13  var 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.
    21  const (
    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.
    36  func 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.
    70  func 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.
    76  func 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.
    90  func 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  
   109  func (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  
   140  const (
   141  	omegaFix = 7
   142  	omegaVar = 5
   143  )
   144  
   145  // doubleMult returns P=mG+nQ.
   146  func (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  }
   181
View as plain text