Class Tnaf


  • class Tnaf
    extends java.lang.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 Summary

      Fields 
      Modifier and Type Field Description
      static ZTauElement[] alpha0
      The αu's for a=0 as an array of ZTauElements.
      static byte[][] alpha0Tnaf
      The αu's for a=0 as an array of TNAFs.
      static ZTauElement[] alpha1
      The αu's for a=1 as an array of ZTauElements.
      static byte[][] alpha1Tnaf
      The αu's for a=1 as an array of TNAFs.
      private static java.math.BigInteger MINUS_ONE  
      private static java.math.BigInteger MINUS_THREE  
      private static java.math.BigInteger MINUS_TWO  
      static byte POW_2_WIDTH
      24
      static byte WIDTH
      The window width of WTNAF.
    • Constructor Summary

      Constructors 
      Constructor Description
      Tnaf()  
    • Field Detail

      • MINUS_ONE

        private static final java.math.BigInteger MINUS_ONE
      • MINUS_TWO

        private static final java.math.BigInteger MINUS_TWO
      • MINUS_THREE

        private static final java.math.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:
        Constant Field Values
      • 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 Detail

      • Tnaf

        Tnaf()
    • Method Detail

      • norm

        public static java.math.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:
        java.lang.IllegalArgumentException - if lambda0 and lambda1 do not have same scale.
      • approximateDivisionByN

        public static SimpleBigDecimal approximateDivisionByN​(java.math.BigInteger k,
                                                              java.math.BigInteger s,
                                                              java.math.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:
        java.lang.IllegalArgumentException - if the given ECCurve is not a Koblitz curve.
      • getLucas

        public static java.math.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 java.math.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 java.math.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:
        java.lang.IllegalArgumentException - if curve is not a Koblitz curve (Anomalous Binary Curve, ABC).
      • partModReduction

        public static ZTauElement partModReduction​(java.math.BigInteger k,
                                                   int m,
                                                   byte a,
                                                   java.math.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,
                                                java.math.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,
                                         java.math.BigInteger pow2w,
                                         java.math.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.