tnaf.java

kmlnjlkj nlkjlkjkljl okopokipoipo oipipipo i

        }
        else if (a.equals(ECConstants.ONE))
        {
            mu = 1;
        }
        else
        {
            throw new IllegalArgumentException("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>&mu;</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(byte mu, int k, boolean doV)
    {
        if (!((mu == 1) || (mu == -1)))
        {
            throw new IllegalArgumentException("mu must be 1 or -1");
        }

        BigInteger u0;
        BigInteger u1;
        BigInteger u2;

        if (doV)
        {
            u0 = ECConstants.TWO;
            u1 = BigInteger.valueOf(mu);
        }
        else
        {
            u0 = ECConstants.ZERO;
            u1 = ECConstants.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>&mu;</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(byte 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 = ECConstants.ZERO.setBit(w);
            BigInteger u1invert = us[1].modInverse(twoToW);
            BigInteger tw;
            tw = ECConstants.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 IllegalArgumentException if <code>curve</code> is not a
     * Koblitz curve (Anomalous Binary Curve, ABC).
     */
    public static BigInteger[] getSi(ECCurve.F2m curve)
    {
        if (!curve.isKoblitz())
        {
            throw new IllegalArgumentException("si is defined for Koblitz curves only");
        }

        int m = curve.getM();
        int a = curve.getA().toBigInteger().intValue();
        byte mu = curve.getMu();
        int h = curve.getH().intValue();
        int index = m + 3 - a;
        BigInteger[] ui = getLucas(mu, index, false);

        BigInteger dividend0;
        BigInteger dividend1;
        if (mu == 1)
        {
            dividend0 = ECConstants.ONE.subtract(ui[1]);
            dividend1 = ECConstants.ONE.subtract(ui[0]);
        }
        else if (mu == -1)
        {
            dividend0 = ECConstants.ONE.add(ui[1]);
            dividend1 = ECConstants.ONE.add(ui[0]);
        }
        else
        {
            throw new IllegalArgumentException("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 IllegalArgumentException("h (Cofactor) must be 2 or 4");
        }

        return si;
    }

    /**
     * Partial modular reduction modulo
     * <code>(&tau;<sup>m</sup> - 1)/(&tau; - 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 &mu; of the elliptic curve.
     * @param c The precision (number of bits of accuracy) of the partial
     * modular reduction.
     * @return <code>&rho; := k partmod (&tau;<sup>m</sup> - 1)/(&tau; - 1)</code>
     */
    public static ZTauElement partModReduction(BigInteger k, int m, byte a,
            BigInteger[] s, byte mu, byte 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.ECPoint.F2m ECPoint.F2m}
     * by a <code>BigInteger</code> using the reduced <code>&tau;</code>-adic
     * NAF (RTNAF) method.
     * @param p The ECPoint.F2m to multiply.
     * @param k The <code>BigInteger</code> by which to multiply <code>p</code>.
     * @return <code>k * p</code>
     */
    public static ECPoint.F2m multiplyRTnaf(ECPoint.F2m p, BigInteger k)
    {
        ECCurve.F2m curve = (ECCurve.F2m) p.getCurve();
        int m = curve.getM();
        byte a = (byte) curve.getA().toBigInteger().intValue();
        byte mu = curve.getMu();
        BigInteger[] s = curve.getSi();
        ZTauElement rho = partModReduction(k, m, a, s, mu, (byte)10);

        return multiplyTnaf(p, rho);
    }

    /**
     * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m}
     * by an element <code>&lambda;</code> of <code><b>Z</b>[&tau;]</code>
     * using the <code>&tau;</code>-adic NAF (TNAF) method.
     * @param p The ECPoint.F2m to multiply.
     * @param lambda The element <code>&lambda;</code> of
     * <code><b>Z</b>[&tau;]</code>.
     * @return <code>&lambda; * p</code>
     */
    public static ECPoint.F2m multiplyTnaf(ECPoint.F2m p, ZTauElement lambda)
    {
        ECCurve.F2m curve = (ECCurve.F2m)p.getCurve();
        byte mu = curve.getMu();
        byte[] u = tauAdicNaf(mu, lambda);

        ECPoint.F2m q = multiplyFromTnaf(p, u);

        return q;
    }

    /**
    * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m}
    * by an element <code>&lambda;</code> of <code><b>Z</b>[&tau;]</code>
    * using the <code>&tau;</code>-adic NAF (TNAF) method, given the TNAF
    * of <code>&lambda;</code>.
    * @param p The ECPoint.F2m to multiply.
    * @param u The the TNAF of <code>&lambda;</code>..
    * @return <code>&lambda; * p</code>
    */
    public static ECPoint.F2m multiplyFromTnaf(ECPoint.F2m p, byte[] u)
    {
        ECCurve.F2m curve = (ECCurve.F2m)p.getCurve();
        ECPoint.F2m q = (ECPoint.F2m) curve.getInfinity();
        for (int i = u.length - 1; i >= 0; i--)
        {
            q = tau(q);
            if (u[i] == 1)
            {
                q = (ECPoint.F2m)q.addSimple(p);
            }
            else if (u[i] == -1)
            {
                q = (ECPoint.F2m)q.subtractSimple(p);
            }
        }
        return q;
    }

    /**
     * Computes the <code>[&tau;]</code>-adic window NAF of an element
     * <code>&lambda;</code> of <code><b>Z</b>[&tau;]</code>.
     * @param mu The parameter &mu; of the elliptic curve.
     * @param lambda The element <code>&lambda;</code> of
     * <code><b>Z</b>[&tau;]</code> of which to compute the
     * <code>[&tau;]</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>&alpha;<sub>u</sub></code>'s for the window width.
     * @return The <code>[&tau;]</code>-adic window NAF of
     * <code>&lambda;</code>.
     */
    public static byte[] tauAdicWNaf(byte mu, ZTauElement lambda,
            byte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha)
    {
        if (!((mu == 1) || (mu == -1)))
        {
            throw new IllegalArgumentException("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
        byte[] u = new byte[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(ECConstants.ZERO))&&(r1.equals(ECConstants.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);
                
                byte uLocal;
                // if uUnMod >= 2^(width - 1)
                if (uUnMod.compareTo(pow2wMin1) >= 0)
                {
                    uLocal = (byte) uUnMod.subtract(pow2w).intValue();
                }
                else
                {
                    uLocal = (byte) uUnMod.intValue();
                }
                // uLocal is now in [-2^(width-1), 2^(width-1)-1]

                u[i] = uLocal;
                boolean s = true;
                if (uLocal < 0)
                {
                    s = false;
                    uLocal = (byte)-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 ECPoint.F2m[] getPreComp(ECPoint.F2m p, byte a)
    {
        ECPoint.F2m[] pu;
        pu = new ECPoint.F2m[16];
        pu[1] = p;
        byte[][] 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;
    }
}