dilog.java

《加密与解密》随书光盘(四)工具 本书在第一版的基础上,更新了第一版中的过时内容。 本书共分三个部分。 第一部分介绍与加密和解密技术相关的基础知识。 第二部分全面讲述各种最新的软件加密与解密技

// <XMP>
// Discrete logarithm calculator
//
// Written by Dario Alejandro Alpern (Buenos Aires - Argentina)
// Last updated March 30th, 2002, See http://www.alpertron.com.ar/DILOG.HTM
//
// No part of this code can be used for commercial purposes without
// the written consent from the author. Otherwise it can be used freely
// except that you have to write somewhere in the code this header.
// 
import java.applet.*;
import java.util.*;
import java.awt.*;
import java.math.*;

public final class dilog extends Applet implements Runnable {

  private TextField textBase, textPower, textMod, textExp;
  private Button btnSolve;
  private boolean TerminateThread;
  private volatile Thread calcThread;
  private BigInteger base, power, modulus;
  private BigInteger BigInt0 = BigInteger.valueOf(0L);
  private BigInteger BigInt1 = BigInteger.valueOf(1L);
  private BigInteger BigInt2 = BigInteger.valueOf(2L);
  private BigInteger BigInt3 = BigInteger.valueOf(3L);
  private BigInteger LastModulus = BigInt0;
  private Frame factorWindow;
  private ecm factorPanel;
  private BigInteger Primes[];
  private int Exponents[];
  private BigInteger PrimesBak[];
  private int ExponentsBak[];
  private BigInteger nbrV[];
  private int NumberLength;
  private int NumberLengthOther;
  private long DosALa32 = (long)1 << 32;
  private long DosALa32_1 = DosALa32 - 1;
  private long DosALa31 = (long)1 << 31;
  private long DosALa31_1 = DosALa31 - 1;
  private long DosALa63 = DosALa32 * DosALa31;
  private long AdjustDiv = 3 * DosALa31 * DosALa31;
  private double dDosALa32 = (double)DosALa32;
  private double dDosALa64 = dDosALa32 * dDosALa32;
  private double dDosALa96 = dDosALa64 * dDosALa32;
  private double dDosALa128 = dDosALa96 * dDosALa32;
  private double dDosALa160 = dDosALa128 * dDosALa32;
  private int NbrFactors;
  private final int NLen = 120;
  private long TestNbr[] = new long[NLen];
  private long TestNbrOther[] = new long[NLen];
  private long nbrA[] = new long[NLen];
  private long nbrA2[] = new long[NLen];
  private long nbrB[] = new long[NLen];
  private long nbrB2[] = new long[NLen];
  private long nbrK[] = new long[NLen];
  private long nbrR[] = new long[NLen];
  private long nbrROther[] = new long[NLen];
  private long nbrR2[] = new long[NLen];
  private long nbrPower[] = new long[NLen];
  private long nbrBase[] = new long[NLen];
  private long CalcBigNbr[] = new long[NLen];
  private long CalcAuxModInvU[] = new long[NLen];
  private long CalcAuxModInvV[] = new long[NLen];
  private long CalcAuxModInvU1[] = new long[NLen];
  private long CalcAuxModInvU3[] = new long[NLen];
  private long CalcAuxModInvV1[] = new long[NLen];
  private long CalcAuxModInvV3[] = new long[NLen];
  private long CalcAuxModInvT1[] = new long[NLen];
  private long CalcAuxModInvT3[] = new long[NLen];
  private long MontgomeryMultR1[] = new long[NLen];
  private long MontgomeryMultR2[] = new long[NLen];
  private long MontgomeryMultAfterInv[] = new long[NLen];
  private long MontgomeryMultN;
  private final long Mi = 1000000000;
  private double dN;
  private double dNOther;
  private long OldTimeElapsed;
  private long Old;
  private long yieldFreq;
  private long lModularMult;
  private Label labelStatus;

