point.go

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

     1  package fourq
     2  
     3  import (
     4  	"crypto/subtle"
     5  	"encoding/binary"
     6  	"math/bits"
     7  )
     8  
     9  type pointR1 struct {
    10  	X, Y, Z, Ta, Tb Fq // (x,y,z,t=ta*tb)
    11  }
    12  
    13  type pointR3 struct {
    14  	addYX Fq // y + x
    15  	subYX Fq // y - x
    16  	dt2   Fq // 2*d*t
    17  }
    18  
    19  type pointR2 struct {
    20  	pointR3
    21  	z2 Fq // 2 * z
    22  }
    23  
    24  // subYDiv16 update x = (x - y) / 16.
    25  func subYDiv16(x *[5]uint64, y int64) {
    26  	s := uint64(y >> 63)
    27  	x0, b0 := bits.Sub64((*x)[0], uint64(y), 0)
    28  	x1, b1 := bits.Sub64((*x)[1], s, b0)
    29  	x2, b2 := bits.Sub64((*x)[2], s, b1)
    30  	x3, b3 := bits.Sub64((*x)[3], s, b2)
    31  	x4, _ := bits.Sub64((*x)[4], s, b3)
    32  	(*x)[0] = (x0 >> 4) | (x1 << 60)
    33  	(*x)[1] = (x1 >> 4) | (x2 << 60)
    34  	(*x)[2] = (x2 >> 4) | (x3 << 60)
    35  	(*x)[3] = (x3 >> 4) | (x4 << 60)
    36  	(*x)[4] = (x4 >> 4)
    37  }
    38  
    39  // condAddOrderN updates x = x+order if x is even, otherwise x remains unchanged.
    40  func condAddOrderN(x *[5]uint64) {
    41  	var o [4]uint64
    42  	isOdd := (x[0] & 0x1) - 1
    43  	for i := range orderGenerator {
    44  		o[i] = isOdd & orderGenerator[i]
    45  	}
    46  	x0, c0 := bits.Add64((*x)[0], o[0], 0)
    47  	x1, c1 := bits.Add64((*x)[1], o[1], c0)
    48  	x2, c2 := bits.Add64((*x)[2], o[2], c1)
    49  	x3, c3 := bits.Add64((*x)[3], o[3], c2)
    50  	x4, _ := bits.Add64((*x)[4], 0, c3)
    51  	(*x)[0] = x0
    52  	(*x)[1] = x1
    53  	(*x)[2] = x2
    54  	(*x)[3] = x3
    55  	(*x)[4] = x4
    56  }
    57  
    58  func recodeScalar(d *[65]int8, k *[32]byte) {
    59  	var m [5]uint64
    60  	m[0] = binary.LittleEndian.Uint64(k[0:8])
    61  	m[1] = binary.LittleEndian.Uint64(k[8:16])
    62  	m[2] = binary.LittleEndian.Uint64(k[16:24])
    63  	m[3] = binary.LittleEndian.Uint64(k[24:32])
    64  	condAddOrderN(&m)
    65  	for i := 0; i < 64; i++ {
    66  		d[i] = int8((m[0] & 0x1f) - 16)
    67  		subYDiv16(&m, int64(d[i]))
    68  	}
    69  	d[64] = int8(m[0])
    70  }
    71  
    72  func (P *pointR1) oddMultiples(T *[8]pointR2) {
    73  	var _2P, R pointR1
    74  	var _p2P pointR2
    75  	_2P.copy(P)
    76  	_2P.double()
    77  	_p2P.FromR1(&_2P)
    78  	R.copy(P)
    79  	T[0].FromR1(P)
    80  	for i := 1; i < 8; i++ {
    81  		R.add(&_p2P)
    82  		T[i].FromR1(&R)
    83  	}
    84  }
    85  
    86  // scalarMult calculates P = k*Q.
    87  func (P *pointR1) ScalarMult(k *[32]byte, Q *pointR1) {
    88  	var TabQ [8]pointR2
    89  	var S pointR2
    90  	var d [65]int8
    91  	Q.oddMultiples(&TabQ)
    92  	recodeScalar(&d, k)
    93  	P.SetIdentity()
    94  	for i := 64; i >= 0; i-- {
    95  		P.double()
    96  		P.double()
    97  		P.double()
    98  		P.double()
    99  		mask := d[i] >> 7
   100  		absDi := (d[i] + mask) ^ mask
   101  		inx := int((absDi - 1) >> 1)
   102  		sig := int((d[i] >> 7) & 0x1)
   103  		for j := range TabQ {
   104  			S.cmov(&TabQ[j], int((uint64(uint32(inx^j))-1)>>63))
   105  		}
   106  		S.cneg(sig)
   107  		P.add(&S)
   108  	}
   109  }
   110  
   111  // absolute returns always a positive value.
   112  func absolute(x int32) int32 {
   113  	mask := x >> 31
   114  	return (x + mask) ^ mask
   115  }
   116  
   117  // div2subY update x = (x/2) - y.
   118  func div2subY(x *[5]uint64, y int64) {
   119  	s := uint64(y >> 63)
   120  	x0 := (*x)[0]
   121  	x1 := (*x)[1]
   122  	x2 := (*x)[2]
   123  	x3 := (*x)[3]
   124  	x0 = (x0 >> 1) | (x1 << 63)
   125  	x1 = (x1 >> 1) | (x2 << 63)
   126  	x2 = (x2 >> 1) | (x3 << 63)
   127  	x3 = (x3 >> 1)
   128  
   129  	x0, b0 := bits.Sub64(x0, uint64(y), 0)
   130  	x1, b1 := bits.Sub64(x1, s, b0)
   131  	x2, b2 := bits.Sub64(x2, s, b1)
   132  	x3, _ = bits.Sub64(x3, s, b2)
   133  	(*x)[0] = x0
   134  	(*x)[1] = x1
   135  	(*x)[2] = x2
   136  	(*x)[3] = x3
   137  }
   138  
   139  // mLSBRecoding is the odd-only modified LSB-set.
   140  //
   141  // Reference:
   142  //
   143  //	"Efficient and secure algorithms for GLV-based scalar multiplication and
   144  //	 their implementation on GLV–GLS curves" by (Faz-Hernandez et al.)
   145  //	 http://doi.org/10.1007/s13389-014-0085-7.
   146  func mLSBRecoding(L []int8, k []byte) {
   147  	const e = (fxT + fxW*fxV - 1) / (fxW * fxV)
   148  	const d = e * fxV
   149  	const l = d * fxW
   150  	if len(L) == (l + 1) {
   151  		var m [5]uint64
   152  		m[0] = binary.LittleEndian.Uint64(k[0:8])
   153  		m[1] = binary.LittleEndian.Uint64(k[8:16])
   154  		m[2] = binary.LittleEndian.Uint64(k[16:24])
   155  		m[3] = binary.LittleEndian.Uint64(k[24:32])
   156  		condAddOrderN(&m)
   157  
   158  		L[d-1] = 1
   159  		for i := 0; i < d-1; i++ {
   160  			kip1 := (m[(i+1)/64] >> (uint(i+1) % 64)) & 0x1
   161  			L[i] = int8(kip1<<1) - 1
   162  		}
   163  		{ // right-shift by d
   164  			const right = (d % 64)
   165  			const left = 64 - (d % 64)
   166  			const lim = (5*64 - d) / 64
   167  			const j = d / 64
   168  			for i := 0; i < lim; i++ {
   169  				m[i] = (m[i+j] >> right) | (m[i+j+1] << left)
   170  			}
   171  			m[lim] = m[lim+j] >> right
   172  		}
   173  		for i := d; i < l; i++ {
   174  			L[i] = L[i%d] * int8(m[0]&0x1)
   175  			div2subY(&m, int64(L[i]>>1))
   176  		}
   177  		L[l] = int8(m[0])
   178  	}
   179  }
   180  
   181  func (P *pointR1) ScalarBaseMult(scalar *[Size]byte) {
   182  	var S pointR3
   183  	const e = (fxT + fxW*fxV - 1) / (fxW * fxV)
   184  	const d = e * fxV
   185  	const l = d * fxW
   186  
   187  	var L [l + 1]int8
   188  	mLSBRecoding(L[:], scalar[:])
   189  	P.SetIdentity()
   190  	for ii := e - 1; ii >= 0; ii-- {
   191  		P.double()
   192  		for j := 0; j < fxV; j++ {
   193  			dig := L[fxW*d-j*e+ii-e]
   194  			for i := (fxW-1)*d - j*e + ii - e; i >= (2*d - j*e + ii - e); i = i - d {
   195  				dig = 2*dig + L[i]
   196  			}
   197  			idx := absolute(int32(dig))
   198  			sig := L[d-j*e+ii-e]
   199  			Tabj := &tableBaseFixed[fxV-j-1]
   200  			for k := 0; k < fx2w1; k++ {
   201  				S.cmov(&Tabj[k], subtle.ConstantTimeEq(int32(k), idx))
   202  			}
   203  			S.cneg(subtle.ConstantTimeEq(int32(sig), -1))
   204  			P.mixAdd(&S)
   205  		}
   206  	}
   207  }
   208  
   209  func (P *pointR1) copy(Q *pointR1) {
   210  	fqCopy(&P.X, &Q.X)
   211  	fqCopy(&P.Y, &Q.Y)
   212  	fqCopy(&P.Ta, &Q.Ta)
   213  	fqCopy(&P.Tb, &Q.Tb)
   214  	fqCopy(&P.Z, &Q.Z)
   215  }
   216  
   217  func (P *pointR1) SetIdentity() {
   218  	P.X.setZero()
   219  	P.Y.setOne()
   220  	P.Ta.setZero()
   221  	P.Tb.setZero()
   222  	P.Z.setOne()
   223  }
   224  
   225  func (P *pointR1) IsIdentity() bool {
   226  	t0, t1 := &Fq{}, &Fq{}
   227  	fqMul(t0, &P.Ta, &P.Tb)
   228  	fqSub(t1, &P.Y, &P.Z)
   229  	return P.X.isZero() && t0.isZero() && t1.isZero()
   230  }
   231  
   232  func (P *pointR1) ToAffine() {
   233  	fqInv(&P.Z, &P.Z)
   234  	fqMul(&P.X, &P.X, &P.Z)
   235  	fqMul(&P.Y, &P.Y, &P.Z)
   236  	fqMul(&P.Ta, &P.X, &P.Y)
   237  	P.Tb.setOne()
   238  	P.Z.setOne()
   239  }
   240  
   241  // Marshal encodes a point P into out buffer.
   242  func (P *Point) Marshal(out *[Size]byte) {
   243  	P.Y.toBytes(out[:])
   244  	// b=0 if x is positive or zero
   245  	// b=1 if x is negative
   246  	b := (1 - fqSgn(&P.X)) >> 1
   247  	out[Size-1] |= byte(b) << 7
   248  }
   249  
   250  // Unmarshal retrieves a point P from the input buffer. On success, returns true.
   251  func (P *Point) Unmarshal(in *[Size]byte) bool {
   252  	s := in[Size-1] >> 7
   253  	in[Size-1] &= 0x7F
   254  	if ok := P.Y.fromBytes(in[:]); !ok {
   255  		return ok
   256  	}
   257  	in[Size-1] |= s << 7
   258  
   259  	t0, t1, one := &Fq{}, &Fq{}, &Fq{}
   260  	one.setOne()
   261  	fqSqr(t0, &P.Y)                  // t0 = y^2
   262  	fqMul(t1, t0, &paramD)           // t1 = d*y^2
   263  	fqSub(t0, t0, one)               // t0 = y^2 - 1
   264  	fqAdd(t1, t1, one)               // t1 = d*y^2 + 1
   265  	fqSqrt(&P.X, t0, t1, 1-2*int(s)) // x = sqrt(t0/t1)
   266  
   267  	if !P.IsOnCurve() {
   268  		fpNeg(&P.X[1], &P.X[1])
   269  	}
   270  	return true
   271  }
   272  
   273  func (P *pointR1) IsOnCurve() bool {
   274  	t0, lhs, rhs := &Fq{}, &Fq{}, &Fq{}
   275  
   276  	fqAdd(t0, &P.Y, &P.X)    // t0  = y + x
   277  	fqSub(lhs, &P.Y, &P.X)   // lhs = y - x
   278  	fqMul(lhs, lhs, t0)      // lhs = y^2 - x^2
   279  	fqMul(rhs, &P.X, &P.Y)   // rhs = xy
   280  	fqSqr(rhs, rhs)          // rhs = x^2y^2
   281  	fqMul(rhs, rhs, &paramD) // rhs = dx^2y^2
   282  	t0.setOne()              // t0  = 1
   283  	fqAdd(rhs, rhs, t0)      // rhs = 1 + dx^2y^2
   284  	fqSub(t0, lhs, rhs)      // t0 = -x^2 + y^2 - (1 + dx^2y^2)
   285  	return t0.isZero()
   286  }
   287  
   288  func (P *pointR1) isEqual(Q *pointR1) bool {
   289  	l, r := &Fq{}, &Fq{}
   290  	fqMul(l, &P.X, &Q.Z)
   291  	fqMul(r, &Q.X, &P.Z)
   292  	fqSub(l, l, r)
   293  	b := l.isZero()
   294  	fqMul(l, &P.Y, &Q.Z)
   295  	fqMul(r, &Q.Y, &P.Z)
   296  	fqSub(l, l, r)
   297  	b = b && l.isZero()
   298  	fqMul(l, &P.Ta, &P.Tb)
   299  	fqMul(l, l, &Q.Z)
   300  	fqMul(r, &Q.Ta, &Q.Tb)
   301  	fqMul(r, r, &P.Z)
   302  	fqSub(l, l, r)
   303  	b = b && l.isZero()
   304  	return b
   305  }
   306  
   307  func (P *pointR1) ClearCofactor() {
   308  	var Q pointR2
   309  	Q.FromR1(P)
   310  	P.double()
   311  	P.add(&Q)
   312  	P.double()
   313  	P.double()
   314  	P.double()
   315  	P.double()
   316  	P.add(&Q)
   317  	P.double()
   318  	P.double()
   319  	P.double()
   320  }
   321  
   322  func (P *pointR2) FromR1(Q *pointR1) {
   323  	fqAdd(&P.addYX, &Q.Y, &Q.X)
   324  	fqSub(&P.subYX, &Q.Y, &Q.X)
   325  	fqAdd(&P.z2, &Q.Z, &Q.Z)
   326  	fqMul(&P.dt2, &Q.Ta, &Q.Tb)
   327  	fqMul(&P.dt2, &P.dt2, &paramD)
   328  	fqAdd(&P.dt2, &P.dt2, &P.dt2)
   329  }
   330  
   331  func (P *pointR2) cmov(Q *pointR2, b int) {
   332  	P.pointR3.cmov(&Q.pointR3, b)
   333  	fqCmov(&P.z2, &Q.z2, b)
   334  }
   335  
   336  func (P *pointR3) cneg(b int) {
   337  	var t Fq
   338  	fqCopy(&t, &P.addYX)
   339  	fqCmov(&P.addYX, &P.subYX, b)
   340  	fqCmov(&P.subYX, &t, b)
   341  	fqNeg(&t, &P.dt2)
   342  	fqCmov(&P.dt2, &t, b)
   343  }
   344  
   345  func (P *pointR3) cmov(Q *pointR3, b int) {
   346  	fqCmov(&P.addYX, &Q.addYX, b)
   347  	fqCmov(&P.subYX, &Q.subYX, b)
   348  	fqCmov(&P.dt2, &Q.dt2, b)
   349  }
   350
View as plain text