algorithm - RSA公開指数もメッセージを復号化しています

Question

私はRSA自分の数値で非常に単純なアルゴリズムを作成しようとしていますが、問題が発生しているようです。

素数 13 と 17 を選択したため、モジュラスは 221φ(221)=12∗16=192 になりました。次に、公開指数 r=19 を選択し、公開extended euclidean algorithm指数 s=91 を使用しました。(19⋅91=1 mod 192)

ここで、メッセージ 42 を次のように暗号化します42^19 mod 221=172。を使用して復号化する172^91 mod 221と、確かに元の 42 が返されます。ただし、指数 ( 172^19 mod 221) として 19 を使用すると、42 も返されます。どこで私は間違えましたか？

Answer 1

19 で 2 回累乗すると、19×19 = 169 (mod 192) で累乗されます。問題は、なぜ x = 42 に対して x ¹⁶⁹ = x (mod 221) であり、x の他の値が非常に多いのかということです。

221 を法とする乗法群に注目しましょう。221=13×17 なので、この群は 12×16 = 192 個の元を持ち、C ₁₂ ×C ₁₆ (C _nは n 次の巡回群) に同型です。

^{x 169 = x (mod 221) は x 168} = 1 (mod 221 ) と同等であることに注意してください。^{f(x) = x 168}を定義しましょう。

• 168 = 0 (mod 12) であるため、f は C ₁₂のすべての要素をニュートラル要素 1 にマップします。
• 168 = 8 (mod 16) であるため、f は C ₁₆のすべての偶数要素をグループの半分である中立要素 1 にマッピングします。

したがって、221 を法とする乗法群の半分については、f(x) = 1 (221 を法とする) です。

しかし x ¹⁶⁹ = x·x ¹⁶⁸なので、乗法群の半分はx ^{169 = x (mod 221) になります。}

乗法群に属さない 221 を法とする 29 個の整数を調べると、そのうちの 21 個についても合同が成り立つことがわかります。これはさらに調査することができます。したがって、合計すると、すべてのメッセージの半分強 (96+21 = 117) が指数 19 を使用して「復号化」されます。

これは、この RSA システムが壊れているということですか? 私はそうは思わない; 公開指数がメッセージの半分を解読できることを確認するには、221 の因数分解が 13×17 であることを知る必要があります。攻撃者は、ランダムな指数を選択することもできます。

更新:この問題は、別の公開指数を選択することで回避できますか?

192 = 2 ⁶ ×3 なので、指数は 2 や 3 の倍数にはならないので、e = 6k±1 でなければなりません。その二乗は e² = (6k±1)² = 36k² ± 12k + 1 = 12k(3k ± 1) + 1 です。コール ケースでは e² = 1 (mod 12) であることがわかります。

• k = 4j の場合、e² = 48j(12j ± 1) + 1 = 1 (mod 16)
• k = 4j+1 の場合、e² = (48j+12)(12j + 3 ± 1) + 1 = 48j(12j+3±1)+144j+36±12+1 = 5∓4 (mod 16) なので、 e = 6k+1 の場合 e² = 1 (16)、e=6k-1 の場合 e²=9 (16)。
• k = 4j+2 の場合、e² = (48j+24)(12j + 6 ± 1) + 1 = 48j(12j+6±1)+288j+144±24+1 = 1±8 = 9 (mod 16)
• k = 4j+3 の場合、e² = (48j+36)(12j + 9 ± 1) + 1 = 48j(12j+9±1)+432j+324±36+1 = 5±4 (mod 16) なので、 e = 6k+1 の場合 e² = 9 (16)、e=6k-1 の場合 e²=1 (16)。

したがって、このモジュラスの公開指数は 19 より優れたものはありません。復号化に公開指数を使用すると、メッセージの少なくとも半分 (e²=9 (16) の場合) で機能し、多くの場合、ほとんどすべてのメッセージで機能します。 (e²=1 (16) の場合)。