计算机如何轻松生成加密密钥？

Question

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

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

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

Java中有一个名为class的大整数，它有产生概率随机素数的方法。但是，如果它可能是质数，则某些包无法解密。不仅是 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的位数尽可能少时，使用高效的mod平方指数算法时，加密和签名验证将非常快。

如果您希望加密和解密同样慢，则不必将其设置为静态值。您可以使用最大公约数 (GCD) 按照 Wikipedia 中的描述进行计算。好东西 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 上的维基百科文章建议计算 mod 元乘法逆 e<sup>-1</sup> (<i>mod</i> φ)。能够做到这一点的算法是 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);

计算机如何轻松生成加密密钥？

How can computers generate encryption keys easily?

java

encryption

rsa

key-generator