1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
using System;
using Org.BouncyCastle.Math;
namespace Org.BouncyCastle.Math.EC
{
public class ECAlgorithms
{
public static ECPoint SumOfTwoMultiplies(ECPoint P, BigInteger a,
ECPoint Q, BigInteger b)
{
ECCurve c = P.Curve;
if (!c.Equals(Q.Curve))
throw new ArgumentException("P and Q must be on same curve");
// Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick
if (c is F2mCurve)
{
F2mCurve f2mCurve = (F2mCurve) 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)
*
* 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
*/
public static ECPoint ShamirsTrick(
ECPoint P,
BigInteger k,
ECPoint Q,
BigInteger l)
{
if (!P.Curve.Equals(Q.Curve))
throw new ArgumentException("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 = System.Math.Max(k.BitLength, l.BitLength);
ECPoint Z = P.Add(Q);
ECPoint R = P.Curve.Infinity;
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;
}
}
}
|
