Class Tnaf

java.lang.Object
org.gudy.bouncycastle.math.ec.Tnaf
class Tnaf extends Object
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.

  • Field Details

    • MINUS_ONE

      private static final BigInteger MINUS_ONE

    • MINUS_TWO

      private static final BigInteger MINUS_TWO

    • MINUS_THREE

      private static final BigInteger MINUS_THREE

    • WIDTH

      public static final byte WIDTH
      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
      See Also:

    • POW_2_WIDTH

      public static final byte POW_2_WIDTH
      24
      See Also:

    • alpha0

      public static final ZTauElement[] alpha0
      The αu's for a=0 as an array of ZTauElements.

    • alpha0Tnaf

      public static final byte[][] alpha0Tnaf
      The αu's for a=0 as an array of TNAFs.

    • alpha1

      public static final ZTauElement[] alpha1
      The αu's for a=1 as an array of ZTauElements.

    • alpha1Tnaf

      public static final byte[][] alpha1Tnaf
      The αu's for a=1 as an array of TNAFs.

  • Constructor Details

    • Tnaf

      Tnaf()

  • Method Details

    • norm

      public static BigInteger norm(byte mu, ZTauElement lambda)
      Computes the norm of an element λ of Z[τ].
      Parameters:
      mu - The parameter μ of the elliptic curve.
      lambda - The element λ of Z[τ].
      Returns:
      The norm of λ.

    • norm

      public static SimpleBigDecimal norm(byte mu, SimpleBigDecimal u, SimpleBigDecimal v)
      Computes the norm of an element λ of R[τ], where λ = u + vτ and u and u are real numbers (elements of R).
      Parameters:
      mu - The parameter μ of the elliptic curve.
      u - The real part of the element λ of R[τ].
      v - The τ-adic part of the element λ of R[τ].
      Returns:
      The norm of λ.

    • round

      public static ZTauElement round(SimpleBigDecimal lambda0, SimpleBigDecimal lambda1, byte mu)
      Rounds an element λ of R[τ] to an element of Z[τ], such that their difference has minimal norm. λ is given as λ = λ0 + λ1τ.
      Parameters:
      lambda0 - The component λ0.
      lambda1 - The component λ1.
      mu - The parameter μ of the elliptic curve. Must equal 1 or -1.
      Returns:
      The rounded element of Z[τ].
      Throws:
      IllegalArgumentException - if lambda0 and lambda1 do not have same scale.

    • approximateDivisionByN

      public static SimpleBigDecimal approximateDivisionByN(BigInteger k, BigInteger s, BigInteger vm, byte a, int m, int c)
      Approximate division by n. For an integer k, the value λ = s k / n is computed to c bits of accuracy.
      Parameters:
      k - The parameter k.
      s - The curve parameter s0 or s1.
      vm - The Lucas Sequence element Vm.
      a - The parameter a of the elliptic curve.
      m - The bit length of the finite field Fm.
      c - The number of bits of accuracy, i.e. the scale of the returned SimpleBigDecimal.
      Returns:
      The value λ = s k / n computed to c bits of accuracy.

    • tauAdicNaf

      public static byte[] tauAdicNaf(byte mu, ZTauElement lambda)
      Computes the τ-adic NAF (non-adjacent form) of an element λ of Z[τ].
      Parameters:
      mu - The parameter μ of the elliptic curve.
      lambda - The element λ of Z[τ].
      Returns:
      The τ-adic NAF of λ.

    • tau

      public static ECPoint.F2m tau(ECPoint.F2m p)
      Applies the operation τ() to an ECPoint.F2m.
      Parameters:
      p - The ECPoint.F2m to which τ() is applied.
      Returns:
      τ(p)

    • getMu

      public static byte getMu(ECCurve.F2m curve)
      Returns the parameter μ of the elliptic curve.
      Parameters:
      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.
      Returns:
      μ of the elliptic curve.
      Throws:
      IllegalArgumentException - if the given ECCurve is not a Koblitz curve.

    • getLucas

      public static BigInteger[] getLucas(byte mu, int k, boolean doV)
      Calculates the Lucas Sequence elements Uk-1 and Uk or Vk-1 and Vk.
      Parameters:
      mu - The parameter μ of the elliptic curve.
      k - The index of the second element of the Lucas Sequence to be returned.
      doV - If set to true, computes Vk-1 and Vk, otherwise Uk-1 and Uk.
      Returns:
      An array with 2 elements, containing Uk-1 and Uk or Vk-1 and Vk.

    • getTw

      public static BigInteger getTw(byte mu, int w)
      Computes the auxiliary value tw. If the width is 4, then for mu = 1, tw = 6 and for mu = -1, tw = 10
      Parameters:
      mu - The parameter μ of the elliptic curve.
      w - The window width of the WTNAF.
      Returns:
      the auxiliary value tw

    • getSi

      public static BigInteger[] getSi(ECCurve.F2m curve)
      Computes the auxiliary values s0 and s1 used for partial modular reduction.
      Parameters:
      curve - The elliptic curve for which to compute s0 and s1.
      Throws:
      IllegalArgumentException - if curve is not a Koblitz curve (Anomalous Binary Curve, ABC).

    • partModReduction

      public static ZTauElement partModReduction(BigInteger k, int m, byte a, BigInteger[] s, byte mu, byte c)
      Partial modular reduction modulo (τm - 1)/(τ - 1).
      Parameters:
      k - The integer to be reduced.
      m - The bitlength of the underlying finite field.
      a - The parameter a of the elliptic curve.
      s - The auxiliary values s0 and s1.
      mu - The parameter μ of the elliptic curve.
      c - The precision (number of bits of accuracy) of the partial modular reduction.
      Returns:
      ρ := k partmod (τm - 1)/(τ - 1)

    • multiplyRTnaf

      public static ECPoint.F2m multiplyRTnaf(ECPoint.F2m p, BigInteger k)
      Multiplies a ECPoint.F2m by a BigInteger using the reduced τ-adic NAF (RTNAF) method.
      Parameters:
      p - The ECPoint.F2m to multiply.
      k - The BigInteger by which to multiply p.
      Returns:
      k * p

    • multiplyTnaf

      public static ECPoint.F2m multiplyTnaf(ECPoint.F2m p, ZTauElement lambda)
      Multiplies a ECPoint.F2m by an element λ of Z[τ] using the τ-adic NAF (TNAF) method.
      Parameters:
      p - The ECPoint.F2m to multiply.
      lambda - The element λ of Z[τ].
      Returns:
      λ * p

    • multiplyFromTnaf

      public static ECPoint.F2m multiplyFromTnaf(ECPoint.F2m p, byte[] u)
      Multiplies a ECPoint.F2m by an element λ of Z[τ] using the τ-adic NAF (TNAF) method, given the TNAF of λ.
      Parameters:
      p - The ECPoint.F2m to multiply.
      u - The the TNAF of λ..
      Returns:
      λ * p

    • tauAdicWNaf

      public static byte[] tauAdicWNaf(byte mu, ZTauElement lambda, byte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha)
      Computes the [τ]-adic window NAF of an element λ of Z[τ].
      Parameters:
      mu - The parameter μ of the elliptic curve.
      lambda - The element λ of Z[τ] of which to compute the [τ]-adic NAF.
      width - The window width of the resulting WNAF.
      pow2w - 2width.
      tw - The auxiliary value tw.
      alpha - The αu's for the window width.
      Returns:
      The [τ]-adic window NAF of λ.

    • getPreComp

      public static ECPoint.F2m[] getPreComp(ECPoint.F2m p, byte a)
      Does the precomputation for WTNAF multiplication.
      Parameters:
      p - The ECPoint for which to do the precomputation.
      a - The parameter a of the elliptic curve.
      Returns:
      The precomputation array for p.