ECAlgorithms.java revision 5db505e1f6a68c8d5dfdb0fed0b8607dea7bed96 
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 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     */
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
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
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
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