java - 计算机如何轻松生成加密 key ？

Question

我想知道计算机如何轻松快速地生成 key ，尤其是 RSA。我一直在尝试使用 Java 生成 24 位 key 2 小时。

我的程序使用随机函数生成 p 和 q，如果它们不是素数，程序将生成新的随机数。最后，程序计算 e 和 d。如您所见，我的程序使用了标准的RSA算法，但是它花费了很多时间。

我认为问题可能出在我的算法上，但不仅是 RSA key ，即使我使用线程，生成 100 位质数也需要数小时。那么使用 HTTPS 的网站(例如 google)如何几乎在一毫秒内生成这些数字呢？

Java中有一个大整数类，它有产生随机素数的方法。但是，如果它可能是质数，则某些包无法解密。不仅 HTTPS，一些网站也可以生成 1024-4096 位 key ，而我正在努力计算 24 位 key 。

请解释它是如何工作的。

编辑:这是我的代码:

private BigInteger minusOne=new BigInteger("-1");
private BigInteger one=new BigInteger("1");
private BigInteger two=new BigInteger("2");
private BigInteger zero=new BigInteger("0");

private void generateKeys(int keySize){
    Random r=new Random();
    q=BigInteger.probablePrime(keySize,r);
    p=BigInteger.probablePrime(keySize, r);
    n=p.multiply(q);
    phi=(p.add(minusOne)).multiply(q.add(minusOne));
    if(p.equals(q)){
        generateKeys(keySize);
        return;
    }
    e=calculate_e();
    d=calculate_d();
    if(d.equals(minusOne)){
        generateKeys(keySize);
        return;
    }
}
private BigInteger calculate_e(){

    Random r=new Random();
    BigInteger e;
    do{
        e=new BigInteger(FindBitSize(phi),r);
    }while(!BetweenPrime(e,phi));
    if(e.compareTo(phi)==-1 && e.compareTo(one)==1){
        return e;

    }else{

        return calculate_e();
    }

}
private BigInteger calculate_d(){
    BigInteger k=new BigInteger("0");
    while(true){
        if(k.multiply(e).mod(phi).equals(one)){
            return k;
        }
        k=k.add(one);
    }
}
private boolean BetweenPrime(BigInteger b2,BigInteger b1){
    BigInteger d=new BigInteger("1");
    while(d.compareTo(b1)==-1 && d.compareTo(b2)==-1){
        d=d.add(one);
        if(b1.mod(d).equals(zero) && b2.mod(d).equals(zero)){
            return false;
        }

    }
    return true;
}

但是我的问题不在于代码。我只是不明白计算机如何在很短的时间内计算出太大的素数。

Answer 1

您的实现速度非常慢是有原因的。您已经实现了文字描述，但当然还有一些算法可以让您更快地到达终点。

通常不需要计算e .有一些常见的值:3 (0x3)、17 (0x11)、65537 (0x10001)。当 e 的几位时尽可能设置，那么当使用高效的模幂算法时，加密和签名验证将非常快。

如果您希望加密和解密同样慢，则不必将其设置为静态值。您可以按照 Wikipedia 中的描述计算它使用最大公约数 (GCD)。好东西BigInteger已经为此提供了一个实现:

private BigInteger calculate_e(){
    Random r = new Random();
    BigInteger e;
    do{
        e = new BigInteger(phi.bitLength(), r);
    } while(!e.gcd(phi).equals(one));
    if(e.compareTo(phi)==-1 && e.compareTo(one)==1){
        return e;
    } else {
        return calculate_e();
    }
}

calculate_d是一个非常天真的实现，只适用于非常小的数字，因为你正在尝试 1 到 phi 之间的每个数字。 .问题是如果 phi大约 20 位长，需要一百万次迭代。如果phi 30 位长的地方需要十亿次迭代。那只是无法扩展。关于 RSA 的维基百科文章建议计算模乘逆 e<sup>-1</sup> (<i>mod</i> phi) .能够做到这一点的算法是 Extended Euclidean algorithm .好东西BigInteger已经实现了这个:

private BigInteger calculate_d(){
    return e.modInverse(phi);
}

---

请注意 Random不会产生加密安全的随机数。你真的需要使用 SecureRandom生成 p和 q .此外，keySize实际上是n的大小，所以它应该是:

SecureRandom r = new SecureRandom();
q = BigInteger.probablePrime(keySize/2, r);
p = BigInteger.probablePrime(keySize/2, r);