ECAlgorithms.java revision 80261dd2d1824bb3862e90e77a5412d56ad88b1f
116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giropackage org.bouncycastle.math.ec; 216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giroimport java.math.BigInteger; 416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giropublic class ECAlgorithms 616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro{ 716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a, 816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro ECPoint Q, BigInteger b) 916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 1080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve cp = P.getCurve(); 1180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro Q = importPoint(cp, Q); 1216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 1316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick 1480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (cp instanceof ECCurve.F2m) 1516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 1680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve.F2m f2mCurve = (ECCurve.F2m)cp; 1716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro if (f2mCurve.isKoblitz()) 1816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 1916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro return P.multiply(a).add(Q.multiply(b)); 2016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 2116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 2216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 2316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro return implShamirsTrick(P, a, Q, b); 2416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 2516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 2616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro /* 2716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * "Shamir's Trick", originally due to E. G. Straus 2816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * (Addition chains of vectors. American Mathematical Monthly, 2916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 71(7):806-808, Aug./Sept. 1964) 3016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * <pre> 3116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * Input: The points P, Q, scalar k = (km?, ... , k1, k0) 3216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * and scalar l = (lm?, ... , l1, l0). 3316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * Output: R = k * P + l * Q. 3416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 1: Z <- P + Q 3516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 2: R <- O 3616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 3: for i from m-1 down to 0 do 3716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 4: R <- R + R {point doubling} 3816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 5: if (ki = 1) and (li = 0) then R <- R + P end if 3916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 6: if (ki = 0) and (li = 1) then R <- R + Q end if 4016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 7: if (ki = 1) and (li = 1) then R <- R + Z end if 4116f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 8: end for 4216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * 9: return R 4316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro * </pre> 4416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro */ 4516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro public static ECPoint shamirsTrick(ECPoint P, BigInteger k, 4616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro ECPoint Q, BigInteger l) 4716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 4880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve cp = P.getCurve(); 4980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro Q = importPoint(cp, Q); 5080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 5180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return implShamirsTrick(P, k, Q, l); 5280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 5380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 5480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static ECPoint importPoint(ECCurve c, ECPoint p) 5580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 5680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve cp = p.getCurve(); 5780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (!c.equals(cp)) 5816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 5980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro throw new IllegalArgumentException("Point must be on the same curve"); 6016f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 6180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return c.importPoint(p); 6280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 6316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 6480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro static void implMontgomeryTrick(ECFieldElement[] zs, int off, int len) 6580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 6680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro /* 6780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * Uses the "Montgomery Trick" to invert many field elements, with only a single actual 6880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * field inversion. See e.g. the paper: 6980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick" 7080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * by Katsuyuki Okeya, Kouichi Sakurai. 7180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro */ 7280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 7380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECFieldElement[] c = new ECFieldElement[len]; 7480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro c[0] = zs[off]; 7580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 7680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int i = 0; 7780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (++i < len) 7880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 7980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro c[i] = c[i - 1].multiply(zs[off + i]); 8080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 8180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 8280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECFieldElement u = c[--i].invert(); 8380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 8480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (i > 0) 8580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 8680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int j = off + i--; 8780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECFieldElement tmp = zs[j]; 8880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro zs[j] = c[i].multiply(u); 8980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro u = u.multiply(tmp); 9080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 9180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 9280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro zs[off] = u; 9316f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 9416f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 9580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro static ECPoint implShamirsTrick(ECPoint P, BigInteger k, 9616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro ECPoint Q, BigInteger l) 9716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 9880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve curve = P.getCurve(); 9980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint infinity = curve.getInfinity(); 10080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 10180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro // TODO conjugate co-Z addition (ZADDC) can return both of these 10280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint PaddQ = P.add(Q); 10380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint PsubQ = P.subtract(Q); 10480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 10580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint[] points = new ECPoint[]{ Q, PsubQ, P, PaddQ }; 10680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro curve.normalizeAll(points); 10716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 10880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint[] table = new ECPoint[] { 10980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro points[3].negate(), points[2].negate(), points[1].negate(), 11080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro points[0].negate(), infinity, points[0], 11180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro points[1], points[2], points[3] }; 11280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 11380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro byte[] jsf = WNafUtil.generateJSF(k, l); 11480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 11580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint R = infinity; 11680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 11780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int i = jsf.length; 11880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (--i >= 0) 11916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro { 12080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int jsfi = jsf[i]; 12180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int kDigit = (jsfi >> 4), lDigit = ((jsfi << 28) >> 28); 12216f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 12380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int index = 4 + (kDigit * 3) + lDigit; 12480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro R = R.twicePlus(table[index]); 12516f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 12616f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro 12716f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro return R; 12816f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro } 12916f9ee464b68937f45d009d9c1b0eb9b544a8deeSergio Giro} 130