twist.go raw

   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