Diffie-Hellman鍵交換で素数が使用された理由

Question

私はそれを検索しましたが、私の答えは見つかりませんでした。 Diffie-Hellman鍵交換アルゴリズムで は

2^8のmod

などの操作に使用（％）素数

私のクエリは素数を使用して代わりに他の任意の数を使用した理由は何ですか？ 可能であれば、私に実生活の例を与えたり、説明が明快な例を教えてください。

Answer 1

素数は、より小さい要素に分解されないため、/ 2または/ 3または/ 4または/ 6で分解する12を使用するよりもはるかに難しくなります。素数7は12未満であるが、因数は7であるため、攻撃ベクトルは少なくなる。これは劇的な過度の単純化ですが、うまくいけば少し助けてください。

2^X MOD 12

にのみ1以上の任意のxに対して、2つの可能な値があります：これは、共有鍵を生成するために使用されるので、4または8ここ

具体例です同様の方法で、あなたは同じ2つの可能性に終わります。言い換えれば、ベースとモデムが2と12（会話を聞いているすべてのコンピュータがピックアップできる）であることを知ると、共有秘密暗号化キーは2つの可能性のうちの1つにしかなりません。メッセージの復号化を決定するのは2つの単純な操作だけです。今度は首相のmodを見てみましょう：

2^Xモッズ13

これは、x> 1のための12個の異なる可能性があります。また、生成可能な12の異なる共有キーもあります。したがって、このプライムモジュラスに基づいてメッセージを復号化するには、mod 12の例よりも6倍の計算能力が必要です。

2^x mod 14には4つの可能性があります。

2^X MOD 15^4

X = 3の後に完全に1つの可能性に

2^X MOD 16の崩壊（DH要件に適合する塩基を選ぶことが重要である理由である）

2を有していますx mod 17は...あなたは16の可能性を推測しています！素数は冷たいではありませんか？ :)

したがって、係数数の因数分解能は、暗号化されたメッセージの分解能と関係があります。