  public void init() {
    Label labelBase, labelPower, labelMod, labelExp, labelBottom;

    Primes=new BigInteger[400];
    Exponents=new int[400];
    PrimesBak=new BigInteger[400];
    ExponentsBak=new int[400];
    nbrV = new BigInteger[400];
    setLayout(null);
    labelBase = new Label("Base");
    labelBase.reshape(10, 15, 40, 14);
    labelBase.setFont(new Font("Courier", Font.PLAIN, 12));
    labelBase.setAlignment(Label.CENTER);
    add(labelBase);
    textBase = new TextField(64);
    textBase.reshape(60, 10, 520, 30);
    textBase.setEditable(true);
    add(textBase);
    labelPower = new Label("Power");
    labelPower.reshape(10, 65, 40, 14);
    labelPower.setFont(new Font("Courier", Font.PLAIN, 12));
    labelPower.setAlignment(Label.CENTER);
    add(labelPower);
    textPower = new TextField(64);
    textPower.reshape(60, 60, 520, 30);
    textPower.setEditable(true);
    add(textPower);
    labelMod = new Label("Mod");
    labelMod.reshape(10, 115, 40, 14);
    labelMod.setFont(new Font("Courier", Font.PLAIN, 12));
    labelMod.setAlignment(Label.CENTER);
    add(labelMod);
    textMod = new TextField(64);
    textMod.reshape(60, 110, 520, 30);
    textMod.setEditable(true);
    add(textMod);
    btnSolve = new Button("Find discrete logarithm");
    btnSolve.reshape(210, 160, 180, 30);
    btnSolve.setFont(new Font("Courier", Font.PLAIN, 12));
    add(btnSolve);
    labelStatus = new Label("");
    labelStatus.reshape(30, 205, 520, 14);
    labelStatus.setFont(new Font("Courier", Font.PLAIN, 12));
    labelStatus.setAlignment(Label.CENTER);
    add(labelStatus);
    textExp = new TextField(64);
    labelExp = new Label("Exp");
    labelExp.reshape(10, 235, 40, 14);
    labelExp.setFont(new Font("Courier", Font.PLAIN, 12));
    labelExp.setAlignment(Label.CENTER);
    add(labelExp);
    textExp = new TextField(64);
    textExp.reshape(60, 230, 520, 30);
    textExp.setEditable(false);
    add(textExp);
    labelBottom = new Label("Written by Dario Alejandro Alpern. Last updated March 30th, 2002");
    labelBottom.reshape(10, 280, 570, 14);
    labelBottom.setFont(new Font("Courier", Font.PLAIN, 12));
    labelBottom.setAlignment(Label.CENTER);
    add(labelBottom);
    validate();
    textBase.requestFocus();
    }

  public void destroy() {           /* Applet end */
    TerminateThread = true;
  }

public boolean handleEvent(Event e) {
  if (e.id == Event.ACTION_EVENT && e.target == btnSolve ||
      e.id == Event.KEY_PRESS && e.key == 13) {
    if (calcThread != null) {
      TerminateThread = true;
      try {
        calcThread.join();        /* Wait until the solving thread dies */
        } catch (InterruptedException ie) {};
      }
    calcThread = new Thread(this);  /* Start solving thread */
    calcThread.start();
    return true;
    }

  if (e.id == Event.KEY_PRESS && e.key == Event.TAB) {
    if (e.target == textBase) {textPower.requestFocus();}
    if (e.target == textPower) {textMod.requestFocus();}
    if (e.target == textMod) {textBase.requestFocus();}
    return true;
    }
  return super.handleEvent(e);
  }

