116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giropackage org.bouncycastle.math.ec; 216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giroimport java.math.BigInteger; 416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.math.ec.endo.ECEndomorphism; 653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.math.ec.endo.GLVEndomorphism; 753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.math.field.FiniteField; 853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.math.field.PolynomialExtensionField; 953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 1016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giropublic class ECAlgorithms 1116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro{ 1253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static boolean isF2mCurve(ECCurve c) 1353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 14bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro return isF2mField(c.getField()); 15bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro } 16bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro 17bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro public static boolean isF2mField(FiniteField field) 18bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro { 1953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return field.getDimension() > 1 && field.getCharacteristic().equals(ECConstants.TWO) 2053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro && field instanceof PolynomialExtensionField; 2153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 2253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 2353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static boolean isFpCurve(ECCurve c) 2453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 25bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro return isFpField(c.getField()); 26bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro } 27bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro 28bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro public static boolean isFpField(FiniteField field) 29bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro { 30bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro return field.getDimension() == 1; 3153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 3253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 3353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static ECPoint sumOfMultiplies(ECPoint[] ps, BigInteger[] ks) 3453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 3553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (ps == null || ks == null || ps.length != ks.length || ps.length < 1) 3653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 3753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro throw new IllegalArgumentException("point and scalar arrays should be non-null, and of equal, non-zero, length"); 3853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 3953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 4053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int count = ps.length; 4153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro switch (count) 4253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 4353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro case 1: 4453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return ps[0].multiply(ks[0]); 4553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro case 2: 4653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return sumOfTwoMultiplies(ps[0], ks[0], ps[1], ks[1]); 4753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro default: 4853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro break; 4953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 5053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 5153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint p = ps[0]; 5253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECCurve c = p.getCurve(); 5353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 5453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] imported = new ECPoint[count]; 5553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro imported[0] = p; 5653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 1; i < count; ++i) 5753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 5853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro imported[i] = importPoint(c, ps[i]); 5953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 6053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 6153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECEndomorphism endomorphism = c.getEndomorphism(); 6253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (endomorphism instanceof GLVEndomorphism) 6353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 6453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return validatePoint(implSumOfMultipliesGLV(imported, ks, (GLVEndomorphism)endomorphism)); 6553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 6653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 6753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return validatePoint(implSumOfMultiplies(imported, ks)); 6853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 6953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 7016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a, 7116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro ECPoint Q, BigInteger b) 7216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 7380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve cp = P.getCurve(); 7480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro Q = importPoint(cp, Q); 7516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 7616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick 77bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro if (cp instanceof ECCurve.AbstractF2m) 7816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 79bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro ECCurve.AbstractF2m f2mCurve = (ECCurve.AbstractF2m)cp; 8016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro if (f2mCurve.isKoblitz()) 8116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 8253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return validatePoint(P.multiply(a).add(Q.multiply(b))); 8316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 8416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 8516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 8653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECEndomorphism endomorphism = cp.getEndomorphism(); 8753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (endomorphism instanceof GLVEndomorphism) 8853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 8953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return validatePoint( 9053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro implSumOfMultipliesGLV(new ECPoint[]{ P, Q }, new BigInteger[]{ a, b }, (GLVEndomorphism)endomorphism)); 9153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 9253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 9353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return validatePoint(implShamirsTrickWNaf(P, a, Q, b)); 9416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 9516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 9616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro /* 9716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * "Shamir's Trick", originally due to E. G. Straus 9816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * (Addition chains of vectors. American Mathematical Monthly, 9916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 71(7):806-808, Aug./Sept. 1964) 10016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * <pre> 10116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * Input: The points P, Q, scalar k = (km?, ... , k1, k0) 10216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * and scalar l = (lm?, ... , l1, l0). 10316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * Output: R = k * P + l * Q. 10416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 1: Z <- P + Q 10516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 2: R <- O 10616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 3: for i from m-1 down to 0 do 10716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 4: R <- R + R {point doubling} 10816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 5: if (ki = 1) and (li = 0) then R <- R + P end if 10916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 6: if (ki = 0) and (li = 1) then R <- R + Q end if 11016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 7: if (ki = 1) and (li = 1) then R <- R + Z end if 11116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 8: end for 11216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 9: return R 11316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * </pre> 11416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro */ 11516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro public static ECPoint shamirsTrick(ECPoint P, BigInteger k, 11616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro ECPoint Q, BigInteger l) 11716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 11880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve cp = P.getCurve(); 11980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro Q = importPoint(cp, Q); 12080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 12153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return validatePoint(implShamirsTrickJsf(P, k, Q, l)); 12280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 12380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 12480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static ECPoint importPoint(ECCurve c, ECPoint p) 12580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 12680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve cp = p.getCurve(); 12780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (!c.equals(cp)) 12816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 12980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro throw new IllegalArgumentException("Point must be on the same curve"); 13016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 13180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return c.importPoint(p); 13280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 13316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 13453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static void montgomeryTrick(ECFieldElement[] zs, int off, int len) 13553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 13653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro montgomeryTrick(zs, off, len, null); 13753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 13853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 13953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static void montgomeryTrick(ECFieldElement[] zs, int off, int len, ECFieldElement scale) 14080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 14180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro /* 14280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * Uses the "Montgomery Trick" to invert many field elements, with only a single actual 14380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * field inversion. See e.g. the paper: 14480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick" 14580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * by Katsuyuki Okeya, Kouichi Sakurai. 14680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro */ 14780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 14880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECFieldElement[] c = new ECFieldElement[len]; 14980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro c[0] = zs[off]; 15080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 15180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int i = 0; 15280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (++i < len) 15380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 15480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro c[i] = c[i - 1].multiply(zs[off + i]); 15580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 15680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 15753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro --i; 15853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 15953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (scale != null) 16053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 16153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro c[i] = c[i].multiply(scale); 16253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 16353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 16453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECFieldElement u = c[i].invert(); 16580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 16680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (i > 0) 16780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 16880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int j = off + i--; 16980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECFieldElement tmp = zs[j]; 17080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro zs[j] = c[i].multiply(u); 17180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro u = u.multiply(tmp); 17280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 17380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 17480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro zs[off] = u; 17516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 17616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 17753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro /** 17853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * Simple shift-and-add multiplication. Serves as reference implementation 17953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * to verify (possibly faster) implementations, and for very small scalars. 18053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * 18153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * @param p 18253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * The point to multiply. 18353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * @param k 18453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * The multiplier. 18553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * @return The result of the point multiplication <code>kP</code>. 18653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro */ 18753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static ECPoint referenceMultiply(ECPoint p, BigInteger k) 18853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 18953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger x = k.abs(); 19053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint q = p.getCurve().getInfinity(); 19153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int t = x.bitLength(); 19253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (t > 0) 19353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 19453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (x.testBit(0)) 19553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 19653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro q = p; 19753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 19853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 1; i < t; i++) 19953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 20053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro p = p.twice(); 20153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (x.testBit(i)) 20253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 20353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro q = q.add(p); 20453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 20553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 20653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 20753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return k.signum() < 0 ? q.negate() : q; 20853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 20953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 21053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static ECPoint validatePoint(ECPoint p) 21153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 21253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (!p.isValid()) 21353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 21453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro throw new IllegalArgumentException("Invalid point"); 21553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 21653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 21753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return p; 21853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 21953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 22053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro static ECPoint implShamirsTrickJsf(ECPoint P, BigInteger k, 22116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro ECPoint Q, BigInteger l) 22216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 22380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve curve = P.getCurve(); 22480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint infinity = curve.getInfinity(); 22580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 22680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro // TODO conjugate co-Z addition (ZADDC) can return both of these 22780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint PaddQ = P.add(Q); 22880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint PsubQ = P.subtract(Q); 22980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 23080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint[] points = new ECPoint[]{ Q, PsubQ, P, PaddQ }; 23180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro curve.normalizeAll(points); 23216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 23380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint[] table = new ECPoint[] { 23480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro points[3].negate(), points[2].negate(), points[1].negate(), 23580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro points[0].negate(), infinity, points[0], 23680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro points[1], points[2], points[3] }; 23780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 23880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro byte[] jsf = WNafUtil.generateJSF(k, l); 23980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 24080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint R = infinity; 24180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 24280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int i = jsf.length; 24380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (--i >= 0) 24416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 24580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int jsfi = jsf[i]; 24653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 24753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro // NOTE: The shifting ensures the sign is extended correctly 24853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int kDigit = ((jsfi << 24) >> 28), lDigit = ((jsfi << 28) >> 28); 24916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 25080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int index = 4 + (kDigit * 3) + lDigit; 25180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro R = R.twicePlus(table[index]); 25216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 25316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 25416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro return R; 25516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 25653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 25753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro static ECPoint implShamirsTrickWNaf(ECPoint P, BigInteger k, 25853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint Q, BigInteger l) 25953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 26053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro boolean negK = k.signum() < 0, negL = l.signum() < 0; 26153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 26253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro k = k.abs(); 26353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro l = l.abs(); 26453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 26553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int widthP = Math.max(2, Math.min(16, WNafUtil.getWindowSize(k.bitLength()))); 26653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int widthQ = Math.max(2, Math.min(16, WNafUtil.getWindowSize(l.bitLength()))); 26753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 26853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo infoP = WNafUtil.precompute(P, widthP, true); 26953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo infoQ = WNafUtil.precompute(Q, widthQ, true); 27053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 27153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompP = negK ? infoP.getPreCompNeg() : infoP.getPreComp(); 27253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompQ = negL ? infoQ.getPreCompNeg() : infoQ.getPreComp(); 27353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompNegP = negK ? infoP.getPreComp() : infoP.getPreCompNeg(); 27453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompNegQ = negL ? infoQ.getPreComp() : infoQ.getPreCompNeg(); 27553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 27653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro byte[] wnafP = WNafUtil.generateWindowNaf(widthP, k); 27753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro byte[] wnafQ = WNafUtil.generateWindowNaf(widthQ, l); 27853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 27953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return implShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ); 28053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 28153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 28253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro static ECPoint implShamirsTrickWNaf(ECPoint P, BigInteger k, ECPointMap pointMapQ, BigInteger l) 28353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 28453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro boolean negK = k.signum() < 0, negL = l.signum() < 0; 28553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 28653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro k = k.abs(); 28753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro l = l.abs(); 28853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 28953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int width = Math.max(2, Math.min(16, WNafUtil.getWindowSize(Math.max(k.bitLength(), l.bitLength())))); 29053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 29153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint Q = WNafUtil.mapPointWithPrecomp(P, width, true, pointMapQ); 29253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo infoP = WNafUtil.getWNafPreCompInfo(P); 29353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo infoQ = WNafUtil.getWNafPreCompInfo(Q); 29453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 29553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompP = negK ? infoP.getPreCompNeg() : infoP.getPreComp(); 29653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompQ = negL ? infoQ.getPreCompNeg() : infoQ.getPreComp(); 29753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompNegP = negK ? infoP.getPreComp() : infoP.getPreCompNeg(); 29853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompNegQ = negL ? infoQ.getPreComp() : infoQ.getPreCompNeg(); 29953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 30053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro byte[] wnafP = WNafUtil.generateWindowNaf(width, k); 30153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro byte[] wnafQ = WNafUtil.generateWindowNaf(width, l); 30253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 30353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return implShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ); 30453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 30553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 30653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro private static ECPoint implShamirsTrickWNaf(ECPoint[] preCompP, ECPoint[] preCompNegP, byte[] wnafP, 30753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompQ, ECPoint[] preCompNegQ, byte[] wnafQ) 30853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 30953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int len = Math.max(wnafP.length, wnafQ.length); 31053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 31153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECCurve curve = preCompP[0].getCurve(); 31253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint infinity = curve.getInfinity(); 31353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 31453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint R = infinity; 31553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int zeroes = 0; 31653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 31753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = len - 1; i >= 0; --i) 31853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 31953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int wiP = i < wnafP.length ? wnafP[i] : 0; 32053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int wiQ = i < wnafQ.length ? wnafQ[i] : 0; 32153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 32253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if ((wiP | wiQ) == 0) 32353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 32453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ++zeroes; 32553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro continue; 32653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 32753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 32853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint r = infinity; 32953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (wiP != 0) 33053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 33153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int nP = Math.abs(wiP); 33253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] tableP = wiP < 0 ? preCompNegP : preCompP; 33353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro r = r.add(tableP[nP >>> 1]); 33453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 33553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (wiQ != 0) 33653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 33753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int nQ = Math.abs(wiQ); 33853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] tableQ = wiQ < 0 ? preCompNegQ : preCompQ; 33953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro r = r.add(tableQ[nQ >>> 1]); 34053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 34153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 34253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (zeroes > 0) 34353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 34453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro R = R.timesPow2(zeroes); 34553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro zeroes = 0; 34653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 34753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 34853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro R = R.twicePlus(r); 34953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 35053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 35153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (zeroes > 0) 35253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 35353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro R = R.timesPow2(zeroes); 35453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 35553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 35653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return R; 35753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 35853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 35953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro static ECPoint implSumOfMultiplies(ECPoint[] ps, BigInteger[] ks) 36053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 36153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int count = ps.length; 36253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro boolean[] negs = new boolean[count]; 36353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo[] infos = new WNafPreCompInfo[count]; 36453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro byte[][] wnafs = new byte[count][]; 36553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 36653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 0; i < count; ++i) 36753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 36853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger ki = ks[i]; negs[i] = ki.signum() < 0; ki = ki.abs(); 36953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 37053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int width = Math.max(2, Math.min(16, WNafUtil.getWindowSize(ki.bitLength()))); 37153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro infos[i] = WNafUtil.precompute(ps[i], width, true); 37253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro wnafs[i] = WNafUtil.generateWindowNaf(width, ki); 37353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 37453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 37553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return implSumOfMultiplies(negs, infos, wnafs); 37653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 37753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 37853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro static ECPoint implSumOfMultipliesGLV(ECPoint[] ps, BigInteger[] ks, GLVEndomorphism glvEndomorphism) 37953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 38053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger n = ps[0].getCurve().getOrder(); 38153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 38253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int len = ps.length; 38353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 38453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger[] abs = new BigInteger[len << 1]; 38553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 0, j = 0; i < len; ++i) 38653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 38753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger[] ab = glvEndomorphism.decomposeScalar(ks[i].mod(n)); 38853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro abs[j++] = ab[0]; 38953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro abs[j++] = ab[1]; 39053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 39153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 39253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPointMap pointMap = glvEndomorphism.getPointMap(); 39353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (glvEndomorphism.hasEfficientPointMap()) 39453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 39553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return ECAlgorithms.implSumOfMultiplies(ps, pointMap, abs); 39653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 39753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 39853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] pqs = new ECPoint[len << 1]; 39953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 0, j = 0; i < len; ++i) 40053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 40153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint p = ps[i], q = pointMap.map(p); 40253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro pqs[j++] = p; 40353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro pqs[j++] = q; 40453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 40553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 40653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return ECAlgorithms.implSumOfMultiplies(pqs, abs); 40753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 40853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 40953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 41053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro static ECPoint implSumOfMultiplies(ECPoint[] ps, ECPointMap pointMap, BigInteger[] ks) 41153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 41253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int halfCount = ps.length, fullCount = halfCount << 1; 41353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 41453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro boolean[] negs = new boolean[fullCount]; 41553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo[] infos = new WNafPreCompInfo[fullCount]; 41653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro byte[][] wnafs = new byte[fullCount][]; 41753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 41853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 0; i < halfCount; ++i) 41953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 42053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int j0 = i << 1, j1 = j0 + 1; 42153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 42253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger kj0 = ks[j0]; negs[j0] = kj0.signum() < 0; kj0 = kj0.abs(); 42353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger kj1 = ks[j1]; negs[j1] = kj1.signum() < 0; kj1 = kj1.abs(); 42453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 42553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int width = Math.max(2, Math.min(16, WNafUtil.getWindowSize(Math.max(kj0.bitLength(), kj1.bitLength())))); 42653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 42753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint P = ps[i], Q = WNafUtil.mapPointWithPrecomp(P, width, true, pointMap); 42853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro infos[j0] = WNafUtil.getWNafPreCompInfo(P); 42953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro infos[j1] = WNafUtil.getWNafPreCompInfo(Q); 43053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro wnafs[j0] = WNafUtil.generateWindowNaf(width, kj0); 43153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro wnafs[j1] = WNafUtil.generateWindowNaf(width, kj1); 43253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 43353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 43453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return implSumOfMultiplies(negs, infos, wnafs); 43553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 43653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 43753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro private static ECPoint implSumOfMultiplies(boolean[] negs, WNafPreCompInfo[] infos, byte[][] wnafs) 43853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 43953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int len = 0, count = wnafs.length; 44053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 0; i < count; ++i) 44153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 44253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro len = Math.max(len, wnafs[i].length); 44353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 44453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 44553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECCurve curve = infos[0].getPreComp()[0].getCurve(); 44653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint infinity = curve.getInfinity(); 44753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 44853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint R = infinity; 44953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int zeroes = 0; 45053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 45153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = len - 1; i >= 0; --i) 45253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 45353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint r = infinity; 45453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 45553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int j = 0; j < count; ++j) 45653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 45753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro byte[] wnaf = wnafs[j]; 45853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int wi = i < wnaf.length ? wnaf[i] : 0; 45953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (wi != 0) 46053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 46153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int n = Math.abs(wi); 46253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo info = infos[j]; 46353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] table = (wi < 0 == negs[j]) ? info.getPreComp() : info.getPreCompNeg(); 46453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro r = r.add(table[n >>> 1]); 46553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 46653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 46753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 46853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (r == infinity) 46953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 47053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ++zeroes; 47153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro continue; 47253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 47353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 47453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (zeroes > 0) 47553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 47653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro R = R.timesPow2(zeroes); 47753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro zeroes = 0; 47853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 47953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 48053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro R = R.twicePlus(r); 48153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 48253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 48353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (zeroes > 0) 48453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 48553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro R = R.timesPow2(zeroes); 48653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 48753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 48853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return R; 48953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 49016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro} 491