point.go

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

     1  package ed25519
     2  
     3  import fp "github.com/cloudflare/circl/math/fp25519"
     4  
     5  type (
     6  	pointR1 struct{ x, y, z, ta, tb fp.Elt }
     7  	pointR2 struct {
     8  		pointR3
     9  		z2 fp.Elt
    10  	}
    11  )
    12  type pointR3 struct{ addYX, subYX, dt2 fp.Elt }
    13  
    14  func (P *pointR1) neg() {
    15  	fp.Neg(&P.x, &P.x)
    16  	fp.Neg(&P.ta, &P.ta)
    17  }
    18  
    19  func (P *pointR1) SetIdentity() {
    20  	P.x = fp.Elt{}
    21  	fp.SetOne(&P.y)
    22  	fp.SetOne(&P.z)
    23  	P.ta = fp.Elt{}
    24  	P.tb = fp.Elt{}
    25  }
    26  
    27  func (P *pointR1) toAffine() {
    28  	fp.Inv(&P.z, &P.z)
    29  	fp.Mul(&P.x, &P.x, &P.z)
    30  	fp.Mul(&P.y, &P.y, &P.z)
    31  	fp.Modp(&P.x)
    32  	fp.Modp(&P.y)
    33  	fp.SetOne(&P.z)
    34  	P.ta = P.x
    35  	P.tb = P.y
    36  }
    37  
    38  func (P *pointR1) ToBytes(k []byte) error {
    39  	P.toAffine()
    40  	var x [fp.Size]byte
    41  	err := fp.ToBytes(k[:fp.Size], &P.y)
    42  	if err != nil {
    43  		return err
    44  	}
    45  	err = fp.ToBytes(x[:], &P.x)
    46  	if err != nil {
    47  		return err
    48  	}
    49  	b := x[0] & 1
    50  	k[paramB-1] = k[paramB-1] | (b << 7)
    51  	return nil
    52  }
    53  
    54  func (P *pointR1) FromBytes(k []byte) bool {
    55  	if len(k) != paramB {
    56  		panic("wrong size")
    57  	}
    58  	signX := k[paramB-1] >> 7
    59  	copy(P.y[:], k[:fp.Size])
    60  	P.y[fp.Size-1] &= 0x7F
    61  	p := fp.P()
    62  	if !isLessThan(P.y[:], p[:]) {
    63  		return false
    64  	}
    65  
    66  	one, u, v := &fp.Elt{}, &fp.Elt{}, &fp.Elt{}
    67  	fp.SetOne(one)
    68  	fp.Sqr(u, &P.y)                // u = y^2
    69  	fp.Mul(v, u, &paramD)          // v = dy^2
    70  	fp.Sub(u, u, one)              // u = y^2-1
    71  	fp.Add(v, v, one)              // v = dy^2+1
    72  	isQR := fp.InvSqrt(&P.x, u, v) // x = sqrt(u/v)
    73  	if !isQR {
    74  		return false
    75  	}
    76  	fp.Modp(&P.x) // x = x mod p
    77  	if fp.IsZero(&P.x) && signX == 1 {
    78  		return false
    79  	}
    80  	if signX != (P.x[0] & 1) {
    81  		fp.Neg(&P.x, &P.x)
    82  	}
    83  	P.ta = P.x
    84  	P.tb = P.y
    85  	fp.SetOne(&P.z)
    86  	return true
    87  }
    88  
    89  // double calculates 2P for curves with A=-1.
    90  func (P *pointR1) double() {
    91  	Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
    92  	a, b, c, e, f, g, h := Px, Py, Pz, Pta, Px, Py, Ptb
    93  	fp.Add(e, Px, Py) // x+y
    94  	fp.Sqr(a, Px)     // A = x^2
    95  	fp.Sqr(b, Py)     // B = y^2
    96  	fp.Sqr(c, Pz)     // z^2
    97  	fp.Add(c, c, c)   // C = 2*z^2
    98  	fp.Add(h, a, b)   // H = A+B
    99  	fp.Sqr(e, e)      // (x+y)^2
   100  	fp.Sub(e, e, h)   // E = (x+y)^2-A-B
   101  	fp.Sub(g, b, a)   // G = B-A
   102  	fp.Sub(f, c, g)   // F = C-G
   103  	fp.Mul(Pz, f, g)  // Z = F * G
   104  	fp.Mul(Px, e, f)  // X = E * F
   105  	fp.Mul(Py, g, h)  // Y = G * H, T = E * H
   106  }
   107  
   108  func (P *pointR1) mixAdd(Q *pointR3) {
   109  	fp.Add(&P.z, &P.z, &P.z) // D = 2*z1
   110  	P.coreAddition(Q)
   111  }
   112  
   113  func (P *pointR1) add(Q *pointR2) {
   114  	fp.Mul(&P.z, &P.z, &Q.z2) // D = 2*z1*z2
   115  	P.coreAddition(&Q.pointR3)
   116  }
   117  
   118  // coreAddition calculates P=P+Q for curves with A=-1.
   119  func (P *pointR1) coreAddition(Q *pointR3) {
   120  	Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
   121  	addYX2, subYX2, dt2 := &Q.addYX, &Q.subYX, &Q.dt2
   122  	a, b, c, d, e, f, g, h := Px, Py, &fp.Elt{}, Pz, Pta, Px, Py, Ptb
   123  	fp.Mul(c, Pta, Ptb)  // t1 = ta*tb
   124  	fp.Sub(h, Py, Px)    // y1-x1
   125  	fp.Add(b, Py, Px)    // y1+x1
   126  	fp.Mul(a, h, subYX2) // A = (y1-x1)*(y2-x2)
   127  	fp.Mul(b, b, addYX2) // B = (y1+x1)*(y2+x2)
   128  	fp.Mul(c, c, dt2)    // C = 2*D*t1*t2
   129  	fp.Sub(e, b, a)      // E = B-A
   130  	fp.Add(h, b, a)      // H = B+A
   131  	fp.Sub(f, d, c)      // F = D-C
   132  	fp.Add(g, d, c)      // G = D+C
   133  	fp.Mul(Pz, f, g)     // Z = F * G
   134  	fp.Mul(Px, e, f)     // X = E * F
   135  	fp.Mul(Py, g, h)     // Y = G * H, T = E * H
   136  }
   137  
   138  func (P *pointR1) oddMultiples(T []pointR2) {
   139  	var R pointR2
   140  	n := len(T)
   141  	T[0].fromR1(P)
   142  	_2P := *P
   143  	_2P.double()
   144  	R.fromR1(&_2P)
   145  	for i := 1; i < n; i++ {
   146  		P.add(&R)
   147  		T[i].fromR1(P)
   148  	}
   149  }
   150  
   151  func (P *pointR1) isEqual(Q *pointR1) bool {
   152  	l, r := &fp.Elt{}, &fp.Elt{}
   153  	fp.Mul(l, &P.x, &Q.z)
   154  	fp.Mul(r, &Q.x, &P.z)
   155  	fp.Sub(l, l, r)
   156  	b := fp.IsZero(l)
   157  	fp.Mul(l, &P.y, &Q.z)
   158  	fp.Mul(r, &Q.y, &P.z)
   159  	fp.Sub(l, l, r)
   160  	b = b && fp.IsZero(l)
   161  	fp.Mul(l, &P.ta, &P.tb)
   162  	fp.Mul(l, l, &Q.z)
   163  	fp.Mul(r, &Q.ta, &Q.tb)
   164  	fp.Mul(r, r, &P.z)
   165  	fp.Sub(l, l, r)
   166  	b = b && fp.IsZero(l)
   167  	return b
   168  }
   169  
   170  func (P *pointR3) neg() {
   171  	P.addYX, P.subYX = P.subYX, P.addYX
   172  	fp.Neg(&P.dt2, &P.dt2)
   173  }
   174  
   175  func (P *pointR2) fromR1(Q *pointR1) {
   176  	fp.Add(&P.addYX, &Q.y, &Q.x)
   177  	fp.Sub(&P.subYX, &Q.y, &Q.x)
   178  	fp.Mul(&P.dt2, &Q.ta, &Q.tb)
   179  	fp.Mul(&P.dt2, &P.dt2, &paramD)
   180  	fp.Add(&P.dt2, &P.dt2, &P.dt2)
   181  	fp.Add(&P.z2, &Q.z, &Q.z)
   182  }
   183  
   184  func (P *pointR3) cneg(b int) {
   185  	t := &fp.Elt{}
   186  	fp.Cswap(&P.addYX, &P.subYX, uint(b))
   187  	fp.Neg(t, &P.dt2)
   188  	fp.Cmov(&P.dt2, t, uint(b))
   189  }
   190  
   191  func (P *pointR3) cmov(Q *pointR3, b int) {
   192  	fp.Cmov(&P.addYX, &Q.addYX, uint(b))
   193  	fp.Cmov(&P.subYX, &Q.subYX, uint(b))
   194  	fp.Cmov(&P.dt2, &Q.dt2, uint(b))
   195  }
   196
View as plain text