暗号化アルゴリズムのセキュリティは、大きな数の素因数分解にどのように依存していますか?
たとえば、いくつかの数学プログラミング フォーラムで、Quadratic Sieve または General Number Field Sieve を使用すると、市販のハードウェアで比較的簡単に 256 ビットの数値を因数分解できると読んだことがあります。
これは、RSA、AES などのアルゴリズムのセキュリティを破ることができるとどのように解釈されますか? 数字をキーの長さだけ因数分解できれば十分ですか?
少し光を当てることができる暗号化と暗号化アルゴリズムに精通している人はいますか?
暗号アルゴリズムであるRSA は、数論、特に 2 つの大きな素数の乗算に依存しており、公開鍵と秘密鍵を区別するために因数分解が難しいという事実に依存しています。
これは、誰かが詳細を提供したYahooの回答に関する質問です。http://answers.yahoo.com/question/index?qid=20070125183948AALJ40l
それはいくつかの事実に依存しています:
n=p.q計算するのは簡単だが、逆にするのは難しい難しいのは大きな数を因数分解することではなく、それ自体が大きな素数である 2 つの大きな数を因数分解することです。これらの素数を見つけるのは難しいからです。
ブックマークをすばやく検索すると、次のことがわかります。rsa 暗号化の仕組みに興味がある場合は、rsa 暗号化の数学的根性。また、ここにもいくつかの説明があります-明確にするために、私の数値理論のメモを読み直してください。
どちらを行うか、DE = 1(p-1)(q-1) を見つけるか、むしろ、ユークリッドの最大公約数アルゴリズム、拡張バージョンを使用して解決します。
上記のすべてを考えると、T^E (pq) を取ると C が得られます。ただし、(T^E)^D (pq) を取ると、T が返されます。
AES は同じではありません。公開鍵暗号化ではありません。AES は 1 つのキーを取得し、それを暗号化と復号化の両方向で使用します。このプロセスは基本的に元に戻すのが非常に難しく、ハッシュに似ていますが、元に戻せるように設計されています。ただし、セキュリティのために大きな数を素数に因数分解することに依存していません。鍵の強度と、アルゴリズムから鍵を推測できないこと、または既知の平文とアルゴリズムから鍵を推測できないことに完全に依存しています。
ウィキペディアには、高レベルのAES に関する優れた記事があり、それがどのように機能するかを示す適切なリンクがあります。こことここを参照してください。私は特に後者のリンクが好きです。
暗号化アルゴリズムのセキュリティは、大きな数の素因数分解にどのように依存していますか?
欠落しているフレーズは「公開鍵」です。「公開鍵暗号化アルゴリズムのセキュリティはどうなっていますか...」
現代の暗号化には、対称 (秘密鍵) と公開鍵 (公開鍵と秘密鍵のペアを使用する) という 2 つの主要な暗号のカテゴリがあります。
各カテゴリ内で、鍵のサイズが比較的近いことがわかります。OpenPGP 電子メール暗号化で使用される RSA や DH/DSA などの公開鍵システムの場合、最近 (2010 年初頭) の一般的な鍵サイズは 1024 ビット以上です。これは、メッセージの暗号化と復号化に使用される適切なキーの数学的要件に関係しています。RSA の場合、要するに、2 つのランダムな大きな素数の因数を生成して乗算する方が、小さい因数を持たない非常に大きな数の因数分解に比べてはるかに簡単です。あなたが発見したように、非常に大きな数の因数分解は、ブルートフォースによってRSAを破るために必要な「問題」またはアプローチです。
Diffie-Hellman / Digital Signature Algorithm (DH/DSA) は、離散対数を計算する別の数学的問題に基づいています。
公開鍵と秘密鍵のペアの特性により、検索空間は大きな素数の因数に制限され、信じられないほどまばらになります。そのため、単純に非常に大きな数をすべて素因数分解しようとするよりも、はるかにインテリジェントにしようとするのが理にかなっています。
一方、AES、RC6、RC4、Twofish、DES、Triple-DES などの対称暗号では、これらのアルゴリズムは特定のビット長のランダム キーを使用します。任意の重要な (つまり、0x000...000 は不適切なキーの選択である可能性があります) ランダム キーが適しています。したがって、これらのシステムでは、アルゴリズム自体に対する攻撃がない場合、キー スペースをブルート フォースで検索するだけで (つまり、可能な 2^256 個のキーをすべて試す)、秘密キーなしでメッセージを復号化できます。どんなキーでもよいので、キーの密度は 2^256 です。
私は量子コンピューティング (理論的および実用的) を無視しています。主な理由は、a) 確固たる答えを出すことができない、および b) 計算の複雑さの多くの応用数学とコンピューター サイエンスをひっくり返す可能性のある大きなパラダイム シフトを表しているためです。その基本的な理解はまだ動く目標です。ああ、私の敵のほとんどはまだ量子コンピューターを持っていません。:)
これで、RSA と AES などの 2 種類の暗号システムの一般的な違いが説明されることを願っています。
Sidebar: Cryptography is a rich and complex topic, where the basics may be simple enough to understand, and even write a naive ("textbook") implementation, the complex subtleties of a secure implementation makes it best for programmers who are not cryptography experts to use high level crypto-systems including using well-known standard protocols to improve your chances that the cryptography of a system is not the exploitable flaw in a system.
AES は大きく異なり、AES は SPN (Substitution Permutation Network) を作成します。暗号化時に生成される多項式関数に基づいて、s-box (置換ボックス) を生成します。バイト レベルの置換とビット レベルの並べ替えを 10 ～ 14 ラウンド実行し、キーのビット長によってラウンド数とラウンド キーが決まります。
RSA は、計算処理が非常に難しい大きな素数の因数に基づいていますが、最初の暗号化は非常に簡単です。
RSAは因数分解で壊れます。実際、RSA は (非対称) 暗号化用とデジタル署名用の 2 つのアルゴリズムです。どちらも同じプリミティブを使用します。RSA には、2 つ (またはそれ以上) の異なる素因数の積である公開値 (モジュラス、しばしばnと示される) があります。nを因数分解すると、秘密鍵が明らかになります。nのサイズが大きくなると因数分解が難しくなる増加します。現在の記録 (今年初めに公開されたもの) は 768 ビット整数のものです。非常に賢い人々による大規模なコンピューティングとハードワークの4年間が必要でした. 同じ人々は、1024 ビット整数で同じスタントを試みる方法についてほとんど手がかりがないことを公然と認めています (最もよく知られている因数分解アルゴリズムの一部には、非常に多くの高速 RAM と 1024 ビット整数を必要とするものがあります)。途方もなく巨大なマシンを必要とする整数)。RSA のキーの長さに関する現在の推奨事項は、短期的なセキュリティでは 1024 ビット、長期的なセキュリティでは 2048 ビットです。RSA の計算コストも鍵のサイズとともに増加することに注意してください。そのため、正当な理由なしに非常に大きな鍵を使用することは望ましくありません。基本的な PC は、1024 ビット キーを使用して 1 秒あたり (およびコアあたり) 約 1000 個の RSA 署名を生成しますが、2048 ビット キーを使用すると 8 分の 1 になります。これはまだかなり良いです。
他の非対称暗号化アルゴリズムとデジタル署名アルゴリズムがあります。RSA に多少関連するのは、Rabin-Williams 暗号化アルゴリズムです。ファクタリングもそれを破ります。次に、離散対数に基づくアルゴリズムがあります (大きな素数を法とする数の乗法群): Diffie-Hellman (鍵交換)、DSA (署名)、El Gamal (暗号化)... これらのアルゴリズムでは、因数分解は直接的ではありません脅威; しかし、それらは数論の同じ部分に依存しており、離散対数の最もよく知られているアルゴリズムは、因数分解の最もよく知られているアルゴリズムと非常によく似ています (そして同じ名前を持っています: GNFS --一般的な数体ふるいとして)。したがって、因数分解の進歩は、離散対数にも光を当てる可能性が高い数論の進歩から生じると思われます。
離散対数アルゴリズムは他のグループに適用できますが、最も一般的なのは楕円曲線です。楕円曲線は因数分解の影響を受けません。因数分解が簡単になり、RSA がスクレイピングされ、DSA と Diffie-Hellman が間接的に危険にさらされるようになると、ECDH と ECDSA に切り替えることになります。標準と実装が存在し、展開されています。
「対称暗号化」、つまりハッシュ関数 (MD5、SHA-256...)、認証コード (HMAC、CBC-MAC...)、対称暗号化 (AES、3DES...)、乱数生成 (RC4.. .) および関連するアクティビティは、因数分解の影響をまったく受けません。これらのアルゴリズムでは、鍵は特別な構造を持たない単なるビットの集まりです。因数分解するものは何もありません。