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