计算机如何容易地生成加密密钥?

Question

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

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

我认为问题可能出在我的算法上，但不仅仅是RSA密钥，即使我使用线程，生成100位素数也需要几个小时。那么，像google这样使用HTTPS的网站是如何在一毫秒内生成这些数字的呢?

Java中有一个名为big integer的类，它具有生成可能随机素数的方法。但是，如果它可能是素数，则某些包无法解密。不仅是HTTPS，还有一些网站可以生成1024-4096位密钥，而我正在努力计算24位密钥。

请解释一下它是如何工作的。

编辑:下面是我的代码:

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位长的东西，它将需要100万次迭代。如果phi长度为30位，则需要10亿次迭代。这是不可伸缩的。关于RSA的维基百科文章建议计算一个模乘法逆e-1 (mod phi)。一个能够做到这一点的算法是扩展欧几里得算法。好在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);