tnaf.java

kmlnjlkj nlkjlkjkljl okopokipoipo oipipipo i

package org.bouncycastle.math.ec;

import java.math.BigInteger;

/**
 * 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.
 */
class Tnaf
{
    private static final BigInteger MINUS_ONE = ECConstants.ONE.negate();
    private static final BigInteger MINUS_TWO = ECConstants.TWO.negate();
    private static final BigInteger MINUS_THREE = ECConstants.THREE.negate();

    /**
     * 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>&alpha;<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 static final byte WIDTH = 4;

    /**
     * 2<sup>4</sup>
     */
    public static final byte POW_2_WIDTH = 16;

    /**
     * The <code>&alpha;<sub>u</sub></code>'s for <code>a=0</code> as an array
     * of <code>ZTauElement</code>s.
     */
    public static final ZTauElement[] alpha0 = {
        null,
        new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null,
        new ZTauElement(MINUS_THREE, MINUS_ONE), null,
        new ZTauElement(MINUS_ONE, MINUS_ONE), null,
        new ZTauElement(ECConstants.ONE, MINUS_ONE), null
    };

    /**
     * The <code>&alpha;<sub>u</sub></code>'s for <code>a=0</code> as an array
     * of TNAFs.
     */
    public static final byte[][] alpha0Tnaf = {
        null, {1}, null, {-1, 0, 1}, null, {1, 0, 1}, null, {-1, 0, 0, 1}
    };

    /**
     * The <code>&alpha;<sub>u</sub></code>'s for <code>a=1</code> as an array
     * of <code>ZTauElement</code>s.
     */
    public static final ZTauElement[] alpha1 = {null,
        new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null,
        new ZTauElement(MINUS_THREE, ECConstants.ONE), null,
        new ZTauElement(MINUS_ONE, ECConstants.ONE), null,
        new ZTauElement(ECConstants.ONE, ECConstants.ONE), null
    };

    /**
     * The <code>&alpha;<sub>u</sub></code>'s for <code>a=1</code> as an array
     * of TNAFs.
     */
    public static final byte[][] alpha1Tnaf = {
        null, {1}, null, {-1, 0, 1}, null, {1, 0, 1}, null, {-1, 0, 0, -1}
    };

    /**
     * Computes the norm of an element <code>&lambda;</code> of
     * <code><b>Z</b>[&tau;]</code>.
     * @param mu The parameter <code>&mu;</code> of the elliptic curve.
     * @param lambda The element <code>&lambda;</code> of
     * <code><b>Z</b>[&tau;]</code>.
     * @return The norm of <code>&lambda;</code>.
     */
    public static BigInteger norm(final byte 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 IllegalArgumentException("mu must be 1 or -1");
        }

