計算機如何輕鬆生成加密密鑰？

我想知道計算機如何輕鬆快速地生成密鑰，特別是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

計算機如何輕鬆生成加密密鑰？

回答

相關問題