解読方法：様々な戦略}

画像の暗号化には RSA 暗号という代表的な公開鍵暗号方式が使われています． 256×256 (= 約 6 万 5 千個）の各画素ごとに， RSA 暗号の秘密鍵¹ を使って暗号化されています． 解読プログラムは， その各々の暗号を解読していかなければなりません． それにはいくつかの戦略が考えられます．

(脚注1: RSA 暗号を使うには， 公開してよい公開鍵と自分だけの秘密鍵が必要です． 審査に使う画像も， ある RSA 暗号で暗号化されていますが， その公開鍵はヒント情報の一部として解読プログラムに与えられます．)

戦略１：RSA 暗号を破る！

一般の RSA 暗号では， 暗号鍵を 500 ビットから 1000 ビットにして， この暗号破りの計算に， （たとえスパコンを使っても）数百万年も必要となるようにしてあります． つまり「原理的に可能」でも，「実際上は不可能」というわけです． 一方， 今回の RSA 暗号では， 約 100 ビットの暗号鍵を使うことにしました． そのため， 暗号破りも絶望的に難しくはありません． ただし，制限時間の 3 分間以内にできますでしょうか？

戦略２：ヒント情報を使う}

そこで，各画素ごとにヒントを与えることにしました． ヒントにも難易があります． 詳細は省略しますが， 難しさ h (h=1〜100) のヒントを使っての解読には 最悪で 2^h 回の「試し計算」が必要となるようになっています． （難しさ h=100が，ちょうど「ヒント無し」に対応します．） このヒントを使わない手はありません．

今回は， 6 万 5 千個の画素に対し， 難しさ h (h=1〜35) のヒントを 右のような割合で割り当てました． 計算時間は， 私たちが作った参考プログラムをもとに推定したものです． まともにh の小さいものから解いて行くと， 解けるのは h=18くらいまででしょうか． ちなみに， そこまでの画素総数は約 6800 個．全体の 1 割程度です．

戦略３：暗号化法の弱点をつく

具体的には， 画素番号 123（画素には 0〜65335 の画素番号が付けられています）の画素と 画素番号 18 の画素の解読に成功すると， その結果を使って， 画素番号 2214 (=123×18) の解読もできるのです． さらに言うならば， このとき画素番号 24354 の画素の解読もできていると， 実は， 画素番号 11 (=24354÷2214) の画素の解読も可能となるのです．

この「解読の伝搬」を上手に使うことができれば， たとえ 1 割しかヒントが有効に使えなくても， かなりの数の画素を解読することが可能になるでしょう．

戦略？：そして皆さんの戦略は