Pete Bentley | 0c61efe | 2019-08-13 09:32:23 +0100 | [diff] [blame^] | 1 | // Copyright (c) 2019, Cloudflare Inc. |
| 2 | // |
| 3 | // Permission to use, copy, modify, and/or distribute this software for any |
| 4 | // purpose with or without fee is hereby granted, provided that the above |
| 5 | // copyright notice and this permission notice appear in all copies. |
| 6 | // |
| 7 | // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| 8 | // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| 9 | // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
| 10 | // SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| 11 | // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
| 12 | // OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
| 13 | // CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| 14 | |
| 15 | package sike |
| 16 | |
| 17 | // Interface for working with isogenies. |
| 18 | type isogeny interface { |
| 19 | // Given a torsion point on a curve computes isogenous curve. |
| 20 | // Returns curve coefficients (A:C), so that E_(A/C) = E_(A/C)/<P>, |
| 21 | // where P is a provided projective point. Sets also isogeny constants |
| 22 | // that are needed for isogeny evaluation. |
| 23 | GenerateCurve(*ProjectivePoint) CurveCoefficientsEquiv |
| 24 | // Evaluates isogeny at caller provided point. Requires isogeny curve constants |
| 25 | // to be earlier computed by GenerateCurve. |
| 26 | EvaluatePoint(*ProjectivePoint) ProjectivePoint |
| 27 | } |
| 28 | |
| 29 | // Stores isogeny 3 curve constants |
| 30 | type isogeny3 struct { |
| 31 | K1 Fp2 |
| 32 | K2 Fp2 |
| 33 | } |
| 34 | |
| 35 | // Stores isogeny 4 curve constants |
| 36 | type isogeny4 struct { |
| 37 | isogeny3 |
| 38 | K3 Fp2 |
| 39 | } |
| 40 | |
| 41 | // Constructs isogeny3 objects |
| 42 | func NewIsogeny3() isogeny { |
| 43 | return &isogeny3{} |
| 44 | } |
| 45 | |
| 46 | // Constructs isogeny4 objects |
| 47 | func NewIsogeny4() isogeny { |
| 48 | return &isogeny4{} |
| 49 | } |
| 50 | |
| 51 | // Helper function for RightToLeftLadder(). Returns A+2C / 4. |
| 52 | func calcAplus2Over4(cparams *ProjectiveCurveParameters) (ret Fp2) { |
| 53 | var tmp Fp2 |
| 54 | |
| 55 | // 2C |
| 56 | add(&tmp, &cparams.C, &cparams.C) |
| 57 | // A+2C |
| 58 | add(&ret, &cparams.A, &tmp) |
| 59 | // 1/4C |
| 60 | add(&tmp, &tmp, &tmp) |
| 61 | inv(&tmp, &tmp) |
| 62 | // A+2C/4C |
| 63 | mul(&ret, &ret, &tmp) |
| 64 | return |
| 65 | } |
| 66 | |
| 67 | // Converts values in x.A and x.B to Montgomery domain |
| 68 | // x.A = x.A * R mod p |
| 69 | // x.B = x.B * R mod p |
| 70 | // Performs v = v*R^2*R^(-1) mod p, for both x.A and x.B |
| 71 | func toMontDomain(x *Fp2) { |
| 72 | var aRR FpX2 |
| 73 | |
| 74 | // convert to montgomery domain |
| 75 | fpMul(&aRR, &x.A, &R2) // = a*R*R |
| 76 | fpMontRdc(&x.A, &aRR) // = a*R mod p |
| 77 | fpMul(&aRR, &x.B, &R2) |
| 78 | fpMontRdc(&x.B, &aRR) |
| 79 | } |
| 80 | |
| 81 | // Converts values in x.A and x.B from Montgomery domain |
| 82 | // a = x.A mod p |
| 83 | // b = x.B mod p |
| 84 | // |
| 85 | // After returning from the call x is not modified. |
| 86 | func fromMontDomain(x *Fp2, out *Fp2) { |
| 87 | var aR FpX2 |
| 88 | |
| 89 | // convert from montgomery domain |
| 90 | copy(aR[:], x.A[:]) |
| 91 | fpMontRdc(&out.A, &aR) // = a mod p in [0, 2p) |
| 92 | fpRdcP(&out.A) // = a mod p in [0, p) |
| 93 | for i := range aR { |
| 94 | aR[i] = 0 |
| 95 | } |
| 96 | copy(aR[:], x.B[:]) |
| 97 | fpMontRdc(&out.B, &aR) |
| 98 | fpRdcP(&out.B) |
| 99 | } |
| 100 | |
| 101 | // Computes j-invariant for a curve y2=x3+A/Cx+x with A,C in F_(p^2). Result |
| 102 | // is returned in 'j'. Implementation corresponds to Algorithm 9 from SIKE. |
| 103 | func Jinvariant(cparams *ProjectiveCurveParameters, j *Fp2) { |
| 104 | var t0, t1 Fp2 |
| 105 | |
| 106 | sqr(j, &cparams.A) // j = A^2 |
| 107 | sqr(&t1, &cparams.C) // t1 = C^2 |
| 108 | add(&t0, &t1, &t1) // t0 = t1 + t1 |
| 109 | sub(&t0, j, &t0) // t0 = j - t0 |
| 110 | sub(&t0, &t0, &t1) // t0 = t0 - t1 |
| 111 | sub(j, &t0, &t1) // t0 = t0 - t1 |
| 112 | sqr(&t1, &t1) // t1 = t1^2 |
| 113 | mul(j, j, &t1) // j = j * t1 |
| 114 | add(&t0, &t0, &t0) // t0 = t0 + t0 |
| 115 | add(&t0, &t0, &t0) // t0 = t0 + t0 |
| 116 | sqr(&t1, &t0) // t1 = t0^2 |
| 117 | mul(&t0, &t0, &t1) // t0 = t0 * t1 |
| 118 | add(&t0, &t0, &t0) // t0 = t0 + t0 |
| 119 | add(&t0, &t0, &t0) // t0 = t0 + t0 |
| 120 | inv(j, j) // j = 1/j |
| 121 | mul(j, &t0, j) // j = t0 * j |
| 122 | } |
| 123 | |
| 124 | // Given affine points x(P), x(Q) and x(Q-P) in a extension field F_{p^2}, function |
| 125 | // recorvers projective coordinate A of a curve. This is Algorithm 10 from SIKE. |
| 126 | func RecoverCoordinateA(curve *ProjectiveCurveParameters, xp, xq, xr *Fp2) { |
| 127 | var t0, t1 Fp2 |
| 128 | |
| 129 | add(&t1, xp, xq) // t1 = Xp + Xq |
| 130 | mul(&t0, xp, xq) // t0 = Xp * Xq |
| 131 | mul(&curve.A, xr, &t1) // A = X(q-p) * t1 |
| 132 | add(&curve.A, &curve.A, &t0) // A = A + t0 |
| 133 | mul(&t0, &t0, xr) // t0 = t0 * X(q-p) |
| 134 | sub(&curve.A, &curve.A, &Params.OneFp2) // A = A - 1 |
| 135 | add(&t0, &t0, &t0) // t0 = t0 + t0 |
| 136 | add(&t1, &t1, xr) // t1 = t1 + X(q-p) |
| 137 | add(&t0, &t0, &t0) // t0 = t0 + t0 |
| 138 | sqr(&curve.A, &curve.A) // A = A^2 |
| 139 | inv(&t0, &t0) // t0 = 1/t0 |
| 140 | mul(&curve.A, &curve.A, &t0) // A = A * t0 |
| 141 | sub(&curve.A, &curve.A, &t1) // A = A - t1 |
| 142 | } |
| 143 | |
| 144 | // Computes equivalence (A:C) ~ (A+2C : A-2C) |
| 145 | func CalcCurveParamsEquiv3(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv { |
| 146 | var coef CurveCoefficientsEquiv |
| 147 | var c2 Fp2 |
| 148 | |
| 149 | add(&c2, &cparams.C, &cparams.C) |
| 150 | // A24p = A+2*C |
| 151 | add(&coef.A, &cparams.A, &c2) |
| 152 | // A24m = A-2*C |
| 153 | sub(&coef.C, &cparams.A, &c2) |
| 154 | return coef |
| 155 | } |
| 156 | |
| 157 | // Computes equivalence (A:C) ~ (A+2C : 4C) |
| 158 | func CalcCurveParamsEquiv4(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv { |
| 159 | var coefEq CurveCoefficientsEquiv |
| 160 | |
| 161 | add(&coefEq.C, &cparams.C, &cparams.C) |
| 162 | // A24p = A+2C |
| 163 | add(&coefEq.A, &cparams.A, &coefEq.C) |
| 164 | // C24 = 4*C |
| 165 | add(&coefEq.C, &coefEq.C, &coefEq.C) |
| 166 | return coefEq |
| 167 | } |
| 168 | |
| 169 | // Recovers (A:C) curve parameters from projectively equivalent (A+2C:A-2C). |
| 170 | func RecoverCurveCoefficients3(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv) { |
| 171 | add(&cparams.A, &coefEq.A, &coefEq.C) |
| 172 | // cparams.A = 2*(A+2C+A-2C) = 4A |
| 173 | add(&cparams.A, &cparams.A, &cparams.A) |
| 174 | // cparams.C = (A+2C-A+2C) = 4C |
| 175 | sub(&cparams.C, &coefEq.A, &coefEq.C) |
| 176 | return |
| 177 | } |
| 178 | |
| 179 | // Recovers (A:C) curve parameters from projectively equivalent (A+2C:4C). |
| 180 | func RecoverCurveCoefficients4(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv) { |
| 181 | // cparams.C = (4C)*1/2=2C |
| 182 | mul(&cparams.C, &coefEq.C, &Params.HalfFp2) |
| 183 | // cparams.A = A+2C - 2C = A |
| 184 | sub(&cparams.A, &coefEq.A, &cparams.C) |
| 185 | // cparams.C = 2C * 1/2 = C |
| 186 | mul(&cparams.C, &cparams.C, &Params.HalfFp2) |
| 187 | return |
| 188 | } |
| 189 | |
| 190 | // Combined coordinate doubling and differential addition. Takes projective points |
| 191 | // P,Q,Q-P and (A+2C)/4C curve E coefficient. Returns 2*P and P+Q calculated on E. |
| 192 | // Function is used only by RightToLeftLadder. Corresponds to Algorithm 5 of SIKE |
| 193 | func xDbladd(P, Q, QmP *ProjectivePoint, a24 *Fp2) (dblP, PaQ ProjectivePoint) { |
| 194 | var t0, t1, t2 Fp2 |
| 195 | xQmP, zQmP := &QmP.X, &QmP.Z |
| 196 | xPaQ, zPaQ := &PaQ.X, &PaQ.Z |
| 197 | x2P, z2P := &dblP.X, &dblP.Z |
| 198 | xP, zP := &P.X, &P.Z |
| 199 | xQ, zQ := &Q.X, &Q.Z |
| 200 | |
| 201 | add(&t0, xP, zP) // t0 = Xp+Zp |
| 202 | sub(&t1, xP, zP) // t1 = Xp-Zp |
| 203 | sqr(x2P, &t0) // 2P.X = t0^2 |
| 204 | sub(&t2, xQ, zQ) // t2 = Xq-Zq |
| 205 | add(xPaQ, xQ, zQ) // Xp+q = Xq+Zq |
| 206 | mul(&t0, &t0, &t2) // t0 = t0 * t2 |
| 207 | mul(z2P, &t1, &t1) // 2P.Z = t1 * t1 |
| 208 | mul(&t1, &t1, xPaQ) // t1 = t1 * Xp+q |
| 209 | sub(&t2, x2P, z2P) // t2 = 2P.X - 2P.Z |
| 210 | mul(x2P, x2P, z2P) // 2P.X = 2P.X * 2P.Z |
| 211 | mul(xPaQ, a24, &t2) // Xp+q = A24 * t2 |
| 212 | sub(zPaQ, &t0, &t1) // Zp+q = t0 - t1 |
| 213 | add(z2P, xPaQ, z2P) // 2P.Z = Xp+q + 2P.Z |
| 214 | add(xPaQ, &t0, &t1) // Xp+q = t0 + t1 |
| 215 | mul(z2P, z2P, &t2) // 2P.Z = 2P.Z * t2 |
| 216 | sqr(zPaQ, zPaQ) // Zp+q = Zp+q ^ 2 |
| 217 | sqr(xPaQ, xPaQ) // Xp+q = Xp+q ^ 2 |
| 218 | mul(zPaQ, xQmP, zPaQ) // Zp+q = Xq-p * Zp+q |
| 219 | mul(xPaQ, zQmP, xPaQ) // Xp+q = Zq-p * Xp+q |
| 220 | return |
| 221 | } |
| 222 | |
| 223 | // Given the curve parameters, xP = x(P), computes xP = x([2^k]P) |
| 224 | // Safe to overlap xP, x2P. |
| 225 | func Pow2k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32) { |
| 226 | var t0, t1 Fp2 |
| 227 | |
| 228 | x, z := &xP.X, &xP.Z |
| 229 | for i := uint32(0); i < k; i++ { |
| 230 | sub(&t0, x, z) // t0 = Xp - Zp |
| 231 | add(&t1, x, z) // t1 = Xp + Zp |
| 232 | sqr(&t0, &t0) // t0 = t0 ^ 2 |
| 233 | sqr(&t1, &t1) // t1 = t1 ^ 2 |
| 234 | mul(z, ¶ms.C, &t0) // Z2p = C24 * t0 |
| 235 | mul(x, z, &t1) // X2p = Z2p * t1 |
| 236 | sub(&t1, &t1, &t0) // t1 = t1 - t0 |
| 237 | mul(&t0, ¶ms.A, &t1) // t0 = A24+ * t1 |
| 238 | add(z, z, &t0) // Z2p = Z2p + t0 |
| 239 | mul(z, z, &t1) // Zp = Z2p * t1 |
| 240 | } |
| 241 | } |
| 242 | |
| 243 | // Given the curve parameters, xP = x(P), and k >= 0, compute xP = x([3^k]P). |
| 244 | // |
| 245 | // Safe to overlap xP, xR. |
| 246 | func Pow3k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32) { |
| 247 | var t0, t1, t2, t3, t4, t5, t6 Fp2 |
| 248 | |
| 249 | x, z := &xP.X, &xP.Z |
| 250 | for i := uint32(0); i < k; i++ { |
| 251 | sub(&t0, x, z) // t0 = Xp - Zp |
| 252 | sqr(&t2, &t0) // t2 = t0^2 |
| 253 | add(&t1, x, z) // t1 = Xp + Zp |
| 254 | sqr(&t3, &t1) // t3 = t1^2 |
| 255 | add(&t4, &t1, &t0) // t4 = t1 + t0 |
| 256 | sub(&t0, &t1, &t0) // t0 = t1 - t0 |
| 257 | sqr(&t1, &t4) // t1 = t4^2 |
| 258 | sub(&t1, &t1, &t3) // t1 = t1 - t3 |
| 259 | sub(&t1, &t1, &t2) // t1 = t1 - t2 |
| 260 | mul(&t5, &t3, ¶ms.A) // t5 = t3 * A24+ |
| 261 | mul(&t3, &t3, &t5) // t3 = t5 * t3 |
| 262 | mul(&t6, &t2, ¶ms.C) // t6 = t2 * A24- |
| 263 | mul(&t2, &t2, &t6) // t2 = t2 * t6 |
| 264 | sub(&t3, &t2, &t3) // t3 = t2 - t3 |
| 265 | sub(&t2, &t5, &t6) // t2 = t5 - t6 |
| 266 | mul(&t1, &t2, &t1) // t1 = t2 * t1 |
| 267 | add(&t2, &t3, &t1) // t2 = t3 + t1 |
| 268 | sqr(&t2, &t2) // t2 = t2^2 |
| 269 | mul(x, &t2, &t4) // X3p = t2 * t4 |
| 270 | sub(&t1, &t3, &t1) // t1 = t3 - t1 |
| 271 | sqr(&t1, &t1) // t1 = t1^2 |
| 272 | mul(z, &t1, &t0) // Z3p = t1 * t0 |
| 273 | } |
| 274 | } |
| 275 | |
| 276 | // Set (y1, y2, y3) = (1/x1, 1/x2, 1/x3). |
| 277 | // |
| 278 | // All xi, yi must be distinct. |
| 279 | func Fp2Batch3Inv(x1, x2, x3, y1, y2, y3 *Fp2) { |
| 280 | var x1x2, t Fp2 |
| 281 | |
| 282 | mul(&x1x2, x1, x2) // x1*x2 |
| 283 | mul(&t, &x1x2, x3) // 1/(x1*x2*x3) |
| 284 | inv(&t, &t) |
| 285 | mul(y1, &t, x2) // 1/x1 |
| 286 | mul(y1, y1, x3) |
| 287 | mul(y2, &t, x1) // 1/x2 |
| 288 | mul(y2, y2, x3) |
| 289 | mul(y3, &t, &x1x2) // 1/x3 |
| 290 | } |
| 291 | |
| 292 | // ScalarMul3Pt is a right-to-left point multiplication that given the |
| 293 | // x-coordinate of P, Q and P-Q calculates the x-coordinate of R=Q+[scalar]P. |
| 294 | // nbits must be smaller or equal to len(scalar). |
| 295 | func ScalarMul3Pt(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint, scalar []uint8) ProjectivePoint { |
| 296 | var R0, R2, R1 ProjectivePoint |
| 297 | aPlus2Over4 := calcAplus2Over4(cparams) |
| 298 | R1 = *P |
| 299 | R2 = *PmQ |
| 300 | R0 = *Q |
| 301 | |
| 302 | // Iterate over the bits of the scalar, bottom to top |
| 303 | prevBit := uint8(0) |
| 304 | for i := uint(0); i < nbits; i++ { |
| 305 | bit := (scalar[i>>3] >> (i & 7) & 1) |
| 306 | swap := prevBit ^ bit |
| 307 | prevBit = bit |
| 308 | condSwap(&R1.X, &R1.Z, &R2.X, &R2.Z, swap) |
| 309 | R0, R2 = xDbladd(&R0, &R2, &R1, &aPlus2Over4) |
| 310 | } |
| 311 | condSwap(&R1.X, &R1.Z, &R2.X, &R2.Z, prevBit) |
| 312 | return R1 |
| 313 | } |
| 314 | |
| 315 | // Given a three-torsion point p = x(PB) on the curve E_(A:C), construct the |
| 316 | // three-isogeny phi : E_(A:C) -> E_(A:C)/<P_3> = E_(A':C'). |
| 317 | // |
| 318 | // Input: (XP_3: ZP_3), where P_3 has exact order 3 on E_A/C |
| 319 | // Output: * Curve coordinates (A' + 2C', A' - 2C') corresponding to E_A'/C' = A_E/C/<P3> |
| 320 | // * isogeny phi with constants in F_p^2 |
| 321 | func (phi *isogeny3) GenerateCurve(p *ProjectivePoint) CurveCoefficientsEquiv { |
| 322 | var t0, t1, t2, t3, t4 Fp2 |
| 323 | var coefEq CurveCoefficientsEquiv |
| 324 | var K1, K2 = &phi.K1, &phi.K2 |
| 325 | |
| 326 | sub(K1, &p.X, &p.Z) // K1 = XP3 - ZP3 |
| 327 | sqr(&t0, K1) // t0 = K1^2 |
| 328 | add(K2, &p.X, &p.Z) // K2 = XP3 + ZP3 |
| 329 | sqr(&t1, K2) // t1 = K2^2 |
| 330 | add(&t2, &t0, &t1) // t2 = t0 + t1 |
| 331 | add(&t3, K1, K2) // t3 = K1 + K2 |
| 332 | sqr(&t3, &t3) // t3 = t3^2 |
| 333 | sub(&t3, &t3, &t2) // t3 = t3 - t2 |
| 334 | add(&t2, &t1, &t3) // t2 = t1 + t3 |
| 335 | add(&t3, &t3, &t0) // t3 = t3 + t0 |
| 336 | add(&t4, &t3, &t0) // t4 = t3 + t0 |
| 337 | add(&t4, &t4, &t4) // t4 = t4 + t4 |
| 338 | add(&t4, &t1, &t4) // t4 = t1 + t4 |
| 339 | mul(&coefEq.C, &t2, &t4) // A24m = t2 * t4 |
| 340 | add(&t4, &t1, &t2) // t4 = t1 + t2 |
| 341 | add(&t4, &t4, &t4) // t4 = t4 + t4 |
| 342 | add(&t4, &t0, &t4) // t4 = t0 + t4 |
| 343 | mul(&t4, &t3, &t4) // t4 = t3 * t4 |
| 344 | sub(&t0, &t4, &coefEq.C) // t0 = t4 - A24m |
| 345 | add(&coefEq.A, &coefEq.C, &t0) // A24p = A24m + t0 |
| 346 | return coefEq |
| 347 | } |
| 348 | |
| 349 | // Given a 3-isogeny phi and a point pB = x(PB), compute x(QB), the x-coordinate |
| 350 | // of the image QB = phi(PB) of PB under phi : E_(A:C) -> E_(A':C'). |
| 351 | // |
| 352 | // The output xQ = x(Q) is then a point on the curve E_(A':C'); the curve |
| 353 | // parameters are returned by the GenerateCurve function used to construct phi. |
| 354 | func (phi *isogeny3) EvaluatePoint(p *ProjectivePoint) ProjectivePoint { |
| 355 | var t0, t1, t2 Fp2 |
| 356 | var q ProjectivePoint |
| 357 | var K1, K2 = &phi.K1, &phi.K2 |
| 358 | var px, pz = &p.X, &p.Z |
| 359 | |
| 360 | add(&t0, px, pz) // t0 = XQ + ZQ |
| 361 | sub(&t1, px, pz) // t1 = XQ - ZQ |
| 362 | mul(&t0, K1, &t0) // t2 = K1 * t0 |
| 363 | mul(&t1, K2, &t1) // t1 = K2 * t1 |
| 364 | add(&t2, &t0, &t1) // t2 = t0 + t1 |
| 365 | sub(&t0, &t1, &t0) // t0 = t1 - t0 |
| 366 | sqr(&t2, &t2) // t2 = t2 ^ 2 |
| 367 | sqr(&t0, &t0) // t0 = t0 ^ 2 |
| 368 | mul(&q.X, px, &t2) // XQ'= XQ * t2 |
| 369 | mul(&q.Z, pz, &t0) // ZQ'= ZQ * t0 |
| 370 | return q |
| 371 | } |
| 372 | |
| 373 | // Given a four-torsion point p = x(PB) on the curve E_(A:C), construct the |
| 374 | // four-isogeny phi : E_(A:C) -> E_(A:C)/<P_4> = E_(A':C'). |
| 375 | // |
| 376 | // Input: (XP_4: ZP_4), where P_4 has exact order 4 on E_A/C |
| 377 | // Output: * Curve coordinates (A' + 2C', 4C') corresponding to E_A'/C' = A_E/C/<P4> |
| 378 | // * isogeny phi with constants in F_p^2 |
| 379 | func (phi *isogeny4) GenerateCurve(p *ProjectivePoint) CurveCoefficientsEquiv { |
| 380 | var coefEq CurveCoefficientsEquiv |
| 381 | var xp4, zp4 = &p.X, &p.Z |
| 382 | var K1, K2, K3 = &phi.K1, &phi.K2, &phi.K3 |
| 383 | |
| 384 | sub(K2, xp4, zp4) |
| 385 | add(K3, xp4, zp4) |
| 386 | sqr(K1, zp4) |
| 387 | add(K1, K1, K1) |
| 388 | sqr(&coefEq.C, K1) |
| 389 | add(K1, K1, K1) |
| 390 | sqr(&coefEq.A, xp4) |
| 391 | add(&coefEq.A, &coefEq.A, &coefEq.A) |
| 392 | sqr(&coefEq.A, &coefEq.A) |
| 393 | return coefEq |
| 394 | } |
| 395 | |
| 396 | // Given a 4-isogeny phi and a point xP = x(P), compute x(Q), the x-coordinate |
| 397 | // of the image Q = phi(P) of P under phi : E_(A:C) -> E_(A':C'). |
| 398 | // |
| 399 | // Input: isogeny returned by GenerateCurve and point q=(Qx,Qz) from E0_A/C |
| 400 | // Output: Corresponding point q from E1_A'/C', where E1 is 4-isogenous to E0 |
| 401 | func (phi *isogeny4) EvaluatePoint(p *ProjectivePoint) ProjectivePoint { |
| 402 | var t0, t1 Fp2 |
| 403 | var q = *p |
| 404 | var xq, zq = &q.X, &q.Z |
| 405 | var K1, K2, K3 = &phi.K1, &phi.K2, &phi.K3 |
| 406 | |
| 407 | add(&t0, xq, zq) |
| 408 | sub(&t1, xq, zq) |
| 409 | mul(xq, &t0, K2) |
| 410 | mul(zq, &t1, K3) |
| 411 | mul(&t0, &t0, &t1) |
| 412 | mul(&t0, &t0, K1) |
| 413 | add(&t1, xq, zq) |
| 414 | sub(zq, xq, zq) |
| 415 | sqr(&t1, &t1) |
| 416 | sqr(zq, zq) |
| 417 | add(xq, &t0, &t1) |
| 418 | sub(&t0, zq, &t0) |
| 419 | mul(xq, xq, &t1) |
| 420 | mul(zq, zq, &t0) |
| 421 | return q |
| 422 | } |