ecfieldelement.java

来自「内容:基于jdk1.4的加密算法的具体实现」· Java 代码 · 共 651 行 · 第 1/2 页

package org.bouncycastle.math.ec;

import java.math.BigInteger;
import java.util.Random;

public abstract class ECFieldElement
    implements ECConstants
{
    BigInteger x;

    protected ECFieldElement(BigInteger x)
    {
        this.x = x;
    }
    
    public BigInteger toBigInteger()
    {
        return x;
    }

    public abstract String         getFieldName();
    public abstract ECFieldElement add(ECFieldElement b);
    public abstract ECFieldElement subtract(ECFieldElement b);
    public abstract ECFieldElement multiply(ECFieldElement b);
    public abstract ECFieldElement divide(ECFieldElement b);
    public abstract ECFieldElement negate();
    public abstract ECFieldElement square();
    public abstract ECFieldElement invert();
    public abstract ECFieldElement sqrt();

    public static class Fp extends ECFieldElement
    {
        BigInteger q;
        
        public Fp(BigInteger q, BigInteger x)
        {
            super(x);
            
            if (x.compareTo(q) >= 0)
            {
                throw new IllegalArgumentException("x value too large in field element");
            }

            this.q = q;
        }

        /**
         * return the field name for this field.
         *
         * @return the string "Fp".
         */
        public String getFieldName()
        {
            return "Fp";
        }

        public BigInteger getQ()
        {
            return q;
        }
        
        public ECFieldElement add(ECFieldElement b)
        {
            return new Fp(q, x.add(b.x).mod(q));
        }

        public ECFieldElement subtract(ECFieldElement b)
        {
            return new Fp(q, x.subtract(b.x).mod(q));
        }

        public ECFieldElement multiply(ECFieldElement b)
        {
            return new Fp(q, x.multiply(b.x).mod(q));
        }

        public ECFieldElement divide(ECFieldElement b)
        {
            return new Fp(q, x.multiply(b.x.modInverse(q)).mod(q));
        }

        public ECFieldElement negate()
        {
            return new Fp(q, x.negate().mod(q));
        }

        public ECFieldElement square()
        {
            return new Fp(q, x.multiply(x).mod(q));
        }

        public ECFieldElement invert()
        {
            return new Fp(q, x.modInverse(q));
        }

        // D.1.4 91
        /**
         * return a sqrt root - the routine verifies that the calculation
         * returns the right value - if none exists it returns null.
         */
        public ECFieldElement sqrt()
        {
            // p mod 4 == 3
            if (q.testBit(1))
            {
                // z = g^(u+1) + p, p = 4u + 3
                ECFieldElement z = new Fp(q, x.modPow(q.shiftRight(2).add(ONE), q));

                return z.square().equals(this) ? z : null;
            }
            // p mod 4 == 1
            if (q.testBit(0))
            {
                /*
                 * TODO: Use Lucas sequence to be faster
                BigInteger Q = this.x;
                BigInteger P = this.x;
                BigInteger U, V;
                while (true)
                {
                    while (!(P.multiply(P).subtract(Q.multiply(BigInteger.valueOf(4))).compareTo(ECConstants.ZERO) == 1))
                    {
                        P = new BigInteger(this.x.bitLength(), new Random());
                    }
                    BigInteger u = q.subtract(ECConstants.ONE).divide(
                            BigInteger.valueOf(4));
                    BigInteger result[] = lucasSequence(q, P, Q, u.multiply(
                            BigInteger.valueOf(2)).add(ECConstants.ONE));
                    U = result[0];
                    V = result[1];
                    if (V.multiply(V).equals(Q.multiply(BigInteger.valueOf(4))))
                    {
                        return new Fp(q, V.divide(BigInteger.valueOf(2)));
                    }
                    if (!U.equals(ECConstants.ONE))
                    {
                        return null;
                    }
                }
 */
                Random rand = new Random();
                BigInteger legendreExponent = q.subtract(ECConstants.ONE).divide(BigInteger.valueOf(2));
                if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
                {
                    return null;
                }
                BigInteger fourX = BigInteger.valueOf(4).multiply(x);
                BigInteger r = new BigInteger(q.bitLength(), rand).mod(q);
                r = BigInteger.valueOf(2);
                while (!(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(q.subtract(ECConstants.ONE))))
                {
                    r = new BigInteger(q.bitLength(), rand).mod(q);
                }
                
                BigInteger n1 = q.subtract(ECConstants.ONE).divide(BigInteger.valueOf(4));
                BigInteger n2 = q.add(BigInteger.valueOf(3)).divide(BigInteger.valueOf(4));
                BigInteger root = x.multiply(BigInteger.valueOf(2).multiply(r).modPow(q.subtract(BigInteger.valueOf(2)), q)).multiply(W(n1, r, x, q).add(W(n2, r, x, q))).mod(q);
                return new Fp(q, root);
            }

            throw new RuntimeException("not done yet");
        }

        private BigInteger W(BigInteger n, BigInteger r, BigInteger x, BigInteger p)
        {
            if (n.equals(ECConstants.ONE))
            {
                return r.multiply(r).multiply(x.modPow(q.subtract(BigInteger.valueOf(2)), q)).subtract(BigInteger.valueOf(2)).mod(p);
            }
            if (!n.testBit(0))
            {
                BigInteger w = W(n.divide(BigInteger.valueOf(2)), r, x, p);
                return w.multiply(w).subtract(BigInteger.valueOf(2)).mod(p);
            }
            BigInteger w1 = W(n.add(ECConstants.ONE).divide(BigInteger.valueOf(2)), r, x, p);
            BigInteger w2 = W(n.subtract(ECConstants.ONE).divide(BigInteger.valueOf(2)), r, x, p);
            return w1.multiply(w2).subtract(W(ECConstants.ONE, r, x, p)).mod(p);
        }
        
        public boolean equals(Object other)
        {
            if (other == this)
            {
                return true;
            }

            if (!(other instanceof ECFieldElement.Fp))
            {
                return false;
            }
            
            ECFieldElement.Fp o = (ECFieldElement.Fp)other;
            return q.equals(o.q) && x.equals(o.x);
        }

        public int hashCode()
        {
            return q.hashCode() ^ x.hashCode();
        }
    }

    /**
     * Class representing the Elements of the finite field
     * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
     * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
     * basis representations are supported. Gaussian normal basis (GNB)
     * representation is not supported.
     */
    public static class F2m extends ECFieldElement
    {
        /**
         * Indicates gaussian normal basis representation (GNB). Number chosen
         * according to X9.62. GNB is not implemented at present.
         */
        public static final int GNB = 1;

        /**
         * Indicates trinomial basis representation (TPB). Number chosen
         * according to X9.62.
         */
        public static final int TPB = 2;

        /**
         * Indicates pentanomial basis representation (PPB). Number chosen
         * according to X9.62.
         */
        public static final int PPB = 3;

        /**
         * TPB or PPB.
         */
        private int representation;

        /**
         * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
         */
        private int m;

        /**
         * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
         * x<sup>k</sup> + 1</code> represents the reduction polynomial
         * <code>f(z)</code>.<br>
         * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
         * represents the reduction polynomial <code>f(z)</code>.<br>
         */
        private int k1;

        /**
         * TPB: Always set to <code>0</code><br>
         * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
         * represents the reduction polynomial <code>f(z)</code>.<br>
         */
        private int k2;

        /**
         * TPB: Always set to <code>0</code><br>
         * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
         * represents the reduction polynomial <code>f(z)</code>.<br>
         */
        private int k3;
        
        /**
         * Constructor for PPB.
         * @param m  The exponent <code>m</code> of
         * <code>F<sub>2<sup>m</sup></sub></code>.
         * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
         * represents the reduction polynomial <code>f(z)</code>.
         * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
         * represents the reduction polynomial <code>f(z)</code>.
         * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
         * represents the reduction polynomial <code>f(z)</code>.
         * @param x The BigInteger representing the value of the field element.
         */
        public F2m(
            int m, 
            int k1, 
            int k2, 
            int k3,
            BigInteger x)
        {
            super(x);

            if ((k2 == 0) && (k3 == 0))
            {
                this.representation = TPB;
            }
            else
            {
                if (k2 >= k3)
                {
                    throw new IllegalArgumentException(
                            "k2 must be smaller than k3");
                }
                if (k2 <= 0)
                {
                    throw new IllegalArgumentException(
                            "k2 must be larger than 0");
                }
                this.representation = PPB;
            }

            if (x.signum() < 0)
            {
                throw new IllegalArgumentException("x value cannot be negative");
            }

            this.m = m;
            this.k1 = k1;
            this.k2 = k2;
            this.k3 = k3;
        }

        /**
         * Constructor for TPB.
         * @param m  The exponent <code>m</code> of
         * <code>F<sub>2<sup>m</sup></sub></code>.
         * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
         * x<sup>k</sup> + 1</code> represents the reduction
         * polynomial <code>f(z)</code>.