math/intpoly/IntegerPolynomialModBinP.java

/*
 * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.security.util.math.intpoly;

import java.math.BigInteger;
import java.nio.ByteBuffer;

/**
 * The field of integers modulo a binomial prime. This is a general-purpose
 * field implementation, that is much slower than more specialized classes
 * like IntegerPolynomial25519. It is suitable when only a small number of
 * arithmetic operations are required in some field. For example, this class
 * can be used for operations on scalars/exponents in signature operations.
 *
 * This class may only be used for primes of the form 2^a + b.
 */

public class IntegerPolynomialModBinP extends IntegerPolynomial {

    private final long[] reduceLimbs;
    private final int bitOffset;
    private final int limbMask;
    private final int rightBitOffset;
    private final int power;

    public IntegerPolynomialModBinP(int bitsPerLimb,
                                    int numLimbs,
                                    int power,
                                    BigInteger subtrahend) {
        super(bitsPerLimb, numLimbs, 1,
            BigInteger.valueOf(2).pow(power).subtract(subtrahend));

        boolean negate = false;
        if (subtrahend.compareTo(BigInteger.ZERO) < 0) {
            negate = true;
            subtrahend = subtrahend.negate();
        }
        int reduceLimbsLength = subtrahend.bitLength() / bitsPerLimb + 1;
        reduceLimbs = new long[reduceLimbsLength];
        ImmutableElement reduceElem = getElement(subtrahend);
        if (negate) {
            reduceElem = reduceElem.additiveInverse();
        }
        System.arraycopy(reduceElem.limbs, 0, reduceLimbs, 0,
            reduceLimbs.length);

        // begin test code
        System.out.println("reduce limbs:");
        for (int i = 0; i < reduceLimbs.length; i++) {
            System.out.println(i + ":" + reduceLimbs[i]);
        }
        // end test code

        this.power = power;
        this.bitOffset = numLimbs * bitsPerLimb - power;
        this.limbMask = -1 >>> (64 - bitsPerLimb);
        this.rightBitOffset = bitsPerLimb - bitOffset;
    }

    @Override
    protected void finalCarryReduceLast(long[] limbs) {

        int extraBits = bitsPerLimb * numLimbs - power;
        int highBits = bitsPerLimb - extraBits;
        long c = limbs[numLimbs - 1] >> highBits;
        limbs[numLimbs - 1] -= c << highBits;
        for (int j = 0; j < reduceLimbs.length; j++) {
            int reduceBits = power + extraBits - j * bitsPerLimb;
            modReduceInBits(limbs, numLimbs, reduceBits, c * reduceLimbs[j]);
        }
    }


    /**
     * Allow more general (and slower) input conversion that takes a large
     * value and reduces it.
     */
    @Override
    public ImmutableElement getElement(byte[] v, int offset, int length,
                                       byte highByte) {

        long[] result = new long[numLimbs];
        int numHighBits = 32 - Integer.numberOfLeadingZeros(highByte);
        int numBits = 8 * length + numHighBits;
        int requiredLimbs = (numBits + bitsPerLimb - 1) / bitsPerLimb;
        if (requiredLimbs > numLimbs) {
            long[] temp = new long[requiredLimbs];
            encode(v, offset, length, highByte, temp);
            // encode does a full carry/reduce
            System.arraycopy(temp, 0, result, 0, result.length);
        } else {
            encode(v, offset, length, highByte, result);
        }

        return new ImmutableElement(result, 0);
    }

    /**
     * Multiply a and b, and store the result in c. Requires that
     * a.length == b.length == numLimbs and c.length >= 2 * numLimbs - 1.
     * It is allowed for a and b to be the same array.
     */
    private void multOnly(long[] a, long[] b, long[] c) {
        for (int i = 0; i < numLimbs; i++) {
            for (int j = 0; j < numLimbs; j++) {
                c[i + j] += a[i] * b[j];
            }
        }
    }

    @Override
    protected void mult(long[] a, long[] b, long[] r) {

        long[] c = new long[2 * numLimbs];
        multOnly(a, b, c);
        carryReduce(c, r);
    }

    private void modReduceInBits(long[] limbs, int index, int bits, long x) {

        if (bits % bitsPerLimb == 0) {
            int pos = bits / bitsPerLimb;
            limbs[index - pos] += x;
        }
        else {
            int secondPos = bits / (bitsPerLimb);
            int bitOffset = (secondPos + 1) * bitsPerLimb - bits;
            int rightBitOffset = bitsPerLimb - bitOffset;
            limbs[index - (secondPos + 1)] += (x << bitOffset) & limbMask;
            limbs[index - secondPos] += x >> rightBitOffset;
        }
    }

    protected void reduceIn(long[] c, long v, int i) {

        for (int j = 0; j < reduceLimbs.length; j++) {
            modReduceInBits(c, i, power - bitsPerLimb * j, reduceLimbs[j] * v);
        }
    }

    private void carryReduce(long[] c, long[] r) {

        // full carry to prevent overflow during reduce
        carry(c);
        // Reduce in from all high positions
        for (int i = c.length - 1; i >= numLimbs; i--) {
            reduceIn(c, c[i], i);
            c[i] = 0;
        }
        // carry on lower positions that possibly carries out one position
        carry(c, 0, numLimbs);
        // reduce in a single position
        reduceIn(c, c[numLimbs], numLimbs);
        c[numLimbs] = 0;
        // final carry
        carry(c, 0, numLimbs - 1);
        System.arraycopy(c, 0, r, 0, r.length);
    }

    @Override
    protected void reduce(long[] a) {
        // TODO: optimize this
        long[] c = new long[a.length + 2];
        System.arraycopy(a, 0, c, 0, a.length);
        carryReduce(c, a);
    }

    @Override
    protected void square(long[] a, long[] r) {

        long[] c = new long[2 * numLimbs];
        for (int i = 0; i < numLimbs; i++) {
            c[2 * i] += a[i] * a[i];
            for (int j = i + 1; j < numLimbs; j++) {
                c[i + j] += 2 * a[i] * a[j];
            }
        }

        carryReduce(c, r);

    }

    /**
     * The field of integers modulo the order of the Curve25519 subgroup
     */
    public static class Curve25519OrderField extends IntegerPolynomialModBinP {

        public Curve25519OrderField() {
            super(26, 10, 252,
                new BigInteger("-27742317777372353535851937790883648493"));
        }
    }

    /**
     * The field of integers modulo the order of the Curve448 subgroup
     */
    public static class Curve448OrderField extends IntegerPolynomialModBinP {

        public Curve448OrderField() {
            super(28, 16, 446,
                new BigInteger("138180668098951153520073867485154268803366" +
                    "92474882178609894547503885"));
        }
    }
}