  public void run() {
    BigInteger groupOrder, subGroupOrder, range, powSubGroupOrder;
    BigInteger Exponent, runningExp, baseExp;
    BigInteger basePH, powerPH;
    BigInteger logar, logarMult;
    BigInteger divideExp, nbrD;
    BigInteger bigNbrA2, bigNbrB2;
    int d, j, indexBase, indexExp;
    long addA, addB, addA2, addB2;
    long mult1, mult2;
    long magnitude;
    int mostSignificantDword, leastSignificantDword;
    long firstLimit, secondLimit;
    long brentK, brentR;

    Old=System.currentTimeMillis();
    OldTimeElapsed = 0;
    lModularMult = 0;
    TerminateThread = false;
    try {
      modulus = new BigInteger(textMod.getText().trim()).abs();
      base = new BigInteger(textBase.getText().trim()).mod(modulus);
      power = new BigInteger(textPower.getText().trim()).mod(modulus);
      } catch (Exception e) {
        textExp.setText("Invalid data entered");
        return;
        }
    if (modulus.compareTo(BigInt1) <= 0 || modulus.isProbablePrime(80) == false) {
      textExp.setText("Modulus is not prime");
      return;
      }
    groupOrder = modulus.subtract(BigInt1);
    textExp.setText("Computing discrete logarithm...");
    if (LastModulus.equals(modulus) == false) {
      if (GetSmallFactors(groupOrder, PrimesBak, ExponentsBak, 0) != 1) {
        LastModulus = modulus;
        factorPanel = new ecm();
        factorWindow = new Frame("Modulus factorization");
        factorWindow.setResizable(false);
        factorWindow.add(factorPanel);
        factorPanel.setSize(600, 390);
        Insets in = factorWindow.getInsets();
        factorWindow.setSize(600+in.right+in.left, 390+in.top+in.bottom);
        factorWindow.show();
        NbrFactors = factorPanel.getFactors(groupOrder, PrimesBak, ExponentsBak);
        factorWindow.remove(factorPanel);
        factorWindow.dispose();
        }
      }
    for (j=0; j<NbrFactors; j++) {
      Primes[j] = PrimesBak[j];
      Exponents[j] = ExponentsBak[j];
      }
    range = modulus.divide(BigInt3);
    logar = BigInt0;
    logarMult = BigInt1;
    BigNbrToBigInt(modulus);
    yieldFreq = 1000000/(NumberLength*NumberLength);
    GetMontgomeryParms();
    if (NumberLength == 1) {
      mostSignificantDword = NLen - 1;
      leastSignificantDword = NumberLength - 1;
      }
    else {
      mostSignificantDword = NumberLength - 1;
      leastSignificantDword = NumberLength - 2;
      }
    secondLimit = ((TestNbr[mostSignificantDword] << 32) +
                    TestNbr[leastSignificantDword]) * 2 / 3;
    firstLimit = secondLimit / 2;

    for (indexBase = 0; indexBase < NbrFactors; indexBase++) {
      textExp.setText("Computing discrete logarithm in subgroup of "+Primes[indexBase]+" elements.");
      runningExp = BigInt0;
      subGroupOrder = Primes[indexBase];
      ExchangeMods();                    // TestNbr <- subGroupOrder
      BigNbrToBigInt(subGroupOrder);
      dN = (double)TestNbr[NumberLength-1];
      if (NumberLength > 1) {
        dN += (double)TestNbr[NumberLength-2]/dDosALa32;
      }
      if (NumberLength > 2) {
        dN += (double)TestNbr[NumberLength-3]/dDosALa64;
      }
      ExchangeMods();                    // TestNbr <- modulus
      baseExp = groupOrder;
      powSubGroupOrder = BigInt1;
      for (indexExp = 0; indexExp < Exponents[indexBase]; indexExp++) {

        /* PH below comes from Pohlig-Hellman algorithm */

        divideExp = BigInt1;
        j = Exponents[indexBase] - indexExp;
        do {
          divideExp = divideExp.multiply(subGroupOrder);
          basePH = base.modPow(groupOrder.divide(divideExp), modulus);
          j--;
          } while (j>0 && basePH.equals(BigInt1));
        powerPH = power.multiply(base.modPow(runningExp.negate(), modulus)).
                          modPow(baseExp.divide(divideExp),modulus);
        baseExp = baseExp.divide(subGroupOrder);
        if (subGroupOrder.compareTo(BigInteger.valueOf(20L)) < 0) {
          for (j=subGroupOrder.intValue()-1; j>=0; j--) {
            if (basePH.modPow(BigInteger.valueOf(j), modulus).equals(powerPH)) {
              break;
              }
            }
          if (j<0) {
            textExp.setText("Cannot compute discrete logarithm    subgroup="+Primes[indexBase]+"   exponent="+indexExp);
            return;
            }
          Exponent = BigInteger.valueOf(j);
          }
        else {        // Use Pollard's rho method with Brent's modification
          BigNbrToMont(powerPH, nbrPower);
          BigNbrToMont(basePH, nbrBase);

          for (j=0; j<NumberLength; j++) {
            nbrR2[j] = nbrBase[j];
            nbrA2[j] = nbrB2[j] = 0;
            }
          nbrB2[0] = 1;
          addA2 = addB2 = 0;
          mult2 = 1;
          brentR = 1;
          brentK = 0;
PollardBrentRho:
          do {
            for (j=0; j<NumberLength; j++) {
              nbrR[j] = nbrR2[j];
              nbrA[j] = nbrA2[j];
              nbrB[j] = nbrB2[j];
              }
            addA = addA2;
            addB = addB2;
            mult1 = mult2;
            brentR *= 2;
            do {
              if (TerminateThread) {
                return;                /* End thread */
              }
              brentK++;
              magnitude = (nbrR2[mostSignificantDword] << 32) +
                           nbrR2[leastSignificantDword];
              if (magnitude < firstLimit) {
                MontgomeryMult(nbrR2, nbrPower, nbrROther);
                addA2++;
                }
              else {
                if (magnitude < secondLimit) {
                  MontgomeryMult(nbrR2, nbrR2, nbrROther);
                  mult2 *= 2;
                  addA2 *= 2;
                  addB2 *= 2;
                  }
                else {
                  MontgomeryMult(nbrR2, nbrBase, nbrROther);
                  addB2++;
                  }
                }
              long [] nbrTemp = nbrR2;
              nbrR2 = nbrROther;
              nbrROther = nbrTemp;
              if (mult2 > 10000000) {
                ExchangeMods();              // TestNbr <- subGroupOrder
                AdjustExponent(nbrA2, mult2, addA2);
                AdjustExponent(nbrB2, mult2, addB2);
                ExchangeMods();              // TestNbr <- modulus
                mult2 = 1;
                addA2 = addB2 = 0;
                }
              for (j=0; j<NumberLength; j++) {
                if (nbrR[j] != nbrR2[j]) {break;}
                }
              if (j==NumberLength) {break PollardBrentRho;}
              } while (brentK < brentR);
            } while (true);
          ExchangeMods();                  // TestNbr <- subGroupOrder
          AdjustExponent(nbrA, mult1, addA);
          AdjustExponent(nbrB, mult1, addB);
          AdjustExponent(nbrA2, mult2, addA2);
          AdjustExponent(nbrB2, mult2, addB2);
          SubtractBigNbrModN(nbrA, nbrA2, nbrA);
          SubtractBigNbrModN(nbrB2, nbrB, nbrB);
          if (BigNbrIsZero(nbrA)) {
            for (j=0; j<NumberLength; j++) {
              nbrK[j] = 0;
              }
            bigNbrA2 = BigInt0;
            bigNbrB2 = BigIntToBigNbr(nbrB);
            d = subGroupOrder.intValue();
            }
          else {                           // gcd is 1.
            ModInvBigNbr(nbrA, nbrB2, TestNbr);
            MultBigNbrModN(nbrB2, nbrB, nbrK);
            bigNbrA2 = BigInt1;
            bigNbrB2 = basePH.modPow(BigIntToBigNbr(nbrK), modulus);
            d = 1;
            }
          ExchangeMods();                  // TestNbr <- modulus