37

公開鍵暗号について私が読んだ説明では、2 つの非常に大きな素数を掛け合わせることで大きな数が得られると言われています。大きな素数の積を因数分解することは、ほとんど不可能なほど時間がかかるため、安全です。

これは、レインボー テーブルで簡単に解決できる問題のようです。使用される素数のおおよそのサイズが分かっていて、それらが 2 つあることがわかっている場合は、すぐにレインボー テーブルを作成できます。それは非常に大きなテーブルになりますが、それは実行でき、タスクはハードウェア全体で並列化できます。

レインボー テーブルが、大きな素数の乗算に基づいて公開鍵暗号を打ち負かす効果的な方法ではないのはなぜですか?

免責事項: 明らかに、何万人ものクレイジーでスマートなセキュリティ意識の高い人々が、私が午後に考えたことを何十年も見逃していたわけではありません。単純化された素人の説明を読んでいたため（例：2つ以上の数字が使用されている場合）、これを誤解していると思いますが、知識のギャップがどこにあるかを知るにはまだ十分に知りません.

編集: 「レインボー テーブル」がルックアップ テーブルで事前に計算されたハッシュを使用することに関連していることは知っていますが、上記はレインボー テーブル攻撃のように聞こえるため、ここではこの用語を使用しています。

編集 2:回答で述べたように、すべての素数だけを保存する方法はなく、すべての積を保存する方法はありません。

  • このサイトによると、512 ビットの素数は、((2^511) * 1) / (512 log(2)) = 4.35 × 10 151ほど多く存在します。
  • 太陽の質量は 2 × 10 30 kg または 2 × 10 33 g
  • これは、太陽 1 グラムあたり2.17 × 10 124個の素数です。
  • 数量 キロバイトに収まる 512 ビットの数値: 1 kb = 1024 バイト = 8192 ビット / 512 = 16
  • これは 1 テラバイトに収まります: 16*1024*1024*1024 = 1.72 × 10 10
  • ペタバイト: 16*1024*1024*1024*1024 = 1.72 × 10 13
  • エクサバイト: 16*1024*1024*1024*1024*1024 = 1.72 × 10 16

1 エクサバイトが 1 グラムの重さであったとしても、これらすべての数値を太陽の質量のハード ドライブに収めるのに必要な2.17 × 10 124にはほど遠いです。

4

3 に答える 3

33

私のお気に入りの本の 1 つ、Bruce Schneier の Applied Cryptography から

「誰かがすべての素数のデータベースを作成した場合、そのデータベースを使用して公開鍵アルゴリズムを破ることはできないでしょうか? はい、しかし彼はそれを行うことはできません. 重さ 1 のドライブに 1 ギガバイトの情報を格納できればgram の場合、512 ビットの素数のリストだけでも非常に重くなり、Chandrasekhar の制限を超えて崩壊し、ブラック ホールになります...とにかくデータを取得することはできません。」

言い換えれば、それは不可能か実行不可能、あるいはその両方です。

于 2010-07-16T18:32:34.360 に答える
10

RSA と Diffie-Hellman で使用される素数は、通常 2 512のオーダーです。それに比べて、既知の宇宙には約 2 256個の原子しかありません。つまり、2 512は、宇宙のすべての原子に 2 256の一意の番号を割り当てるのに十分な大きさです。

それほど多くのデータを保存/計算する方法はありません。

余談ですが、「素数の大きなテーブル」を意味していると思います-レインボーテーブルはハッシュ用に特別に調整されており、ここでは実際の意味はありません.

于 2010-07-16T18:14:46.037 に答える
2

主な問題は、特定のアルゴリズム用に事前に生成されたレインボー テーブルがかなり「小さい」範囲 (通常は 128 ビットの範囲) を使用することだと思います。これは通常、範囲全体をカバーするわけではありませんが、ブルート フォース プロセスを高速化します。これらは通常、数 TB のスペースを消費します。

素因数分解では、素数ははるかに大きくなります (安全な RSA の場合、2048 ビットが推奨されます)。したがって、レインボー テーブルは「非常に大きく」はなりませんが、どこにも保存できません (数百万 TB のスペースを使い果たします)。

また、レインボー テーブルはハッシュ チェーンを使用してプロセスを高速化しすぎます (ウィキペディアには適切な説明があります)。素数には使用できません。

于 2010-07-16T18:14:04.667 に答える