ベストアンサー
暗号解読の分野では、「 crack “および” break “。
最も簡単な意味で、次のコマンドでシステムのロックを解除しようとすると、パスワードが解読されます。そのパスワードのすべての可能な反復、ブルートフォースクラッキングとして知られている方法。パスワードの作成と使用を管理するルールを知っている場合は、その暗号に固有の時間/労力コストも事前に知っています。そこにあるすべてのアルゴリズムには、それを解読するために必要な計算の労力に既知の期待があります。
MD5やSHA-1（実際の例）のようなアルゴリズムは、ある種のアルゴリズムを見つけると壊れると言われます予想されるユニバースを減らす衝突（キー/パスワードの作成に使用される式のすべての可能な解決策）。
簡単にするために、WPS（Wi-Fi Protected Setup）の実際の例を紹介します。 ）。 WPSは、ユーザーがWi-Fiネットワークを簡単に保護できるようにするために作成されました。これは、ボタンを押すと要求元のユーザーとルーターの間で交換される8桁のPINで構成されていました。
システムの作成者は、予想される宇宙を事前に知っていました。8つの数字で1億の可能性があります。組み合わせ（10 ^ 8）。ただし、プロトコルの実装により、その数値は2つの4桁の組み合わせに分割され、別々に検証されました。
つまり、実際に試す必要があるのは10,000（10 ^ 4）+ 10.000（10 ^ 4）だけです。最悪の場合のシナリオでは、PINを解読するための組み合わせ。 1億の組み合わせの世界は、突然20,000の組み合わせにまで落ち込みました。アルゴリズムは事実上壊れています。次に、それをクラックすることを試みることができます-それが壊れていない場合と同じように-しかし、それが壊れているので、成功する可能性ははるかに高く、1億回ではなく最大2万回の試行が必要です。
これから導き出される結論：
解読と解読は別物です。解読された暗号は、安全でないことを意味するのではなく、ただ「今は簡単に解読できます。それによって保護されているものの価値によっては、破壊されても特定のシステムが死ぬわけではなく、当初の予想よりも安全性が低いことを理解しているだけです。」 p>
RSA-2048は、暗号を解読するために予想される組み合わせの数を本質的に減らす衝突を作成する方法を見つけた場合に壊れます。RSA2048は、他の暗号と同様に、ブルートフォースによってそのまま解読できます。
回答
RSAは、それ自体で、パブリックモジュラス（通常はセミプライム、またはランダムに選択された2つの大きなプライム）に対してわずかな攻撃しか行いません。 sを掛け合わせます）。基本的な算術を使用して秘密鍵の導出を可能にする、因数分解問題を解決するための最も効率的な古典的なアルゴリズムは、数体篩法（GNFS）です。このアルゴリズムは指数関数以下の時間で実行され、正しく実装された RSA-2048ビットシステムで使用することはできません。
も存在します。 Shorのアルゴリズムですが、一般的な攻撃者がRSA-2048にマウントすることはできません。量子コンピューターメーカーは、特にD-Waveが主導する寡占を実行しています。入手するには非常に費用がかかるだけでなく、それらを実行および保守するための専用の機器も必要です。数ビット以上を壊すのに十分な情報の永続性と能力を備えたチップは作成されていません。
前述のように、暗号システムは正しい実装なしには何もありません。 RSAのほとんどの実装では、公開鍵フィンガープリントアルゴリズム（通常はハッシュ）も利用されます。それに加えて、素数の因数分解を見つけることは、信じられないほどまれであり、成功率の点で統計的に無視できる1つのエクスプロイトで可能です。 Euclidが指摘したように、無限の素数がありますが、無限の素数があるだけでなく、特定のキースペース内にたくさんあります。 2つの係数がたまたま同じ素数を共有している場合、それらの因数分解を見つけるのは簡単です。線形時間で実行される最大公約数アルゴリズムを使用すると（これを表示しているデバイスで数ミリ秒以内に簡単に実行できます）、共通因子は次のことができます。が見つかったら、係数から除算して、他の2つの欠落している素数を生成します。これにより、両方のキーにアクセスできます。 RSAを正しく実装すると、素数を個別のキーに再利用することはなく、完全にランダムに選択されます。 2048ビットのキースペース内には多くの可能なモジュラスが存在するため、素数の長さ2048 select 2（または非標準のモジュラスを使用する場合は2より大きい）として記述できるため、2つのキーが2つの素数を共有する可能性はごくわずかです。 。言い換えると、キーサーバーからすべてのキーを取得し、それらすべてでGCDアルゴリズムを実行することは、単に時間の無駄です。