95 lines
2.0 KiB
C#
95 lines
2.0 KiB
C#
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");
|
||
|
||
// TODO Put back in once WTNAF F2m point multiplication is enabled
|
||
// // 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;
|
||
}
|
||
}
|
||
}
|