18212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompackage org.bouncycastle.math.ec; 28212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 38212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport java.math.BigInteger; 48212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootimport org.bouncycastle.math.ec.endo.ECEndomorphism; 6d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootimport org.bouncycastle.math.ec.endo.GLVEndomorphism; 7d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootimport org.bouncycastle.math.field.FiniteField; 8d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootimport org.bouncycastle.math.field.PolynomialExtensionField; 9d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompublic class ECAlgorithms 118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom{ 12d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static boolean isF2mCurve(ECCurve c) 13d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 1479d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro return isF2mField(c.getField()); 1579d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro } 1679d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro 1779d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro public static boolean isF2mField(FiniteField field) 1879d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro { 19d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return field.getDimension() > 1 && field.getCharacteristic().equals(ECConstants.TWO) 20d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root && field instanceof PolynomialExtensionField; 21d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 22d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 23d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static boolean isFpCurve(ECCurve c) 24d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 2579d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro return isFpField(c.getField()); 2679d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro } 2779d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro 2879d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro public static boolean isFpField(FiniteField field) 2979d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro { 3079d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro return field.getDimension() == 1; 31d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 32d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 33d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static ECPoint sumOfMultiplies(ECPoint[] ps, BigInteger[] ks) 34d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 35d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (ps == null || ks == null || ps.length != ks.length || ps.length < 1) 36d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 37d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root throw new IllegalArgumentException("point and scalar arrays should be non-null, and of equal, non-zero, length"); 38d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 39d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 40d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int count = ps.length; 41d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root switch (count) 42d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 43d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root case 1: 44d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return ps[0].multiply(ks[0]); 45d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root case 2: 46d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return sumOfTwoMultiplies(ps[0], ks[0], ps[1], ks[1]); 47d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root default: 48d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root break; 49d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 50d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 51d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint p = ps[0]; 52d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECCurve c = p.getCurve(); 53d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 54d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] imported = new ECPoint[count]; 55d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root imported[0] = p; 56d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = 1; i < count; ++i) 57d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 58d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root imported[i] = importPoint(c, ps[i]); 59d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 60d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 61d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECEndomorphism endomorphism = c.getEndomorphism(); 62d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (endomorphism instanceof GLVEndomorphism) 63d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 64d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return validatePoint(implSumOfMultipliesGLV(imported, ks, (GLVEndomorphism)endomorphism)); 65d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 66d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 67d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return validatePoint(implSumOfMultiplies(imported, ks)); 68d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 69d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a, 718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECPoint Q, BigInteger b) 728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECCurve cp = P.getCurve(); 745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Q = importPoint(cp, Q); 758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 766e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick 7779d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro if (cp instanceof ECCurve.AbstractF2m) 786e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 7979d3bf2425a53baab7feb744dad710b6c15533c9Sergio Giro ECCurve.AbstractF2m f2mCurve = (ECCurve.AbstractF2m)cp; 806e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom if (f2mCurve.isKoblitz()) 816e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom { 82d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return validatePoint(P.multiply(a).add(Q.multiply(b))); 836e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 846e736056d64d0e33b26cf9f7c4e351b496241fdeBrian Carlstrom } 858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 86d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECEndomorphism endomorphism = cp.getEndomorphism(); 87d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (endomorphism instanceof GLVEndomorphism) 88d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 89d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return validatePoint( 90d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root implSumOfMultipliesGLV(new ECPoint[]{ P, Q }, new BigInteger[]{ a, b }, (GLVEndomorphism)endomorphism)); 91d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 92d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 93d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return validatePoint(implShamirsTrickWNaf(P, a, Q, b)); 948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /* 978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * "Shamir's Trick", originally due to E. G. Straus 988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * (Addition chains of vectors. American Mathematical Monthly, 998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 71(7):806-808, Aug./Sept. 1964) 1008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <pre> 1018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Input: The points P, Q, scalar k = (km?, ... , k1, k0) 1028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * and scalar l = (lm?, ... , l1, l0). 1038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Output: R = k * P + l * Q. 1048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 1: Z <- P + Q 1058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 2: R <- O 1068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 3: for i from m-1 down to 0 do 1078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 4: R <- R + R {point doubling} 1088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 5: if (ki = 1) and (li = 0) then R <- R + P end if 1098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 6: if (ki = 0) and (li = 1) then R <- R + Q end if 1108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 7: if (ki = 1) and (li = 1) then R <- R + Z end if 1118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 8: end for 1128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 9: return R 1138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * </pre> 1148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 1158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ECPoint shamirsTrick(ECPoint P, BigInteger k, 1168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECPoint Q, BigInteger l) 1178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECCurve cp = P.getCurve(); 1195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Q = importPoint(cp, Q); 1205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 121d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return validatePoint(implShamirsTrickJsf(P, k, Q, l)); 1225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public static ECPoint importPoint(ECCurve c, ECPoint p) 1255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECCurve cp = p.getCurve(); 1275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (!c.equals(cp)) 1288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root throw new IllegalArgumentException("Point must be on the same curve"); 1308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return c.importPoint(p); 1325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 134d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void montgomeryTrick(ECFieldElement[] zs, int off, int len) 1355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 136028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro montgomeryTrick(zs, off, len, null); 137028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro } 138028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro 139028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro public static void montgomeryTrick(ECFieldElement[] zs, int off, int len, ECFieldElement scale) 140028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro { 1415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 1425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Uses the "Montgomery Trick" to invert many field elements, with only a single actual 1435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * field inversion. See e.g. the paper: 1445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick" 1455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * by Katsuyuki Okeya, Kouichi Sakurai. 1465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 1475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECFieldElement[] c = new ECFieldElement[len]; 1495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root c[0] = zs[off]; 1505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i = 0; 1525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (++i < len) 1535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root c[i] = c[i - 1].multiply(zs[off + i]); 1555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 157028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro --i; 158028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro 159028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro if (scale != null) 160028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro { 161028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro c[i] = c[i].multiply(scale); 162028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro } 163028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro 164028ab6e01e3b911024b9b9243e9a0f4ac377c0faSergio Giro ECFieldElement u = c[i].invert(); 1655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (i > 0) 1675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int j = off + i--; 1695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECFieldElement tmp = zs[j]; 1705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root zs[j] = c[i].multiply(u); 1715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root u = u.multiply(tmp); 1725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root zs[off] = u; 1758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 177d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root /** 178d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * Simple shift-and-add multiplication. Serves as reference implementation 179d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * to verify (possibly faster) implementations, and for very small scalars. 180d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * 181d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * @param p 182d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * The point to multiply. 183d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * @param k 184d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * The multiplier. 185d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * @return The result of the point multiplication <code>kP</code>. 186d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root */ 187d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static ECPoint referenceMultiply(ECPoint p, BigInteger k) 188d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 189d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger x = k.abs(); 190d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint q = p.getCurve().getInfinity(); 191d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int t = x.bitLength(); 192d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (t > 0) 193d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 194d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (x.testBit(0)) 195d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 196d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root q = p; 197d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 198d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = 1; i < t; i++) 199d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 200d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root p = p.twice(); 201d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (x.testBit(i)) 202d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 203d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root q = q.add(p); 204d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 205d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 206d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 207d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return k.signum() < 0 ? q.negate() : q; 208d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 209d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 210d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static ECPoint validatePoint(ECPoint p) 211d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 212d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (!p.isValid()) 213d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 214d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root throw new IllegalArgumentException("Invalid point"); 215d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 216d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 217d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return p; 218d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 219d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 220d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static ECPoint implShamirsTrickJsf(ECPoint P, BigInteger k, 2218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECPoint Q, BigInteger l) 2228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECCurve curve = P.getCurve(); 2245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint infinity = curve.getInfinity(); 2255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // TODO conjugate co-Z addition (ZADDC) can return both of these 2275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint PaddQ = P.add(Q); 2285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint PsubQ = P.subtract(Q); 2295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint[] points = new ECPoint[]{ Q, PsubQ, P, PaddQ }; 2315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root curve.normalizeAll(points); 2328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint[] table = new ECPoint[] { 2345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root points[3].negate(), points[2].negate(), points[1].negate(), 2355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root points[0].negate(), infinity, points[0], 2365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root points[1], points[2], points[3] }; 2375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root byte[] jsf = WNafUtil.generateJSF(k, l); 2395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint R = infinity; 2415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i = jsf.length; 2435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--i >= 0) 2448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int jsfi = jsf[i]; 246d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 247d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root // NOTE: The shifting ensures the sign is extended correctly 248d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int kDigit = ((jsfi << 24) >> 28), lDigit = ((jsfi << 28) >> 28); 2498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int index = 4 + (kDigit * 3) + lDigit; 2515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root R = R.twicePlus(table[index]); 2528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return R; 2558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 256d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 257d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static ECPoint implShamirsTrickWNaf(ECPoint P, BigInteger k, 258d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint Q, BigInteger l) 259d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 260d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root boolean negK = k.signum() < 0, negL = l.signum() < 0; 261d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 262d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root k = k.abs(); 263d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root l = l.abs(); 264d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 265d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int widthP = Math.max(2, Math.min(16, WNafUtil.getWindowSize(k.bitLength()))); 266d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int widthQ = Math.max(2, Math.min(16, WNafUtil.getWindowSize(l.bitLength()))); 267d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 268d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WNafPreCompInfo infoP = WNafUtil.precompute(P, widthP, true); 269d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WNafPreCompInfo infoQ = WNafUtil.precompute(Q, widthQ, true); 270d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 271d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompP = negK ? infoP.getPreCompNeg() : infoP.getPreComp(); 272d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompQ = negL ? infoQ.getPreCompNeg() : infoQ.getPreComp(); 273d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompNegP = negK ? infoP.getPreComp() : infoP.getPreCompNeg(); 274d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompNegQ = negL ? infoQ.getPreComp() : infoQ.getPreCompNeg(); 275d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 276d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root byte[] wnafP = WNafUtil.generateWindowNaf(widthP, k); 277d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root byte[] wnafQ = WNafUtil.generateWindowNaf(widthQ, l); 278d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 279d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return implShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ); 280d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 281d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 282d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static ECPoint implShamirsTrickWNaf(ECPoint P, BigInteger k, ECPointMap pointMapQ, BigInteger l) 283d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 284d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root boolean negK = k.signum() < 0, negL = l.signum() < 0; 285d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 286d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root k = k.abs(); 287d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root l = l.abs(); 288d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 289d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int width = Math.max(2, Math.min(16, WNafUtil.getWindowSize(Math.max(k.bitLength(), l.bitLength())))); 290d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 291d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint Q = WNafUtil.mapPointWithPrecomp(P, width, true, pointMapQ); 292d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WNafPreCompInfo infoP = WNafUtil.getWNafPreCompInfo(P); 293d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WNafPreCompInfo infoQ = WNafUtil.getWNafPreCompInfo(Q); 294d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 295d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompP = negK ? infoP.getPreCompNeg() : infoP.getPreComp(); 296d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompQ = negL ? infoQ.getPreCompNeg() : infoQ.getPreComp(); 297d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompNegP = negK ? infoP.getPreComp() : infoP.getPreCompNeg(); 298d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompNegQ = negL ? infoQ.getPreComp() : infoQ.getPreCompNeg(); 299d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 300d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root byte[] wnafP = WNafUtil.generateWindowNaf(width, k); 301d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root byte[] wnafQ = WNafUtil.generateWindowNaf(width, l); 302d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 303d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return implShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ); 304d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 305d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 306d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root private static ECPoint implShamirsTrickWNaf(ECPoint[] preCompP, ECPoint[] preCompNegP, byte[] wnafP, 307d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] preCompQ, ECPoint[] preCompNegQ, byte[] wnafQ) 308d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 309d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int len = Math.max(wnafP.length, wnafQ.length); 310d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 311d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECCurve curve = preCompP[0].getCurve(); 312d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint infinity = curve.getInfinity(); 313d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 314d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint R = infinity; 315d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int zeroes = 0; 316d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 317d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = len - 1; i >= 0; --i) 318d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 319d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int wiP = i < wnafP.length ? wnafP[i] : 0; 320d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int wiQ = i < wnafQ.length ? wnafQ[i] : 0; 321d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 322d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if ((wiP | wiQ) == 0) 323d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 324d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ++zeroes; 325d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root continue; 326d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 327d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 328d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint r = infinity; 329d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (wiP != 0) 330d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 331d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int nP = Math.abs(wiP); 332d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] tableP = wiP < 0 ? preCompNegP : preCompP; 333d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root r = r.add(tableP[nP >>> 1]); 334d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 335d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (wiQ != 0) 336d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 337d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int nQ = Math.abs(wiQ); 338d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] tableQ = wiQ < 0 ? preCompNegQ : preCompQ; 339d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root r = r.add(tableQ[nQ >>> 1]); 340d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 341d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 342d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (zeroes > 0) 343d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 344d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root R = R.timesPow2(zeroes); 345d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root zeroes = 0; 346d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 347d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 348d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root R = R.twicePlus(r); 349d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 350d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 351d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (zeroes > 0) 352d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 353d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root R = R.timesPow2(zeroes); 354d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 355d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 356d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return R; 357d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 358d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 359d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static ECPoint implSumOfMultiplies(ECPoint[] ps, BigInteger[] ks) 360d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 361d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int count = ps.length; 362d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root boolean[] negs = new boolean[count]; 363d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WNafPreCompInfo[] infos = new WNafPreCompInfo[count]; 364d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root byte[][] wnafs = new byte[count][]; 365d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 366d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = 0; i < count; ++i) 367d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 368d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger ki = ks[i]; negs[i] = ki.signum() < 0; ki = ki.abs(); 369d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 370d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int width = Math.max(2, Math.min(16, WNafUtil.getWindowSize(ki.bitLength()))); 371d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root infos[i] = WNafUtil.precompute(ps[i], width, true); 372d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root wnafs[i] = WNafUtil.generateWindowNaf(width, ki); 373d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 374d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 375d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return implSumOfMultiplies(negs, infos, wnafs); 376d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 377d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 378d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static ECPoint implSumOfMultipliesGLV(ECPoint[] ps, BigInteger[] ks, GLVEndomorphism glvEndomorphism) 379d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 380d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger n = ps[0].getCurve().getOrder(); 381d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 382d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int len = ps.length; 383d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 384d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger[] abs = new BigInteger[len << 1]; 385d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = 0, j = 0; i < len; ++i) 386d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 387d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger[] ab = glvEndomorphism.decomposeScalar(ks[i].mod(n)); 388d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root abs[j++] = ab[0]; 389d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root abs[j++] = ab[1]; 390d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 391d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 392d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPointMap pointMap = glvEndomorphism.getPointMap(); 393d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (glvEndomorphism.hasEfficientPointMap()) 394d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 395d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return ECAlgorithms.implSumOfMultiplies(ps, pointMap, abs); 396d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 397d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 398d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] pqs = new ECPoint[len << 1]; 399d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = 0, j = 0; i < len; ++i) 400d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 401d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint p = ps[i], q = pointMap.map(p); 402d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root pqs[j++] = p; 403d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root pqs[j++] = q; 404d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 405d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 406d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return ECAlgorithms.implSumOfMultiplies(pqs, abs); 407d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 408d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 409d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 410d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static ECPoint implSumOfMultiplies(ECPoint[] ps, ECPointMap pointMap, BigInteger[] ks) 411d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 412d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int halfCount = ps.length, fullCount = halfCount << 1; 413d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 414d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root boolean[] negs = new boolean[fullCount]; 415d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WNafPreCompInfo[] infos = new WNafPreCompInfo[fullCount]; 416d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root byte[][] wnafs = new byte[fullCount][]; 417d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 418d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = 0; i < halfCount; ++i) 419d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 420d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int j0 = i << 1, j1 = j0 + 1; 421d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 422d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger kj0 = ks[j0]; negs[j0] = kj0.signum() < 0; kj0 = kj0.abs(); 423d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root BigInteger kj1 = ks[j1]; negs[j1] = kj1.signum() < 0; kj1 = kj1.abs(); 424d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 425d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int width = Math.max(2, Math.min(16, WNafUtil.getWindowSize(Math.max(kj0.bitLength(), kj1.bitLength())))); 426d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 427d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint P = ps[i], Q = WNafUtil.mapPointWithPrecomp(P, width, true, pointMap); 428d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root infos[j0] = WNafUtil.getWNafPreCompInfo(P); 429d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root infos[j1] = WNafUtil.getWNafPreCompInfo(Q); 430d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root wnafs[j0] = WNafUtil.generateWindowNaf(width, kj0); 431d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root wnafs[j1] = WNafUtil.generateWindowNaf(width, kj1); 432d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 433d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 434d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return implSumOfMultiplies(negs, infos, wnafs); 435d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 436d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 437d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root private static ECPoint implSumOfMultiplies(boolean[] negs, WNafPreCompInfo[] infos, byte[][] wnafs) 438d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 439d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int len = 0, count = wnafs.length; 440d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = 0; i < count; ++i) 441d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 442d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root len = Math.max(len, wnafs[i].length); 443d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 444d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 445d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECCurve curve = infos[0].getPreComp()[0].getCurve(); 446d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint infinity = curve.getInfinity(); 447d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 448d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint R = infinity; 449d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int zeroes = 0; 450d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 451d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int i = len - 1; i >= 0; --i) 452d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 453d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint r = infinity; 454d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 455d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root for (int j = 0; j < count; ++j) 456d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 457d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root byte[] wnaf = wnafs[j]; 458d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int wi = i < wnaf.length ? wnaf[i] : 0; 459d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (wi != 0) 460d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 461d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int n = Math.abs(wi); 462d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root WNafPreCompInfo info = infos[j]; 463d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ECPoint[] table = (wi < 0 == negs[j]) ? info.getPreComp() : info.getPreCompNeg(); 464d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root r = r.add(table[n >>> 1]); 465d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 466d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 467d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 468d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (r == infinity) 469d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 470d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root ++zeroes; 471d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root continue; 472d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 473d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 474d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (zeroes > 0) 475d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 476d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root R = R.timesPow2(zeroes); 477d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root zeroes = 0; 478d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 479d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 480d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root R = R.twicePlus(r); 481d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 482d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 483d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (zeroes > 0) 484d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 485d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root R = R.timesPow2(zeroes); 486d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 487d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 488d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return R; 489d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 4908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom} 491