| 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, ¶ms.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, ¶ms.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, ¶ms.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, ¶ms.C, &t0) // Z2p = C24 * t0 |
| 178 |
mul(x, z, &t1) // X2p = Z2p * t1 |
| 179 |
sub(&t1, &t1, &t0) // t1 = t1 - t0 |
| 180 |
mul(&t0, ¶ms.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, ¶ms.A) // t5 = t3 * A24+ |
| 204 |
mul(&t3, &t3, &t5) // t3 = t5 * t3 |
| 205 |
mul(&t6, &t2, ¶ms.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 |
} |