羊さんの換字式暗号

暗号

(一度非公開にした記事の再投稿です)

ここで扱う内容はすべて解読済みで，鍵も本人から公開されている*1が，もし鍵が公開されない場合でも現実的に解けるのかどうかを検証する．

概要

角巻わためさんのオリジナル曲『ゼロの足跡』には単一換字式暗号で暗号化された文が含まれている．単一換字式暗号では平文と暗号文の文字は一対一で対応する．また，ある言語で書かれた文章に含まれる文字の頻度は，どの十分長い文章でも一定になるため，単一換字式暗号の解読には頻度分析が有効である．しかし，ゼロの足跡に含まれる暗号文は24音しかなく，頻度分析の有効性に疑問が残る．本記事では非常に短い暗号文を用いた単一換字式暗号系の暗号文単独攻撃について考察する．

モチベーション

私の専攻は暗号理論で，普段は楕円曲線暗号などをやっているが，たまには原始に還って古典暗号を考えるのもなかなか趣があると思った．

前提知識

単一換字式暗号

単一換字式暗号とは文字集合\Sigma=\lbrace \text{a,b,c,...,x,y,z}\rbrace についての写像\Phi:\Sigma \rightarrow \Sigmaで定義される．

\Phiは全単射写像でなければならない．全単射写像\Phiには逆写像\Phi^{-1}が定義される． 単一換字式暗号の暗号化処理は^\forall\sigma\in\Sigmaに対して\Phi(\sigma)である． 復号処理は\Phi^{-1}を用いて\Phi^{-1}(\sigma)と表せる．

単一換字式暗号の鍵空間のサイズは|\Sigma|!である．

頻度分析

ある言語で書かれた文章に含まれる文字の出現頻度の分布は，文章が十分長ければほかの文章でも同じような分布が現れる．文字から文字へ移す全単射写像で文字を置換するシーザー暗号や単一換字式暗号では，暗号文中の文字の出現頻度の分布は，平文の文字の出現頻度の分布と似た形になるため，頻度分析が解読の助けとなることがある．

ゼロの足跡の暗号

ゼロの足跡の暗号文は(tu tu ke fa o i ni so si ku tu tu lu)(tu tu fa fa o e o li te fo ci)であることが明かされている．

暗号の素敵な歌唱部分はここの冒頭で聴くことができるが，フルで聴くとなお良い．

解読

前述のとおりゼロの足跡の暗号文は(tu tu ke fa o i ni so si ku tu tu lu)(tu tu fa fa o e o li te fo ci)である． 24音からなる短い暗号文だが，子音と母音の組もしくは母音単独でトークンになっていることから，平文は日本語であり，暗号化写像\Phiは\text{子音}\rightarrow\text{子音}, \text{母音}\rightarrow\text{母音}であると推測される．また，日本語に含まれない子音\lbrace \text{c, j, l, q, v, x} \rbraceは平文にも含まれていないと推測できるため，\Phi^{-1}の終域で\lbrace \text{c, j, l, q, v, x} \rbraceを考える必要がなくなる．この時点で，鍵空間のなかで考えるべき鍵の数は(21-6)!\cdot 5!=156920924160000 \lt 2^{48}となる．

暗号文は歌詞の一部なので，文字の出現頻度は平文の歌詞と似る可能性が高い．以下に平文歌詞と暗号文のそれぞれの文字の出現頻度を示す．

平文と暗号文のそれぞれの文字の頻度：平文歌詞は読みを平仮名に変換したうえで頻度を分析した

暗号文において最も頻度の高いtuは暗号文中ではtu tuと必ず二つ連続している．平文歌詞で特に出現頻度が高い子音と母音の組は\lbrace\text{き, こ, た, み, な, と, に, し, ...}\rbraceであり，且つ平文歌詞中で連続して出現するものは\lbrace\text{こ, す, で}\rbraceのみである．「ここ」という並びは平文中に4回含まれている．このことから，tu tuに対応する平文が「ここ」で，\Phi^{-1}は\text{t}\mapsto\text{k}, \text{u}\mapsto\text{o}である可能性が高い．これが正しいとして，この時点で解読できていない文字は子音が14個，母音が4個であり， 2^{41}\gt14!\cdot 4!=2092278988800 通りの鍵が可能性としてあり得る．

暗号文中で連続しているほかのトークンにfaがある．平文歌詞中で連続して出現する「こ」以外の文字は「す」と「で」である．faが「す」であると考えるとfa o iやfa o eといった暗号文が「す<母音><母音>」に対応することになるが，そのような並びは平文歌詞中には登場しないことからfaが「す」に対応するかどうかは分からない．一方，平文歌詞中に「で<母音><母音>」という並びは「であう」として頻出するため，faは「で」，oは「あ」である可能性が高い．o，faの頻度からみてもそれぞれ平文の「あ」，「で」に対応することは不思議ではない．この時点で解読できていない文字は子音が13個，母音が2個であり，2^{34}\gt 13!\cdot 2!=12454041600 通りの鍵があり得る．

現在までの解読が正しいとすれば途中までの復号は次のようになる．「(こ こ ke で あ i ni sa si ko こ こ lo)(こ こ で で あ e あ li ke だ ci)」ここまでで解読できていない暗号文中の子音は\lbrace \text{k,n,s,l,c} \rbraceの5つ，母音は\lbrace\text{e,i}\rbraceの2つまで減っていた．復号結果の候補は2^{19}\gt P(13,5)\cdot 2!=308880 通りとなる．

暗号文中のkeは「ここ」と「出会」に挟まれており非常に高い確率で格助詞と対応する．平文歌詞に出現する文字のうち，格助詞として挙げられるものは\lbrace \text{と, に, が, で, の, を} \rbraceであるが，ここからすでに判明している母音と子音が含まれたものを除くと\lbrace \text{に} \rbraceしか残らない．よって\text{k}\mapsto\text{n}, \text{e}\mapsto\text{i}, \text{i}\mapsto\text{u}とわかる．

現在までの復号結果は次のようになる．「(こ こ に で あ う nu sa su の こ こ lo)(こ こ で で あ い あ lu き だ cu)」現時点での復号結果の候補は2^{15}\gt P(12,4)=11880 通りある．これ以上の復号は頻度分析や日本語の文法からは期待できず，あとは経験と勘で解読する．鍵と完全な復号結果は以下から閲覧できる．

まとめ

24音という非常に短い暗号文でも同一の世界観の下で書かれた平文の標本があれば，頻度分析が一定程度解読の助けになることを確認した．実際に頻度の高いtuが同じく頻度の高い「こ」と対応している．また，同音の連続や母音の連続といった，暗号文中の特徴的な文字の並びも解読においては重要であることも確認した．

これらの重要な要素を十分に活用すれば非常に短い暗号文からでも平文に関する情報を多く得られることが判明した．攻撃者の経験と勘次第では完全な解読も可能だと思われる．

マドロミの暗号も解読したので是非見てくれよな． I also decoded a cipher in "Madoromi."

ouchiminh.hatenablog.com

*1:https://www.youtube.com/watch?v=aXPuJKMSs40&t=11651s