2

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

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

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

Javaにはbig integerというクラスがあり、おそらくランダムな素数を生成するメソッドを持っています。ただし、おそらくプライムの場合、一部のパッケージは復号化できません。HTTPS だけでなく、一部の Web サイトでは 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が設定されている場合、効率的なべき剰余アルゴリズムが使用されると、暗号化と署名の検証が非常に高速になります。

暗号化と復号化を同じくらい遅くしたい場合は、静的な値に設定する必要はありません。ウィキペディアで説明されているように、最大​​公約数 (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 ビット程度の場合、100 万回の反復が必要になることです。phi30 ビット長の場合、10 億回の反復が必要になります。それは単にスケーリングしません。RSA に関するウィキペディアの記事では、モジュラー乗法逆数を計算することを提案しています。それが可能なアルゴリズムが拡張ユークリッド アルゴリズムです。すでにこれを実装している良いこと:e-1 (mod phi)BigInteger

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

Randomは、暗号的に安全な乱数を生成しないことに注意してください。およびSecureRandomを生成するには、実際に使用する必要があります。また、は実際には のサイズなので、次のようになります。pqkeySizen

SecureRandom r = new SecureRandom();
q = BigInteger.probablePrime(keySize/2, r);
p = BigInteger.probablePrime(keySize/2, r);
于 2016-08-13T15:32:39.013 に答える