util/math/BigIntegerModuloP.java

/*
 * Copyright (c) 2018, 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.
 */

import sun.security.util.math.*;

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.util.Arrays;
import java.util.Optional;

/**
 * Arithmetic in the field of integers modulo a prime value implemented using
 * BigInteger. This implementation is very versatile, but it is slow and none
 * of the operations are value-independent. This class is intended for use in
 * testing and prototyping, and production code should probably use a more
 * specialized arithmetic implementation.
 */

public class BigIntegerModuloP implements IntegerFieldModuloP {

    private final BigInteger p;

    public BigIntegerModuloP(BigInteger p) {
        this.p = p;
    }

    @Override
    public BigInteger getSize() {
        return p;
    }

    @Override
    public ImmutableElement get0() {
        return new ImmutableElement(BigInteger.ZERO);
    }
    @Override
    public ImmutableElement get1() {
        return new ImmutableElement(BigInteger.ONE);
    }
    @Override
    public ImmutableElement getElement(BigInteger v) {
        return new ImmutableElement(v);
    }
    @Override
    public ImmutableElement getElement(byte[] v, int offset, int length,
                                       byte highByte) {
        byte[] bigIntIn = new byte[length + 1];
        System.arraycopy(v, offset, bigIntIn, 0, length);
        bigIntIn[length] = highByte;
        reverse(bigIntIn);
        return new ImmutableElement(new BigInteger(1, bigIntIn).mod(getSize()));
    }
    @Override
    public SmallValue getSmallValue(int i) {
        return new SmallElement(i);
    }

    private abstract class Element implements IntegerModuloP {

        protected BigInteger v;

        protected Element(BigInteger v) {
            this.v = v;
        }

        protected Element(boolean v) {
            this.v = BigInteger.valueOf(v ? 1 : 0);
        }

        private BigInteger getModulus() {
            return getField().getSize();
        }

        @Override
        public IntegerFieldModuloP getField() {
            return BigIntegerModuloP.this;
        }

        @Override
        public BigInteger asBigInteger() {
            return v;
        }

        @Override
        public MutableElement mutable() {
            return new MutableElement(v);
        }

        @Override
        public ImmutableElement fixed() {
            return new ImmutableElement(v);
        }

        @Override
        public ImmutableElement add(IntegerModuloP b) {
            return new ImmutableElement(
                v.add(b.asBigInteger()).mod(getModulus()));
        }

        @Override
        public ImmutableElement additiveInverse() {
            return new ImmutableElement(v.negate().mod(getModulus()));
        }

        @Override
        public ImmutableElement multiply(IntegerModuloP b) {
            return new ImmutableElement(
                v.multiply(b.asBigInteger()).mod(getModulus()));
        }

        @Override
        public void addModPowerTwo(IntegerModuloP arg, byte[] result) {
            BigInteger biThis = asBigInteger();
            BigInteger biArg = arg.asBigInteger();
            bigIntAsByteArray(biThis.add(biArg), result);
        }

        private void bigIntAsByteArray(BigInteger arg, byte[] result) {
            byte[] bytes = arg.toByteArray();
            // bytes is backwards and possibly too big
            // Copy the low-order bytes into result in reverse
            int sourceIndex = bytes.length - 1;
            for (int i = 0; i < result.length; i++) {
                if (sourceIndex >= 0) {
                    result[i] = bytes[sourceIndex--];
                } else {
                    result[i] = 0;
                }
            }
        }

        @Override
        public void asByteArray(byte[] result) {
            bigIntAsByteArray(v, result);
        }
    }

    private class ImmutableElement extends Element
        implements ImmutableIntegerModuloP {

        private ImmutableElement(BigInteger v) {
            super(v);
        }
    }

    private class MutableElement extends Element
        implements MutableIntegerModuloP {

        private MutableElement(BigInteger v) {
            super(v);
        }

        @Override
        public void conditionalSet(IntegerModuloP b, int set) {
            if (set == 1) {
                v = b.asBigInteger();
            }
        }

        @Override
        public void conditionalSwapWith(MutableIntegerModuloP b, int swap) {
            if (swap == 1) {
                BigInteger temp = v;
                v = b.asBigInteger();
                ((Element) b).v = temp;
            }
        }

        @Override
        public MutableElement setValue(IntegerModuloP v) {
            this.v = ((Element) v).v;

            return this;
        }

        @Override
        public MutableElement setValue(byte[] arr, int offset, int length,
                                       byte highByte) {
            byte[] bigIntIn = new byte[length + 1];
            System.arraycopy(arr, offset, bigIntIn, 0, length);
            bigIntIn[length] = highByte;
            reverse(bigIntIn);
            v = new BigInteger(bigIntIn).mod(getSize());

            return this;
        }

        @Override
        public MutableElement setValue(ByteBuffer buf, int length,
                                       byte highByte) {
            byte[] bigIntIn = new byte[length + 1];
            buf.get(bigIntIn, 0, length);
            bigIntIn[length] = highByte;
            reverse(bigIntIn);
            v = new BigInteger(bigIntIn).mod(getSize());

            return this;
        }

        @Override
        public MutableElement setSquare() {
            v = v.multiply(v).mod(getSize());
            return this;
        }

        @Override
        public MutableElement setProduct(IntegerModuloP b) {
            Element other = (Element) b;
            v = v.multiply(other.v).mod(getSize());
            return this;
        }

        @Override
        public MutableElement setProduct(SmallValue value) {
            BigInteger bigIntValue = ((SmallElement) value).asBigInteger();
            v = v.multiply(bigIntValue).mod(getSize());
            return this;
        }

        @Override
        public MutableElement setSum(IntegerModuloP b) {
            Element other = (Element) b;
            v = v.add(other.v).mod(getSize());
            return this;
        }

        @Override
        public MutableElement setDifference(IntegerModuloP b) {
            Element other = (Element) b;
            v = v.subtract(other.v).mod(getSize());
            return this;
        }

        @Override
        public MutableElement setAdditiveInverse() {
            v = BigInteger.ZERO.subtract(v);
            return this;
        }

        @Override
        public MutableElement setReduced() {
            // do nothing
            return this;
        }

    }

    private class SmallElement extends ImmutableElement implements SmallValue {

        public SmallElement(int v) {
            super(BigInteger.valueOf(v).mod(getSize()));
        }
    }

    private static void swap(byte[] arr, int i, int j) {
        byte tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static void reverse(byte [] arr) {
        int i = 0;
        int j = arr.length - 1;

        while (i < j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }

}