アテネの裏で行われた暗号解読をめぐる死闘――「SuperCon2004」開催（2/2 ページ）

[西尾泰三，ITmedia]

RSA暗号方式とは

　RSA暗号方式とは公開鍵暗号方式の1つで、整数として符号化された文を整数の暗号文に変換するものである。

　RSA暗号方式における1つのRSAセットは、3つの数の組(n,d,e)で定まる。このうち、dを復号鍵もしくは秘密鍵といい、nとeを暗号鍵もしくは公開鍵という。この3つの数の背後には、大きな2つの素数p,qがあり、次のような関係が成り立つ。

n = p × q
φ = (p-1)×(q-1)
d × e ≡ 1(mod φ)

　これだけではd、eは一意に定まらないが、今回の問題ではe = 17（= 0x11）に固定しているため、それに対するdは、法nの下では1つに定まる。また、p、qには、50ビット以下の整数を選ぶため、nは100ビット以下の整数になる。

　RSAセットが決まると、暗号文を計算する暗号化関数、暗号文から平文を求める復号化関数を計算できる。

　さて、画像の暗号化について述べよう。画像は256×256の白黒画素だが、ここでは説明のため、その画素情報が配列im[256][256]に入っているものとする。つまり、各(i,j)、0 ≤i,j≤255に対し、im[i][j]は上からi番目、左からj番目の画素(0or1)を表わす。一方、eim[256][256] は、暗号化された画素情報が入る配列とする。以上より、各(i,j)の画素に対する暗号化の計算は次のように記述できる。

ci,j = i × 256 + j
mi,j = drsa(ci,j)
bi,j = mi,j の最下位ビット
eim[i][j] = im[i][j] ⊕ bi,j（注：演算⊕は排他論理和）

　復号化は、各(i,j)に対してbi,jを計算することに他ならない。復号化関数が分かっていれば簡単だが、それには与えられたRSAセットを破らなければならない。

　一方、暗号化関数ならば計算できるので、復号化関数を知らなくてもbi,jを求めることは可能である。すべてのmi,jの候補mに対し、ersa(m)を求め、ちょうどci,jとなるmをmi,jとすればよい。しかし2の100乗個の候補（正確にはn個の候補）について、すべてを調べるのは非常に困難なため、そこで今回は、各(i,j)に対して、mi,jの右hビットだけを0にマスクした情報（つまり、mi,jの上位100-hビットの情報）を、画素(i,j)に対するヒント情報hi,jとして与えることにする。これが前述のヒントファイルである。

終了間際、僅差での奇跡的逆転

　前評判も高く、本命と思われていた中国チーム「china」はその評判どおり、プログラム動作開始から2分半程度経ったところで99％以上の正答率の解答を出した。その後も徐々に正答率を高め、最終的には99.81％まで達した。

　これに対し、他のチームは5割から8割程度の正答率で、中国チームの優勝はほぼ決まったかに思われた。しかしドラマは残り1秒程度となったときに起こった。それまで2位だった浅野高校の「nomean」チームの後ろにつけ、70％台の正答率を出していた麻布高校の「nemui」チームが一気に中国チームを抜き、正答率99.92％でトップに立ったのだ。そのままタイム・リミットとなり、0.11パーセント、わずか71ピクセルの差で麻布高校チームの優勝となった。

優勝した麻布高校の「nemui」チーム

　計算結果は、誰がみてもわかりやすいように可視化され、正答率が高いほど、宇宙から見た地球の様子が紺と白の2色で鮮明に表示され、誤り部分は赤く表示された。

暗号解読結果の可視化

　こうして夏の電脳甲子園は盛況のうちにその幕を閉じた。しかし高校生たちの戦いは終わらない。参加者の多くが「まだ続けたかった」、「また来年も是非、参加したい」といった意見を出すなど、すでにその目は来年に向いているようだった。