java - 为什么我的 RSA 加密代码适用于小位大小，但不适用于较大位大小？

Question

我编写的代码不多，但是，当我尝试在 JAVA 中实现 RSA 加密时，我的加密和解密适用于较小尺寸的素数，但是，当我尝试对 1536 位大小的素数进行加密和解密时，解密将停止工作。我已经经历过了，但我不明白问题出在哪里。

我已经尝试查看位长度在什么时候开始成为问题，似乎当我将其设置为 50 时停止工作。如果我的 mod inverse 方法抛出有关 e.modinv(lambda) 的错误，我也往往会收到错误 不可能。我尝试通过添加 do 循环来解决此问题，但是似乎这并没有解决问题。

public BigInteger Random_Prime()
{
    SecureRandom random = new SecureRandom();
    byte [] randomize = new byte [192];
    random.nextBytes(randomize);
    BigInteger big = new BigInteger(randomize);
    return big.probablePrime(1536,random);
}
public BigInteger lcm(BigInteger p, BigInteger q)
{
    long p1 = p.longValue()-1;
    long q1 = q.longValue()-1;
    BigInteger test1 = p.valueOf(p1);
    BigInteger test2 = p.valueOf(q1);
    return test1.multiply(test2).divide(test1.gcd(test2));

做{

        p = obj1.Random_Prime();
        q = obj1.Random_Prime();
        lambda = obj1.lcm(p, q);
    }
    while(lambda.gcd(e).compareTo(ONE)!=0);
    BigInteger n = p.multiply(q);
    BigInteger m = new BigInteger("75");
    BigInteger d = e.modInverse(lambda);
    BigInteger c = obj1.Encrypt(n,e,m);

我预计 75 经过加密和解密后会返回为 75。

Answer 1

你的lcm()是错误的。

Java long 只有 64 位(包括符号)，不能表示大于 2^63 的数字。 (或等于，但大素数永远不等于 2 的幂。)因此，您的 lcm 计算应该适用于高达 63 位的 p,q，对我来说也是如此，但产生完全错误的结果对于更大的东西来说无用的结果。而是使用 {p,q}.subtract(BigInteger.ONE) 来表示与 gcd 相乘的数字。

此外，BigInteger.probablePrime(int,Random) 是一个静态(也称为类范围)方法；您不需要使用任何实例来调用它，更不用说使用您浪费时间计算的随机值来调用它，因为它被忽略了。就此而言，BigInteger.valueOf(long) 也是静态，并忽略用于调用它的任何实例。如果您使用的 Java 开发环境比简单地在 shell 或 COMMAND 中键入 javac 更高级，那么它应该(至少可选地)向您发出有关使用实例调用静态方法的警告。

最后，如果您不知道，直接使用 RSA 原语 m^e mod n 和 c^d mod n 来加密/解密数据(尤其是小数据)是不安全的。您必须使用足够大且随机的填充方案才能保证安全；请参阅wikipedia以获得简短的解释，如果您想更多搜索 https://crypto.stackexchange.com也许https://security.stackexchange.com这个问题已经被多次询问和回答。如果您简单地通过执行 c.modPow(d,n) 来解密(您没有显示)，那么效率低下(请参阅有关 CRT 的维基百科)并且不安全(请参阅有关定时攻击的维基百科，并且再次是 crypto.SX 和 security.SX)。直接使用 RSA 来处理数据非常有限且效率低下，因此在实践中人们使用混合加密——使用对称算法(现在通常是 AES)在随机数 key 下加密数据，然后对该随机数进行加密使用 RSA key ——或者更好地使用 RSA-KEM 派生它(再次参见 wikipedia crypto.SX security.SX)。

如果您确实想要安全性而不仅仅是玩玩，使用 Java 库中的加密，该库已由有能力的人员正确实现(并经过审查)，这与你的代码。