ある RSA 暗号を用いて， 画素ごとに暗号化された 256 × 256 の白黒画素の画像を， 画素ごとに与えられるヒントを用いて解読する課題である． 具体的には，
暗号化された画像とヒント情報を入力とし， 3 分以内にできる限り元画像に近い画像を出力するプログラムを作成せよ，
という問題が，
今回の課題問題である(詳細は
プログラムの性能は，
審査で使用したデータに対し，
プログラムが出力した画像の正解率（正しく解読された画素数の割合）で評価した．
以下に，
プログラム作成の戦略，
今回審査に使用したデータ，
そして見事第１位となったチーム nemui（麻布高校，君，君）のプログラムについて，
簡単に解説する．
この RSA 鍵セットを用いて，
画像は 256 × 256 (= 約 6 万 5 千個）の各画素ごとに，
ある規則（
つまり，
解読プログラムは，
その各々の暗号を解読していかなければならないのだ．
それにはいくつかの戦略が考えられるだろう．
一般の RSA 暗号では，
暗号鍵を 500 ビットから 1000 ビットにして，
この暗号破りの計算に，
（たとえスパコンを使っても）数百年も必要となるようにしてある．
つまり「原理的に可能」でも「実際上は不可能」だろう．
一方，
今回の RSA 暗号では，
約 100 ビットの暗号鍵を使うことにして，
暗号破りが絶望的というほど難しくはしなかった．
しかし，制限時間の 3 分間以内で破ることができるかどうか，
出題者側でも，この点は確認していない．
そこで，各画素ごとにヒントを与えることにした．
ただし，ヒントにも難易がある．
詳細は省略するが，
ヒントごとに難しさの程度 h (h = 1 〜 100) が決まっていて，
難しさ h のヒントを用いて画素を解読すると，
最悪で 2h 回の「試し計算」が必要となるようになっているのだ．
難しさ h = 100 が，ちょうど「ヒント無し」に対応している．
すべての画素に簡単（h = 1）のヒントを与えることも可能だが，
この点は出題者側が自由にコントロールできる．
審査には下記表のような難しさ h の分布を持つヒント情報を用いた．
（注：プログラム作成中に配布した例データも，この分布を用いて作成．）
という訳で，
戦略としては，親切な（難しさ h の小さい）ヒントを持つ画素から，
ヒントを用いて解読していくという手があるだろう．
(* 注：推定計算時間は，スパコンで 64 CPU を使った場合，1 秒間に約 100 万回の
「試し計算」ができると推定して求めた．単位は秒．*)
どんなに強固な暗号方式を使っても，
その使い方が悪ければ「抜け穴」ができてしまって簡単に解読されてしまう．
今回の暗号化にも，
その抜け穴（大きな弱点）があったのである．
実は，
とてもお薦めできないような「安易な」方法で RSA 暗号を使っていて，
そのために抜け穴ができてしまったのである．
再び詳細は省略するが，
画素番号 123（画素には 0 〜 65335 の画素番号が付けられている）の画素と
画素番号 18 の画素の解読に成功すると，
その結果を使って，
画素番号 2214 (= 123 × 18) の解読もできてしまうのだ．
さらに言うならば，
このとき画素番号 24354 の画素の解読もできていると，
実は，
画素番号 11 (= 24354 ÷ 2214) の画素の解読も可能となってしまう．
これを「解読の伝播」と呼ぶことにしよう．
細かくは，
前者を，×伝播，後者を，÷伝播とでも呼ぶことにしよう．
元画像は，ランダムではない，何らかの画像であるという仮定のもとでは，
この補間法は無視できないほど，結構よく働く．
ただし，
我々もこの点は予想していて，
元画像には，結構複雑な絵を用いたのだが．．．
先にも述べたように，
審査に用いたデータでは，表のように，
ヒントの難しさを分布させた．
ただし，
「解読の伝播」を考えると，
6 万 5 千個の画素の中にも，
多くの伝播を引き起こす重要な画素（例：画素番号 2 の画素）とそうでない画素がある．
そうした重要な画素に，
低い難しさ h を持ったヒントが与えられると，
当然，有利になる．
逆に，
重要な画素には，低い h のヒントを与えないようにすれば，
意地の悪いデータ（ヒント情報）を作ることができる．
今回の審査では，
適度に意地悪く（？）なるようにデータを作成した．
具体的には，
伝播を使うと
h ≦ 18 程度までは何とか解読したとして，
なお，先にも述べたように，
これと同じ考え方で作ったヒント情報を，
プログラム作成時の例題データ（例データA, C）
として配布し，
審査でも同様のデータを用いるという情報も与えておいた．
画像は，例データのときに使用した画像よりも少し簡単だったので，
元画像に 5 % ほどのランダムノイズをかけたものを用いた．
つまり，ランダムに選んだ約 5 % の画素で，白黒を反転させたものを使った．
画像修復技術だけでは，95 % を上回ることができないようにしたのである．
（注：元画像と審査用元画像を比較してみよう．
地球の周囲に星のように見えるのがノイズ．）
一言でいえば，
このプログラムは，
解読の伝播を使って，
ヒントの難しさ h の低いところから，解けてない画素を順に解読していく，
という正攻法のプログラムである．
（最後の手段の画像の補間も行っている．）
ちなみに，
講習会のヒントで×伝播を教えておいたので，
それを使ったチームはかなりの数いたが，
÷伝播まで使った完全な「解の伝播」を使っているのは，
第２位のチーム china までだった．
今回は，このアイデアが勝負を決めたといえよう．
出題者側は，
この正攻法では並列化したとしても，
制限時間に解読できるのは h = 18 の難しさまでだろう，
と試算していた．
しかし，
チーム nemui は，
冪を 17 と固定したことをうまく使い，
また，並列化を効率よく行ったため，
ギリギリ，
178 秒で，h = 20 に隠されていた宝物を見つけることに成功したのである．
なお，
後で彼らに聞いたのだが，
例データを解析してみたところ，
解読の戦略
画像の暗号化には RSA 暗号方式が使われている．
正確には，
平文・暗号文ともに，
ほぼ 100 ビット長になるような 1 組の RSA 鍵セットが用いられる．
この鍵セットは画像ごとに異なる．
なお，鍵セットのうち，
公開鍵（剰余をとるときの n と暗号化するときの冪 e）は，
ヒント情報の一部として与えられる．
（注：冪 e は 17 に固定した．）
戦略１：RSA 暗号を破る！
RSA 鍵セットのうちの秘密鍵を用いれば解読は簡単にできる．
この秘密鍵だが，
暗号化に使う RSA 暗号の公開鍵から，
秘密鍵を計算することは原理的には可能．
これが，いわゆる RSA 暗号に対する「暗号破り」である．
したがって，
この暗号破りを行うことが戦略の１つとして考えられる．
戦略２：ヒント情報を使う
暗号破りが原理的には可能なのと同様，
与えられる公開鍵を使うと，
各画素ごとで，
何度も「試し計算」を行うことにより，
その画素の解読も原理的には可能となる．
ただ，
そのためには，
最悪で 2100 回もの「試し計算」が必要になる．
これもスパコンをもってしても実際上不可能な数である．
難しさh 難易度 h のヒントを与えた画素数 累計画素数
推定累計計算時間 推定計算時間（画素ごと）
1 351 351 0.0 0.00
2 352 703 0.0 0.00
3 352 1055 0.0 0.00
4 353 1408 0.0 0.00
5 354 1762 0.0 0.00
6 355 2117 0.0 0.00
7 356 2473 0.0 0.00
8 358 2831 0.1 0.00
9 361 3192 0.2 0.00
10 364 3556 0.4 0.00
11 369 3925 0.7 0.00
12 375 4300 1.4 0.00
13 382 4682 2.9 0.00
14 393 5075 6.0 0.01
15 406 5481 12.3 0.02
16 424 5905 25.6 0.03
17 447 6352 53.5 0.06
18 478 6830 113.1 0.12
19 518 7348 242.5 0.25
20 571 7919 527.6 0.50
21 641 8560 1167.7 1.00
22 733 9293 2631.7 2.00
23 854 10147 6043.1 3.99
24 1014 11161 14144.1 7.99
25 1224 12385 33701.5 15.98
26 1500 13885 81636.4 31.96
27 1863 15748 200706.7 63.91
28 2341 18089 499948.3 127.83
29 2970 21059 1259237.2 255.65
30 3798 24857 3201175.9 511.31
31 4888 29745 8199699.5 1022.61
32 6322 36067 21129597.3 2045.22
33 8209 44276 54708060.7 4090.45
34 10693 54969 142186314.4 8180.89
35 10567 65536 315081229.5 16361.78
戦略３：暗号法の弱点をつく：解読の伝播を用いる
難しさ h の低いものから順に総当り的に解読していったとしよう．
そのときに必要な計算時間を推定してみると（上記表の右欄），
解けるのは h=18 くらいまでにとどまってしまう．
そこまでの画素総数は約 6800 個，
つまり全体の 1 割程度しか解けない．
別の戦略が（も？）必要だ．
解読の伝搬
画素 123
画素 18 ==> 画素 2214
画素 24354 ==> 画素 11
この解読の伝搬を上手に使うことができれば，
たとえ 1 割のヒントしか有効に使えなくても，
かなりの数の画素を解読することが可能になるのである．
戦略４：最後の手段！？補間法
以上は，正攻法だったが，少しでも精度を上げようと努力した結果，
画像の補間を行うという戦略を思いついたチームもいくつかいた．
つまり，
もし，ある画素が最後まで解読できなかったとして，
しかも，周囲の画素がすべて 1 と解読できていれば，
その画素も多分 1 だろう，と推定して解読するのである．
審査に用いたデータ
審査に用いたデータ(上記表参照)について簡単に説明しておく．
（なお，ヒント情報はかなり大きなファイルになるので，
ヒントの難しさ h の分布だけ見るにはヒント情報縮小版を参照するとよい）．
h ≦ 16基本的な画素全部で 15 % 程度が解読可能
h ＝ 17, 18重要な画素が数個全部で 20 % 程度が解読可能
h ＝ 20極度に重要な画素が 1 個それ 1 個で 90 % 程度が解読可能
h ＝ 25極度に重要な画素が多数各 1 個で 90 % 程度が解読可能
となるようにヒントを与えた．
後は，
賢く探さないと有効な画素が見つからないようにヒントを配置したのである．
第一位のプログラム
見事第１位となったチーム nemui（麻布高校，小野嶋勇介君，林信吾君）の
プログラムについて，
簡単に解説する．
を確認していたそうで，
だからこそ「賭け」に出たのだと思われる．
単にプログラムを作成しただけでなく，
ここまで調べた点を高く評価したい．
