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 * αu'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; /** * 24 */ public const sbyte Pow2Width = 16; /** * The αu's for a=0 as an array * of ZTauElements. */ 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 αu's for a=0 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 αu's for a=1 as an array * of ZTauElements. */ 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 αu's for a=1 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 λ of * Z[τ]. * @param mu The parameter μ of the elliptic curve. * @param lambda The element λ of * Z[τ]. * @return The norm of λ. */ 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 λ of * R[τ], where λ = u + vτ * and u and u are real numbers (elements of * R). * @param mu The parameter μ of the elliptic curve. * @param u The real part of the element λ of * R[τ]. * @param v The τ-adic part of the element * λ of R[τ]. * @return The norm of λ. */ 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 λ of R[τ] * to an element of Z[τ], such that their difference * has minimal norm. λ is given as * λ = λ0 + λ1τ. * @param lambda0 The component λ0. * @param lambda1 The component λ1. * @param mu The parameter μ of the elliptic curve. Must * equal 1 or -1. * @return The rounded element of Z[τ]. * @throws ArgumentException if lambda0 and * lambda1 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 n. For an integer * k, the value λ = s k / n is * computed to c bits of accuracy. * @param k The parameter k. * @param s The curve parameter s0 or * s1. * @param vm The Lucas Sequence element Vm. * @param a The parameter a of the elliptic curve. * @param m The bit length of the finite field * Fm. * @param c The number of bits of accuracy, i.e. the scale of the returned * SimpleBigDecimal. * @return The value λ = s k / n computed to * c 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 τ-adic NAF (non-adjacent form) of an * element λ of Z[τ]. * @param mu The parameter μ of the elliptic curve. * @param lambda The element λ of * Z[τ]. * @return The τ-adic NAF of λ. */ 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 τ() to an * AbstractF2mPoint. * @param p The AbstractF2mPoint to which τ() is applied. * @return τ(p) */ public static AbstractF2mPoint Tau(AbstractF2mPoint p) { return p.Tau(); } /** * Returns the parameter μ of the elliptic curve. * @param curve The elliptic curve from which to obtain μ. * The curve must be a Koblitz curve, i.e. a Equals * 0 or 1 and b Equals * 1. * @return μ of the elliptic curve. * @throws ArgumentException if the given ECCurve is not a Koblitz * curve. */ public static sbyte GetMu(AbstractF2mCurve 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; } 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 Uk-1 and * Uk or Vk-1 and * Vk. * @param mu The parameter μ 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 Vk-1 and * Vk, otherwise Uk-1 and * Uk. * @return An array with 2 elements, containing Uk-1 * and Uk or Vk-1 * and Vk. */ 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 tw. If the width is * 4, then for mu = 1, tw = 6 and for * mu = -1, tw = 10 * @param mu The parameter μ of the elliptic curve. * @param w The window width of the WTNAF. * @return the auxiliary value tw */ 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 s0 and * s1 used for partial modular reduction. * @param curve The elliptic curve for which to compute * s0 and s1. * @throws ArgumentException if curve is not a * Koblitz curve (Anomalous Binary Curve, ABC). */ public static BigInteger[] GetSi(AbstractF2mCurve curve) { if (!curve.IsKoblitz) throw new ArgumentException("si is defined for Koblitz curves only"); int m = curve.FieldSize; int a = curve.A.ToBigInteger().IntValue; sbyte mu = GetMu(a); int shifts = GetShiftsForCofactor(curve.Cofactor); int index = m + 3 - a; BigInteger[] ui = GetLucas(mu, index, false); if (mu == 1) { ui[0] = ui[0].Negate(); ui[1] = ui[1].Negate(); } BigInteger dividend0 = BigInteger.One.Add(ui[1]).ShiftRight(shifts); BigInteger dividend1 = BigInteger.One.Add(ui[0]).ShiftRight(shifts).Negate(); 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) { ui[0] = ui[0].Negate(); ui[1] = ui[1].Negate(); } 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) { int hi = h.IntValue; if (hi == 2) return 1; if (hi == 4) return 2; } throw new ArgumentException("h (Cofactor) must be 2 or 4"); } /** * Partial modular reduction modulo * m - 1)/(τ - 1). * @param k The integer to be reduced. * @param m The bitlength of the underlying finite field. * @param a The parameter a of the elliptic curve. * @param s The auxiliary values s0 and * s1. * @param mu The parameter μ of the elliptic curve. * @param c The precision (number of bits of accuracy) of the partial * modular reduction. * @return ρ := k partmod (τm - 1)/(τ - 1) */ 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.AbstractF2mPoint AbstractF2mPoint} * by a BigInteger using the reduced τ-adic * NAF (RTNAF) method. * @param p The AbstractF2mPoint to Multiply. * @param k The BigInteger by which to Multiply p. * @return k * p */ public static AbstractF2mPoint MultiplyRTnaf(AbstractF2mPoint p, BigInteger k) { 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, (sbyte)a, s, mu, (sbyte)10); return MultiplyTnaf(p, rho); } /** * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element λ of Z[τ] * using the τ-adic NAF (TNAF) method. * @param p The AbstractF2mPoint to Multiply. * @param lambda The element λ of * Z[τ]. * @return λ * p */ public static AbstractF2mPoint MultiplyTnaf(AbstractF2mPoint p, ZTauElement lambda) { AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve; sbyte mu = GetMu(curve.A); sbyte[] u = TauAdicNaf(mu, lambda); AbstractF2mPoint q = MultiplyFromTnaf(p, u); return q; } /** * Multiplies a {@link org.bouncycastle.math.ec.AbstractF2mPoint AbstractF2mPoint} * by an element λ of Z[τ] * using the τ-adic NAF (TNAF) method, given the TNAF * of λ. * @param p The AbstractF2mPoint to Multiply. * @param u The the TNAF of λ.. * @return λ * p */ public static AbstractF2mPoint MultiplyFromTnaf(AbstractF2mPoint p, sbyte[] u) { 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--) { ++tauCount; sbyte ui = u[i]; if (ui != 0) { 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; } /** * Computes the [τ]-adic window NAF of an element * λ of Z[τ]. * @param mu The parameter μ of the elliptic curve. * @param lambda The element λ of * Z[τ] of which to compute the * [τ]-adic NAF. * @param width The window width of the resulting WNAF. * @param pow2w 2width. * @param tw The auxiliary value tw. * @param alpha The αu's for the window width. * @return The [τ]-adic window NAF of * λ. */ 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 ECPoint for which to do the precomputation. * @param a The parameter a of the elliptic curve. * @return The precomputation array for p. */ public static AbstractF2mPoint[] GetPreComp(AbstractF2mPoint p, sbyte a) { sbyte[][] alphaTnaf = (a == 0) ? Tnaf.Alpha0Tnaf : Tnaf.Alpha1Tnaf; AbstractF2mPoint[] pu = new AbstractF2mPoint[(uint)(alphaTnaf.Length + 1) >> 1]; pu[0] = p; uint precompLen = (uint)alphaTnaf.Length; for (uint i = 3; i < precompLen; i += 2) { pu[i >> 1] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]); } p.Curve.NormalizeAll(pu); return pu; } } }