        return norm;
    }

    /**
     * Computes the norm of an element <code>&lambda;</code> of
     * <code><b>R</b>[&tau;]</code>, where <code>&lambda; = u + v&tau;</code>
     * and <code>u</code> and <code>u</code> are real numbers (elements of
     * <code><b>R</b></code>). 
     * @param mu The parameter <code>&mu;</code> of the elliptic curve.
     * @param u The real part of the element <code>&lambda;</code> of
     * <code><b>R</b>[&tau;]</code>.
     * @param v The <code>&tau;</code>-adic part of the element
     * <code>&lambda;</code> of <code><b>R</b>[&tau;]</code>.
     * @return The norm of <code>&lambda;</code>.
     */
    public static SimpleBigDecimal norm(final byte 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 IllegalArgumentException("mu must be 1 or -1");
        }

        return norm;
    }

    /**
     * Rounds an element <code>&lambda;</code> of <code><b>R</b>[&tau;]</code>
     * to an element of <code><b>Z</b>[&tau;]</code>, such that their difference
     * has minimal norm. <code>&lambda;</code> is given as
     * <code>&lambda; = &lambda;<sub>0</sub> + &lambda;<sub>1</sub>&tau;</code>.
     * @param lambda0 The component <code>&lambda;<sub>0</sub></code>.
     * @param lambda1 The component <code>&lambda;<sub>1</sub></code>.
     * @param mu The parameter <code>&mu;</code> of the elliptic curve. Must
     * equal 1 or -1.
     * @return The rounded element of <code><b>Z</b>[&tau;]</code>.
     * @throws IllegalArgumentException if <code>lambda0</code> and
     * <code>lambda1</code> do not have same scale.
     */
    public static ZTauElement round(SimpleBigDecimal lambda0,
            SimpleBigDecimal lambda1, byte mu)
    {
        int scale = lambda0.getScale();
        if (lambda1.getScale() != scale)
        {
            throw new IllegalArgumentException("lambda0 and lambda1 do not " +
                    "have same scale");
        }

        if (!((mu == 1) || (mu == -1)))
        {
            throw new IllegalArgumentException("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);
        }

        byte h0 = 0;
        byte h1 = 0;

        // if eta >= 1
        if (eta.compareTo(ECConstants.ONE) >= 0)
        {
            if (check1.compareTo(MINUS_ONE) < 0)
            {
                h1 = mu;
            }
            else
            {
                h0 = 1;
            }
        }
        else
        {
            // eta < 1
            if (check2.compareTo(ECConstants.TWO) >= 0)
            {
                h1 = mu;
            }
        }

        // if eta < -1
        if (eta.compareTo(MINUS_ONE) < 0)
        {
            if (check1.compareTo(ECConstants.ONE) >= 0)
            {
                h1 = (byte)-mu;
            }
            else
            {
                h0 = -1;
            }
        }
        else
        {
            // eta >= -1
            if (check2.compareTo(MINUS_TWO) < 0)
            {
                h1 = (byte)-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>&lambda; = 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>&lambda; = s k / n</code> computed to
     * <code>c</code> bits of accuracy.
     */
    public static SimpleBigDecimal approximateDivisionByN(BigInteger k,
            BigInteger s, BigInteger vm, byte 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(ECConstants.ONE);
        }

        return new SimpleBigDecimal(ls, c);
    }

    /**
     * Computes the <code>&tau;</code>-adic NAF (non-adjacent form) of an
     * element <code>&lambda;</code> of <code><b>Z</b>[&tau;]</code>.
     * @param mu The parameter <code>&mu;</code> of the elliptic curve.
     * @param lambda The element <code>&lambda;</code> of
     * <code><b>Z</b>[&tau;]</code>.
     * @return The <code>&tau;</code>-adic NAF of <code>&lambda;</code>.
     */
    public static byte[] tauAdicNaf(byte mu, ZTauElement lambda)
    {
        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 : 34;

        // The array holding the TNAF
        byte[] u = new byte[maxLength];
        int i = 0;

        // The actual length of the TNAF
        int length = 0;

        BigInteger r0 = lambda.u;
        BigInteger r1 = lambda.v;

        while(!((r0.equals(ECConstants.ZERO)) && (r1.equals(ECConstants.ZERO))))
        {
            // If r0 is odd
            if (r0.testBit(0))
            {
                u[i] = (byte) ECConstants.TWO.subtract((r0.subtract(r1.shiftLeft(1))).mod(ECConstants.FOUR)).intValue();

                // r0 = r0 - u[i]
                if (u[i] == 1)
                {
                    r0 = r0.clearBit(0);
                }
                else
                {
                    // u[i] == -1
                    r0 = r0.add(ECConstants.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
        byte[] tnaf = new byte[length];
        System.arraycopy(u, 0, tnaf, 0, length);
        return tnaf;
    }

    /**
     * Applies the operation <code>&tau;()</code> to an
     * <code>ECPoint.F2m</code>. 
     * @param p The ECPoint.F2m to which <code>&tau;()</code> is applied.
     * @return <code>&tau;(p)</code>
     */
    public static ECPoint.F2m tau(ECPoint.F2m p)
    {
        if (p.isInfinity())
        {
            return p;
        }

        ECFieldElement x = p.getX();
        ECFieldElement y = p.getY();

        return new ECPoint.F2m(p.getCurve(), x.square(), y.square(), p.isCompressed());
    }

    /**
     * Returns the parameter <code>&mu;</code> of the elliptic curve.
     * @param curve The elliptic curve from which to obtain <code>&mu;</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>&mu;</code> of the elliptic curve.
     * @throws IllegalArgumentException if the given ECCurve is not a Koblitz
     * curve.
     */
    public static byte getMu(ECCurve.F2m curve)
    {
        BigInteger a = curve.getA().toBigInteger();
        byte mu;

        if (a.equals(ECConstants.ZERO))
        {
            mu = -1;