多くの設計者は、暗号化スキームには80ビットのセキュリティがあると主張しました。では、ある種のCPUを使用した80ビットセキュリティRSAなど、この80ビットセキュリティ暗号化スキームを使用する時間を計算するにはどうすればよいでしょうか。
コメント
- 80ビットRSAは、たとえば、 GMP-ECM 。 RSA因数分解レコードの詳細については、これを参照してください。 80ビットセキュリティの詳細については、これを参照してください。キーサイズの選択については、これを参照してください。
- ご回答ありがとうございます。ここで、例として128ビットのセキュリティを取り上げます。 128ビットセキュリティとは、このスキームを攻撃するための2 ^ 128の基本操作を意味することをお聞きしたいと思います。これは本当ですか？そして、基本的な操作は一般的な乗算または加算を意味しますか？そして、このスキームを攻撃する具体的な時間を計算する方法は？ 2 ^ 128は、一般的な乗算または加算を行う時間を乗算しますか？
- ああ、あなたの質問は、$ n $ビットのセキュリティとはどういう意味ですか。 'これに関するQ / Aを見つけようとしています。簡単に言うと、システムを破壊するには$ 2 ^ n $ステップが必要であり、" step "は大まかに定義されています。対称暗号の場合、通常は" 1つの暗号化またはハッシュ"と同じくらいの作業です。非対称暗号に関する理論的な作業の場合、" step "は" 1つのグループになる傾向があります（またはフィールド）操作または1つのハッシュ"。 RSAの場合、これは（公開鍵の）1つのモジュラー乗算mod N、または1つのハッシュである可能性があります。しかし実際には、$ n $ビットセキュリティは次の目的で使用されることがよくあります。$ n $ビットセキュリティで対称暗号を解読するのと同じくらいの（コンピュータ）作業。
- 64ビットのセキュリティ不足。サミットのようなスーパーコンピューターは、1年で$ 2 ^ {72} $に達する可能性があります。ただし、ビットコインマイナーのような専用グループは1年で$ 2 ^ {92} $に達する可能性があるため、80ビットはもはや安全ではありません。 AES-128でさえ利用可能なマルチターゲット攻撃がすべてのターゲットに対して安全ではない場合は、こことマルチターゲット攻撃とはとここ AES-128は完全に壊れていますか？
- @fgrieuご回答ありがとうございます。また、2 ^ {128}をクロックサイクルと見なすことができることも知りたいですか？実行時間はクロックサイクルでも測定できることがわかります。
回答
質問の大部分は要約されます。 to：
$ n $ -ビットセキュリティは特定の値に対して実際には何を意味しますかof $ n $ ？
TL; DR：優れた対称暗号と同じくらい安全 $ n $ ビットキー。
古典的な攻撃者に限定したとしても、より正確な定義は1つもありません。この答えがそうであるように、（量子コンピューターではなく）コンピューター。
一般的に受け入れられている意味の1つは、システムを破壊する「ステップ」の数がであると考えられていることです。 $ 2 ^ n $ ;より正確には、 $ s $ の「ステップ」でシステムを壊す確率が
対称暗号化の理論では、「ステップ」は通常、新しいキーを使用した暗号の1回の実行と見なされます。このように、キーが $ n $ ビットの理想的な暗号には、 $ n $ ビットのセキュリティがあります。ブルートフォースキー検索中。練習に移るとき、攻撃者はブルートフォースキー検索に縛られることはなく、「ステップ」の定義は、1つに必要なサブステップと数と計算コストが同等のサブステップの数になる必要があります。キーのサイズのプレーンテキスト用の新しいキーを使用した暗号の実行。この定義では、キーが $ n $ ビットの実用的な暗号は最大で
ハッシュに移行すると、ステップの定義は、必要なサブステップと数と計算コストが同等のサブステップの数になる可能性があります。新しいメッセージをハッシュする場合、ハッシュ出力のサイズ。
上記の多くの問題の1つは、メモリとメモリアクセスのコストをカウントするかどうかについて合意がないことです。計算コストで。ユーザーの観点から安全なことはそれを数えることではありませんが、それは攻撃者にとって最も重要である可能性があります。
非対称暗号化に関しては、「ステップ」の定義はさらに曖昧になります。 RSAのように。理論的には、「ステップ」は、暗号システムに使用される代数的構造の1つの計算である可能性があります。たとえば、RSAの場合、任意の整数pan class = “math-に対するモジュラー乗算
GNFS アルゴリズム。計算コストはモジュラー乗算とほとんど類似していない演算によって支配され、実際のコストはメモリとメモリへのアクセスによって支配されます。これにより、TL; DRのあいまいな定義が使用されます。
この80ビットセキュリティ暗号化スキームを攻撃する時間を計算する方法（次のようなもの）。ある種のCPUを使用する80ビットセキュリティRSA？
「80ビットセキュリティRSA」は、80ビットパブリックのRSAとして理解されるべきではありません。モジュラス
次のようになります： $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ ここで、 $ n $ はビット単位のセキュリティレベル、 $ k $ は、超最適化アルゴリズムを使用して適切な暗号を評価するためのCPUサイクル数の推定値であり、 $ p $ は、敵の成功の残りの確率です。視点によっては、 $ k = 1 $ （詳細を調べる手間が省けます）、 $ k = 32 $ （これは、汎用コンピューターを使用した優れた暗号に対する最善の攻撃よりもまだ少ないため）、またはそれ以上です。観点に応じて、 $ p = 1 $ （正当なユーザーの観点から最も賢明）、 $ pを取ることができます。 = 1/2 $ （ブロック暗号の場合は予想時間を生成します）、またはセキュリティマージンが必要な場合は $ p $ を小さくします¹。
たとえば、 $ n = 80 $ の場合、 $ k = 1 $ 、 $ p = 1/1000 \ approx2 ^ {-10} $ 、 $ \ text {Frequency} = 4 \ text {GHz} \ appendx2 ^ {32} \ text {s} ^ {-1} $ 、 $ \ text {Number-of-CPUs} = 1000 \ upperx2 ^ {10} $ 、 $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28}を取得します\ text {s} $ 、つまり約8年です。言い換えると、1000個のCPUは、技術的に時代遅れになるまで、80ビットの対称暗号に対して成功する可能性はごくわずかです。
一方、1000CPUはごく一部です世界中のCPUとビットコインマイニングは、ASICを設計し、大量に構築し、運用のエネルギーコストを維持する機能を備えた敵に対して、80ビット暗号ではもはや十分ではないことを決定的に示しています。 これを参照してください。
¹