diff options
Diffstat (limited to 'crypto/src/math/ec/abc/Tnaf.cs')
| -rw-r--r-- | crypto/src/math/ec/abc/Tnaf.cs | 1652 |
1 files changed, 823 insertions, 829 deletions
diff --git a/crypto/src/math/ec/abc/Tnaf.cs b/crypto/src/math/ec/abc/Tnaf.cs index 225fc3075..0ba414e68 100644 --- a/crypto/src/math/ec/abc/Tnaf.cs +++ b/crypto/src/math/ec/abc/Tnaf.cs @@ -2,833 +2,827 @@ using System; namespace Org.BouncyCastle.Math.EC.Abc { - /** - * Class holding methods for point multiplication based on the window - * τ-adic nonadjacent form (WTNAF). The algorithms are based on the - * paper "Improved Algorithms for Arithmetic on Anomalous Binary Curves" - * by Jerome A. Solinas. The paper first appeared in the Proceedings of - * Crypto 1997. - */ - internal class Tnaf - { - private static readonly BigInteger MinusOne = BigInteger.One.Negate(); - private static readonly BigInteger MinusTwo = BigInteger.Two.Negate(); - private static readonly BigInteger MinusThree = BigInteger.Three.Negate(); - private static readonly BigInteger Four = BigInteger.ValueOf(4); - - /** - * The window width of WTNAF. The standard value of 4 is slightly less - * than optimal for running time, but keeps space requirements for - * precomputation low. For typical curves, a value of 5 or 6 results in - * a better running time. When changing this value, the - * <code>α<sub>u</sub></code>'s must be computed differently, see - * e.g. "Guide to Elliptic Curve Cryptography", Darrel Hankerson, - * Alfred Menezes, Scott Vanstone, Springer-Verlag New York Inc., 2004, - * p. 121-122 - */ - public const sbyte Width = 4; - - /** - * 2<sup>4</sup> - */ - public const sbyte Pow2Width = 16; - - /** - * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array - * of <code>ZTauElement</code>s. - */ - public static readonly ZTauElement[] Alpha0 = - { - null, - new ZTauElement(BigInteger.One, BigInteger.Zero), null, - new ZTauElement(MinusThree, MinusOne), null, - new ZTauElement(MinusOne, MinusOne), null, - new ZTauElement(BigInteger.One, MinusOne), null - }; - - /** - * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array - * of TNAFs. - */ - public static readonly sbyte[][] Alpha0Tnaf = - { - null, new sbyte[]{1}, null, new sbyte[]{-1, 0, 1}, null, new sbyte[]{1, 0, 1}, null, new sbyte[]{-1, 0, 0, 1} - }; - - /** - * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array - * of <code>ZTauElement</code>s. - */ - public static readonly ZTauElement[] Alpha1 = - { - null, - new ZTauElement(BigInteger.One, BigInteger.Zero), null, - new ZTauElement(MinusThree, BigInteger.One), null, - new ZTauElement(MinusOne, BigInteger.One), null, - new ZTauElement(BigInteger.One, BigInteger.One), null - }; - - /** - * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array - * of TNAFs. - */ - public static readonly sbyte[][] Alpha1Tnaf = - { - null, new sbyte[]{1}, null, new sbyte[]{-1, 0, 1}, null, new sbyte[]{1, 0, 1}, null, new sbyte[]{-1, 0, 0, -1} - }; - - /** - * Computes the norm of an element <code>λ</code> of - * <code><b>Z</b>[τ]</code>. - * @param mu The parameter <code>μ</code> of the elliptic curve. - * @param lambda The element <code>λ</code> of - * <code><b>Z</b>[τ]</code>. - * @return The norm of <code>λ</code>. - */ - public static BigInteger Norm(sbyte mu, ZTauElement lambda) - { - BigInteger norm; - - // s1 = u^2 - BigInteger s1 = lambda.u.Multiply(lambda.u); - - // s2 = u * v - BigInteger s2 = lambda.u.Multiply(lambda.v); - - // s3 = 2 * v^2 - BigInteger s3 = lambda.v.Multiply(lambda.v).ShiftLeft(1); - - if (mu == 1) - { - norm = s1.Add(s2).Add(s3); - } - else if (mu == -1) - { - norm = s1.Subtract(s2).Add(s3); - } - else - { - throw new ArgumentException("mu must be 1 or -1"); - } - - return norm; - } - - /** - * Computes the norm of an element <code>λ</code> of - * <code><b>R</b>[τ]</code>, where <code>λ = u + vτ</code> - * and <code>u</code> and <code>u</code> are real numbers (elements of - * <code><b>R</b></code>). - * @param mu The parameter <code>μ</code> of the elliptic curve. - * @param u The real part of the element <code>λ</code> of - * <code><b>R</b>[τ]</code>. - * @param v The <code>τ</code>-adic part of the element - * <code>λ</code> of <code><b>R</b>[τ]</code>. - * @return The norm of <code>λ</code>. - */ - public static SimpleBigDecimal Norm(sbyte mu, SimpleBigDecimal u, SimpleBigDecimal v) - { - SimpleBigDecimal norm; - - // s1 = u^2 - SimpleBigDecimal s1 = u.Multiply(u); - - // s2 = u * v - SimpleBigDecimal s2 = u.Multiply(v); - - // s3 = 2 * v^2 - SimpleBigDecimal s3 = v.Multiply(v).ShiftLeft(1); - - if (mu == 1) - { - norm = s1.Add(s2).Add(s3); - } - else if (mu == -1) - { - norm = s1.Subtract(s2).Add(s3); - } - else - { - throw new ArgumentException("mu must be 1 or -1"); - } - - return norm; - } - - /** - * Rounds an element <code>λ</code> of <code><b>R</b>[τ]</code> - * to an element of <code><b>Z</b>[τ]</code>, such that their difference - * has minimal norm. <code>λ</code> is given as - * <code>λ = λ<sub>0</sub> + λ<sub>1</sub>τ</code>. - * @param lambda0 The component <code>λ<sub>0</sub></code>. - * @param lambda1 The component <code>λ<sub>1</sub></code>. - * @param mu The parameter <code>μ</code> of the elliptic curve. Must - * equal 1 or -1. - * @return The rounded element of <code><b>Z</b>[τ]</code>. - * @throws ArgumentException if <code>lambda0</code> and - * <code>lambda1</code> do not have same scale. - */ - public static ZTauElement Round(SimpleBigDecimal lambda0, - SimpleBigDecimal lambda1, sbyte mu) - { - int scale = lambda0.Scale; - if (lambda1.Scale != scale) - throw new ArgumentException("lambda0 and lambda1 do not have same scale"); - - if (!((mu == 1) || (mu == -1))) - throw new ArgumentException("mu must be 1 or -1"); - - BigInteger f0 = lambda0.Round(); - BigInteger f1 = lambda1.Round(); - - SimpleBigDecimal eta0 = lambda0.Subtract(f0); - SimpleBigDecimal eta1 = lambda1.Subtract(f1); - - // eta = 2*eta0 + mu*eta1 - SimpleBigDecimal eta = eta0.Add(eta0); - if (mu == 1) - { - eta = eta.Add(eta1); - } - else - { - // mu == -1 - eta = eta.Subtract(eta1); - } - - // check1 = eta0 - 3*mu*eta1 - // check2 = eta0 + 4*mu*eta1 - SimpleBigDecimal threeEta1 = eta1.Add(eta1).Add(eta1); - SimpleBigDecimal fourEta1 = threeEta1.Add(eta1); - SimpleBigDecimal check1; - SimpleBigDecimal check2; - if (mu == 1) - { - check1 = eta0.Subtract(threeEta1); - check2 = eta0.Add(fourEta1); - } - else - { - // mu == -1 - check1 = eta0.Add(threeEta1); - check2 = eta0.Subtract(fourEta1); - } - - sbyte h0 = 0; - sbyte h1 = 0; - - // if eta >= 1 - if (eta.CompareTo(BigInteger.One) >= 0) - { - if (check1.CompareTo(MinusOne) < 0) - { - h1 = mu; - } - else - { - h0 = 1; - } - } - else - { - // eta < 1 - if (check2.CompareTo(BigInteger.Two) >= 0) - { - h1 = mu; - } - } - - // if eta < -1 - if (eta.CompareTo(MinusOne) < 0) - { - if (check1.CompareTo(BigInteger.One) >= 0) - { - h1 = (sbyte)-mu; - } - else - { - h0 = -1; - } - } - else - { - // eta >= -1 - if (check2.CompareTo(MinusTwo) < 0) - { - h1 = (sbyte)-mu; - } - } - - BigInteger q0 = f0.Add(BigInteger.ValueOf(h0)); - BigInteger q1 = f1.Add(BigInteger.ValueOf(h1)); - return new ZTauElement(q0, q1); - } - - /** - * Approximate division by <code>n</code>. For an integer - * <code>k</code>, the value <code>λ = s k / n</code> is - * computed to <code>c</code> bits of accuracy. - * @param k The parameter <code>k</code>. - * @param s The curve parameter <code>s<sub>0</sub></code> or - * <code>s<sub>1</sub></code>. - * @param vm The Lucas Sequence element <code>V<sub>m</sub></code>. - * @param a The parameter <code>a</code> of the elliptic curve. - * @param m The bit length of the finite field - * <code><b>F</b><sub>m</sub></code>. - * @param c The number of bits of accuracy, i.e. the scale of the returned - * <code>SimpleBigDecimal</code>. - * @return The value <code>λ = s k / n</code> computed to - * <code>c</code> bits of accuracy. - */ - public static SimpleBigDecimal ApproximateDivisionByN(BigInteger k, - BigInteger s, BigInteger vm, sbyte a, int m, int c) - { - int _k = (m + 5)/2 + c; - BigInteger ns = k.ShiftRight(m - _k - 2 + a); - - BigInteger gs = s.Multiply(ns); - - BigInteger hs = gs.ShiftRight(m); - - BigInteger js = vm.Multiply(hs); - - BigInteger gsPlusJs = gs.Add(js); - BigInteger ls = gsPlusJs.ShiftRight(_k-c); - if (gsPlusJs.TestBit(_k-c-1)) - { - // round up - ls = ls.Add(BigInteger.One); - } - - return new SimpleBigDecimal(ls, c); - } - - /** - * Computes the <code>τ</code>-adic NAF (non-adjacent form) of an - * element <code>λ</code> of <code><b>Z</b>[τ]</code>. - * @param mu The parameter <code>μ</code> of the elliptic curve. - * @param lambda The element <code>λ</code> of - * <code><b>Z</b>[τ]</code>. - * @return The <code>τ</code>-adic NAF of <code>λ</code>. - */ - public static sbyte[] TauAdicNaf(sbyte mu, ZTauElement lambda) - { - if (!((mu == 1) || (mu == -1))) - throw new ArgumentException("mu must be 1 or -1"); - - BigInteger norm = Norm(mu, lambda); - - // Ceiling of log2 of the norm - int log2Norm = norm.BitLength; - - // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 - int maxLength = log2Norm > 30 ? log2Norm + 4 : 34; - - // The array holding the TNAF - sbyte[] u = new sbyte[maxLength]; - int i = 0; - - // The actual length of the TNAF - int length = 0; - - BigInteger r0 = lambda.u; - BigInteger r1 = lambda.v; - - while(!((r0.Equals(BigInteger.Zero)) && (r1.Equals(BigInteger.Zero)))) - { - // If r0 is odd - if (r0.TestBit(0)) - { - u[i] = (sbyte) BigInteger.Two.Subtract((r0.Subtract(r1.ShiftLeft(1))).Mod(Four)).IntValue; - - // r0 = r0 - u[i] - if (u[i] == 1) - { - r0 = r0.ClearBit(0); - } - else - { - // u[i] == -1 - r0 = r0.Add(BigInteger.One); - } - length = i; - } - else - { - u[i] = 0; - } - - BigInteger t = r0; - BigInteger s = r0.ShiftRight(1); - if (mu == 1) - { - r0 = r1.Add(s); - } - else - { - // mu == -1 - r0 = r1.Subtract(s); - } - - r1 = t.ShiftRight(1).Negate(); - i++; - } - - length++; - - // Reduce the TNAF array to its actual length - sbyte[] tnaf = new sbyte[length]; - Array.Copy(u, 0, tnaf, 0, length); - return tnaf; - } - - /** - * Applies the operation <code>τ()</code> to an - * <code>F2mPoint</code>. - * @param p The F2mPoint to which <code>τ()</code> is applied. - * @return <code>τ(p)</code> - */ - public static F2mPoint Tau(F2mPoint p) - { - if (p.IsInfinity) - return p; - - ECFieldElement x = p.X; - ECFieldElement y = p.Y; - - return new F2mPoint(p.Curve, x.Square(), y.Square(), p.IsCompressed); - } - - /** - * Returns the parameter <code>μ</code> of the elliptic curve. - * @param curve The elliptic curve from which to obtain <code>μ</code>. - * The curve must be a Koblitz curve, i.e. <code>a</code> Equals - * <code>0</code> or <code>1</code> and <code>b</code> Equals - * <code>1</code>. - * @return <code>μ</code> of the elliptic curve. - * @throws ArgumentException if the given ECCurve is not a Koblitz - * curve. - */ - public static sbyte GetMu(F2mCurve curve) - { - BigInteger a = curve.A.ToBigInteger(); - - sbyte mu; - if (a.SignValue == 0) - { - mu = -1; - } - else if (a.Equals(BigInteger.One)) - { - mu = 1; - } - else - { - throw new ArgumentException("No Koblitz curve (ABC), TNAF multiplication not possible"); - } - return mu; - } - - /** - * 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 - * <code>V<sub>k</sub></code>. - * @param mu The parameter <code>μ</code> of the elliptic curve. - * @param k The index of the second element of the Lucas Sequence to be - * returned. - * @param doV If set to true, computes <code>V<sub>k-1</sub></code> and - * <code>V<sub>k</sub></code>, otherwise <code>U<sub>k-1</sub></code> and - * <code>U<sub>k</sub></code>. - * @return An array with 2 elements, containing <code>U<sub>k-1</sub></code> - * and <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> - * and <code>V<sub>k</sub></code>. - */ - public static BigInteger[] GetLucas(sbyte mu, int k, bool doV) - { - if (!(mu == 1 || mu == -1)) - throw new ArgumentException("mu must be 1 or -1"); - - BigInteger u0; - BigInteger u1; - BigInteger u2; - - if (doV) - { - u0 = BigInteger.Two; - u1 = BigInteger.ValueOf(mu); - } - else - { - u0 = BigInteger.Zero; - u1 = BigInteger.One; - } - - for (int i = 1; i < k; i++) - { - // u2 = mu*u1 - 2*u0; - BigInteger s = null; - if (mu == 1) - { - s = u1; - } - else - { - // mu == -1 - s = u1.Negate(); - } - - u2 = s.Subtract(u0.ShiftLeft(1)); - u0 = u1; - u1 = u2; - // System.out.println(i + ": " + u2); - // System.out.println(); - } - - BigInteger[] retVal = {u0, u1}; - return retVal; - } - - /** - * Computes the auxiliary value <code>t<sub>w</sub></code>. If the width is - * 4, then for <code>mu = 1</code>, <code>t<sub>w</sub> = 6</code> and for - * <code>mu = -1</code>, <code>t<sub>w</sub> = 10</code> - * @param mu The parameter <code>μ</code> of the elliptic curve. - * @param w The window width of the WTNAF. - * @return the auxiliary value <code>t<sub>w</sub></code> - */ - public static BigInteger GetTw(sbyte mu, int w) - { - if (w == 4) - { - if (mu == 1) - { - return BigInteger.ValueOf(6); - } - else - { - // mu == -1 - return BigInteger.ValueOf(10); - } - } - else - { - // For w <> 4, the values must be computed - BigInteger[] us = GetLucas(mu, w, false); - BigInteger twoToW = BigInteger.Zero.SetBit(w); - BigInteger u1invert = us[1].ModInverse(twoToW); - BigInteger tw; - tw = BigInteger.Two.Multiply(us[0]).Multiply(u1invert).Mod(twoToW); - //System.out.println("mu = " + mu); - //System.out.println("tw = " + tw); - return tw; - } - } - - /** - * Computes the auxiliary values <code>s<sub>0</sub></code> and - * <code>s<sub>1</sub></code> used for partial modular reduction. - * @param curve The elliptic curve for which to compute - * <code>s<sub>0</sub></code> and <code>s<sub>1</sub></code>. - * @throws ArgumentException if <code>curve</code> is not a - * Koblitz curve (Anomalous Binary Curve, ABC). - */ - public static BigInteger[] GetSi(F2mCurve curve) - { - if (!curve.IsKoblitz) - throw new ArgumentException("si is defined for Koblitz curves only"); - - int m = curve.M; - int a = curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); - int h = curve.H.IntValue; - 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"); - } - - BigInteger[] si = new BigInteger[2]; - - if (h == 2) - { - si[0] = dividend0.ShiftRight(1); - si[1] = dividend1.ShiftRight(1).Negate(); - } - else if (h == 4) - { - si[0] = dividend0.ShiftRight(2); - si[1] = dividend1.ShiftRight(2).Negate(); - } - else - { - throw new ArgumentException("h (Cofactor) must be 2 or 4"); - } - - return si; - } - - /** - * Partial modular reduction modulo - * <code>(τ<sup>m</sup> - 1)/(τ - 1)</code>. - * @param k The integer to be reduced. - * @param m The bitlength of the underlying finite field. - * @param a The parameter <code>a</code> of the elliptic curve. - * @param s The auxiliary values <code>s<sub>0</sub></code> and - * <code>s<sub>1</sub></code>. - * @param mu The parameter μ of the elliptic curve. - * @param c The precision (number of bits of accuracy) of the partial - * modular reduction. - * @return <code>ρ := k partmod (τ<sup>m</sup> - 1)/(τ - 1)</code> - */ - public static ZTauElement PartModReduction(BigInteger k, int m, sbyte a, - BigInteger[] s, sbyte mu, sbyte c) - { - // d0 = s[0] + mu*s[1]; mu is either 1 or -1 - BigInteger d0; - if (mu == 1) - { - d0 = s[0].Add(s[1]); - } - else - { - d0 = s[0].Subtract(s[1]); - } - - BigInteger[] v = GetLucas(mu, m, true); - BigInteger vm = v[1]; - - SimpleBigDecimal lambda0 = ApproximateDivisionByN( - k, s[0], vm, a, m, c); - - SimpleBigDecimal lambda1 = ApproximateDivisionByN( - k, s[1], vm, a, m, c); - - ZTauElement q = Round(lambda0, lambda1, mu); - - // r0 = n - d0*q0 - 2*s1*q1 - BigInteger r0 = k.Subtract(d0.Multiply(q.u)).Subtract( - BigInteger.ValueOf(2).Multiply(s[1]).Multiply(q.v)); - - // r1 = s1*q0 - s0*q1 - BigInteger r1 = s[1].Multiply(q.u).Subtract(s[0].Multiply(q.v)); - - return new ZTauElement(r0, r1); - } - - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * by a <code>BigInteger</code> using the reduced <code>τ</code>-adic - * NAF (RTNAF) method. - * @param p The F2mPoint 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) - { - F2mCurve curve = (F2mCurve) p.Curve; - int m = curve.M; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); - BigInteger[] s = curve.GetSi(); - ZTauElement rho = PartModReduction(k, m, a, s, mu, (sbyte)10); - - return MultiplyTnaf(p, rho); - } - - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * 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 lambda The element <code>λ</code> of - * <code><b>Z</b>[τ]</code>. - * @return <code>λ * p</code> - */ - public static F2mPoint MultiplyTnaf(F2mPoint p, ZTauElement lambda) - { - F2mCurve curve = (F2mCurve)p.Curve; - sbyte mu = curve.GetMu(); - sbyte[] u = TauAdicNaf(mu, lambda); - - F2mPoint q = MultiplyFromTnaf(p, u); - - return q; - } - - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * 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 u The the TNAF of <code>λ</code>.. - * @return <code>λ * p</code> - */ - public static F2mPoint MultiplyFromTnaf(F2mPoint p, sbyte[] u) - { - F2mCurve curve = (F2mCurve)p.Curve; - F2mPoint q = (F2mPoint) curve.Infinity; - 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) - { - q = (F2mPoint)q.SubtractSimple(p); - } - } - return q; - } - - /** - * Computes the <code>[τ]</code>-adic window NAF of an element - * <code>λ</code> of <code><b>Z</b>[τ]</code>. - * @param mu The parameter μ of the elliptic curve. - * @param lambda The element <code>λ</code> of - * <code><b>Z</b>[τ]</code> of which to compute the - * <code>[τ]</code>-adic NAF. - * @param width The window width of the resulting WNAF. - * @param pow2w 2<sup>width</sup>. - * @param tw The auxiliary value <code>t<sub>w</sub></code>. - * @param alpha The <code>α<sub>u</sub></code>'s for the window width. - * @return The <code>[τ]</code>-adic window NAF of - * <code>λ</code>. - */ - public static sbyte[] TauAdicWNaf(sbyte mu, ZTauElement lambda, - sbyte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha) - { - if (!((mu == 1) || (mu == -1))) - throw new ArgumentException("mu must be 1 or -1"); - - BigInteger norm = Norm(mu, lambda); - - // Ceiling of log2 of the norm - int log2Norm = norm.BitLength; - - // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 - int maxLength = log2Norm > 30 ? log2Norm + 4 + width : 34 + width; - - // The array holding the TNAF - sbyte[] u = new sbyte[maxLength]; - - // 2^(width - 1) - BigInteger pow2wMin1 = pow2w.ShiftRight(1); - - // Split lambda into two BigIntegers to simplify calculations - BigInteger r0 = lambda.u; - BigInteger r1 = lambda.v; - int i = 0; - - // while lambda <> (0, 0) - while (!((r0.Equals(BigInteger.Zero))&&(r1.Equals(BigInteger.Zero)))) - { - // if r0 is odd - if (r0.TestBit(0)) - { - // uUnMod = r0 + r1*tw Mod 2^width - BigInteger uUnMod - = r0.Add(r1.Multiply(tw)).Mod(pow2w); - - sbyte uLocal; - // if uUnMod >= 2^(width - 1) - if (uUnMod.CompareTo(pow2wMin1) >= 0) - { - uLocal = (sbyte) uUnMod.Subtract(pow2w).IntValue; - } - else - { - uLocal = (sbyte) uUnMod.IntValue; - } - // uLocal is now in [-2^(width-1), 2^(width-1)-1] - - u[i] = uLocal; - bool s = true; - if (uLocal < 0) - { - s = false; - uLocal = (sbyte)-uLocal; - } - // uLocal is now >= 0 - - if (s) - { - r0 = r0.Subtract(alpha[uLocal].u); - r1 = r1.Subtract(alpha[uLocal].v); - } - else - { - r0 = r0.Add(alpha[uLocal].u); - r1 = r1.Add(alpha[uLocal].v); - } - } - else - { - u[i] = 0; - } - - BigInteger t = r0; - - if (mu == 1) - { - r0 = r1.Add(r0.ShiftRight(1)); - } - else - { - // mu == -1 - r0 = r1.Subtract(r0.ShiftRight(1)); - } - r1 = t.ShiftRight(1).Negate(); - i++; - } - return u; - } - - /** - * Does the precomputation for WTNAF multiplication. - * @param p The <code>ECPoint</code> for which to do the precomputation. - * @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) - { - F2mPoint[] pu; - pu = new F2mPoint[16]; - pu[1] = p; - sbyte[][] alphaTnaf; - if (a == 0) - { - alphaTnaf = Tnaf.Alpha0Tnaf; - } - else - { - // a == 1 - alphaTnaf = Tnaf.Alpha1Tnaf; - } - - int precompLen = alphaTnaf.Length; - for (int i = 3; i < precompLen; i = i + 2) - { - pu[i] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]); - } - - return pu; - } - } + /** + * Class holding methods for point multiplication based on the window + * τ-adic nonadjacent form (WTNAF). The algorithms are based on the + * paper "Improved Algorithms for Arithmetic on Anomalous Binary Curves" + * by Jerome A. Solinas. The paper first appeared in the Proceedings of + * Crypto 1997. + */ + internal class Tnaf + { + private static readonly BigInteger MinusOne = BigInteger.One.Negate(); + private static readonly BigInteger MinusTwo = BigInteger.Two.Negate(); + private static readonly BigInteger MinusThree = BigInteger.Three.Negate(); + private static readonly BigInteger Four = BigInteger.ValueOf(4); + + /** + * The window width of WTNAF. The standard value of 4 is slightly less + * than optimal for running time, but keeps space requirements for + * precomputation low. For typical curves, a value of 5 or 6 results in + * a better running time. When changing this value, the + * <code>α<sub>u</sub></code>'s must be computed differently, see + * e.g. "Guide to Elliptic Curve Cryptography", Darrel Hankerson, + * Alfred Menezes, Scott Vanstone, Springer-Verlag New York Inc., 2004, + * p. 121-122 + */ + public const sbyte Width = 4; + + /** + * 2<sup>4</sup> + */ + public const sbyte Pow2Width = 16; + + /** + * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array + * of <code>ZTauElement</code>s. + */ + public static readonly ZTauElement[] Alpha0 = + { + null, + new ZTauElement(BigInteger.One, BigInteger.Zero), null, + new ZTauElement(MinusThree, MinusOne), null, + new ZTauElement(MinusOne, MinusOne), null, + new ZTauElement(BigInteger.One, MinusOne), null + }; + + /** + * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array + * of TNAFs. + */ + public static readonly sbyte[][] Alpha0Tnaf = + { + null, new sbyte[]{1}, null, new sbyte[]{-1, 0, 1}, null, new sbyte[]{1, 0, 1}, null, new sbyte[]{-1, 0, 0, 1} + }; + + /** + * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array + * of <code>ZTauElement</code>s. + */ + public static readonly ZTauElement[] Alpha1 = + { + null, + new ZTauElement(BigInteger.One, BigInteger.Zero), null, + new ZTauElement(MinusThree, BigInteger.One), null, + new ZTauElement(MinusOne, BigInteger.One), null, + new ZTauElement(BigInteger.One, BigInteger.One), null + }; + + /** + * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array + * of TNAFs. + */ + public static readonly sbyte[][] Alpha1Tnaf = + { + null, new sbyte[]{1}, null, new sbyte[]{-1, 0, 1}, null, new sbyte[]{1, 0, 1}, null, new sbyte[]{-1, 0, 0, -1} + }; + + /** + * Computes the norm of an element <code>λ</code> of + * <code><b>Z</b>[τ]</code>. + * @param mu The parameter <code>μ</code> of the elliptic curve. + * @param lambda The element <code>λ</code> of + * <code><b>Z</b>[τ]</code>. + * @return The norm of <code>λ</code>. + */ + public static BigInteger Norm(sbyte mu, ZTauElement lambda) + { + BigInteger norm; + + // s1 = u^2 + BigInteger s1 = lambda.u.Multiply(lambda.u); + + // s2 = u * v + BigInteger s2 = lambda.u.Multiply(lambda.v); + + // s3 = 2 * v^2 + BigInteger s3 = lambda.v.Multiply(lambda.v).ShiftLeft(1); + + if (mu == 1) + { + norm = s1.Add(s2).Add(s3); + } + else if (mu == -1) + { + norm = s1.Subtract(s2).Add(s3); + } + else + { + throw new ArgumentException("mu must be 1 or -1"); + } + + return norm; + } + + /** + * Computes the norm of an element <code>λ</code> of + * <code><b>R</b>[τ]</code>, where <code>λ = u + vτ</code> + * and <code>u</code> and <code>u</code> are real numbers (elements of + * <code><b>R</b></code>). + * @param mu The parameter <code>μ</code> of the elliptic curve. + * @param u The real part of the element <code>λ</code> of + * <code><b>R</b>[τ]</code>. + * @param v The <code>τ</code>-adic part of the element + * <code>λ</code> of <code><b>R</b>[τ]</code>. + * @return The norm of <code>λ</code>. + */ + public static SimpleBigDecimal Norm(sbyte mu, SimpleBigDecimal u, SimpleBigDecimal v) + { + SimpleBigDecimal norm; + + // s1 = u^2 + SimpleBigDecimal s1 = u.Multiply(u); + + // s2 = u * v + SimpleBigDecimal s2 = u.Multiply(v); + + // s3 = 2 * v^2 + SimpleBigDecimal s3 = v.Multiply(v).ShiftLeft(1); + + if (mu == 1) + { + norm = s1.Add(s2).Add(s3); + } + else if (mu == -1) + { + norm = s1.Subtract(s2).Add(s3); + } + else + { + throw new ArgumentException("mu must be 1 or -1"); + } + + return norm; + } + + /** + * Rounds an element <code>λ</code> of <code><b>R</b>[τ]</code> + * to an element of <code><b>Z</b>[τ]</code>, such that their difference + * has minimal norm. <code>λ</code> is given as + * <code>λ = λ<sub>0</sub> + λ<sub>1</sub>τ</code>. + * @param lambda0 The component <code>λ<sub>0</sub></code>. + * @param lambda1 The component <code>λ<sub>1</sub></code>. + * @param mu The parameter <code>μ</code> of the elliptic curve. Must + * equal 1 or -1. + * @return The rounded element of <code><b>Z</b>[τ]</code>. + * @throws ArgumentException if <code>lambda0</code> and + * <code>lambda1</code> do not have same scale. + */ + public static ZTauElement Round(SimpleBigDecimal lambda0, + SimpleBigDecimal lambda1, sbyte mu) + { + int scale = lambda0.Scale; + if (lambda1.Scale != scale) + throw new ArgumentException("lambda0 and lambda1 do not have same scale"); + + if (!((mu == 1) || (mu == -1))) + throw new ArgumentException("mu must be 1 or -1"); + + BigInteger f0 = lambda0.Round(); + BigInteger f1 = lambda1.Round(); + + SimpleBigDecimal eta0 = lambda0.Subtract(f0); + SimpleBigDecimal eta1 = lambda1.Subtract(f1); + + // eta = 2*eta0 + mu*eta1 + SimpleBigDecimal eta = eta0.Add(eta0); + if (mu == 1) + { + eta = eta.Add(eta1); + } + else + { + // mu == -1 + eta = eta.Subtract(eta1); + } + + // check1 = eta0 - 3*mu*eta1 + // check2 = eta0 + 4*mu*eta1 + SimpleBigDecimal threeEta1 = eta1.Add(eta1).Add(eta1); + SimpleBigDecimal fourEta1 = threeEta1.Add(eta1); + SimpleBigDecimal check1; + SimpleBigDecimal check2; + if (mu == 1) + { + check1 = eta0.Subtract(threeEta1); + check2 = eta0.Add(fourEta1); + } + else + { + // mu == -1 + check1 = eta0.Add(threeEta1); + check2 = eta0.Subtract(fourEta1); + } + + sbyte h0 = 0; + sbyte h1 = 0; + + // if eta >= 1 + if (eta.CompareTo(BigInteger.One) >= 0) + { + if (check1.CompareTo(MinusOne) < 0) + { + h1 = mu; + } + else + { + h0 = 1; + } + } + else + { + // eta < 1 + if (check2.CompareTo(BigInteger.Two) >= 0) + { + h1 = mu; + } + } + + // if eta < -1 + if (eta.CompareTo(MinusOne) < 0) + { + if (check1.CompareTo(BigInteger.One) >= 0) + { + h1 = (sbyte)-mu; + } + else + { + h0 = -1; + } + } + else + { + // eta >= -1 + if (check2.CompareTo(MinusTwo) < 0) + { + h1 = (sbyte)-mu; + } + } + + BigInteger q0 = f0.Add(BigInteger.ValueOf(h0)); + BigInteger q1 = f1.Add(BigInteger.ValueOf(h1)); + return new ZTauElement(q0, q1); + } + + /** + * Approximate division by <code>n</code>. For an integer + * <code>k</code>, the value <code>λ = s k / n</code> is + * computed to <code>c</code> bits of accuracy. + * @param k The parameter <code>k</code>. + * @param s The curve parameter <code>s<sub>0</sub></code> or + * <code>s<sub>1</sub></code>. + * @param vm The Lucas Sequence element <code>V<sub>m</sub></code>. + * @param a The parameter <code>a</code> of the elliptic curve. + * @param m The bit length of the finite field + * <code><b>F</b><sub>m</sub></code>. + * @param c The number of bits of accuracy, i.e. the scale of the returned + * <code>SimpleBigDecimal</code>. + * @return The value <code>λ = s k / n</code> computed to + * <code>c</code> bits of accuracy. + */ + public static SimpleBigDecimal ApproximateDivisionByN(BigInteger k, + BigInteger s, BigInteger vm, sbyte a, int m, int c) + { + int _k = (m + 5)/2 + c; + BigInteger ns = k.ShiftRight(m - _k - 2 + a); + + BigInteger gs = s.Multiply(ns); + + BigInteger hs = gs.ShiftRight(m); + + BigInteger js = vm.Multiply(hs); + + BigInteger gsPlusJs = gs.Add(js); + BigInteger ls = gsPlusJs.ShiftRight(_k-c); + if (gsPlusJs.TestBit(_k-c-1)) + { + // round up + ls = ls.Add(BigInteger.One); + } + + return new SimpleBigDecimal(ls, c); + } + + /** + * Computes the <code>τ</code>-adic NAF (non-adjacent form) of an + * element <code>λ</code> of <code><b>Z</b>[τ]</code>. + * @param mu The parameter <code>μ</code> of the elliptic curve. + * @param lambda The element <code>λ</code> of + * <code><b>Z</b>[τ]</code>. + * @return The <code>τ</code>-adic NAF of <code>λ</code>. + */ + public static sbyte[] TauAdicNaf(sbyte mu, ZTauElement lambda) + { + if (!((mu == 1) || (mu == -1))) + throw new ArgumentException("mu must be 1 or -1"); + + BigInteger norm = Norm(mu, lambda); + + // Ceiling of log2 of the norm + int log2Norm = norm.BitLength; + + // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 + int maxLength = log2Norm > 30 ? log2Norm + 4 : 34; + + // The array holding the TNAF + sbyte[] u = new sbyte[maxLength]; + int i = 0; + + // The actual length of the TNAF + int length = 0; + + BigInteger r0 = lambda.u; + BigInteger r1 = lambda.v; + + while(!((r0.Equals(BigInteger.Zero)) && (r1.Equals(BigInteger.Zero)))) + { + // If r0 is odd + if (r0.TestBit(0)) + { + u[i] = (sbyte) BigInteger.Two.Subtract((r0.Subtract(r1.ShiftLeft(1))).Mod(Four)).IntValue; + + // r0 = r0 - u[i] + if (u[i] == 1) + { + r0 = r0.ClearBit(0); + } + else + { + // u[i] == -1 + r0 = r0.Add(BigInteger.One); + } + length = i; + } + else + { + u[i] = 0; + } + + BigInteger t = r0; + BigInteger s = r0.ShiftRight(1); + if (mu == 1) + { + r0 = r1.Add(s); + } + else + { + // mu == -1 + r0 = r1.Subtract(s); + } + + r1 = t.ShiftRight(1).Negate(); + i++; + } + + length++; + + // Reduce the TNAF array to its actual length + sbyte[] tnaf = new sbyte[length]; + Array.Copy(u, 0, tnaf, 0, length); + return tnaf; + } + + /** + * Applies the operation <code>τ()</code> to an + * <code>F2mPoint</code>. + * @param p The F2mPoint to which <code>τ()</code> is applied. + * @return <code>τ(p)</code> + */ + public static F2mPoint Tau(F2mPoint p) + { + return p.Tau(); + } + + /** + * Returns the parameter <code>μ</code> of the elliptic curve. + * @param curve The elliptic curve from which to obtain <code>μ</code>. + * The curve must be a Koblitz curve, i.e. <code>a</code> Equals + * <code>0</code> or <code>1</code> and <code>b</code> Equals + * <code>1</code>. + * @return <code>μ</code> of the elliptic curve. + * @throws ArgumentException if the given ECCurve is not a Koblitz + * curve. + */ + public static sbyte GetMu(F2mCurve curve) + { + BigInteger a = curve.A.ToBigInteger(); + + sbyte mu; + if (a.SignValue == 0) + { + mu = -1; + } + else if (a.Equals(BigInteger.One)) + { + mu = 1; + } + else + { + throw new ArgumentException("No Koblitz curve (ABC), TNAF multiplication not possible"); + } + return mu; + } + + /** + * 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 + * <code>V<sub>k</sub></code>. + * @param mu The parameter <code>μ</code> of the elliptic curve. + * @param k The index of the second element of the Lucas Sequence to be + * returned. + * @param doV If set to true, computes <code>V<sub>k-1</sub></code> and + * <code>V<sub>k</sub></code>, otherwise <code>U<sub>k-1</sub></code> and + * <code>U<sub>k</sub></code>. + * @return An array with 2 elements, containing <code>U<sub>k-1</sub></code> + * and <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> + * and <code>V<sub>k</sub></code>. + */ + public static BigInteger[] GetLucas(sbyte mu, int k, bool doV) + { + if (!(mu == 1 || mu == -1)) + throw new ArgumentException("mu must be 1 or -1"); + + BigInteger u0; + BigInteger u1; + BigInteger u2; + + if (doV) + { + u0 = BigInteger.Two; + u1 = BigInteger.ValueOf(mu); + } + else + { + u0 = BigInteger.Zero; + u1 = BigInteger.One; + } + + for (int i = 1; i < k; i++) + { + // u2 = mu*u1 - 2*u0; + BigInteger s = null; + if (mu == 1) + { + s = u1; + } + else + { + // mu == -1 + s = u1.Negate(); + } + + u2 = s.Subtract(u0.ShiftLeft(1)); + u0 = u1; + u1 = u2; + // System.out.println(i + ": " + u2); + // System.out.println(); + } + + BigInteger[] retVal = {u0, u1}; + return retVal; + } + + /** + * Computes the auxiliary value <code>t<sub>w</sub></code>. If the width is + * 4, then for <code>mu = 1</code>, <code>t<sub>w</sub> = 6</code> and for + * <code>mu = -1</code>, <code>t<sub>w</sub> = 10</code> + * @param mu The parameter <code>μ</code> of the elliptic curve. + * @param w The window width of the WTNAF. + * @return the auxiliary value <code>t<sub>w</sub></code> + */ + public static BigInteger GetTw(sbyte mu, int w) + { + if (w == 4) + { + if (mu == 1) + { + return BigInteger.ValueOf(6); + } + else + { + // mu == -1 + return BigInteger.ValueOf(10); + } + } + else + { + // For w <> 4, the values must be computed + BigInteger[] us = GetLucas(mu, w, false); + BigInteger twoToW = BigInteger.Zero.SetBit(w); + BigInteger u1invert = us[1].ModInverse(twoToW); + BigInteger tw; + tw = BigInteger.Two.Multiply(us[0]).Multiply(u1invert).Mod(twoToW); + //System.out.println("mu = " + mu); + //System.out.println("tw = " + tw); + return tw; + } + } + + /** + * Computes the auxiliary values <code>s<sub>0</sub></code> and + * <code>s<sub>1</sub></code> used for partial modular reduction. + * @param curve The elliptic curve for which to compute + * <code>s<sub>0</sub></code> and <code>s<sub>1</sub></code>. + * @throws ArgumentException if <code>curve</code> is not a + * Koblitz curve (Anomalous Binary Curve, ABC). + */ + public static BigInteger[] GetSi(F2mCurve curve) + { + if (!curve.IsKoblitz) + throw new ArgumentException("si is defined for Koblitz curves only"); + + int m = curve.M; + int a = curve.A.ToBigInteger().IntValue; + sbyte mu = curve.GetMu(); + int h = curve.H.IntValue; + 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"); + } + + BigInteger[] si = new BigInteger[2]; + + if (h == 2) + { + si[0] = dividend0.ShiftRight(1); + si[1] = dividend1.ShiftRight(1).Negate(); + } + else if (h == 4) + { + si[0] = dividend0.ShiftRight(2); + si[1] = dividend1.ShiftRight(2).Negate(); + } + else + { + throw new ArgumentException("h (Cofactor) must be 2 or 4"); + } + + return si; + } + + /** + * Partial modular reduction modulo + * <code>(τ<sup>m</sup> - 1)/(τ - 1)</code>. + * @param k The integer to be reduced. + * @param m The bitlength of the underlying finite field. + * @param a The parameter <code>a</code> of the elliptic curve. + * @param s The auxiliary values <code>s<sub>0</sub></code> and + * <code>s<sub>1</sub></code>. + * @param mu The parameter μ of the elliptic curve. + * @param c The precision (number of bits of accuracy) of the partial + * modular reduction. + * @return <code>ρ := k partmod (τ<sup>m</sup> - 1)/(τ - 1)</code> + */ + public static ZTauElement PartModReduction(BigInteger k, int m, sbyte a, + BigInteger[] s, sbyte mu, sbyte c) + { + // d0 = s[0] + mu*s[1]; mu is either 1 or -1 + BigInteger d0; + if (mu == 1) + { + d0 = s[0].Add(s[1]); + } + else + { + d0 = s[0].Subtract(s[1]); + } + + BigInteger[] v = GetLucas(mu, m, true); + BigInteger vm = v[1]; + + SimpleBigDecimal lambda0 = ApproximateDivisionByN( + k, s[0], vm, a, m, c); + + SimpleBigDecimal lambda1 = ApproximateDivisionByN( + k, s[1], vm, a, m, c); + + ZTauElement q = Round(lambda0, lambda1, mu); + + // r0 = n - d0*q0 - 2*s1*q1 + BigInteger r0 = k.Subtract(d0.Multiply(q.u)).Subtract( + BigInteger.ValueOf(2).Multiply(s[1]).Multiply(q.v)); + + // r1 = s1*q0 - s0*q1 + BigInteger r1 = s[1].Multiply(q.u).Subtract(s[0].Multiply(q.v)); + + return new ZTauElement(r0, r1); + } + + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * by a <code>BigInteger</code> using the reduced <code>τ</code>-adic + * NAF (RTNAF) method. + * @param p The F2mPoint 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) + { + F2mCurve curve = (F2mCurve) p.Curve; + int m = curve.M; + sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; + sbyte mu = curve.GetMu(); + BigInteger[] s = curve.GetSi(); + ZTauElement rho = PartModReduction(k, m, a, s, mu, (sbyte)10); + + return MultiplyTnaf(p, rho); + } + + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * 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 lambda The element <code>λ</code> of + * <code><b>Z</b>[τ]</code>. + * @return <code>λ * p</code> + */ + public static F2mPoint MultiplyTnaf(F2mPoint p, ZTauElement lambda) + { + F2mCurve curve = (F2mCurve)p.Curve; + sbyte mu = curve.GetMu(); + sbyte[] u = TauAdicNaf(mu, lambda); + + F2mPoint q = MultiplyFromTnaf(p, u); + + return q; + } + + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * 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 u The the TNAF of <code>λ</code>.. + * @return <code>λ * p</code> + */ + public static F2mPoint MultiplyFromTnaf(F2mPoint p, sbyte[] u) + { + F2mCurve curve = (F2mCurve)p.Curve; + F2mPoint q = (F2mPoint) curve.Infinity; + 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) + { + q = (F2mPoint)q.SubtractSimple(p); + } + } + return q; + } + + /** + * Computes the <code>[τ]</code>-adic window NAF of an element + * <code>λ</code> of <code><b>Z</b>[τ]</code>. + * @param mu The parameter μ of the elliptic curve. + * @param lambda The element <code>λ</code> of + * <code><b>Z</b>[τ]</code> of which to compute the + * <code>[τ]</code>-adic NAF. + * @param width The window width of the resulting WNAF. + * @param pow2w 2<sup>width</sup>. + * @param tw The auxiliary value <code>t<sub>w</sub></code>. + * @param alpha The <code>α<sub>u</sub></code>'s for the window width. + * @return The <code>[τ]</code>-adic window NAF of + * <code>λ</code>. + */ + public static sbyte[] TauAdicWNaf(sbyte mu, ZTauElement lambda, + sbyte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha) + { + if (!((mu == 1) || (mu == -1))) + throw new ArgumentException("mu must be 1 or -1"); + + BigInteger norm = Norm(mu, lambda); + + // Ceiling of log2 of the norm + int log2Norm = norm.BitLength; + + // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 + int maxLength = log2Norm > 30 ? log2Norm + 4 + width : 34 + width; + + // The array holding the TNAF + sbyte[] u = new sbyte[maxLength]; + + // 2^(width - 1) + BigInteger pow2wMin1 = pow2w.ShiftRight(1); + + // Split lambda into two BigIntegers to simplify calculations + BigInteger r0 = lambda.u; + BigInteger r1 = lambda.v; + int i = 0; + + // while lambda <> (0, 0) + while (!((r0.Equals(BigInteger.Zero))&&(r1.Equals(BigInteger.Zero)))) + { + // if r0 is odd + if (r0.TestBit(0)) + { + // uUnMod = r0 + r1*tw Mod 2^width + BigInteger uUnMod + = r0.Add(r1.Multiply(tw)).Mod(pow2w); + + sbyte uLocal; + // if uUnMod >= 2^(width - 1) + if (uUnMod.CompareTo(pow2wMin1) >= 0) + { + uLocal = (sbyte) uUnMod.Subtract(pow2w).IntValue; + } + else + { + uLocal = (sbyte) uUnMod.IntValue; + } + // uLocal is now in [-2^(width-1), 2^(width-1)-1] + + u[i] = uLocal; + bool s = true; + if (uLocal < 0) + { + s = false; + uLocal = (sbyte)-uLocal; + } + // uLocal is now >= 0 + + if (s) + { + r0 = r0.Subtract(alpha[uLocal].u); + r1 = r1.Subtract(alpha[uLocal].v); + } + else + { + r0 = r0.Add(alpha[uLocal].u); + r1 = r1.Add(alpha[uLocal].v); + } + } + else + { + u[i] = 0; + } + + BigInteger t = r0; + + if (mu == 1) + { + r0 = r1.Add(r0.ShiftRight(1)); + } + else + { + // mu == -1 + r0 = r1.Subtract(r0.ShiftRight(1)); + } + r1 = t.ShiftRight(1).Negate(); + i++; + } + return u; + } + + /** + * Does the precomputation for WTNAF multiplication. + * @param p The <code>ECPoint</code> for which to do the precomputation. + * @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) + { + F2mPoint[] pu; + pu = new F2mPoint[16]; + pu[1] = p; + sbyte[][] alphaTnaf; + if (a == 0) + { + alphaTnaf = Tnaf.Alpha0Tnaf; + } + else + { + // a == 1 + alphaTnaf = Tnaf.Alpha1Tnaf; + } + + int precompLen = alphaTnaf.Length; + for (int i = 3; i < precompLen; i = i + 2) + { + pu[i] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]); + } + + return pu; + } + } } |