ECAlgorithms.java revision e6bf3e8dfa2804891a82075cb469b736321b4827 
1package org.bouncycastle.math.ec;
2
3import java.math.BigInteger;
4
5public class ECAlgorithms
6{
7    public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a,
8        ECPoint Q, BigInteger b)
9    {
10        ECCurve c = P.getCurve();
11        if (!c.equals(Q.getCurve()))
12        {
13            throw new IllegalArgumentException("P and Q must be on same curve");
14        }
15
16        // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick
17        if (c instanceof ECCurve.F2m)
18        {
19            ECCurve.F2m f2mCurve = (ECCurve.F2m)c;
20            if (f2mCurve.isKoblitz())
21            {
22                return P.multiply(a).add(Q.multiply(b));
23            }
24        }
25
26        return implShamirsTrick(P, a, Q, b);
27    }
28
29    /*
30     * "Shamir's Trick", originally due to E. G. Straus
31     * (Addition chains of vectors. American Mathematical Monthly,
32     * 71(7):806-808, Aug./Sept. 1964)
33     * <pre>
34     * Input: The points P, Q, scalar k = (km?, ... , k1, k0)
35     * and scalar l = (lm?, ... , l1, l0).
36     * Output: R = k * P + l * Q.
37     * 1: Z <- P + Q
38     * 2: R <- O
39     * 3: for i from m-1 down to 0 do
40     * 4:        R <- R + R        {point doubling}
41     * 5:        if (ki = 1) and (li = 0) then R <- R + P end if
42     * 6:        if (ki = 0) and (li = 1) then R <- R + Q end if
43     * 7:        if (ki = 1) and (li = 1) then R <- R + Z end if
44     * 8: end for
45     * 9: return R
46     * </pre>
47     */
48    public static ECPoint shamirsTrick(ECPoint P, BigInteger k,
49        ECPoint Q, BigInteger l)
50    {
51        if (!P.getCurve().equals(Q.getCurve()))
52        {
53            throw new IllegalArgumentException("P and Q must be on same curve");
54        }
55
56        return implShamirsTrick(P, k, Q, l);
57    }
58
59    private static ECPoint implShamirsTrick(ECPoint P, BigInteger k,
60        ECPoint Q, BigInteger l)
61    {
62        int m = Math.max(k.bitLength(), l.bitLength());
63        ECPoint Z = P.add(Q);
64        ECPoint R = P.getCurve().getInfinity();
65
66        for (int i = m - 1; i >= 0; --i)
67        {
68            R = R.twice();
69
70            if (k.testBit(i))
71            {
72                if (l.testBit(i))
73                {
74                    R = R.add(Z);
75                }
76                else
77                {
78                    R = R.add(P);
79                }
80            }
81            else
82            {
83                if (l.testBit(i))
84                {
85                    R = R.add(Q);
86                }
87            }
88        }
89
90        return R;
91    }
92}
93