src/main/java/org/bouncycastle/math/ec/WNafMultiplier.java

package org.bouncycastle.math.ec;

import java.math.BigInteger;

/**
 * Class implementing the WNAF (Window Non-Adjacent Form) multiplication
 * algorithm.
 */
class WNafMultiplier implements ECMultiplier
{
    /**
     * Computes the Window NAF (non-adjacent Form) of an integer.
     * @param width The width <code>w</code> of the Window NAF. The width is
     * defined as the minimal number <code>w</code>, such that for any
     * <code>w</code> consecutive digits in the resulting representation, at
     * most one is non-zero.
     * @param k The integer of which the Window NAF is computed.
     * @return The Window NAF of the given width, such that the following holds:
     * <code>k = &sum;<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup>
     * </code>, where the <code>k<sub>i</sub></code> denote the elements of the
     * returned <code>byte[]</code>.
     */
    public byte[] windowNaf(byte width, BigInteger k)
    {
        // The window NAF is at most 1 element longer than the binary
        // representation of the integer k. byte can be used instead of short or
        // int unless the window width is larger than 8. For larger width use
        // short or int. However, a width of more than 8 is not efficient for
        // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than
        // 1000 Bits are currently not used in practice.
        byte[] wnaf = new byte[k.bitLength() + 1];

        // 2^width as short and BigInteger
        short pow2wB = (short)(1 << width);
        BigInteger pow2wBI = BigInteger.valueOf(pow2wB);

        int i = 0;

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

        // while k >= 1
        while (k.signum() > 0)
        {
            // if k is odd
            if (k.testBit(0))
            {
                // k mod 2^width
                BigInteger remainder = k.mod(pow2wBI);

                // if remainder > 2^(width - 1) - 1
                if (remainder.testBit(width - 1))
                {
                    wnaf[i] = (byte)(remainder.intValue() - pow2wB);
                }
                else
                {
                    wnaf[i] = (byte)remainder.intValue();
                }
                // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1]

                k = k.subtract(BigInteger.valueOf(wnaf[i]));
                length = i;
            }
            else
            {
                wnaf[i] = 0;
            }

            // k = k/2
            k = k.shiftRight(1);
            i++;
        }

        length++;

        // Reduce the WNAF array to its actual length
        byte[] wnafShort = new byte[length];
        System.arraycopy(wnaf, 0, wnafShort, 0, length);
        return wnafShort;
    }

    /**
     * Multiplies <code>this</code> by an integer <code>k</code> using the
     * Window NAF method.
     * @param k The integer by which <code>this</code> is multiplied.
     * @return A new <code>ECPoint</code> which equals <code>this</code>
     * multiplied by <code>k</code>.
     */
    public ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo)
    {
        WNafPreCompInfo wnafPreCompInfo;

        if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo))
        {
            wnafPreCompInfo = (WNafPreCompInfo)preCompInfo;
        }
        else
        {
            // Ignore empty PreCompInfo or PreCompInfo of incorrect type
            wnafPreCompInfo = new WNafPreCompInfo();
        }

        // floor(log2(k))
        int m = k.bitLength();

        // width of the Window NAF
        byte width;

        // Required length of precomputation array
        int reqPreCompLen;

        // Determine optimal width and corresponding length of precomputation
        // array based on literature values
        if (m < 13)
        {
            width = 2;
            reqPreCompLen = 1;
        }
        else
        {
            if (m < 41)
            {
                width = 3;
                reqPreCompLen = 2;
            }
            else
            {
                if (m < 121)
                {
                    width = 4;
                    reqPreCompLen = 4;
                }
                else
                {
                    if (m < 337)
                    {
                        width = 5;
                        reqPreCompLen = 8;
                    }
                    else
                    {
                        if (m < 897)
                        {
                            width = 6;
                            reqPreCompLen = 16;
                        }
                        else
                        {
                            if (m < 2305)
                            {
                                width = 7;
                                reqPreCompLen = 32;
                            }
                            else
                            {
                                width = 8;
                                reqPreCompLen = 127;
                            }
                        }
                    }
                }
            }
        }

        // The length of the precomputation array
        int preCompLen = 1;

        ECPoint[] preComp = wnafPreCompInfo.getPreComp();
        ECPoint twiceP = wnafPreCompInfo.getTwiceP();

        // Check if the precomputed ECPoints already exist
        if (preComp == null)
        {
            // Precomputation must be performed from scratch, create an empty
            // precomputation array of desired length
            preComp = new ECPoint[]{ p };
        }
        else
        {
            // Take the already precomputed ECPoints to start with
            preCompLen = preComp.length;
        }

        if (twiceP == null)
        {
            // Compute twice(p)
            twiceP = p.twice();
        }

        if (preCompLen < reqPreCompLen)
        {
            // Precomputation array must be made bigger, copy existing preComp
            // array into the larger new preComp array
            ECPoint[] oldPreComp = preComp;
            preComp = new ECPoint[reqPreCompLen];
            System.arraycopy(oldPreComp, 0, preComp, 0, preCompLen);

            for (int i = preCompLen; i < reqPreCompLen; i++)
            {
                // Compute the new ECPoints for the precomputation array.
                // The values 1, 3, 5, ..., 2^(width-1)-1 times p are
                // computed
                preComp[i] = twiceP.add(preComp[i - 1]);
            }            
        }

        // Compute the Window NAF of the desired width
        byte[] wnaf = windowNaf(width, k);
        int l = wnaf.length;

        // Apply the Window NAF to p using the precomputed ECPoint values.
        ECPoint q = p.getCurve().getInfinity();
        for (int i = l - 1; i >= 0; i--)
        {
            q = q.twice();

            if (wnaf[i] != 0)
            {
                if (wnaf[i] > 0)
                {
                    q = q.add(preComp[(wnaf[i] - 1)/2]);
                }
                else
                {
                    // wnaf[i] < 0
                    q = q.subtract(preComp[(-wnaf[i] - 1)/2]);
                }
            }
        }

        // Set PreCompInfo in ECPoint, such that it is available for next
        // multiplication.
        wnafPreCompInfo.setPreComp(preComp);
        wnafPreCompInfo.setTwiceP(twiceP);
        p.setPreCompInfo(wnafPreCompInfo);
        return q;
    }

}