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

我想知道计算机如何轻松快速地生成密钥，特别是RSA。我一直试图用Java生成2个小时的24位密钥。计算机如何轻松生成加密密钥？

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

我认为这个问题可能存在于我的算法中，但是不仅RSA密钥也生成100位素数，即使我使用线程也需要几个小时。那么，如何使用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; 
}

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

来源

2016-08-13 F. Eser

TLS西弗斯不上飞生成新的RSA密钥，他们使用的是验证为一个属于他们的静态RSA密钥值得信赖的第三方，并在其证书中认可。但是，那说我电脑上的'openssl genrsa 2048'是0.2秒，而4096是1.06秒。 4096是痛苦地慢:)。 – bartonjs

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

通常没有必要计算e。有一些常见的值：3（0x3），17（0x11），65537（0x10001）。当尽可能少地设置e时，那么当使用高效的模幂运算算法时，加密和签名验证将非常快。

如果您想要加密和解密速度同样缓慢，则不必将其设置为静态值。您可以使用最大公约数（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的文章建议计算一个模乘法逆e^-1 (mod 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);

来源

2016-08-13 15:32:39

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

回答

相关问题