biginteger.java

这是linux下ssl vpn的实现程序

/*
 *  SSL-Explorer
 *
 *  Copyright (C) 2003-2006 3SP LTD. All Rights Reserved
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 2 of
 *  the License, or (at your option) any later version.
 *  This program 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 for more details.
 *
 *  You should have received a copy of the GNU General Public
 *  License along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
			
package com.maverick.crypto.math;

import java.util.Random;
import java.util.Stack;

public class BigInteger {

  private int signum; // -1 means -ve; +1 means +ve; 0 means 0;
  private int mag[]; // array of ints with [0] being the most significant
  private int nBits = -1; // cache bitCount() value
  private int nBitLength = -1; // cache bitLength() value
  private static final long IMASK = 0xffffffffL;
  private long mQuote = -1L; // -m^(-1) mod b, b = 2^32 (see Montgomery mult.)
  int firstNonzeroIntNum = -2;
  private BigInteger() {
  }

  private BigInteger(int nWords) {
    signum = 1;
    mag = new int[nWords];
  }

  private BigInteger(
      int signum,
      int[] mag) {
    this.signum = signum;
    if (mag.length > 0) {
      int i = 0;
      while (i < mag.length && mag[i] == 0) {
        i++;
      }
      if (i == 0) {
        this.mag = mag;
      }
      else {
        // strip leading 0 bytes
        int[] newMag = new int[mag.length - i];
        System.arraycopy(mag, i, newMag, 0, newMag.length);
        this.mag = newMag;
        if (newMag.length == 0) {
          this.signum = 0;
        }
      }
    }
    else {
      this.mag = mag;
      this.signum = 0;
    }
  }

  public BigInteger(
      String sval) throws NumberFormatException {
    this(sval, 10);
  }

  public BigInteger(
      String sval,
      int rdx) throws NumberFormatException {
    if (sval.length() == 0) {
      throw new NumberFormatException("Zero length BigInteger");
    }

    if (rdx < Character.MIN_RADIX || rdx > Character.MAX_RADIX) {
      throw new NumberFormatException("Radix out of range");
    }

    int index = 0;
    signum = 1;

    if (sval.charAt(0) == '-') {
      if (sval.length() == 1) {
        throw new NumberFormatException("Zero length BigInteger");
      }

      signum = -1;
      index = 1;
    }

    // strip leading zeros from the string value
    while (index < sval.length() &&
           Character.digit(sval.charAt(index), rdx) == 0) {
      index++;
    }

    if (index >= sval.length()) {
      // zero value - we're done
      signum = 0;
      mag = new int[0];
      return;
    }

    //////
    // could we work out the max number of ints required to store
    // sval.length digits in the given base, then allocate that
    // storage in one hit?, then generate the magnitude in one hit too?
    //////

    BigInteger b = BigInteger.ZERO;
    BigInteger r = valueOf(rdx);
    while (index < sval.length()) {
      // (optimise this by taking chunks of digits instead?)
      b = b.multiply(r).add(valueOf(Character.digit(sval.charAt(index), rdx)));
      index++;
    }

    mag = b.mag;
    return;
  }

  public BigInteger(
      byte[] bval) throws NumberFormatException {
    if (bval.length == 0) {
      throw new NumberFormatException("Zero length BigInteger");
    }

    signum = 1;
    if (bval[0] < 0) {
      // FIXME:
      int iBval;
      signum = -1;
      // strip leading sign bytes
      for (iBval = 0; iBval < bval.length && bval[iBval] == -1; iBval++) {
        ;
      }
      mag = new int[ (bval.length - iBval) / 2 + 1];
      // copy bytes to magnitude
      // invert bytes then add one to find magnitude of value
    }
    else {
      // strip leading zero bytes and return magnitude bytes
      mag = makeMagnitude(bval);
    }
  }

  private int[] makeMagnitude(byte[] bval) {
    int i;
    int[] mag;
    int firstSignificant;

    // strip leading zeros
    for (firstSignificant = 0;
         firstSignificant < bval.length && bval[firstSignificant] == 0;
         firstSignificant++) {
      ;
    }

    if (firstSignificant >= bval.length) {
      return new int[0];
    }

    int nInts = (bval.length - firstSignificant + 3) / 4;
    int bCount = (bval.length - firstSignificant) % 4;
    if (bCount == 0) {
      bCount = 4;

    }
    mag = new int[nInts];
    int v = 0;
    int magnitudeIndex = 0;
    for (i = firstSignificant; i < bval.length; i++) {
      v <<= 8;
      v |= bval[i] & 0xff;
      bCount--;
      if (bCount <= 0) {
        mag[magnitudeIndex] = v;
        magnitudeIndex++;
        bCount = 4;
        v = 0;
      }
    }

    if (magnitudeIndex < mag.length) {
      mag[magnitudeIndex] = v;
    }

    return mag;
  }

  public BigInteger(
      int sign,
      byte[] mag) throws NumberFormatException {
    if (sign < -1 || sign > 1) {
      throw new NumberFormatException("Invalid sign value");
    }

    if (sign == 0) {
      this.signum = 0;
      this.mag = new int[0];
      return;
    }

    // copy bytes
    this.mag = makeMagnitude(mag);
    this.signum = sign;
  }

  public BigInteger(
      int numBits,
      Random rnd) throws IllegalArgumentException {
    if (numBits < 0) {
      throw new IllegalArgumentException("numBits must be non-negative");
    }

    int nBytes = (numBits + 7) / 8;

    byte[] b = new byte[nBytes];

    if (nBytes > 0) {
      nextRndBytes(rnd, b);
      // strip off any excess bits in the MSB
      b[0] &= rndMask[8 * nBytes - numBits];
    }

    this.mag = makeMagnitude(b);
    this.signum = 1;
    this.nBits = -1;
    this.nBitLength = -1;
  }

  private static final int BITS_PER_BYTE = 8;
  private static final int BYTES_PER_INT = 4;

  /**
   * strictly speaking this is a little dodgey from a compliance
   * point of view as it forces people to be using SecureRandom as
   * well, that being said - this implementation is for a crypto
   * library and you do have the source!
   */
  private void nextRndBytes(
      Random rnd,
      byte[] bytes) {
    int numRequested = bytes.length;
    int numGot = 0, r = 0;

    if (rnd instanceof com.maverick.crypto.security.SecureRandom) {
      ( (com.maverick.crypto.security.SecureRandom) rnd).nextBytes(bytes);
    }
    else {
      for (; ; ) {
        for (int i = 0; i < BYTES_PER_INT; i++) {
          if (numGot == numRequested) {
            return;
          }

          r = (i == 0 ? rnd.nextInt() : r >> BITS_PER_BYTE);
          bytes[numGot++] = (byte) r;
        }
      }
    }
  }

  private static final byte[] rndMask = {
      (byte) 255, 127, 63, 31, 15, 7, 3, 1};

  public BigInteger(
      int bitLength,
      int certainty,
      Random rnd) throws ArithmeticException {
    int nBytes = (bitLength + 7) / 8;

    byte[] b = new byte[nBytes];

    do {
      if (nBytes > 0) {
        nextRndBytes(rnd, b);
        // strip off any excess bits in the MSB
        b[0] &= rndMask[8 * nBytes - bitLength];
      }

      this.mag = makeMagnitude(b);
      this.signum = 1;
      this.nBits = -1;
      this.nBitLength = -1;
      if (certainty > 0 && bitLength > 2) {
        this.mag[this.mag.length - 1] |= 1;
      }
    }
    while (this.bitLength() != bitLength
           || !this.isProbablePrime(certainty));
  }

  public BigInteger abs() {
    return (signum >= 0) ? this : this.negate();
  }

  /**
   * return a = a + b - b preserved.
   */
  private int[] add(
      int[] a,
      int[] b) {
    int tI = a.length - 1;
    int vI = b.length - 1;
    long m = 0;

    while (vI >= 0) {
      m += ( ( (long) a[tI]) & IMASK) + ( ( (long) b[vI--]) & IMASK);
      a[tI--] = (int) m;
      m >>>= 32;
    }

    while (tI >= 0 && m != 0) {
      m += ( ( (long) a[tI]) & IMASK);
      a[tI--] = (int) m;
      m >>>= 32;
    }

    return a;
  }

  public BigInteger add(
      BigInteger val) throws ArithmeticException {
    if (val.signum == 0 || val.mag.length == 0) {
      return this;
    }
    if (this.signum == 0 || this.mag.length == 0) {
      return val;
    }

    if (val.signum < 0) {
      if (this.signum > 0) {
        return this.subtract(val.negate());
      }
    }
    else {
      if (this.signum < 0) {
        return val.subtract(this.negate());
      }
    }

    // both BigIntegers are either +ve or -ve; set the sign later

    int[] mag, op;

    if (this.mag.length < val.mag.length) {
      mag = new int[val.mag.length + 1];

      System.arraycopy(val.mag, 0, mag, 1, val.mag.length);
      op = this.mag;
    }
    else {
      mag = new int[this.mag.length + 1];

      System.arraycopy(this.mag, 0, mag, 1, this.mag.length);
      op = val.mag;
    }

    return new BigInteger(this.signum, add(mag, op));
  }

  public int bitCount() {
    if (nBits == -1) {
      nBits = 0;
      for (int i = 0; i < mag.length; i++) {
        nBits += bitCounts[mag[i] & 0xff];
        nBits += bitCounts[ (mag[i] >> 8) & 0xff];
        nBits += bitCounts[ (mag[i] >> 16) & 0xff];
        nBits += bitCounts[ (mag[i] >> 24) & 0xff];
      }
    }

    return nBits;
  }

  private final static byte bitCounts[] = {
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

  private int bitLength(
      int indx,
      int[] mag) {
    int bitLength;

    if (mag.length == 0) {
      return 0;
    }
    else {
      while (indx != mag.length && mag[indx] == 0) {
        indx++;
      }

      if (indx == mag.length) {
        return 0;
      }

      // bit length for everything after the first int
      bitLength = 32 * ( (mag.length - indx) - 1);

      // and determine bitlength of first int
      bitLength += bitLen(mag[indx]);

      if (signum < 0) {
        // Check if magnitude is a power of two
        boolean pow2 =
            ( (bitCounts[mag[indx] & 0xff]) +
             (bitCounts[ (mag[indx] >> 8) & 0xff]) +
             (bitCounts[ (mag[indx] >> 16) & 0xff]) +
             (bitCounts[ (mag[indx] >> 24) & 0xff])) == 1;

        for (int i = indx + 1; i < mag.length && pow2; i++) {
          pow2 = (mag[i] == 0);
        }

        bitLength -= (pow2 ? 1 : 0);
      }
    }

    return bitLength;
  }

  public int bitLength() {
    if (nBitLength == -1) {
      if (signum == 0) {
        nBitLength = 0;
      }
      else {
        nBitLength = bitLength(0, mag);
      }
    }

    return nBitLength;
  }

  //
  // bitLen(val) is the number of bits in val.
  //
  static int bitLen(int w) {
    // Binary search - decision tree (5 tests, rarely 6)
    return
        (w < 1 << 15 ?
         (w < 1 << 7 ?
          (w < 1 << 3 ?
           (w < 1 << 1 ? (w < 1 << 0 ? (w < 0 ? 32 : 0) : 1) :
            (w < 1 << 2 ? 2 : 3)) :
           (w < 1 << 5 ? (w < 1 << 4 ? 4 : 5) : (w < 1 << 6 ? 6 : 7))) :
          (w < 1 << 11 ?
           (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9) : (w < 1 << 10 ? 10 : 11)) :
           (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13) : (w < 1 << 14 ? 14 : 15)))) :
         (w < 1 << 23 ?
          (w < 1 << 19 ?
           (w < 1 << 17 ? (w < 1 << 16 ? 16 : 17) : (w < 1 << 18 ? 18 : 19)) :
           (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21) : (w < 1 << 22 ? 22 : 23))) :
          (w < 1 << 27 ?
           (w < 1 << 25 ? (w < 1 << 24 ? 24 : 25) : (w < 1 << 26 ? 26 : 27)) :
           (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29) : (w < 1 << 30 ? 30 : 31)))));
  }

  private final static byte bitLengths[] = {
      0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
      5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
      6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,