問題
正解
解説
ソリティア帝国とシャッフル王国…暗号化とパリティチェック、頻度分析、ハフマン符号化の融合問題でした。
問1
エ
各選択肢の暗号文を平文にできるか試してみましょう。
暗号文→平文
⓪♡♡♡♡→♡♡♡♡
①♡♠♠♡→♡♣
②♡♠♠♠→♡♢
③♠♠♡♡→♣♡
④♠♠♠♡→♢♡
⑤♠♠♠♠→×
オ
⓪× 暗号化したときに、1文字や3文字になる文字があるのであり得ます。
①× 平文が♠だけで構成される文である場合や♣♡のような場合は偶数になるのであり得ます。
②× 平文に♢がある場合はあり得ます。
③× ♡が平文中に多い場合はあり得ます。
④〇 ♡♠で終わることはありません。
⑤× 平文♢は♠♠♠に暗号化されるのであり得ます。
問2
いたずらが大好きな妖精が記号を♬に変えてしまうことがあるそうです。
「おまけ」（パリティビット）の条件は次のようになっています。
・暗号文中の♡の数が偶数なら、おまけとして♡を文末に加える。
・暗号文中の♡の数が奇数なら、おまけとして♠を文末に加える。
ク
条件から、どんな暗号文もおまけを加えると必ず♡の数が奇数になります。
ケ
1文字だけが♬になっている場合は、「暗号文は」「どんな暗号文もおまけを加えると必ず♡の数が奇数になる」という性質から、♡が偶数なら♬を♡に、♡が奇数なら音符を♠に書き換えればよいことが分かります。
コサ
2文字以上が♬になっている場合を考えます。
今回の例の♠♡♠♠♬♬♡♠という暗号文について考えると、表1から、次の4つの可能性があります。
1.♠♡♠♠「♡♡」♡♠
2.♠♡♠♠「♡♠」♡♠
3.♠♡♠♠「♠♡」♡♠
4.♠♡♠♠「♠♠」♡♠
今回は、おまけが♠なので、♡が奇数になるものを考えると、♡♠か♠♡のいずれかだとはわかるのですが、どちらなのかはわかりません。
2か所以上誤りがある場合についてはハミング符号など別の方法を考える必要があります。
また、今回は、♬という別の文字が登場しているので垂直パリティだけでも1ビットの誤りを検出&訂正ができますが、0か1かだけの場合については水平パリティも追加しておく必要があります。
問3
ソリティア王国の王子が暗号解読を試みているようです。
シス
王子は、送り込んだスパイから次の情報を得たそうです。
情報1 平文中の♡, ♠, ♣, ♢のどの1文字を暗号化しても、♡と♠だけを使った1～3文字のそれぞれ
異なる文字列になる。
情報2 平文中にある1文字を暗号化すると文字列x, ほかの1文字を暗号化すると文字列yになるとき, xの先頭から何文字を切り出してもyにはならない。例えば, 平文中の♡を暗号化した結果が♡♠♠の3文字だとすると, ♠, ♣, ♢のどの1文字を暗号化しても♡にも♡♠にもならない。
問題文 p.34
これはつまり、瞬時復号可能な符号であるということを言っています。
そのため、♡が♠1文字になると仮定した場合は、平文中の♠、♣、♢が♠から始まることはありません。
もし、平文♣が♠♡♡に暗号化されるとすると、暗号文の最初の1文字を読んだ時点で♡なのか♣なのか分かりません。
そのため、文頭が♠の暗号文はすべて文頭が♡の平文に対応するはずです…が、
表3の文頭が♠になっているところを見ると、
10% + 20% + 20% + 10%で計60%となっており、表2の♡出現割合40%と違うので、仮定した「平文中の♡を暗号化すると♠︎1文字なる」とは考えにくいです。
セ
次に王子は、「平文中の♡を暗号化すると♠︎♠︎の2文字になる」という可能性を検討したそうです。
しかし、表3で、♠︎♠︎が文頭の暗号文の割合は20% + 10%で30%となっており、表2の♡の割合40%と異なるのでこれも違うことがわかります。
色々試行錯誤した結果、最終的には、「平文中の♡を暗号化すると♡1文字になる」と確信したそうです。
ソタ
次に、平文中の♠︎を暗号化すると得られる文字列zについて考えます。
zは、情報2より、♠︎から始まるはずです。（空欄セ までに平文♡を暗号化すると♡になることがわかっているため）
しかも、zが文頭の暗号文の割合と文頭が♠︎の平文の割合が対応するようにしなければなりません。
表2の♠︎の割合は30%になっています。この割合になる♠︎から始まる組み合わせを探すと…
赤で囲ったⅠか、青で囲ったⅡであると推測できます。
よって、zは♠︎♡か、♠︎♠︎のどちらかではないかと考えられます。
チツ
最後はなんと、ハフマン符号化まで登場します。
表2の出現割合から、二分木を書いてみます。符号木の選び方やラベルの付け方には自由度があるのでいくつか考えられますが、今回は平文♡を♡に暗号化しているので以下の2つが考えられます。（見づらくて申し訳ありません）
方法A ♡を♡、♠︎を♠︎♡、♣︎を♠︎♠︎♡、♢を♠︎♠︎♠︎に暗号化する方法
方法B ♡を♡、♠︎を♠︎♠︎、♣︎を♠︎♡♠︎、♢を♠︎♡♡に暗号化する方法
知識がなくても解ける問題でしたが、過去の第二問と比べると、読む分量や記号を理解する時間等を考えても難化したのではないかと思います。
問題文最後には、「しかし王子は、暗号文には「おまけ」を加えてあり、そのままではうまく復号できないことを知らなかった」とあるので、まだまだ問題を作れそうな感じを残してあり、やはり情報関係基礎の作問をされている方々はすごいなと思いました。このような問題が作れるようになりたいですね。
