twist.go

Documentation: github.com/cloudflare/circl/ecc/goldilocks

     1  package goldilocks
     2  
     3  import (
     4  	"crypto/subtle"
     5  	"math/bits"
     6  
     7  	"github.com/cloudflare/circl/internal/conv"
     8  	"github.com/cloudflare/circl/math"
     9  	fp "github.com/cloudflare/circl/math/fp448"
    10  )
    11  
    12  // twistCurve is -x^2+y^2=1-39082x^2y^2 and is 4-isogenous to Goldilocks.
    13  type twistCurve struct{}
    14  
    15  // Identity returns the identity point.
    16  func (twistCurve) Identity() *twistPoint {
    17  	return &twistPoint{
    18  		y: fp.One(),
    19  		z: fp.One(),
    20  	}
    21  }
    22  
    23  // subYDiv16 update x = (x - y) / 16.
    24  func subYDiv16(x *scalar64, y int64) {
    25  	s := uint64(y >> 63)
    26  	x0, b0 := bits.Sub64((*x)[0], uint64(y), 0)
    27  	x1, b1 := bits.Sub64((*x)[1], s, b0)
    28  	x2, b2 := bits.Sub64((*x)[2], s, b1)
    29  	x3, b3 := bits.Sub64((*x)[3], s, b2)
    30  	x4, b4 := bits.Sub64((*x)[4], s, b3)
    31  	x5, b5 := bits.Sub64((*x)[5], s, b4)
    32  	x6, _ := bits.Sub64((*x)[6], s, b5)
    33  	x[0] = (x0 >> 4) | (x1 << 60)
    34  	x[1] = (x1 >> 4) | (x2 << 60)
    35  	x[2] = (x2 >> 4) | (x3 << 60)
    36  	x[3] = (x3 >> 4) | (x4 << 60)
    37  	x[4] = (x4 >> 4) | (x5 << 60)
    38  	x[5] = (x5 >> 4) | (x6 << 60)
    39  	x[6] = (x6 >> 4)
    40  }
    41  
    42  func recodeScalar(d *[113]int8, k *Scalar) {
    43  	var k64 scalar64
    44  	k64.fromScalar(k)
    45  	for i := 0; i < 112; i++ {
    46  		d[i] = int8((k64[0] & 0x1f) - 16)
    47  		subYDiv16(&k64, int64(d[i]))
    48  	}
    49  	d[112] = int8(k64[0])
    50  }
    51  
    52  // ScalarMult returns kP.
    53  func (e twistCurve) ScalarMult(k *Scalar, P *twistPoint) *twistPoint {
    54  	var TabP [8]preTwistPointProy
    55  	var S preTwistPointProy
    56  	var d [113]int8
    57  
    58  	var isZero int
    59  	if k.IsZero() {
    60  		isZero = 1
    61  	}
    62  	subtle.ConstantTimeCopy(isZero, k[:], order[:])
    63  
    64  	minusK := *k
    65  	isEven := 1 - int(k[0]&0x1)
    66  	minusK.Neg()
    67  	subtle.ConstantTimeCopy(isEven, k[:], minusK[:])
    68  	recodeScalar(&d, k)
    69  
    70  	P.oddMultiples(TabP[:])
    71  	Q := e.Identity()
    72  	for i := 112; i >= 0; i-- {
    73  		Q.Double()
    74  		Q.Double()
    75  		Q.Double()
    76  		Q.Double()
    77  		mask := d[i] >> 7
    78  		absDi := (d[i] + mask) ^ mask
    79  		inx := int32((absDi - 1) >> 1)
    80  		sig := int((d[i] >> 7) & 0x1)
    81  		for j := range TabP {
    82  			S.cmov(&TabP[j], uint(subtle.ConstantTimeEq(inx, int32(j))))
    83  		}
    84  		S.cneg(sig)
    85  		Q.mixAdd(&S)
    86  	}
    87  	Q.cneg(uint(isEven))
    88  	return Q
    89  }
    90  
    91  const (
    92  	omegaFix = 7
    93  	omegaVar = 5
    94  )
    95  
    96  // CombinedMult returns mG+nP.
    97  func (e twistCurve) CombinedMult(m, n *Scalar, P *twistPoint) *twistPoint {
    98  	nafFix := math.OmegaNAF(conv.BytesLe2BigInt(m[:]), omegaFix)
    99  	nafVar := math.OmegaNAF(conv.BytesLe2BigInt(n[:]), omegaVar)
   100  
   101  	if len(nafFix) > len(nafVar) {
   102  		nafVar = append(nafVar, make([]int32, len(nafFix)-len(nafVar))...)
   103  	} else if len(nafFix) < len(nafVar) {
   104  		nafFix = append(nafFix, make([]int32, len(nafVar)-len(nafFix))...)
   105  	}
   106  
   107  	var TabQ [1 << (omegaVar - 2)]preTwistPointProy
   108  	P.oddMultiples(TabQ[:])
   109  	Q := e.Identity()
   110  	for i := len(nafFix) - 1; i >= 0; i-- {
   111  		Q.Double()
   112  		// Generator point
   113  		if nafFix[i] != 0 {
   114  			idxM := absolute(nafFix[i]) >> 1
   115  			R := tabVerif[idxM]
   116  			if nafFix[i] < 0 {
   117  				R.neg()
   118  			}
   119  			Q.mixAddZ1(&R)
   120  		}
   121  		// Variable input point
   122  		if nafVar[i] != 0 {
   123  			idxN := absolute(nafVar[i]) >> 1
   124  			S := TabQ[idxN]
   125  			if nafVar[i] < 0 {
   126  				S.neg()
   127  			}
   128  			Q.mixAdd(&S)
   129  		}
   130  	}
   131  	return Q
   132  }
   133  
   134  // absolute returns always a positive value.
   135  func absolute(x int32) int32 {
   136  	mask := x >> 31
   137  	return (x + mask) ^ mask
   138  }
   139
View as plain text