2

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

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

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

Java中有一个名为大整数的类，它具有生成可能随机素数的方法。但是，如果它可能是素数，则某些包无法解密。不仅 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;
}

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

4

1 回答 1

2

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

通常不需要计算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 位长的东西，则需要一百万次迭代。如果phi30 位长，则需要十亿次迭代。那只是没有规模。关于 RSA 的 Wikipedia 文章建议计算模乘逆。能够做到这一点的算法是扩展欧几里得算法。已经实现了这一点的好东西：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);
于 2016-08-13T15:32:39.013 回答