为什么我的RSA加密代码适用于小尺寸，但不是更大的？

Question

我编写的代码不多，但是当我尝试在JAVA中实现RSA加密时，我的加密和解密工作适用于较小尺寸的素数，但是当我尝试为1536位大小的素数执行时，解密就会停止工作。我已经完成了它但是，我不知道问题是什么。

我已经试着看看比特长度在什么时候开始成为一个问题，而且当我将它设置为50时就停止工作了。我也倾向于得到一个错误，因为我的mod逆方法抛出了关于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计算应该适用于p，q高达63位，对我来说，但是对于任何更大的东西都会产生完全错误和无用的结果。而是使用{p,q}.subtract(BigInteger.ONE)作为你乘以和除以gcd的数字。

此外，BigInteger.probablePrime(int,Random)是static（aka全范围）方法;你不需要使用任何实例来调用它，更不用说你浪费时间计算的随机值，因为它被忽略了。就此而言，BigInteger.valueOf(long)也是static并且忽略了用来调用它的任何实例。如果您使用的任何类型的Java开发环境都比简单地将javac键入shell或COMMAND更先进，它应该（至少可选地）向您发出有关使用实例调用静态方法的警告。

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

如果你真的想要安全而不仅仅是玩游戏，那就使用Java库中的加密，这个加密已经由有能力的人正确实施（并且已经过审查），与你的代码不同。