Debian Codegraph @

dh/sidh/internal/templates/curve.gotemp

raw
1 // Code generated by go generate; DO NOT EDIT.
2 // This file was generated by robots.
3
4 package {{.PACKAGE}}
5
6 import (
7 "math"
8 "errors"
9 . "github.com/cloudflare/circl/dh/sidh/internal/common"
10 )
11
12 // Stores isogeny 3 curve constants
13 type isogeny3 struct {
14 K1 Fp2
15 K2 Fp2
16 }
17
18 // Stores isogeny 4 curve constants
19 type isogeny4 struct {
20 isogeny3
21 K3 Fp2
22 }
23
24 // Computes j-invariant for a curve y2=x3+A/Cx+x with A,C in F_(p^2). Result
25 // is returned in jBytes buffer, encoded in little-endian format. Caller
26 // provided jBytes buffer has to be big enough to j-invariant value. In case
27 // of SIDH, buffer size must be at least size of shared secret.
28 // Implementation corresponds to Algorithm 9 from SIKE.
29 func Jinvariant(cparams *ProjectiveCurveParameters, j *Fp2) {
30 var t0, t1 Fp2
31
32 sqr(j, &cparams.A) // j = A^2
33 sqr(&t1, &cparams.C) // t1 = C^2
34 add(&t0, &t1, &t1) // t0 = t1 + t1
35 sub(&t0, j, &t0) // t0 = j - t0
36 sub(&t0, &t0, &t1) // t0 = t0 - t1
37 sub(j, &t0, &t1) // t0 = t0 - t1
38 sqr(&t1, &t1) // t1 = t1^2
39 mul(j, j, &t1) // j = j * t1
40 add(&t0, &t0, &t0) // t0 = t0 + t0
41 add(&t0, &t0, &t0) // t0 = t0 + t0
42 sqr(&t1, &t0) // t1 = t0^2
43 mul(&t0, &t0, &t1) // t0 = t0 * t1
44 add(&t0, &t0, &t0) // t0 = t0 + t0
45 add(&t0, &t0, &t0) // t0 = t0 + t0
46 inv(j, j) // j = 1/j
47 mul(j, &t0, j) // j = t0 * j
48 }
49
50 // Given affine points x(P), x(Q) and x(Q-P) in a extension field F_{p^2}, function
51 // recovers projective coordinate A of a curve. This is Algorithm 10 from SIKE.
52 func RecoverCoordinateA(curve *ProjectiveCurveParameters, xp, xq, xr *Fp2) {
53 var t0, t1 Fp2
54
55 add(&t1, xp, xq) // t1 = Xp + Xq
56 mul(&t0, xp, xq) // t0 = Xp * Xq
57 mul(&curve.A, xr, &t1) // A = X(q-p) * t1
58 add(&curve.A, &curve.A, &t0) // A = A + t0
59 mul(&t0, &t0, xr) // t0 = t0 * X(q-p)
60 sub(&curve.A, &curve.A, &params.OneFp2) // A = A - 1
61 add(&t0, &t0, &t0) // t0 = t0 + t0
62 add(&t1, &t1, xr) // t1 = t1 + X(q-p)
63 add(&t0, &t0, &t0) // t0 = t0 + t0
64 sqr(&curve.A, &curve.A) // A = A^2
65 inv(&t0, &t0) // t0 = 1/t0
66 mul(&curve.A, &curve.A, &t0) // A = A * t0
67 sub(&curve.A, &curve.A, &t1) // A = A - t1
68 }
69
70 // Computes equivalence (A:C) ~ (A+2C : A-2C)
71 func CalcCurveParamsEquiv3(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv {
72 var coef CurveCoefficientsEquiv
73 var c2 Fp2
74
75 add(&c2, &cparams.C, &cparams.C)
76 // A24p = A+2*C
77 add(&coef.A, &cparams.A, &c2)
78 // A24m = A-2*C
79 sub(&coef.C, &cparams.A, &c2)
80 return coef
81 }
82
83 // Computes equivalence (A:C) ~ (A+2C : 4C)
84 func CalcCurveParamsEquiv4(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv {
85 var coefEq CurveCoefficientsEquiv
86
87 add(&coefEq.C, &cparams.C, &cparams.C)
88 // A24p = A+2C
89 add(&coefEq.A, &cparams.A, &coefEq.C)
90 // C24 = 4*C
91 add(&coefEq.C, &coefEq.C, &coefEq.C)
92 return coefEq
93 }
94
95 // Helper function for RightToLeftLadder(). Returns A+2C / 4.
96 func CalcAplus2Over4(cparams *ProjectiveCurveParameters) (ret Fp2) {
97 var tmp Fp2
98
99 // 2C
100 add(&tmp, &cparams.C, &cparams.C)
101 // A+2C
102 add(&ret, &cparams.A, &tmp)
103 // 1/4C
104 add(&tmp, &tmp, &tmp)
105 inv(&tmp, &tmp)
106 // A+2C/4C
107 mul(&ret, &ret, &tmp)
108 return
109 }
110
111 // Recovers (A:C) curve parameters from projectively equivalent (A+2C:A-2C).
112 func RecoverCurveCoefficients3(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv) {
113 add(&cparams.A, &coefEq.A, &coefEq.C)
114 // cparams.A = 2*(A+2C+A-2C) = 4A
115 add(&cparams.A, &cparams.A, &cparams.A)
116 // cparams.C = (A+2C-A+2C) = 4C
117 sub(&cparams.C, &coefEq.A, &coefEq.C)
118 return
119 }
120
121 // Recovers (A:C) curve parameters from projectively equivalent (A+2C:4C).
122 func RecoverCurveCoefficients4(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv) {
123 // cparams.C = (4C)*1/2=2C
124 mul(&cparams.C, &coefEq.C, &params.HalfFp2)
125 // cparams.A = A+2C - 2C = A
126 sub(&cparams.A, &coefEq.A, &cparams.C)
127 // cparams.C = 2C * 1/2 = C
128 mul(&cparams.C, &cparams.C, &params.HalfFp2)
129 }
130
131
132 // Combined coordinate doubling and differential addition. Takes projective points
133 // P,Q,Q-P and (A+2C)/4C curve E coefficient. Returns 2*P and P+Q calculated on E.
134 // Function is used only by RightToLeftLadder. Corresponds to Algorithm 5 of SIKE
135 func xDbladd(P, Q, QmP *ProjectivePoint, a24 *Fp2) (dblP, PaQ ProjectivePoint) {
136 var t0, t1, t2 Fp2
137
138 xQmP, zQmP := &QmP.X, &QmP.Z
139 xPaQ, zPaQ := &PaQ.X, &PaQ.Z
140 x2P, z2P := &dblP.X, &dblP.Z
141 xP, zP := &P.X, &P.Z
142 xQ, zQ := &Q.X, &Q.Z
143
144 add(&t0, xP, zP) // t0 = Xp+Zp
145 sub(&t1, xP, zP) // t1 = Xp-Zp
146 sqr(x2P, &t0) // 2P.X = t0^2
147 sub(&t2, xQ, zQ) // t2 = Xq-Zq
148 add(xPaQ, xQ, zQ) // Xp+q = Xq+Zq
149 mul(&t0, &t0, &t2) // t0 = t0 * t2
150 mul(z2P, &t1, &t1) // 2P.Z = t1 * t1
151 mul(&t1, &t1, xPaQ) // t1 = t1 * Xp+q
152 sub(&t2, x2P, z2P) // t2 = 2P.X - 2P.Z
153 mul(x2P, x2P, z2P) // 2P.X = 2P.X * 2P.Z
154 mul(xPaQ, a24, &t2) // Xp+q = A24 * t2
155 sub(zPaQ, &t0, &t1) // Zp+q = t0 - t1
156 add(z2P, xPaQ, z2P) // 2P.Z = Xp+q + 2P.Z
157 add(xPaQ, &t0, &t1) // Xp+q = t0 + t1
158 mul(z2P, z2P, &t2) // 2P.Z = 2P.Z * t2
159 sqr(zPaQ, zPaQ) // Zp+q = Zp+q ^ 2
160 sqr(xPaQ, xPaQ) // Xp+q = Xp+q ^ 2
161 mul(zPaQ, xQmP, zPaQ) // Zp+q = Xq-p * Zp+q
162 mul(xPaQ, zQmP, xPaQ) // Xp+q = Zq-p * Xp+q
163 return
164 }
165
166 // Given the curve parameters, xP = x(P), computes xP = x([2^k]P)
167 // Safe to overlap xP, x2P.
168 func Pow2k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32) {
169 var t0, t1 Fp2
170
171 x, z := &xP.X, &xP.Z
172 for i := uint32(0); i < k; i++ {
173 sub(&t0, x, z) // t0 = Xp - Zp
174 add(&t1, x, z) // t1 = Xp + Zp
175 sqr(&t0, &t0) // t0 = t0 ^ 2
176 sqr(&t1, &t1) // t1 = t1 ^ 2
177 mul(z, &params.C, &t0) // Z2p = C24 * t0
178 mul(x, z, &t1) // X2p = Z2p * t1
179 sub(&t1, &t1, &t0) // t1 = t1 - t0
180 mul(&t0, &params.A, &t1) // t0 = A24+ * t1
181 add(z, z, &t0) // Z2p = Z2p + t0
182 mul(z, z, &t1) // Zp = Z2p * t1
183 }
184 }
185
186 // Given the curve parameters, xP = x(P), and k >= 0, compute xP = x([3^k]P).
187 //
188 // Safe to overlap xP, xR.
189 func Pow3k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32) {
190 var t0, t1, t2, t3, t4, t5, t6 Fp2
191
192 x, z := &xP.X, &xP.Z
193 for i := uint32(0); i < k; i++ {
194 sub(&t0, x, z) // t0 = Xp - Zp
195 sqr(&t2, &t0) // t2 = t0^2
196 add(&t1, x, z) // t1 = Xp + Zp
197 sqr(&t3, &t1) // t3 = t1^2
198 add(&t4, &t1, &t0) // t4 = t1 + t0
199 sub(&t0, &t1, &t0) // t0 = t1 - t0
200 sqr(&t1, &t4) // t1 = t4^2
201 sub(&t1, &t1, &t3) // t1 = t1 - t3
202 sub(&t1, &t1, &t2) // t1 = t1 - t2
203 mul(&t5, &t3, &params.A) // t5 = t3 * A24+
204 mul(&t3, &t3, &t5) // t3 = t5 * t3
205 mul(&t6, &t2, &params.C) // t6 = t2 * A24-
206 mul(&t2, &t2, &t6) // t2 = t2 * t6
207 sub(&t3, &t2, &t3) // t3 = t2 - t3
208 sub(&t2, &t5, &t6) // t2 = t5 - t6
209 mul(&t1, &t2, &t1) // t1 = t2 * t1
210 add(&t2, &t3, &t1) // t2 = t3 + t1
211 sqr(&t2, &t2) // t2 = t2^2
212 mul(x, &t2, &t4) // X3p = t2 * t4
213 sub(&t1, &t3, &t1) // t1 = t3 - t1
214 sqr(&t1, &t1) // t1 = t1^2
215 mul(z, &t1, &t0) // Z3p = t1 * t0
216 }
217 }
218
219 // Set (y1, y2, y3) = (1/x1, 1/x2, 1/x3).
220 //
221 // All xi, yi must be distinct.
222 func Fp2Batch3Inv(x1, x2, x3, y1, y2, y3 *Fp2) {
223 var x1x2, t Fp2
224
225 mul(&x1x2, x1, x2) // x1*x2
226 mul(&t, &x1x2, x3) // 1/(x1*x2*x3)
227 inv(&t, &t)
228 mul(y1, &t, x2) // 1/x1
229 mul(y1, y1, x3)
230 mul(y2, &t, x1) // 1/x2
231 mul(y2, y2, x3)
232 mul(y3, &t, &x1x2) // 1/x3
233 }
234
235 // Scalarmul3Pt is a right-to-left point multiplication that given the
236 // x-coordinate of P, Q and P-Q calculates the x-coordinate of R=Q+[scalar]P.
237 // nbits must be smaller or equal to len(scalar).
238 func ScalarMul3Pt(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint, scalar []uint8) ProjectivePoint {
239 var R0, R2, R1 ProjectivePoint
240 aPlus2Over4 := CalcAplus2Over4(cparams)
241 R1 = *P
242 R2 = *PmQ
243 R0 = *Q
244
245
246 // Iterate over the bits of the scalar, bottom to top
247 prevBit := uint8(0)
248 for i := uint(0); i < nbits; i++ {
249 bit := (scalar[i>>3] >> (i & 7) & 1)
250 swap := prevBit ^ bit
251 prevBit = bit
252 cswap(&R1.X, &R1.Z, &R2.X, &R2.Z, swap)
253 R0, R2 = xDbladd(&R0, &R2, &R1, &aPlus2Over4)
254 }
255 cswap(&R1.X, &R1.Z, &R2.X, &R2.Z, prevBit)
256 return R1
257 }
258
259 // Given a three-torsion point p = x(PB) on the curve E_(A:C), construct the
260 // three-isogeny phi : E_(A:C) -> E_(A:C)/<P_3> = E_(A':C').
261 //
262 // Input: (XP_3: ZP_3), where P_3 has exact order 3 on E_A/C
263 // Output:
264 // - Curve coordinates (A' + 2C', A' - 2C') corresponding to E_A'/C' = A_E/C/<P3>
265 // - Isogeny phi with constants in F_p^2
266 func (phi *isogeny3) GenerateCurve(p *ProjectivePoint) CurveCoefficientsEquiv {
267 var t0, t1, t2, t3, t4 Fp2
268 var coefEq CurveCoefficientsEquiv
269 K1, K2 := &phi.K1, &phi.K2
270
271 sub(K1, &p.X, &p.Z) // K1 = XP3 - ZP3
272 sqr(&t0, K1) // t0 = K1^2
273 add(K2, &p.X, &p.Z) // K2 = XP3 + ZP3
274 sqr(&t1, K2) // t1 = K2^2
275 add(&t2, &t0, &t1) // t2 = t0 + t1
276 add(&t3, K1, K2) // t3 = K1 + K2
277 sqr(&t3, &t3) // t3 = t3^2
278 sub(&t3, &t3, &t2) // t3 = t3 - t2
279 add(&t2, &t1, &t3) // t2 = t1 + t3
280 add(&t3, &t3, &t0) // t3 = t3 + t0
281 add(&t4, &t3, &t0) // t4 = t3 + t0
282 add(&t4, &t4, &t4) // t4 = t4 + t4
283 add(&t4, &t1, &t4) // t4 = t1 + t4
284 mul(&coefEq.C, &t2, &t4) // A24m = t2 * t4
285 add(&t4, &t1, &t2) // t4 = t1 + t2
286 add(&t4, &t4, &t4) // t4 = t4 + t4
287 add(&t4, &t0, &t4) // t4 = t0 + t4
288 mul(&t4, &t3, &t4) // t4 = t3 * t4
289 sub(&t0, &t4, &coefEq.C) // t0 = t4 - A24m
290 add(&coefEq.A, &coefEq.C, &t0) // A24p = A24m + t0
291 return coefEq
292 }
293
294 // Given a 3-isogeny phi and a point pB = x(PB), compute x(QB), the x-coordinate
295 // of the image QB = phi(PB) of PB under phi : E_(A:C) -> E_(A':C').
296 //
297 // The output xQ = x(Q) is then a point on the curve E_(A':C'); the curve
298 // parameters are returned by the GenerateCurve function used to construct phi.
299 func (phi *isogeny3) EvaluatePoint(p *ProjectivePoint) {
300 var t0, t1, t2 Fp2
301 K1, K2 := &phi.K1, &phi.K2
302 px, pz := &p.X, &p.Z
303
304 add(&t0, px, pz) // t0 = XQ + ZQ
305 sub(&t1, px, pz) // t1 = XQ - ZQ
306 mul(&t0, K1, &t0) // t2 = K1 * t0
307 mul(&t1, K2, &t1) // t1 = K2 * t1
308 add(&t2, &t0, &t1) // t2 = t0 + t1
309 sub(&t0, &t1, &t0) // t0 = t1 - t0
310 sqr(&t2, &t2) // t2 = t2 ^ 2
311 sqr(&t0, &t0) // t0 = t0 ^ 2
312 mul(px, px, &t2) // XQ'= XQ * t2
313 mul(pz, pz, &t0) // ZQ'= ZQ * t0
314 }
315
316 // Given a four-torsion point p = x(PB) on the curve E_(A:C), construct the
317 // four-isogeny phi : E_(A:C) -> E_(A:C)/<P_4> = E_(A':C').
318 //
319 // Input: (XP_4: ZP_4), where P_4 has exact order 4 on E_A/C
320 // Output:
321 // - Curve coordinates (A' + 2C', 4C') corresponding to E_A'/C' = A_E/C/<P4>
322 // - Isogeny phi with constants in F_p^2
323 func (phi *isogeny4) GenerateCurve(p *ProjectivePoint) CurveCoefficientsEquiv {
324 var coefEq CurveCoefficientsEquiv
325 xp4, zp4 := &p.X, &p.Z
326 K1, K2, K3 := &phi.K1, &phi.K2, &phi.K3
327
328 sub(K2, xp4, zp4)
329 add(K3, xp4, zp4)
330 sqr(K1, zp4)
331 add(K1, K1, K1)
332 sqr(&coefEq.C, K1)
333 add(K1, K1, K1)
334 sqr(&coefEq.A, xp4)
335 add(&coefEq.A, &coefEq.A, &coefEq.A)
336 sqr(&coefEq.A, &coefEq.A)
337 return coefEq
338 }
339
340 // Given a 4-isogeny phi and a point xP = x(P), compute x(Q), the x-coordinate
341 // of the image Q = phi(P) of P under phi : E_(A:C) -> E_(A':C').
342 //
343 // Input: Isogeny returned by GenerateCurve and point q=(Qx,Qz) from E0_A/C
344 // Output: Corresponding point q from E1_A'/C', where E1 is 4-isogenous to E0
345 func (phi *isogeny4) EvaluatePoint(p *ProjectivePoint) {
346 var t0, t1 Fp2
347 xq, zq := &p.X, &p.Z
348 K1, K2, K3 := &phi.K1, &phi.K2, &phi.K3
349
350 add(&t0, xq, zq)
351 sub(&t1, xq, zq)
352 mul(xq, &t0, K2)
353 mul(zq, &t1, K3)
354 mul(&t0, &t0, &t1)
355 mul(&t0, &t0, K1)
356 add(&t1, xq, zq)
357 sub(zq, xq, zq)
358 sqr(&t1, &t1)
359 sqr(zq, zq)
360 add(xq, &t0, &t1)
361 sub(&t0, zq, &t0)
362 mul(xq, xq, &t1)
363 mul(zq, zq, &t0)
364 }
365
366 // PublicKeyValidation preforms public key/ciphertext validation using the CLN test.
367 // CLN test: Check that P and Q are both of order 3^e3 and they generate the torsion E_A[3^e3]
368 // A countermeasure for remote timing attacks on SIKE; suggested by https://eprint.iacr.org/2022/054.pdf
369 // Any curve E_A (SIKE 434, 503, 751) that passes CLN test is supersingular.
370 // Input: The public key / ciphertext P, Q, PmQ. The projective coordinate A of the curve defined by (P, Q, PmQ)
371 // Outputs: Whether (P,Q,PmQ) follows the CLN test
372 func PublicKeyValidation(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint) error {
373
374
375 var PmQX, PmQZ Fp2
376 FromMontgomery(&PmQX, &PmQ.X)
377 FromMontgomery(&PmQZ, &PmQ.Z)
378
379 // PmQ is not point T or O
380 if((isZero(&PmQX)==1)||(isZero(&PmQZ)==1)){
381 return errors.New("curve: PmQ is invalid")
382 }
383
384 cparam := CalcCurveParamsEquiv3(cparams)
385
386 // Compute e_3 = log3(2^(nbits+1))
387 var e3 uint32
388 e3_float := float64(int(nbits)+1)/math.Log2(3)
389 e3 = uint32(e3_float)
390
391 // Verify that P and Q generate E_A[3^e_3] by checking: [3^(e_3-1)]P != [+-3^(e_3-1)]Q
392 var test_P, test_Q ProjectivePoint
393 test_P = *P
394 test_Q = *Q
395
396
397 Pow3k(&test_P, &cparam, e3-1)
398 Pow3k(&test_Q, &cparam, e3-1)
399
400
401 var PZ, QZ Fp2
402 FromMontgomery(&PZ, &test_P.Z)
403 FromMontgomery(&QZ, &test_Q.Z)
404
405
406 // P, Q are not of full order 3^e_3
407 if((isZero(&PZ)==1)||(isZero(&QZ)==1)){
408 return errors.New("curve: ciphertext/public key are not of full order 3^e3")
409 }
410
411 // PX/PZ = affine(PX)
412 // QX/QZ = affine(QX)
413 // If PX/PZ = QX/QZ, we have P=+-Q
414 var PXQZ_PZQX_fromMont, PXQZ_PZQX, PXQZ, PZQX Fp2
415 mul(&PXQZ, &test_P.X, &test_Q.Z)
416 mul(&PZQX, &test_P.Z, &test_Q.X)
417 sub(&PXQZ_PZQX, &PXQZ, &PZQX)
418 FromMontgomery(&PXQZ_PZQX_fromMont, &PXQZ_PZQX)
419
420 // [3^(e_3-1)]P == [+-3^(e_3-1)]Q
421 if(isZero(&PXQZ_PZQX_fromMont)==1){
422 return errors.New("curve: ciphertext/public key are not linearly independent")
423 }
424
425 // Check that Ord(P) = Ord(Q) = 3^(e_3)
426 Pow3k(&test_P, &cparam, 1)
427 Pow3k(&test_Q, &cparam, 1)
428
429 FromMontgomery(&PZ, &test_P.Z)
430 FromMontgomery(&QZ, &test_Q.Z)
431
432 // P, Q are not of correct order 3^e_3
433 if((isZero(&PZ)==0)||(isZero(&QZ)==0)){
434 return errors.New("curve: ciphertext/public key are not of correct order 3^e3")
435 }
436 return nil
437 }