1 files changed, 92 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java b/core/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java
new file mode 100644
index 00000000..78a7a8f9
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java
@@ -0,0 +1,92 @@
+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 c = P.getCurve();
+        if (!c.equals(Q.getCurve()))
+        {
+            throw new IllegalArgumentException("P and Q must be on same curve");
+        }
+
+        // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick
+        if (c instanceof ECCurve.F2m)
+        {
+            ECCurve.F2m f2mCurve = (ECCurve.F2m)c;
+            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)
+    {
+        if (!P.getCurve().equals(Q.getCurve()))
+        {
+            throw new IllegalArgumentException("P and Q must be on same curve");
+        }
+
+        return implShamirsTrick(P, k, Q, l);
+    }
+
+    private static ECPoint implShamirsTrick(ECPoint P, BigInteger k,
+        ECPoint Q, BigInteger l)
+    {
+        int m = Math.max(k.bitLength(), l.bitLength());
+        ECPoint Z = P.add(Q);
+        ECPoint R = P.getCurve().getInfinity();
+
+        for (int i = m - 1; i >= 0; --i)
+        {
+            R = R.twice();
+
+            if (k.testBit(i))
+            {
+                if (l.testBit(i))
+                {
+                    R = R.add(Z);
+                }
+                else
+                {
+                    R = R.add(P);
+                }
+            }
+            else
+            {
+                if (l.testBit(i))
+                {
+                    R = R.add(Q);
+                }
+            }
+        }
+
+        return R;
+    }
+}