1 package org.bouncycastle.math.ec; 2 3 import java.math.BigInteger; 4 5 public class ECAlgorithms 6 { sumOfTwoMultiplies(ECPoint P, BigInteger a, ECPoint Q, BigInteger b)7 public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a, 8 ECPoint Q, BigInteger b) 9 { 10 ECCurve cp = P.getCurve(); 11 Q = importPoint(cp, Q); 12 13 // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick 14 if (cp instanceof ECCurve.F2m) 15 { 16 ECCurve.F2m f2mCurve = (ECCurve.F2m)cp; 17 if (f2mCurve.isKoblitz()) 18 { 19 return P.multiply(a).add(Q.multiply(b)); 20 } 21 } 22 23 return implShamirsTrick(P, a, Q, b); 24 } 25 26 /* 27 * "Shamir's Trick", originally due to E. G. Straus 28 * (Addition chains of vectors. American Mathematical Monthly, 29 * 71(7):806-808, Aug./Sept. 1964) 30 * <pre> 31 * Input: The points P, Q, scalar k = (km?, ... , k1, k0) 32 * and scalar l = (lm?, ... , l1, l0). 33 * Output: R = k * P + l * Q. 34 * 1: Z <- P + Q 35 * 2: R <- O 36 * 3: for i from m-1 down to 0 do 37 * 4: R <- R + R {point doubling} 38 * 5: if (ki = 1) and (li = 0) then R <- R + P end if 39 * 6: if (ki = 0) and (li = 1) then R <- R + Q end if 40 * 7: if (ki = 1) and (li = 1) then R <- R + Z end if 41 * 8: end for 42 * 9: return R 43 * </pre> 44 */ shamirsTrick(ECPoint P, BigInteger k, ECPoint Q, BigInteger l)45 public static ECPoint shamirsTrick(ECPoint P, BigInteger k, 46 ECPoint Q, BigInteger l) 47 { 48 ECCurve cp = P.getCurve(); 49 Q = importPoint(cp, Q); 50 51 return implShamirsTrick(P, k, Q, l); 52 } 53 importPoint(ECCurve c, ECPoint p)54 public static ECPoint importPoint(ECCurve c, ECPoint p) 55 { 56 ECCurve cp = p.getCurve(); 57 if (!c.equals(cp)) 58 { 59 throw new IllegalArgumentException("Point must be on the same curve"); 60 } 61 return c.importPoint(p); 62 } 63 implMontgomeryTrick(ECFieldElement[] zs, int off, int len)64 static void implMontgomeryTrick(ECFieldElement[] zs, int off, int len) 65 { 66 /* 67 * Uses the "Montgomery Trick" to invert many field elements, with only a single actual 68 * field inversion. See e.g. the paper: 69 * "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick" 70 * by Katsuyuki Okeya, Kouichi Sakurai. 71 */ 72 73 ECFieldElement[] c = new ECFieldElement[len]; 74 c[0] = zs[off]; 75 76 int i = 0; 77 while (++i < len) 78 { 79 c[i] = c[i - 1].multiply(zs[off + i]); 80 } 81 82 ECFieldElement u = c[--i].invert(); 83 84 while (i > 0) 85 { 86 int j = off + i--; 87 ECFieldElement tmp = zs[j]; 88 zs[j] = c[i].multiply(u); 89 u = u.multiply(tmp); 90 } 91 92 zs[off] = u; 93 } 94 implShamirsTrick(ECPoint P, BigInteger k, ECPoint Q, BigInteger l)95 static ECPoint implShamirsTrick(ECPoint P, BigInteger k, 96 ECPoint Q, BigInteger l) 97 { 98 ECCurve curve = P.getCurve(); 99 ECPoint infinity = curve.getInfinity(); 100 101 // TODO conjugate co-Z addition (ZADDC) can return both of these 102 ECPoint PaddQ = P.add(Q); 103 ECPoint PsubQ = P.subtract(Q); 104 105 ECPoint[] points = new ECPoint[]{ Q, PsubQ, P, PaddQ }; 106 curve.normalizeAll(points); 107 108 ECPoint[] table = new ECPoint[] { 109 points[3].negate(), points[2].negate(), points[1].negate(), 110 points[0].negate(), infinity, points[0], 111 points[1], points[2], points[3] }; 112 113 byte[] jsf = WNafUtil.generateJSF(k, l); 114 115 ECPoint R = infinity; 116 117 int i = jsf.length; 118 while (--i >= 0) 119 { 120 int jsfi = jsf[i]; 121 int kDigit = (jsfi >> 4), lDigit = ((jsfi << 28) >> 28); 122 123 int index = 4 + (kDigit * 3) + lDigit; 124 R = R.twicePlus(table[index]); 125 } 126 127 return R; 128 } 129 } 130