java - 我已经为 RSA 加密和解密编写了一个 Java 代码，其中解密 key 太大，因此解密过程需要永远执行

Question

我必须根据程序的要求使用 p=78511 和 q=5657，代码执行没有错误，但由于 dec_key 的值太大，它不显示解密文本，继续运行。我该如何解决这个问题？有没有办法让 dec_key 更小，或者我做的解密方法全错了。在这里，我暂时尝试在加密方法中传递一个字符“H”。附上代码。请不要阻止我的问题。我是新来的，不太确定如何提问，请让我知道我哪里错了。谢谢!

package crypto.assgn4;  
import static crypto.assgn4.Problem2.phi;
import java.math.BigInteger;
class Test {

static char[] characters = {' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
static BigInteger p = BigInteger.valueOf(78511);
static BigInteger q = BigInteger.valueOf(5657);
static BigInteger N = p.multiply(q);
static BigInteger phi = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
static BigInteger e = BigInteger.ZERO, d;

public static void main(String args[]) {

    e = new BigInteger("4");
    while ((gcd(phi, e).intValue()>1)) {
        e = e.add(new BigInteger("1"));
    }

    d = BigInteger.valueOf(mul_inverse(e, phi));
    if (d.equals(e)) {
        d.add(phi);
    }

    System.out.println("Encryption Key : "+e);
    System.out.println("Decryption Key : "+d);

    String c = encrypt("H",e,N);
    String p = decrypt(c,d,N);

    System.out.println("Cipher : "+c);
    System.out.println("Text : " +p);


}

public static BigInteger gcd(BigInteger a, BigInteger b) {
    while (b != BigInteger.ZERO) {
        BigInteger temp = b;
        b = a.mod(b);
        a = temp;
    }
    return a;
}


public static int mul_inverse(BigInteger number, BigInteger sizeOfAlphabet) {
    int a = number.intValue() % sizeOfAlphabet.intValue();
    for (int x = 1; x < sizeOfAlphabet.intValue(); x++) {
        if ((a * x) % sizeOfAlphabet.intValue() == 1) {
            return getMod(x, sizeOfAlphabet.intValue());
        }
    }
    return -1;
}


public static int getMod(int x, int y) {
    int result = x % y;
    if (result < 0) {
        result += y;
    }
    return result;
}

/**
 * ********************************************************************************
 */
static String encrypt(String plainText, BigInteger e, BigInteger N) {
    StringBuilder cipherText = new StringBuilder();

    for (int i = 0; i < plainText.length(); i++) {
        int index = plainText.charAt(i);
        cipherText.append("").append((char) (new BigInteger(index + "").pow(e.intValue()).mod(N).intValue()));
        char c1 = (char) (new BigInteger(index + "").intValue());
    }
    return cipherText.toString();
}

static String decrypt(String cipherText, BigInteger d, BigInteger N) {

    String plainText = "";
    for (int i = 0; i < cipherText.length(); i++) {
        int index = cipherText.charAt(i);
        plainText += "" + (char) (new BigInteger(index + "").pow(d.intValue()).mod(N).intValue());

    }
    return plainText;
}

}

Answer 1

看起来你做的加密/解密都是错误的。

RSA 的要点是采用字符串编码的整个位模式，并将其视为一个 BigNumber(例如 BigInteger)本身。 (注意:如果那个 BigNumber 是 > 模数，那么字符串必须分成几部分，这样 BigNumber 就变成了 <模数。)

你在逐个字符的基础上所做的是不必要的矫枉过正，也可能是完全错误的，显然是运行时间长的根源。 (加密你的单字符字符串可能仍然很顺利，因为即使在逐个字符的基础上，你也只会进行一次加密。但它会产生一个长度为 x 的字符串，然后解密将进行 x BigInteger 计算，这将不可避免地需要更长的时间。)