biginteger.java

这是linux下ssl vpn的实现程序

    if (!useMonty) {
      if (mag.length <= m.mag.length) {
        //zAccum = new int[m.magnitude.length * 2];
        zVal = new int[m.mag.length];

        System.arraycopy(mag, 0, zVal,
                         zVal.length - mag.length, mag.length);
      }
      else {
        //
        // in normal practice we'll never see this...
        //
        BigInteger tmp = this.remainder(m);

        //zAccum = new int[m.magnitude.length * 2];
        zVal = new int[m.mag.length];

        System.arraycopy(tmp.mag, 0, zVal,
                         zVal.length - tmp.mag.length, tmp.mag.length);
      }

      yAccum = new int[m.mag.length * 2];
    }

    yVal = new int[m.mag.length];

    //
    // from LSW to MSW
    //
    for (int i = 0; i < exponent.mag.length; i++) {
      int v = exponent.mag[i];
      int bits = 0;

      if (i == 0) {
        while (v > 0) {
          v <<= 1;
          bits++;
        }

        //
        // first time in initialise y
        //
        System.arraycopy(zVal, 0, yVal, 0, zVal.length);

        v <<= 1;
        bits++;
      }

      while (v != 0) {
        if (useMonty) {
          // Montgomery square algo doesn't exist, and a normal
          // square followed by a Montgomery reduction proved to
          // be almost as heavy as a Montgomery mulitply.
          multiplyMonty(yAccum, yVal, yVal, m.mag, mQ);
        }
        else {
          square(yAccum, yVal);
          remainder(yAccum, m.mag);
          System.arraycopy(yAccum, yAccum.length - yVal.length,
                           yVal, 0, yVal.length);
          zero(yAccum);
        }
        bits++;

        if (v < 0) {
          if (useMonty) {
            multiplyMonty(yAccum, yVal, zVal, m.mag, mQ);
          }
          else {
            multiply(yAccum, yVal, zVal);
            remainder(yAccum, m.mag);
            System.arraycopy(yAccum, yAccum.length - yVal.length,
                             yVal, 0, yVal.length);
            zero(yAccum);
          }
        }

        v <<= 1;
      }

      while (bits < 32) {
        if (useMonty) {
          multiplyMonty(yAccum, yVal, yVal, m.mag, mQ);
        }
        else {
          square(yAccum, yVal);
          remainder(yAccum, m.mag);
          System.arraycopy(yAccum, yAccum.length - yVal.length,
                           yVal, 0, yVal.length);
          zero(yAccum);
        }
        bits++;
      }
    }

    if (useMonty) {
      // Return y * R^(-1) mod m by doing y * 1 * R^(-1) mod m
      zero(zVal);
      zVal[zVal.length - 1] = 1;
      multiplyMonty(yAccum, yVal, zVal, m.mag, mQ);
    }

    return new BigInteger(1, yVal);
  }

  /**
   * return w with w = x * x - w is assumed to have enough space.
   */
  private int[] square(
      int[] w,
      int[] x) {
    long u1, u2, c;

    if (w.length != 2 * x.length) {
      throw new IllegalArgumentException("no I don't think so...");
    }

    for (int i = x.length - 1; i != 0; i--) {
      long v = (x[i] & IMASK);

      u1 = v * v;
      u2 = u1 >>> 32;
      u1 = u1 & IMASK;

      u1 += (w[2 * i + 1] & IMASK);

      w[2 * i + 1] = (int) u1;
      c = u2 + (u1 >> 32);

      for (int j = i - 1; j >= 0; j--) {
        u1 = (x[j] & IMASK) * v;
        u2 = u1 >>> 31; // multiply by 2!
        u1 = (u1 & 0x7fffffff) << 1; // multiply by 2!
        u1 += (w[i + j + 1] & IMASK) + c;

        w[i + j + 1] = (int) u1;
        c = u2 + (u1 >>> 32);
      }
      c += w[i] & IMASK;
      w[i] = (int) c;
      w[i - 1] = (int) (c >> 32);
    }

    u1 = (x[0] & IMASK);
    u1 = u1 * u1;
    u2 = u1 >>> 32;
    u1 = u1 & IMASK;

    u1 += (w[1] & IMASK);

    w[1] = (int) u1;
    w[0] = (int) (u2 + (u1 >> 32) + w[0]);

    return w;
  }

  /**
   * return x with x = y * z - x is assumed to have enough space.
   */
  private int[] multiply(
      int[] x,
      int[] y,
      int[] z) {
    for (int i = z.length - 1; i >= 0; i--) {
      long a = z[i] & IMASK;
      long value = 0;

      for (int j = y.length - 1; j >= 0; j--) {
        value += a * (y[j] & IMASK) + (x[i + j + 1] & IMASK);

        x[i + j + 1] = (int) value;

        value >>>= 32;
      }

      x[i] = (int) value;
    }

    return x;
  }

  /**
   * Calculate mQuote = -m^(-1) mod b with b = 2^32 (32 = word size)
   */
  private long getMQuote() {
    if (mQuote != -1L) { // allready calculated
      return mQuote;
    }
    if ( (mag[mag.length - 1] & 1) == 0) {
      return -1L; // not for even numbers
    }

    byte[] bytes = {
        1, 0, 0, 0, 0};
    BigInteger b = new BigInteger(1, bytes); // 2^32
    mQuote = this.negate().mod(b).modInverse(b).longValue();
    return mQuote;
  }

  /**
   * Montgomery multiplication: a = x * y * R^(-1) mod m
   * <br>
   * Based algorithm 14.36 of Handbook of Applied Cryptography.
   * <br>
   * <li> m, x, y should have length n </li>
   * <li> a should have length (n + 1) </li>
   * <li> b = 2^32, R = b^n </li>
   * <br>
   * The result is put in x
   * <br>
   * NOTE: the indices of x, y, m, a different in HAC and in Java
   */
  public void multiplyMonty(
      int[] a,
      int[] x,
      int[] y,
      int[] m,
      long mQuote) { // mQuote = -m^(-1) mod b
    int n = m.length;
    int nMinus1 = n - 1;
    long y_0 = y[n - 1] & IMASK;

    // 1. a = 0 (Notation: a = (a_{n} a_{n-1} ... a_{0})_{b} )
    for (int i = 0; i <= n; i++) {
      a[i] = 0;
    }

    // 2. for i from 0 to (n - 1) do the following:
    for (int i = n; i > 0; i--) {

      long x_i = x[i - 1] & IMASK;

      // 2.1 u = ((a[0] + (x[i] * y[0]) * mQuote) mod b
      long u = ( ( ( (a[n] & IMASK) + ( (x_i * y_0) & IMASK)) & IMASK) *
                mQuote) & IMASK;

      // 2.2 a = (a + x_i * y + u * m) / b
      long prod1 = x_i * y_0;
      long prod2 = u * (m[n - 1] & IMASK);
      long tmp = (a[n] & IMASK) + (prod1 & IMASK) + (prod2 & IMASK);
      long carry = (prod1 >>> 32) + (prod2 >>> 32) + (tmp >>> 32);
      for (int j = nMinus1; j > 0; j--) {
        prod1 = x_i * (y[j - 1] & IMASK);
        prod2 = u * (m[j - 1] & IMASK);
        tmp = (a[j] & IMASK) + (prod1 & IMASK) +
            (prod2 & IMASK) + (carry & IMASK);
        carry = (carry >>> 32) + (prod1 >>> 32) +
            (prod2 >>> 32) + (tmp >>> 32);
        a[j + 1] = (int) tmp; // division by b
      }
      carry += (a[0] & IMASK);
      a[1] = (int) carry;
      a[0] = (int) (carry >>> 32);
    }

    // 3. if x >= m the x = x - m
    if (compareTo(0, a, 0, m) >= 0) {
      subtract(0, a, 0, m);
    }

    // put the result in x
    for (int i = 0; i < n; i++) {
      x[i] = a[i + 1];
    }
  }

  public BigInteger multiply(
      BigInteger val) {
    if (signum == 0 || val.signum == 0) {
      return BigInteger.ZERO;
    }

    int[] res = new int[mag.length + val.mag.length];

    return new BigInteger(signum * val.signum, multiply(res, mag, val.mag));
  }

  public BigInteger negate() {
    return new BigInteger( -signum, mag);
  }

  public BigInteger pow(
      int exp) throws ArithmeticException {
    if (exp < 0) {
      throw new ArithmeticException("Negative exponent");
    }
    if (signum == 0) {
      return (exp == 0 ? BigInteger.ONE : this);
    }

    BigInteger y, z;
    y = BigInteger.ONE;
    z = this;

    while (exp != 0) {
      if ( (exp & 0x1) == 1) {
        y = y.multiply(z);
      }
      exp >>= 1;
      if (exp != 0) {
        z = z.multiply(z);
      }
    }

    return y;
  }

  /**
   * return x = x % y - done in place (y value preserved)
   */
  private int[] remainder(
      int[] x,
      int[] y) {
    int xyCmp = compareTo(0, x, 0, y);

    if (xyCmp > 0) {
      int[] c;
      int shift = bitLength(0, x) - bitLength(0, y);

      if (shift > 1) {
        c = shiftLeft(y, shift - 1);
      }
      else {
        c = new int[x.length];

        System.arraycopy(y, 0, c, c.length - y.length, y.length);
      }

      subtract(0, x, 0, c);

      int xStart = 0;
      int cStart = 0;

      for (; ; ) {
        int cmp = compareTo(xStart, x, cStart, c);

        while (cmp >= 0) {
          subtract(xStart, x, cStart, c);
          cmp = compareTo(xStart, x, cStart, c);
        }

        xyCmp = compareTo(xStart, x, 0, y);

        if (xyCmp > 0) {
          if (x[xStart] == 0) {
            xStart++;
          }

          shift = bitLength(cStart, c) - bitLength(xStart, x);

          if (shift == 0) {
            c = shiftRightOne(cStart, c);
          }
          else {
            c = shiftRight(cStart, c, shift);
          }

          if (c[cStart] == 0) {
            cStart++;
          }
        }
        else if (xyCmp == 0) {
          for (int i = xStart; i != x.length; i++) {
            x[i] = 0;
          }
          break;
        }
        else {
          break;
        }
      }
    }
    else if (xyCmp == 0) {
      for (int i = 0; i != x.length; i++) {
        x[i] = 0;
      }
    }

    return x;
  }

  /**
   * Returns a BigInteger whose value is <tt>(this | val)</tt>.  (This method
   * returns a negative BigInteger if and only if either this or val is
   * negative.)
   *
   * @param val value to be OR'ed with this BigInteger.
   * @return <tt>this | val</tt>
   */
  public BigInteger or(BigInteger val) {
    int[] result = new int[Math.max(intLength(), val.intLength())];
    for (int i = 0; i < result.length; i++) {
      result[i] = (int) (getInt(result.length - i - 1)
                         | val.getInt(result.length - i - 1));

    }
    return valueOf(result);
  }

  private static int[] makePositive(int a[]) {
    int keep, j;

    // Find first non-sign (0xffffffff) int of input
    for (keep = 0; keep < a.length && a[keep] == -1; keep++) {
      ;
    }

    /* Allocate output array.  If all non-sign ints are 0x00, we must
     * allocate space for one extra output int. */
    for (j = keep; j < a.length && a[j] == 0; j++) {
      ;
    }
    int extraInt = (j == a.length ? 1 : 0);
    int result[] = new int[a.length - keep + extraInt];

    /* Copy one's complement of input into into output, leaving extra
     * int (if it exists) == 0x00 */
    for (int i = keep; i < a.length; i++) {
      result[i - keep + extraInt] = ~a[i];

      // Add one to one's complement to generate two's complement
    }
    for (int i = result.length - 1; ++result[i] == 0; i--) {
      ;
    }

    return result;
  }

  private static int[] makePositive(byte a[]) {
    int keep, k;
    int byteLength = a.length;

    // Find first non-sign (0xff) byte of input
    for (keep = 0; keep < byteLength && a[keep] == -1; keep++) {
      ;
    }

    /* Allocate output array.  If all non-sign bytes are 0x00, we must
     * allocate space for one extra output byte. */
    for (k = keep; k < byteLength && a[k] == 0; k++) {
      ;
    }

    int extraByte = (k == byteLength) ? 1 : 0;
    int intLength = ( (byteLength - keep + extraByte) + 3) / 4;
    int result[] = new int[intLength];

    /* Copy one's complement of input into into output, leaving extra
     * byte (if it exists) == 0x00 */
    int b = byteLength - 1;
    for (int i = intLength - 1; i >= 0; i--) {
      result[i] = a[b--] & 0xff;
      int numBytesToTransfer = Math.min(3, b - keep + 1);
      if (numBytesToTransfer < 0) {
        numBytesToTransfer = 0;
      }
      for (int j = 8; j <= 8 * numBytesToTransfer; j += 8) {
        result[i] |= ( (a[b--] & 0xff) << j);

        // Mask indicates which bits must be complemented
      }
      int mask = -1 >>> (8 * (3 - numBytesToTransfer));
      result[i] = ~result[i] & mask;
    }

    // Add one to one's complement to generate two's complement
    for (int i = result.length - 1; i >= 0; i--) {
      result[i] = (int) ( (result[i] & 0xffffffffL) + 1);
      if (result[i] != 0) {
        break;
      }
    }

    return result;
  }

  private BigInteger(int[] val) {
    if (val.length == 0) {
      throw new NumberFormatException("Zero length BigInteger");
    }

    if (val[0] < 0) {
      mag = makePositive(val);
      signum = -1;
    }
    else {
      mag = trustedStripLeadingZeroInts(val);
      signum = (mag.length == 0 ? 0 : 1);
    }
  }