diff options
Diffstat (limited to 'crypto/src/math/ec/abc/Tnaf.cs')
| -rw-r--r-- | crypto/src/math/ec/abc/Tnaf.cs | 171 |
1 files changed, 94 insertions, 77 deletions
diff --git a/crypto/src/math/ec/abc/Tnaf.cs b/crypto/src/math/ec/abc/Tnaf.cs index 9f16886f5..b6e792aa4 100644 --- a/crypto/src/math/ec/abc/Tnaf.cs +++ b/crypto/src/math/ec/abc/Tnaf.cs @@ -384,11 +384,11 @@ namespace Org.BouncyCastle.Math.EC.Abc /** * Applies the operation <code>τ()</code> to an - * <code>F2mPoint</code>. - * @param p The F2mPoint to which <code>τ()</code> is applied. + * <code>AbstractF2mPoint</code>. + * @param p The AbstractF2mPoint to which <code>τ()</code> is applied. * @return <code>τ(p)</code> */ - public static F2mPoint Tau(F2mPoint p) + public static AbstractF2mPoint Tau(AbstractF2mPoint p) { return p.Tau(); } @@ -403,7 +403,7 @@ namespace Org.BouncyCastle.Math.EC.Abc * @throws ArgumentException if the given ECCurve is not a Koblitz * curve. */ - public static sbyte GetMu(F2mCurve curve) + public static sbyte GetMu(AbstractF2mCurve curve) { BigInteger a = curve.A.ToBigInteger(); @@ -423,6 +423,16 @@ namespace Org.BouncyCastle.Math.EC.Abc return mu; } + public static sbyte GetMu(ECFieldElement curveA) + { + return (sbyte)(curveA.IsZero ? -1 : 1); + } + + public static sbyte GetMu(int curveA) + { + return (sbyte)(curveA == 0 ? -1 : 1); + } + /** * Calculates the Lucas Sequence elements <code>U<sub>k-1</sub></code> and * <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> and @@ -526,53 +536,60 @@ namespace Org.BouncyCastle.Math.EC.Abc * @throws ArgumentException if <code>curve</code> is not a * Koblitz curve (Anomalous Binary Curve, ABC). */ - public static BigInteger[] GetSi(F2mCurve curve) + public static BigInteger[] GetSi(AbstractF2mCurve curve) { if (!curve.IsKoblitz) throw new ArgumentException("si is defined for Koblitz curves only"); - int m = curve.M; + int m = curve.FieldSize; int a = curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); - int h = curve.Cofactor.IntValue; + sbyte mu = GetMu(a); + int shifts = GetShiftsForCofactor(curve.Cofactor); int index = m + 3 - a; BigInteger[] ui = GetLucas(mu, index, false); - BigInteger dividend0; - BigInteger dividend1; if (mu == 1) { - dividend0 = BigInteger.One.Subtract(ui[1]); - dividend1 = BigInteger.One.Subtract(ui[0]); - } - else if (mu == -1) - { - dividend0 = BigInteger.One.Add(ui[1]); - dividend1 = BigInteger.One.Add(ui[0]); - } - else - { - throw new ArgumentException("mu must be 1 or -1"); + ui[0] = ui[0].Negate(); + ui[1] = ui[1].Negate(); } - BigInteger[] si = new BigInteger[2]; + BigInteger dividend0 = BigInteger.One.Add(ui[1]).ShiftRight(shifts); + BigInteger dividend1 = BigInteger.One.Add(ui[0]).ShiftRight(shifts).Negate(); - if (h == 2) - { - si[0] = dividend0.ShiftRight(1); - si[1] = dividend1.ShiftRight(1).Negate(); - } - else if (h == 4) + return new BigInteger[] { dividend0, dividend1 }; + } + + public static BigInteger[] GetSi(int fieldSize, int curveA, BigInteger cofactor) + { + sbyte mu = GetMu(curveA); + int shifts = GetShiftsForCofactor(cofactor); + int index = fieldSize + 3 - curveA; + BigInteger[] ui = GetLucas(mu, index, false); + if (mu == 1) { - si[0] = dividend0.ShiftRight(2); - si[1] = dividend1.ShiftRight(2).Negate(); + ui[0] = ui[0].Negate(); + ui[1] = ui[1].Negate(); } - else + + BigInteger dividend0 = BigInteger.One.Add(ui[1]).ShiftRight(shifts); + BigInteger dividend1 = BigInteger.One.Add(ui[0]).ShiftRight(shifts).Negate(); + + return new BigInteger[] { dividend0, dividend1 }; + } + + protected static int GetShiftsForCofactor(BigInteger h) + { + if (h != null && h.BitLength < 4) { - throw new ArgumentException("h (Cofactor) must be 2 or 4"); + int hi = h.IntValue; + if (hi == 2) + return 1; + if (hi == 4) + return 2; } - return si; + throw new ArgumentException("h (Cofactor) must be 2 or 4"); } /** @@ -624,70 +641,77 @@ namespace Org.BouncyCastle.Math.EC.Abc } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by a <code>BigInteger</code> using the reduced <code>τ</code>-adic * NAF (RTNAF) method. - * @param p The F2mPoint to Multiply. + * @param p The AbstractF2mPoint to Multiply. * @param k The <code>BigInteger</code> by which to Multiply <code>p</code>. * @return <code>k * p</code> */ - public static F2mPoint MultiplyRTnaf(F2mPoint p, BigInteger k) + public static AbstractF2mPoint MultiplyRTnaf(AbstractF2mPoint p, BigInteger k) { - F2mCurve curve = (F2mCurve) p.Curve; - int m = curve.M; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); + AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve; + int m = curve.FieldSize; + int a = curve.A.ToBigInteger().IntValue; + sbyte mu = GetMu(a); BigInteger[] s = curve.GetSi(); - ZTauElement rho = PartModReduction(k, m, a, s, mu, (sbyte)10); + ZTauElement rho = PartModReduction(k, m, (sbyte)a, s, mu, (sbyte)10); return MultiplyTnaf(p, rho); } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> * using the <code>τ</code>-adic NAF (TNAF) method. - * @param p The F2mPoint to Multiply. + * @param p The AbstractF2mPoint to Multiply. * @param lambda The element <code>λ</code> of * <code><b>Z</b>[τ]</code>. * @return <code>λ * p</code> */ - public static F2mPoint MultiplyTnaf(F2mPoint p, ZTauElement lambda) + public static AbstractF2mPoint MultiplyTnaf(AbstractF2mPoint p, ZTauElement lambda) { - F2mCurve curve = (F2mCurve)p.Curve; - sbyte mu = curve.GetMu(); + AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve; + sbyte mu = GetMu(curve.A); sbyte[] u = TauAdicNaf(mu, lambda); - F2mPoint q = MultiplyFromTnaf(p, u); + AbstractF2mPoint q = MultiplyFromTnaf(p, u); return q; } /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> * using the <code>τ</code>-adic NAF (TNAF) method, given the TNAF * of <code>λ</code>. - * @param p The F2mPoint to Multiply. + * @param p The AbstractF2mPoint to Multiply. * @param u The the TNAF of <code>λ</code>.. * @return <code>λ * p</code> */ - public static F2mPoint MultiplyFromTnaf(F2mPoint p, sbyte[] u) + public static AbstractF2mPoint MultiplyFromTnaf(AbstractF2mPoint p, sbyte[] u) { - F2mCurve curve = (F2mCurve)p.Curve; - F2mPoint q = (F2mPoint) curve.Infinity; + ECCurve curve = p.Curve; + AbstractF2mPoint q = (AbstractF2mPoint)curve.Infinity; + AbstractF2mPoint pNeg = (AbstractF2mPoint)p.Negate(); + int tauCount = 0; for (int i = u.Length - 1; i >= 0; i--) { - q = Tau(q); - if (u[i] == 1) - { - q = (F2mPoint)q.AddSimple(p); - } - else if (u[i] == -1) + ++tauCount; + sbyte ui = u[i]; + if (ui != 0) { - q = (F2mPoint)q.SubtractSimple(p); + q = q.TauPow(tauCount); + tauCount = 0; + + ECPoint x = ui > 0 ? p : pNeg; + q = (AbstractF2mPoint)q.Add(x); } } + if (tauCount > 0) + { + q = q.TauPow(tauCount); + } return q; } @@ -800,28 +824,21 @@ namespace Org.BouncyCastle.Math.EC.Abc * @param a The parameter <code>a</code> of the elliptic curve. * @return The precomputation array for <code>p</code>. */ - public static F2mPoint[] GetPreComp(F2mPoint p, sbyte a) + public static AbstractF2mPoint[] GetPreComp(AbstractF2mPoint p, sbyte a) { - F2mPoint[] pu; - pu = new F2mPoint[16]; - pu[1] = p; - sbyte[][] alphaTnaf; - if (a == 0) - { - alphaTnaf = Tnaf.Alpha0Tnaf; - } - else - { - // a == 1 - alphaTnaf = Tnaf.Alpha1Tnaf; - } + sbyte[][] alphaTnaf = (a == 0) ? Tnaf.Alpha0Tnaf : Tnaf.Alpha1Tnaf; + + AbstractF2mPoint[] pu = new AbstractF2mPoint[(uint)(alphaTnaf.Length + 1) >> 1]; + pu[0] = p; - int precompLen = alphaTnaf.Length; - for (int i = 3; i < precompLen; i = i + 2) + uint precompLen = (uint)alphaTnaf.Length; + for (uint i = 3; i < precompLen; i += 2) { - pu[i] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]); + pu[i >> 1] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]); } - + + p.Curve.NormalizeAll(pu); + return pu; } } |