マルチスレッドRSAクラッキング

マルチスレッドを使用して、指定されたビット長のRSAキーをクラックします。それが機能するようになったら、より長いビット長でコードを試してください。

コードの弱点は、キーの平方根からビット長で可能な最大値まで、考えられる要因を検索することです。十分に小さい範囲に達するまで検索範囲のサイズを繰り返し半分にし、その後実際の検索を開始します。

mainを変更してこのコードを改善し、ForkJoinRsaTaskの呼び出しで開始範囲が狭くなるようにし（たとえば、20000など）、これをループして範囲を最大までカバーします。可能な限り最大のビット長でコードを効率的に機能させるようにしてください。 32ビットが使用できない場合があることに注意してください。 8ビット（実際には16ビット暗号化）から徐々に作業を進めて、どこまで進むことができるかを確認してください。

このアプローチは、11〜15行目で使用されている暗号化技術を攻撃しようとします。テストのp、q、およびn値を作成した後、現在の時刻をミリ秒単位でキャプチャします。
その量を妥当な量だけデクリメントします（pとqが作成された正確な時刻がわからないふりをするため）。

Random（）の可能なシード値をループしてnを因数分解し、そこからpを作成して（pをテストするだけでよいので、qは必要ありません）、pを因数としてテストします。

それが機能しない場合は、次のシードに進みます。因数分解のランダムの作成、および因数分解テストコードは、計算メソッドに表示される必要があります-範囲（iおよびmax）がテストする潜在的な因数ではなく、この範囲（i、max）がテストする可能性のあるシード値の範囲です。

作ったコードは下です。

import java.math.BigInteger;
import java.util.;
import java.util.concurrent.;

public class Rsa {

static final BigInteger TWO = new BigInteger("2");

public static void main (String [] args) {

    Random r = new Random();
    int bitLength = 2048; // start at 8 and double
    BigInteger p = BigInteger.probablePrime(bitLength, r);
    BigInteger q = BigInteger.probablePrime(bitLength, r);
    BigInteger n = p.multiply(q);
    System.out.println("p="+p+" q="+q+" n="+n);

    int calcBitLength = n.bitLength()/2;
    BigInteger max = TWO.pow(calcBitLength+1).subtract(BigInteger.ONE);
    System.out.println("bitLength="+calcBitLength+ ",\n max="+max);

  // nを因数分解しようとします
   // BigInteger i = n.sqrt（）;
    BigInteger i = n.multiply(n);
    System.out.println("initial i="+i);

    ForkJoinPool fjPool = new ForkJoinPool();

 // ForkJoinRsaTaskを機能させた後、次の行をループに入れます
     //検索スペースのより狭い範囲（おそらく1000または20000）を段階的に攻撃します。
     //サイズをいじって、何が最適かを確認できます
    ForkJoinRsaTask forkJoinRsaTask = new ForkJoinRsaTask(n, i, max);
    fjPool.invoke(forkJoinRsaTask);
}

}

class ForkJoinRsaTask extends RecursiveAction {
BigInteger i, n, max;
private static final BigInteger THRESHOLD = new BigInteger("100");

public ForkJoinRsaTask(BigInteger n, BigInteger i, BigInteger max) {
    this.i = i;
    this.n=n;
    this.max=max;
}

@Override
protected void compute() {

    BigInteger diff = max.subtract(i);

//Random（）の可能なシード値をループしてnを因数分解し、そこからpを作成して（pをテストするだけでよいので、qは必要ありません）、pを因数としてテストします。

    if (diff.compareTo(THRESHOLD)<0) {

// max 未満の各素数をループし、n を除算するかどうかを確認します。その場合は、見つ
かった値を出力し、システムを終了してすべてのスレッドを終了します
//ループを通過するたびに、BigIntegernextProbablePrime メソッドを使用してテストする
次の値を選択します
int i=0,n=0,max=0;
ForkJoinRsaTask(i,n,max);

    }
    else {//それが機能しない場合

//リストを半分に切り、2 つの半分に対して ForkJoinRsaTask を呼び出します（マルチスレ
ッドクイックソートと同様）
List<ForkJoinRsaTask> folkjoinrsatask=new ArrayList<ForkJoinRsaTask>();
folkjoinrsatask.add(0);
folkjoinrsatask.add(1);
List<ForkJoinRsaTask> sbList = folkjoinrsatask.subList(1, 3);

}
}

}

computeメソッドで、

max 未満の各素数をループし、n を除算するかどうかを確認します。その場合は、見つ
かった値を出力し、システムを終了してすべてのスレッドを終了し、
ループを通過するたびに、BigIntegernextProbablePrime メソッドを使用してテストするために値を選択し、無理ならelseでリストを半分に切り、2 つの半分に対して ForkJoinRsaTask を呼び出します（マルチスレ
ッドクイックソートと同様）にはどうしたらいいのかわかりません。（私のコードだとエラーが出ます。）

y_waiwai

2020/12/13 23:13

> 迷っていますで、しつもんはなんでしょうか

dodox86

2020/12/13 23:51

「迷う」と言うのは、自分の中でいくつか既にできあがっている選択肢があって、どれを使おうか悩んでいることを指します。

cha-

2020/12/14 15:52

computeのifの中はForkJoinRsaTask(i,n,max);と呼び出しをしましたが、エラーのままでです。ループを通過するたびに、BigIntegernextProbablePrime メソッドを使用してテストってなると方法がおもいつきません elseに関してはリストを半分に切りたいですが、 List<ForkJoinRsaTask> folkjoinrsatask=new ArrayList<ForkJoinRsaTask>(); folkjoinrsatask.add(0); folkjoinrsatask.add(1); List<ForkJoinRsaTask> sbList = folkjoinrsatask.subList(1, 3); だと作動しません

cha-

2021/03/10 18:14

解決できました！