（以下は細かい話。読まなくても問題を解くのには支障ないけれど）
　通常ＲＳＡ暗号化するときは、予備操作として文字順を入れ替えてから暗号化する、などの操作が加わることがありますが、それをすると人間の手で解読することが困難になる（し、長文がないと入れ替え順の推測ができない）ので、今回はやっていません。
　それから、本問と直接関係ないですが、通常のインターネット通信において、ＲＳＡ暗号は計算に時間がかかるので、もっと計算量が少ない共通鍵暗号を、データ本体の通信には使います。そしてその暗号の鍵を送るのに、ＲＳＡ暗号を使います。つまり、ＲＳＡ暗号で送られるデータは次の共通鍵暗号通信で使う暗号のカギ、なんですが・・・本問では、そういう設定にするとメンドクサくなりすぎるので、ＲＳＡ暗号でデータ本体が通信されている、という設定でお願いします。細かい話終わり。

これでいいのかな

挑戦者がいないですね・・・
個人的にはこの暗号、すごく好きなテーマなんですが・・・
ちょっと難解すぎる・・・のか・・・


まあとりあえず、少しずつ情報提供していこうかと。
最初は雑談というか雑学的なところからですが・・・

まず、暗号というと、大事なのは暗号方式と暗号の鍵。
暗号方式は皆が使うとバレてしまいますので、十分な多様性を持たせるために、
鍵で秘匿します。（それがないと、常に方式が一定なので、簡単に破れてしまいます）

しかし問題は、鍵をどう相手に渡すかということ。
暗号化と復号化で同じ鍵を使う「共通鍵暗号」方式だと、この問題が悩ましいんですね。

昔は、戦争前に相手に暗号の鍵をまとめて（直接会って）渡しておいて、順番に使って、使ったものは破棄するということをしていたようですが・・・途中で足りなくなって鍵を再使用したりすると、破られる危険性が高くなってしまうんですね。

そこで、暗号の鍵も、通信路を使って送りたいということを考えました。
公開鍵Ｅで暗号化した暗号文は、秘密鍵Ｄでしか復号化できない。
そして、暗号化の計算の逆計算（逆関数）が容易に計算できない。
そういう計算方法があれば、通信路を使って鍵を送る方式が成立するわけです。

これが、公開鍵暗号方式と言われるものです。ＲＳＡ暗号は最も広く使われている公開鍵暗号です。

公開鍵をＥ、秘密鍵をＤとします。
あとＮを法とした世界で計算を行うのでＮが必要です。
平文（ひらぶん：暗号化する前のデータ）をＡ、
暗号文（あんごうぶん：暗号化した後のデータ）をＢとすると、

Ｂ＝Ａ＾Ｅ　（mod　Ｎ）
これで暗号化します。そして、

Ａ＝Ｂ＾Ｄ　（mod　Ｎ）
これで復号化します。


公開鍵で暗号化した暗号文は、同じ公開鍵では復号化できません。
こんな仕組みを考えた人はスゴイと思います。

（つづく）

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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


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

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

手計算だと相当しんどいです。私は電卓でまず計算し、Excelでも確認しました。

解答＆解説です。

公開鍵　3,33
暗号文　29,21,3,20,14,1,3,24,21,11,9

ですから、ここから公開鍵Ｅが３、法Ｎが３３であろうと推測がつきます。
Ｎ＝Ｐ×Ｑ（ＰとＱはふたつの素数）ですから、
Ｐ＝３、Ｑ＝１１。

ここから、秘密鍵を求めるわけですが、
Ｄ＝（ｎ（Ｐ−１）×（Ｑ−１）＋１）／Ｅ
に当てはめていきます。
ｎは順に１、２、３と試行錯誤します。

とりあえず１から。
Ｄ＝（１×２×１０＋１）／Ｅ
　＝２１／３
　＝７

というわけで、Ｄは整数でなければいけないのですが、あっさり７だと分かりました。

ここからは、復号化の、単なる計算問題です。
29,21,3,20,14,1,3,24,21,11,9　のデータを順々に、７乗して３３で割った余りを求めます。

最初の１個だけ丁寧にやってみると、
29⁷=17249876309　（←すごい桁数ですね ）
で、これを３３で割った余りを求めます。
17249876309 = 17 (mod 33)　（←ヘンな書き方ですが、ふつうこう表記します）

ということで、29→17という変換が成立しました。これが復号化です。

あとのデータも同じ方法で、順に復号化すると、
17,21,9,26,20,1,9,18,21,11,15　と、なります。

さてなんでしょう？


とりあえず、１から２６までしか数字がないので、単純に発想して、アルファベットに置き換えてみましょうか。

quiztairuko
と、なります。

ＲＳＡ暗号と言えば、現代の暗号の中核をなす、極めて重要な暗号方式ですが、

その暗号方式が、公開鍵が分かれば、極論すれば秘密鍵が分かってしまう。
今回のように、簡単に計算できてしまうという、そんな数学的な根拠に立脚しているというのは、とても不思議で、場合によっては怖いことだと思います。

そういう話は、科学系のニュースなどでは概略は出てくるのですが、本当の意味が分かるためには、自分で暗号を解いてみた方がいいのでは・・・？なんて思って、問題を作ってみました。


公開鍵と秘密鍵は、数学的にペアなので、片方が決まればもう一方もほぼ自明な形で決まるんですね。じゃあヒミツにしている意味がないじゃないか。私は最初そう思いましたが・・・

桁数が増えていくと、素因数分解をすること自体が、極めて困難になっていくので、
３３なら誰でも、一瞬で３と１１に素因数分解できてしまいますが、これが現在の暗号強度では、１０進数でいうと、７７桁程度の素数をふたつかけ算して、大体１５５桁程度の数をＮとして用いるようです。

まあここまでの桁数になると、ＰとＱがなんだったのか求めることが、現実的なコンピュータ資源では不可能になってしまうため、計算の困難さを根拠にして、暗号の安全性が担保されていると、見なされているわけです。

おしまい。