コンピュータはどのようにして暗号化キーを簡単に生成できますか？

Question

どのようにしてコンピュータがキー、特にRSAを簡単かつ迅速に生成できるのだろうか。私は、Javaを使用して2時間24ビットキーを生成しようとしていました。

私のプログラムは、random関数を使ってpとqを生成していますが、それらが素数でない場合、プログラムは新しい乱数を生成します。最後に、プログラムはeとdを計算します。ご覧のとおり、私のプログラムは標準のRSAアルゴリズムを使用していますが、時間がかかります。

問題は私のアルゴリズムにあると思っていましたが、スレッドを使用しても、100ビットの素数を生成するRSAキーだけでなく数時間もかかります。では、googleなどのHTTPSを使用するサイトでは、これらの数値をほぼ1ミリ秒単位で生成することができますか？

Javaにはbig integerという名前のクラスがあり、おそらくランダムプライムを生成するメソッドがあります。しかし、おそらく素数であれば、いくつかのパッケージを解読することはできません。 HTTPSだけでなく、24ビットキーの計算に苦労している間に、一部のWebサイトで1024-4096ビットのキーを生成することもできます。

どのように動作するか説明してください。

編集：ここに は私のコードです：

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に設定されていると、効率的なモジュラ累乗アルゴリズムが使用されると、暗号化と署名の検証が非常に高速になります。

暗号化と復号化を同等に遅くする場合は、静的な値に設定する必要はありません。最大公約数（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ビットのようなものであれば、100万回の反復が必要になることです。 3032ビットの場合、phiには10億回の反復が必要です。それだけではスケールされません。 RSAに関するWikipediaの記事は、モジュラ乗法逆数e-1 (mod phi)を計算することを示唆している。それを可能にするアルゴリズムはExtended Euclidean algorithmです。 Randomは、暗号的に安全な乱数を生成していないこと

private BigInteger calculate_d(){ 
    return e.modInverse(phi); 
} 

---

注：BigIntegerはすでにこれを実装することを良いこと。 pとqを生成するには、実際にSecureRandomを使用する必要があります。また、keySizeは実際にnのサイズですので、それは次のようになります。

SecureRandom r = new SecureRandom(); 
q = BigInteger.probablePrime(keySize/2, r); 
p = BigInteger.probablePrime(keySize/2, r);