| package org.bouncycastle.math.ec; |
| |
| import java.math.BigInteger; |
| |
| public class ECAlgorithms |
| { |
| public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a, |
| ECPoint Q, BigInteger b) |
| { |
| ECCurve cp = P.getCurve(); |
| Q = importPoint(cp, Q); |
| |
| // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick |
| if (cp instanceof ECCurve.F2m) |
| { |
| ECCurve.F2m f2mCurve = (ECCurve.F2m)cp; |
| if (f2mCurve.isKoblitz()) |
| { |
| return P.multiply(a).add(Q.multiply(b)); |
| } |
| } |
| |
| return implShamirsTrick(P, a, Q, b); |
| } |
| |
| /* |
| * "Shamir's Trick", originally due to E. G. Straus |
| * (Addition chains of vectors. American Mathematical Monthly, |
| * 71(7):806-808, Aug./Sept. 1964) |
| * <pre> |
| * Input: The points P, Q, scalar k = (km?, ... , k1, k0) |
| * and scalar l = (lm?, ... , l1, l0). |
| * Output: R = k * P + l * Q. |
| * 1: Z <- P + Q |
| * 2: R <- O |
| * 3: for i from m-1 down to 0 do |
| * 4: R <- R + R {point doubling} |
| * 5: if (ki = 1) and (li = 0) then R <- R + P end if |
| * 6: if (ki = 0) and (li = 1) then R <- R + Q end if |
| * 7: if (ki = 1) and (li = 1) then R <- R + Z end if |
| * 8: end for |
| * 9: return R |
| * </pre> |
| */ |
| public static ECPoint shamirsTrick(ECPoint P, BigInteger k, |
| ECPoint Q, BigInteger l) |
| { |
| ECCurve cp = P.getCurve(); |
| Q = importPoint(cp, Q); |
| |
| return implShamirsTrick(P, k, Q, l); |
| } |
| |
| public static ECPoint importPoint(ECCurve c, ECPoint p) |
| { |
| ECCurve cp = p.getCurve(); |
| if (!c.equals(cp)) |
| { |
| throw new IllegalArgumentException("Point must be on the same curve"); |
| } |
| return c.importPoint(p); |
| } |
| |
| static void implMontgomeryTrick(ECFieldElement[] zs, int off, int len) |
| { |
| /* |
| * Uses the "Montgomery Trick" to invert many field elements, with only a single actual |
| * field inversion. See e.g. the paper: |
| * "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick" |
| * by Katsuyuki Okeya, Kouichi Sakurai. |
| */ |
| |
| ECFieldElement[] c = new ECFieldElement[len]; |
| c[0] = zs[off]; |
| |
| int i = 0; |
| while (++i < len) |
| { |
| c[i] = c[i - 1].multiply(zs[off + i]); |
| } |
| |
| ECFieldElement u = c[--i].invert(); |
| |
| while (i > 0) |
| { |
| int j = off + i--; |
| ECFieldElement tmp = zs[j]; |
| zs[j] = c[i].multiply(u); |
| u = u.multiply(tmp); |
| } |
| |
| zs[off] = u; |
| } |
| |
| static ECPoint implShamirsTrick(ECPoint P, BigInteger k, |
| ECPoint Q, BigInteger l) |
| { |
| ECCurve curve = P.getCurve(); |
| ECPoint infinity = curve.getInfinity(); |
| |
| // TODO conjugate co-Z addition (ZADDC) can return both of these |
| ECPoint PaddQ = P.add(Q); |
| ECPoint PsubQ = P.subtract(Q); |
| |
| ECPoint[] points = new ECPoint[]{ Q, PsubQ, P, PaddQ }; |
| curve.normalizeAll(points); |
| |
| ECPoint[] table = new ECPoint[] { |
| points[3].negate(), points[2].negate(), points[1].negate(), |
| points[0].negate(), infinity, points[0], |
| points[1], points[2], points[3] }; |
| |
| byte[] jsf = WNafUtil.generateJSF(k, l); |
| |
| ECPoint R = infinity; |
| |
| int i = jsf.length; |
| while (--i >= 0) |
| { |
| int jsfi = jsf[i]; |
| int kDigit = (jsfi >> 4), lDigit = ((jsfi << 28) >> 28); |
| |
| int index = 4 + (kDigit * 3) + lDigit; |
| R = R.twicePlus(table[index]); |
| } |
| |
| return R; |
| } |
| } |