p384opt.go

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

     1  //go:build (!noasm && arm64) || (!noasm && amd64)
     2  // +build !noasm,arm64 !noasm,amd64
     3  
     4  package p384
     5  
     6  import (
     7  	"crypto/subtle"
     8  	"math/big"
     9  
    10  	"github.com/cloudflare/circl/math"
    11  )
    12  
    13  type curve struct{}
    14  
    15  // P384 returns a Curve which implements P-384 (see FIPS 186-3, section D.2.4).
    16  func P384() Curve { return curve{} }
    17  
    18  // IsOnCurve reports whether the given (x,y) lies on the curve.
    19  func (c curve) IsOnCurve(x, y *big.Int) bool {
    20  	x1, y1 := &fp384{}, &fp384{}
    21  	x1.SetBigInt(x)
    22  	y1.SetBigInt(y)
    23  	montEncode(x1, x1)
    24  	montEncode(y1, y1)
    25  
    26  	y2, x3 := &fp384{}, &fp384{}
    27  	fp384Sqr(y2, y1)
    28  	fp384Sqr(x3, x1)
    29  	fp384Mul(x3, x3, x1)
    30  
    31  	threeX := &fp384{}
    32  	fp384Add(threeX, x1, x1)
    33  	fp384Add(threeX, threeX, x1)
    34  
    35  	fp384Sub(x3, x3, threeX)
    36  	fp384Add(x3, x3, &bb)
    37  
    38  	return *y2 == *x3
    39  }
    40  
    41  // Add returns the sum of (x1,y1) and (x2,y2).
    42  func (c curve) Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int) {
    43  	P := newAffinePoint(x1, y1).toJacobian()
    44  	P.mixadd(P, newAffinePoint(x2, y2))
    45  	return P.toAffine().toInt()
    46  }
    47  
    48  // Double returns 2*(x,y).
    49  func (c curve) Double(x1, y1 *big.Int) (x, y *big.Int) {
    50  	P := newAffinePoint(x1, y1).toJacobian()
    51  	P.double()
    52  	return P.toAffine().toInt()
    53  }
    54  
    55  // reduceScalar shorten a scalar modulo the order of the curve.
    56  func (c curve) reduceScalar(k []byte) []byte {
    57  	bigK := new(big.Int).SetBytes(k)
    58  	bigK.Mod(bigK, c.Params().N)
    59  	return bigK.FillBytes(make([]byte, sizeFp))
    60  }
    61  
    62  // toOdd performs k = (-k mod N) if k is even.
    63  func (c curve) toOdd(k []byte) ([]byte, int) {
    64  	var X, Y big.Int
    65  	X.SetBytes(k)
    66  	Y.Neg(&X).Mod(&Y, c.Params().N)
    67  	isEven := 1 - int(X.Bit(0))
    68  	x := X.Bytes()
    69  	y := Y.Bytes()
    70  
    71  	if len(x) < len(y) {
    72  		x = append(make([]byte, len(y)-len(x)), x...)
    73  	} else if len(x) > len(y) {
    74  		y = append(make([]byte, len(x)-len(y)), y...)
    75  	}
    76  	subtle.ConstantTimeCopy(isEven, x, y)
    77  	return x, isEven
    78  }
    79  
    80  // ScalarMult returns (Qx,Qy)=k*(Px,Py) where k is a number in big-endian form.
    81  func (c curve) ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int) {
    82  	return c.scalarMultOmega(x1, y1, k, 5)
    83  }
    84  
    85  func (c curve) scalarMultOmega(x1, y1 *big.Int, k []byte, omega uint) (x, y *big.Int) {
    86  	k = c.reduceScalar(k)
    87  	oddK, isEvenK := c.toOdd(k)
    88  
    89  	var scalar big.Int
    90  	scalar.SetBytes(oddK)
    91  	if scalar.Sign() == 0 {
    92  		return new(big.Int), new(big.Int)
    93  	}
    94  	const bitsN = uint(384)
    95  	L := math.SignedDigit(&scalar, omega, bitsN)
    96  
    97  	var R jacobianPoint
    98  	Q := zeroPoint().toJacobian()
    99  	TabP := newAffinePoint(x1, y1).oddMultiples(omega)
   100  	for i := len(L) - 1; i > 0; i-- {
   101  		for j := uint(0); j < omega-1; j++ {
   102  			Q.double()
   103  		}
   104  		idx := absolute(L[i]) >> 1
   105  		for j := range TabP {
   106  			R.cmov(&TabP[j], subtle.ConstantTimeEq(int32(j), idx))
   107  		}
   108  		R.cneg(int(L[i]>>31) & 1)
   109  		Q.add(Q, &R)
   110  	}
   111  	// Calculate the last iteration using complete addition formula.
   112  	for j := uint(0); j < omega-1; j++ {
   113  		Q.double()
   114  	}
   115  	idx := absolute(L[0]) >> 1
   116  	for j := range TabP {
   117  		R.cmov(&TabP[j], subtle.ConstantTimeEq(int32(j), idx))
   118  	}
   119  	R.cneg(int(L[0]>>31) & 1)
   120  	QQ := Q.toProjective()
   121  	QQ.completeAdd(QQ, R.toProjective())
   122  	QQ.cneg(isEvenK)
   123  	return QQ.toAffine().toInt()
   124  }
   125  
   126  // ScalarBaseMult returns k*G, where G is the base point of the group
   127  // and k is an integer in big-endian form.
   128  func (c curve) ScalarBaseMult(k []byte) (x, y *big.Int) {
   129  	params := c.Params()
   130  	return c.ScalarMult(params.Gx, params.Gy, k)
   131  }
   132  
   133  // CombinedMult calculates P=mG+nQ, where G is the generator and Q=(x,y,z).
   134  // The scalars m and n are integers in big-endian form. Non-constant time.
   135  func (c curve) CombinedMult(xQ, yQ *big.Int, m, n []byte) (xP, yP *big.Int) {
   136  	const nOmega = uint(5)
   137  	var k big.Int
   138  	k.SetBytes(m)
   139  	nafM := math.OmegaNAF(&k, baseOmega)
   140  	k.SetBytes(n)
   141  	nafN := math.OmegaNAF(&k, nOmega)
   142  
   143  	if len(nafM) > len(nafN) {
   144  		nafN = append(nafN, make([]int32, len(nafM)-len(nafN))...)
   145  	} else if len(nafM) < len(nafN) {
   146  		nafM = append(nafM, make([]int32, len(nafN)-len(nafM))...)
   147  	}
   148  
   149  	TabQ := newAffinePoint(xQ, yQ).oddMultiples(nOmega)
   150  	var jR jacobianPoint
   151  	var aR affinePoint
   152  	P := zeroPoint().toJacobian()
   153  	for i := len(nafN) - 1; i >= 0; i-- {
   154  		P.double()
   155  		// Generator point
   156  		if nafM[i] != 0 {
   157  			idxM := absolute(nafM[i]) >> 1
   158  			aR = baseOddMultiples[idxM]
   159  			if nafM[i] < 0 {
   160  				aR.neg()
   161  			}
   162  			P.mixadd(P, &aR)
   163  		}
   164  		// Input point
   165  		if nafN[i] != 0 {
   166  			idxN := absolute(nafN[i]) >> 1
   167  			jR = TabQ[idxN]
   168  			if nafN[i] < 0 {
   169  				jR.neg()
   170  			}
   171  			P.add(P, &jR)
   172  		}
   173  	}
   174  	return P.toAffine().toInt()
   175  }
   176  
   177  // absolute returns always a positive value.
   178  func absolute(x int32) int32 {
   179  	mask := x >> 31
   180  	return (x + mask) ^ mask
   181  }
   182
View as plain text