ｸｲｽﾞ大陸

少し解説を（つづきです）。

ＲＳＡ暗号の計算方法は、以下の通りです。

まず、公開しないふたつの素数ＰとＱを適当に決めます。
そこから【公開鍵】【秘密鍵】【法】のみっつの数値を作ります。

法としては、Ｎ＝Ｐ×Ｑを使います。
これは、暗号化、復号化のときにＮで割った余りを求める、
という計算を行う、という意味です。
公開鍵の一部のような感じで、Ｎは通信路を使って送ります。

そして、秘密鍵Ｄと公開鍵Ｅを求めます。
実は公開鍵Ｅは結構適当に決めてもいいんですが・・・

たとえば、本問ですと、公開鍵Ｅは３ですね。
実際の暗号通信でも３や６５５３７がよく使われるようです。

Ｄ＝（ｎ（Ｐ−１）×（Ｑ−１）＋１）／Ｅ
この式で、秘密鍵を求めます。

本当は厳密に言うと、普通の割り算ではなくて、
（Ｐ−１）（Ｑ−１）を法とした世界での計算なので、

ＤＥ＝１（mod （Ｐ−１）（Ｑ−１）)
という定義式になるのですが、ぱっと見て計算しづらいですね。

先ほどの式で、小文字ｎに、適当に正の整数を当てはめていき、
Ｄが整数になるものを見つけるわけです。

暗号破りをするときは、このｎについては初めから一発で求める
ことはできず、少しばかり試行錯誤する必要があります。


そして、暗号化と復号化の計算方法ですが、

平文（ひらぶん：暗号化する前の情報）のデータをＡ
暗号文のデータをＢとすると、

Ｂ＝Ａ＾Ｅ　（mod Ｎ）
で暗号化します。
ＡをＥ乗して、Ｎで割った余りを求める。

Ａ＝Ｂ＾Ｄ　（mod Ｎ）
で復号化します。
ＢをＤ乗して、Ｎで割った余りを求める。


本問では、【公開鍵】と【法】が晒してあるわけですから、ここからＰとＱを推測できてしまいます。すると、秘密鍵も分かり・・・暗号解読が成功！

と、なるでしょうか（いや、なります。既に正解者出ました）。