OK、RSAの数学的動作についての私の理解は、それほど深くはないかもしれません。ですから、これがばかげている場合は、遠慮なく頭を叩いてください。
秘密鍵を生成するには、2つのランダムな大きな素数が必要です。これを正確かつ効率的に実行できるアルゴリズムはありませんが、99.99999 ...（バジリオン9）... 999％の素数の確率を持つ大きな数を生成できるアルゴリズムがあります。
私の質問は、不運の驚異的なストロークによって、キーを生成しているときに、素数生成アルゴリズムが非素数を生成した場合はどうなるでしょうか。それは、その不運なキーを使用するソフトウェアにどのように影響しますか？
編集：私は他の要因がこの問題に関する悪い結果のはるかに可能性の高い原因であることを知っています。これは純粋なオタク数学の好奇心です。
1.確率的素数性テストについて
コンピューターは信頼性の高い決定論的なシステムです。同じ入力に対して、同じアルゴリズムを同じ出力に対して実行します。それは常にそれをしますか？ほとんど。宇宙を歩き回る高エネルギー粒子のようなものがあり、通常は宇宙線として知られています。このような粒子がCPUの奥深くに隠されたトランジスタに当たると、しゃっくりを引き起こす可能性があります。基本的に、非常に一時的な方法で出力電圧が変化し、1クロックサイクルの間、トランジスタの出力が表すビットが反転します。
ここで、乱数を作成して素数性をテストする素数ジェネレーターアルゴリズムを実行しているコンピューターについて考えてみます。素数性テストはブール値を返す関数です。ある時点で、結果（true「プライム」のブール値false、非プライムのブール値）は、レジスターにコピーされた定数値になります。したがって、その結果が1ビットである数クロックサイクルのウィンドウがあり、フリップフロップ構造（6つのトランジスタで構成されています）に含まれています。
それでは、宇宙線がちょうど「正しい」クロックサイクルでその重要なビットを反転させ、プログラムに非プライムを実際にプライムと見なさせる確率はどれくらいですか？その確率は非常に低いです。私が言ったように、コンピュータは信頼できるシステムです。それにもかかわらず、その確率は大まかに見積もることができます。通常、特定のCPUでは3か月に1回宇宙線ビットフリップが発生すると考えられています。Core2 Duoプロセッサには、約2億9,100万個のトランジスタが搭載されており、（たとえば）2.4GHzで動作します。単一の「クリティカル」トランジスタがあり、そのトランジスタが単一のクロックサイクルに対してクリティカルである場合、宇宙線が非プライムから見かけのプライムに変わる確率は約1.8 * 10-24です。。これは非常に楽観的な下限です。実際には、多くのトランジスタが反転して素数テストの失敗を意味する可能性があり、ターゲットタイミングは数サイクルをカバーし、プライムジェネレータはプライム世代ごとに数十の非プライムを検査します。しかし、私たちが幸運であると考えてみましょう。
1.8 * 10 -24の確率は、決定論的であるかどうかに関係なく、すべての素数性テストに影響します。
通常のプライムジェネレーターは、 2〜100の「確実性」でミラーラビンテストを実行します（テストは50回実行され、毎回非プライムを見逃す確率は0.25以下です）。「100」は任意ですが一般的です。その確率は10-30より少し少ないです。これで、ミラーラビン素数が素数を非素数と宣言する確率は、宇宙線がトランジスタに当たってアプリケーションに素数を仮定させる確率の100万分の1未満であるのに対し、ミラーラビン素数はラビンテストはそうではないと言った。
簡単に言えば、素数ジェネレーターから非素数を取得する場合、これは、素数性テストの確率的性質ではなく、宇宙線などのハードウェアの問題が原因です。
宇宙線のために悪い素数を持つことは、実際には非常に幸運のストロークです。宇宙を疾走する小惑星が最終的にあなたの家に落ちる確率は、あなたがあなたの鍵を生成した後の最初の1秒間にあなたを焼却します。あなたのことはわかりませんが、個人的には、落下する岩に押しつぶされるよりも、RSAキーが悪い方が好きです。
2.悪いキー
RSAキーで非プライムを使用すると、不正なキーが取得されます。不正なキーは不正な署名を生成します。署名ジェネレーターは正しい長さのバイトのストリームを生成しますが、署名ベリファイアは署名が無効であると宣言します。注：実際には、署名は有効である可能性がありますが、確率はわずかです。RSAで「素数」pとqを使用することは、ミラーラビン検定と同様に、確率的素数判定に似ています。ただし、キーがすぐに誤動作することが判明する可能性があります。非対称暗号化でも同様の動作が見られます。
不正な署名の生成、またはRSA暗号化メッセージの復号化の失敗は、さらに別の宇宙線、またははるかにありふれた不正なRAMの発生によっても発生する可能性があることに注意してください。
結論として、RSAキーの不良を心配しているが、ハードウェア障害の可能性がはるかに高いイベント（宇宙線のために避けられないが、ありがたいことにあまり一般的ではない）について心配していない場合は、優先順位が間違っています。
あなたはすぐにそれに気付くでしょう：秘密鍵は間違っているでしょう。
pまたはqが複合の場合、公開鍵（通常は65537）を選択し、拡張ユークリッドアルゴリズムを使用して秘密鍵を計算します：65537 * x mod n = 1（ここで、n =（p-1）*（q-1））
ただし、x秘密鍵を使用するdecrypt（encrypt（m））！= m式：（m ^ 65537）^ x mod n！= m
iveは、rsaを次のように使用できることを学びました。
p=プライム q=プライム n = p * q phi（n）= phi（p）* phi（q）= p-1 * q-1
しかし、あなたが素数なしのファイを行うと、素数ではない-1になるので、上のステップでクラッシュするだろうと聞いた（しかし、理由は言えない）
真の素数がある場合、ショートカットはありませんが、ブルートフォースです。100％確信が持てない場合、攻撃者も確信が持てません。また、素数テストアルゴリズムに十分な自信を持っている可能性があるため、素数以外の数を持つリスクは、キースペース全体に対して1未満です。基本的に、あなたは自分の数が素数であることを統計的に確認することができます。言い換えれば、それが素数ではないと推測する確率は、正しいキーを推測するよりも高くなければなりません。キー生成時にある程度の忍耐が必要です。
大きなコンポジットを因数分解するための単純なアルゴリズムがあります-（常に疑われているように）。これは1989年以来、米国と同盟国によって知られています。また、素数を簡単に識別します。
また、RSAは知っています。