curve.go

Documentation: github.com/cloudflare/circl/dh/csidh

     1  package csidh
     2  
     3  // xAdd implements differential arithmetic in P^1 for Montgomery
     4  // curves E(x): x^3 + A*x^2 + x by using x-coordinate only arithmetic.
     5  //
     6  //	x(PaQ) = x(P) + x(Q) by using x(P-Q)
     7  //
     8  // This algorithms is correctly defined only for cases when
     9  // P!=inf, Q!=inf, P!=Q and P!=-Q.
    10  func xAdd(PaQ, P, Q, PdQ *point) {
    11  	var t0, t1, t2, t3 fp
    12  	addRdc(&t0, &P.x, &P.z)
    13  	subRdc(&t1, &P.x, &P.z)
    14  	addRdc(&t2, &Q.x, &Q.z)
    15  	subRdc(&t3, &Q.x, &Q.z)
    16  	mulRdc(&t0, &t0, &t3)
    17  	mulRdc(&t1, &t1, &t2)
    18  	addRdc(&t2, &t0, &t1)
    19  	subRdc(&t3, &t0, &t1)
    20  	mulRdc(&t2, &t2, &t2) // sqr
    21  	mulRdc(&t3, &t3, &t3) // sqr
    22  	mulRdc(&PaQ.x, &PdQ.z, &t2)
    23  	mulRdc(&PaQ.z, &PdQ.x, &t3)
    24  }
    25  
    26  // xDbl implements point doubling on a Montgomery curve
    27  // E(x): x^3 + A*x^2 + x by using x-coordinate only arithmetic.
    28  //
    29  //	x(Q) = [2]*x(P)
    30  //
    31  // It is correctly defined for all P != inf.
    32  func xDbl(Q, P, A *point) {
    33  	var t0, t1, t2 fp
    34  	addRdc(&t0, &P.x, &P.z)
    35  	mulRdc(&t0, &t0, &t0) // sqr
    36  	subRdc(&t1, &P.x, &P.z)
    37  	mulRdc(&t1, &t1, &t1) // sqr
    38  	subRdc(&t2, &t0, &t1)
    39  	mulRdc(&t1, &four, &t1)
    40  	mulRdc(&t1, &t1, &A.z)
    41  	mulRdc(&Q.x, &t0, &t1)
    42  	addRdc(&t0, &A.z, &A.z)
    43  	addRdc(&t0, &t0, &A.x)
    44  	mulRdc(&t0, &t0, &t2)
    45  	addRdc(&t0, &t0, &t1)
    46  	mulRdc(&Q.z, &t0, &t2)
    47  }
    48  
    49  // xDblAdd implements combined doubling of point P
    50  // and addition of points P and Q on a Montgomery curve
    51  // E(x): x^3 + A*x^2 + x by using x-coordinate only arithmetic.
    52  //
    53  //	x(PaP) = x(2*P)
    54  //	x(PaQ) = x(P+Q)
    55  func xDblAdd(PaP, PaQ, P, Q, PdQ *point, A24 *coeff) {
    56  	var t0, t1, t2 fp
    57  
    58  	addRdc(&t0, &P.x, &P.z)
    59  	subRdc(&t1, &P.x, &P.z)
    60  	mulRdc(&PaP.x, &t0, &t0)
    61  	subRdc(&t2, &Q.x, &Q.z)
    62  	addRdc(&PaQ.x, &Q.x, &Q.z)
    63  	mulRdc(&t0, &t0, &t2)
    64  	mulRdc(&PaP.z, &t1, &t1)
    65  	mulRdc(&t1, &t1, &PaQ.x)
    66  	subRdc(&t2, &PaP.x, &PaP.z)
    67  	mulRdc(&PaP.z, &PaP.z, &A24.c)
    68  	mulRdc(&PaP.x, &PaP.x, &PaP.z)
    69  	mulRdc(&PaQ.x, &A24.a, &t2)
    70  	subRdc(&PaQ.z, &t0, &t1)
    71  	addRdc(&PaP.z, &PaP.z, &PaQ.x)
    72  	addRdc(&PaQ.x, &t0, &t1)
    73  	mulRdc(&PaP.z, &PaP.z, &t2)
    74  	mulRdc(&PaQ.z, &PaQ.z, &PaQ.z)
    75  	mulRdc(&PaQ.x, &PaQ.x, &PaQ.x)
    76  	mulRdc(&PaQ.z, &PaQ.z, &PdQ.x)
    77  	mulRdc(&PaQ.x, &PaQ.x, &PdQ.z)
    78  }
    79  
    80  // cswappoint swaps P1 with P2 in constant time. The 'choice'
    81  // parameter must have a value of either 1 (results
    82  // in swap) or 0 (results in no-swap).
    83  func cswappoint(P1, P2 *point, choice uint8) {
    84  	cswap512(&P1.x, &P2.x, choice)
    85  	cswap512(&P1.z, &P2.z, choice)
    86  }
    87  
    88  // xMul implements point multiplication with left-to-right Montgomery
    89  // adder. co is A coefficient of x^3 + A*x^2 + x curve. k must be > 0
    90  //
    91  // Non-constant time!
    92  func xMul(kP, P *point, co *coeff, k *fp) {
    93  	var A24 coeff
    94  	var Q point
    95  	var j uint
    96  	A := point{x: co.a, z: co.c}
    97  	R := *P
    98  
    99  	// Precompyte A24 = (A+2C:4C) => (A24.x = A.x+2A.z; A24.z = 4*A.z)
   100  	addRdc(&A24.a, &co.c, &co.c)
   101  	addRdc(&A24.a, &A24.a, &co.a)
   102  	mulRdc(&A24.c, &co.c, &four)
   103  
   104  	// Skip initial 0 bits.
   105  	for j = 511; j > 0; j-- {
   106  		// performance hit from making it constant-time is actually
   107  		// quite big, so... unsafe branch for now
   108  		if uint8(k[j>>6]>>(j&63)&1) != 0 {
   109  			break
   110  		}
   111  	}
   112  
   113  	xDbl(&Q, P, &A)
   114  	prevBit := uint8(1)
   115  	for i := j; i > 0; {
   116  		i--
   117  		bit := uint8(k[i>>6] >> (i & 63) & 1)
   118  		cswappoint(&Q, &R, prevBit^bit)
   119  		xDblAdd(&Q, &R, &Q, &R, P, &A24)
   120  		prevBit = bit
   121  	}
   122  	cswappoint(&Q, &R, uint8(k[0]&1))
   123  	*kP = Q
   124  }
   125  
   126  // xIso computes the isogeny with kernel point kern of a given order
   127  // kernOrder. Returns the new curve coefficient co and the image img.
   128  //
   129  // During computation function switches between Montgomery and twisted
   130  // Edwards curves in order to compute image curve parameters faster.
   131  // This technique is described by Meyer and Reith in ia.cr/2018/782.
   132  //
   133  // Non-constant time.
   134  func xIso(img *point, co *coeff, kern *point, kernOrder uint64) {
   135  	var t0, t1, t2, S, D fp
   136  	var Q, prod point
   137  	var coEd coeff
   138  	M := [3]point{*kern}
   139  
   140  	// Compute twisted Edwards coefficients
   141  	// coEd.a = co.a + 2*co.c
   142  	// coEd.c = co.a - 2*co.c
   143  	// coEd.a*X^2 + Y^2 = 1 + coEd.c*X^2*Y^2
   144  	addRdc(&coEd.c, &co.c, &co.c)
   145  	addRdc(&coEd.a, &co.a, &coEd.c)
   146  	subRdc(&coEd.c, &co.a, &coEd.c)
   147  
   148  	// Transfer point to twisted Edwards YZ-coordinates
   149  	// (X:Z)->(Y:Z) = (X-Z : X+Z)
   150  	addRdc(&S, &img.x, &img.z)
   151  	subRdc(&D, &img.x, &img.z)
   152  
   153  	subRdc(&prod.x, &kern.x, &kern.z)
   154  	addRdc(&prod.z, &kern.x, &kern.z)
   155  
   156  	mulRdc(&t1, &prod.x, &S)
   157  	mulRdc(&t0, &prod.z, &D)
   158  	addRdc(&Q.x, &t0, &t1)
   159  	subRdc(&Q.z, &t0, &t1)
   160  
   161  	xDbl(&M[1], kern, &point{x: co.a, z: co.c})
   162  
   163  	// NOTE: Not constant time.
   164  	for i := uint64(1); i < kernOrder>>1; i++ {
   165  		if i >= 2 {
   166  			xAdd(&M[i%3], &M[(i-1)%3], kern, &M[(i-2)%3])
   167  		}
   168  		subRdc(&t1, &M[i%3].x, &M[i%3].z)
   169  		addRdc(&t0, &M[i%3].x, &M[i%3].z)
   170  		mulRdc(&prod.x, &prod.x, &t1)
   171  		mulRdc(&prod.z, &prod.z, &t0)
   172  		mulRdc(&t1, &t1, &S)
   173  		mulRdc(&t0, &t0, &D)
   174  		addRdc(&t2, &t0, &t1)
   175  		mulRdc(&Q.x, &Q.x, &t2)
   176  		subRdc(&t2, &t0, &t1)
   177  		mulRdc(&Q.z, &Q.z, &t2)
   178  	}
   179  
   180  	mulRdc(&Q.x, &Q.x, &Q.x)
   181  	mulRdc(&Q.z, &Q.z, &Q.z)
   182  	mulRdc(&img.x, &img.x, &Q.x)
   183  	mulRdc(&img.z, &img.z, &Q.z)
   184  
   185  	// coEd.a^kernOrder and coEd.c^kernOrder
   186  	modExpRdc64(&coEd.a, &coEd.a, kernOrder)
   187  	modExpRdc64(&coEd.c, &coEd.c, kernOrder)
   188  
   189  	// prod^8
   190  	mulRdc(&prod.x, &prod.x, &prod.x)
   191  	mulRdc(&prod.x, &prod.x, &prod.x)
   192  	mulRdc(&prod.x, &prod.x, &prod.x)
   193  	mulRdc(&prod.z, &prod.z, &prod.z)
   194  	mulRdc(&prod.z, &prod.z, &prod.z)
   195  	mulRdc(&prod.z, &prod.z, &prod.z)
   196  
   197  	// Compute image curve params
   198  	mulRdc(&coEd.c, &coEd.c, &prod.x)
   199  	mulRdc(&coEd.a, &coEd.a, &prod.z)
   200  
   201  	// Convert curve coefficients back to Montgomery
   202  	addRdc(&co.a, &coEd.a, &coEd.c)
   203  	subRdc(&co.c, &coEd.a, &coEd.c)
   204  	addRdc(&co.a, &co.a, &co.a)
   205  }
   206  
   207  // montEval evaluates x^3 + Ax^2 + x.
   208  func montEval(res, A, x *fp) {
   209  	var t fp
   210  
   211  	*res = *x
   212  	mulRdc(res, res, res)
   213  	mulRdc(&t, A, x)
   214  	addRdc(res, res, &t)
   215  	addRdc(res, res, &one)
   216  	mulRdc(res, res, x)
   217  }
   218
View as plain text