fq.go

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

     1  package fourq
     2  
     3  import (
     4  	"crypto/subtle"
     5  	"math/big"
     6  )
     7  
     8  // Fq implements operations of a field of size q=p^2 as a quadratic
     9  // extension of the base field where i^2=-1.
    10  // An element in Fq is represented as f[0]+f[1]*i, where f[0],f[1] are in Fp.
    11  type Fq [2]Fp
    12  
    13  func (e *Fq) String() string              { return e[1].String() + " *i+ " + e[0].String() }
    14  func (e *Fq) toBigInt() (f0, f1 *big.Int) { return e[0].toBigInt(), e[1].toBigInt() }
    15  func (e *Fq) setBigInt(f0, f1 *big.Int)   { e[0].setBigInt(f0); e[1].setBigInt(f1) }
    16  func (e *Fq) setZero()                    { var z Fp; e[0] = z; e[1] = z }
    17  func (e *Fq) setOne()                     { e.setZero(); e[0][0] = 1 }
    18  func (e *Fq) isZero() bool                { return e[0].isZero() && e[1].isZero() }
    19  
    20  func (e *Fq) toBytes(buf []byte) {
    21  	if len(buf) == 2*SizeFp {
    22  		e[0].toBytes(buf[:SizeFp])
    23  		e[1].toBytes(buf[SizeFp:])
    24  	}
    25  }
    26  
    27  func (e *Fq) fromBytes(buf []byte) bool {
    28  	if len(buf) == 2*SizeFp {
    29  		return e[0].fromBytes(buf[:SizeFp]) &&
    30  			e[1].fromBytes(buf[SizeFp:])
    31  	}
    32  	return false
    33  }
    34  
    35  func fqSgn(c *Fq) int {
    36  	s0 := fpSgn(&c[0])
    37  	s1 := fpSgn(&c[1])
    38  	return subtle.ConstantTimeSelect(s0&0x1, s0, s1)
    39  }
    40  func fqCopy(c, a *Fq) { *c = *a }
    41  func fqNeg(c, a *Fq)  { fpNeg(&c[0], &a[0]); fpNeg(&c[1], &a[1]) }
    42  
    43  // fqSqrt calculates c = sqrt(u/v) such that sgn(c)=s.
    44  func fqSqrt(c, u, v *Fq, s int) {
    45  	t0, t1, t, r := &Fp{}, &Fp{}, &Fp{}, &Fp{}
    46  	a, b, g := &Fp{}, &Fp{}, &Fp{}
    47  
    48  	// a = u0*v0 + u1*v1
    49  	fpMul(a, &u[0], &v[0])
    50  	fpMul(t0, &u[1], &v[1])
    51  	fpAdd(a, a, t0)
    52  
    53  	// b = v0^2 + v1^2
    54  	fpSqr(b, &v[0])
    55  	fpSqr(t0, &v[1])
    56  	fpAdd(b, b, t0)
    57  
    58  	// g = u1*v0 - u0*v1
    59  	fpMul(g, &u[1], &v[0])
    60  	fpMul(t0, &u[0], &v[1])
    61  	fpSub(g, g, t0)
    62  
    63  	// t = 2(a + sqrt(a^2+g^2)) = 2*(a + (a^2+g^2)^(2^125))
    64  	// if t=0; then t = 2*(a - (a^2+g^2)^(2^125))
    65  	fpSqr(t0, a)
    66  	fpSqr(t1, g)
    67  	fpAdd(t0, t0, t1)
    68  	for i := 0; i < 125; i++ {
    69  		fpSqr(t0, t0)
    70  	}
    71  	fpAdd(t, a, t0)
    72  	if t.isZero() {
    73  		fpSub(t, a, t0)
    74  	}
    75  	fpAdd(t, t, t)
    76  
    77  	// r = (t*b^3)^(2^125-1)
    78  	fpSqr(r, b)
    79  	fpMul(r, r, b)
    80  	fpMul(r, r, t)
    81  	fpTwo1251(r, r)
    82  
    83  	// x0 = (r*b*t)/2
    84  	// x1 = (r*b*g)
    85  	fpMul(&c[1], r, b)
    86  	fpMul(&c[0], &c[1], t)
    87  	fpHlf(&c[0], &c[0])
    88  	fpMul(&c[1], &c[1], g)
    89  
    90  	// if b*(2*x0)^2 == t then (x0,x1) <- (x1,x0)
    91  	fpAdd(t0, &c[0], &c[0])
    92  	fpSqr(t0, t0)
    93  	fpMul(t0, t0, b)
    94  	fpSub(t0, t0, t)
    95  	if !t0.isZero() {
    96  		*t0 = c[0]
    97  		c[0] = c[1]
    98  		c[1] = *t0
    99  	}
   100  
   101  	if fqSgn(c) != s {
   102  		fqNeg(c, c)
   103  	}
   104  }
   105  
   106  func fqInv(c, a *Fq) {
   107  	t1, t2 := &Fp{}, &Fp{}
   108  	fpSqr(t1, &a[0])
   109  	fpSqr(t2, &a[1])
   110  	fpAdd(t1, t1, t2)
   111  	fpInv(t1, t1)
   112  	fpMul(&c[0], &a[0], t1)
   113  	fpNeg(t1, t1)
   114  	fpMul(&c[1], &a[1], t1)
   115  }
   116
View as plain text