TOUCH THE SECURITY Powered by Security Service G

コラム

2019.12.27

暗号を振り返る ――その2 単一換字式暗号

パーソルテクノロジースタッフの「Zライダー」です。

前回は「シーザー暗号」と呼ばれる暗号を紹介しました。シーザー暗号は確保できる「鍵空間」があまりに小さく、暗号アルゴリズムも単純なため、紙とペンという古典的な道具だけでも一定の労力と時間で総当たり攻撃が可能です。

シーザーが活躍した時代では通用した暗号も時代が進むにつれ安全ではなくなり、もう少し複雑な暗号が使われるようになります。今回は、単純なシーザー暗号よりもはるかに大きな鍵空間を確保できる、変換リストを利用した「単一換字暗号」について考えてみたいと思います。

1.単一換字式暗号

平文の文字に対して、必ず同じ暗号文の文字に変換される暗号を「単一換字式暗号」と呼びます。

例えば平文の「a」が、暗号文の「c」に ”必ず” 暗号化されるのであれば、それは単一換字式暗号です。前回紹介した「シーザー暗号」も単純な単一換字式暗号の一種ということが出来ます。

シーザー暗号は暗号化アルゴリズムが単純であり、使用される文字の種類の数しか鍵空間を確保できないことが強度の面で大きな問題点となっていました。それではシーザー暗号に工夫を加えて、より大きな鍵空間を確保できれば問題は解決するでしょうか?

すべての文字が同じアルファベット順だけシフトするという単純な暗号アルゴリズムではなく、変換リストを利用して、それぞれの文字が異なる文字数シフトするように工夫してみます。

英語アルファベット26文字のみが対象だとしても26×25×24×23×22…3×2×1 = 4000兆の1兆倍もの鍵空間を確保できることになります。シーザー暗号の鍵空間とは比較にならない大きさです。

これだけの鍵空間を確保できれば、総当たり攻撃による解読方法の実行は現実的ではなく、解読は困難であるように思えてきます。

2.Pythonで実際に暗号化してみる

変換リストを用いた単一換字式暗号を行うプログラムを「Python」で実装してみました。実際に暗号化を行い、結果を確認してみます。

後に解析作業を行うなどの便宜上、平文を英語小文字、暗号文を大文字で表現しています(入力値のエラーチェックなどは省略)。

♦ソースコード


# plain_char_list > 平文の文字リスト
# subst_char_list > 換字リスト
# plain_text > 暗号化対象の平文
def SubstituteCipher(plain_char_list, subst_char_list, plain_text):
    cryptogramList = []
    for char in plain_text:
        if char in plain_char_list:
            index = plain_char_list.index(char)
            cryptogramList.append(subst_char_list[index])
print('平 文: ' + plain_text)
print('暗号文: ' + ''.join(cryptogramList))

if __name__ == '__main__':
    plain_char_list = 'abcdefghijklmnopqrstuvwxyz'
    subst_char_list = 'ZYXWVUTSRQPONMLKJIHGFEDCBA'
SubstituteCipher(plain_char_list, subst_char_list, ‘ilovemotorcycles’)

♦実行結果


平 文: ilovemotorcycles
暗号文: ROLEVNLGLIXBXOVH

「ilovemotorcycles」が「ROLEVNLGLIXBXOVH」に暗号化されました。

平文の「i」が9文字分シフトされ、暗号文の「R」に暗号化されています。もしもこれが「シーザー暗号」であれば、平文の「c」「e」はそれぞれ「L」「N」に暗号化されるはずですが、上記の「変換リスト」を用いた「単一換字式暗号」では、それぞれ「X」「V」に暗号化されていることが確認できます。

3.頻度分析

英文素材から選んだある英文を、スペースを削除したうえですべて小文字に加工した文字列を前項のプログラムで暗号化したところ、以下の暗号文に暗号化されました。

変換リストを用いずにこの暗号文を解読する方法について考えてみます。暗号文が少し長いので、一見すると解読が困難に感じるかもしれませんが大丈夫です。むしろ暗号文が長いほど解読は有利になります。理由は後述します。

暗号鍵となる変換リストを総当たりで試すのは、前述したとおり膨大な鍵空間を試さなければならなくなるので現実的ではありません。

しかしいくら鍵空間が大きくても、単一換字式暗号は<平文のそれぞれの文字が、暗号文のどの文字に暗号化されるか>が決まってしまっているという大きな弱点を抱えています。そのため解読には「頻度分析」と呼ばれる手法が有効です。英文を例に考えてみます。

英語文における文字の使用頻度分布 via Wikipedia Commons

一般的に使用される頻度の高い文字や、文字の組み合わせの統計がデータとして存在します。

1文字単体としてみた場合、最も使用される文字は「e」であり、次に使用される文字は「t」、以下「a」「o」「i」「n」「h」と続きます。逆に使用頻度が低い文字として「z」「q」「x」「j」が挙げられます。筆者は「j」の使用頻度が低いということが意外に感じました。

また、2文字、3文字の組み合わせを考えた場合も、出現頻度の高い文字の組み合わせが存在します。3文字の場合「t-h-e」「i-n-g」「a-n-d」「i-o-n」の組み合わせの出現頻度が高く、2文字の場合は「t-h」「h-e」「o-o」の文字の組み合わせが高い頻度で出現します。

4.単一換字暗号を解読してみる

「頻度分析」の考え方を踏まえて、暗号文を解析してみましょう。

先程の英文素材を暗号化した暗号文を再掲します。

上記の暗号文の中で使用頻度が高い文字は以下になります。
V:48か所、R:33か所、M:29か所、G:25か所、L:22か所、S:19か所、Z:19か所

さらに、出現頻度が高い3文字または2文字の組み合わせは以下のとおりです。
G-S-V:9か所、R-M-T:7か所、S-V:11か所、G-S:10か所

単一換字式暗号において、暗号文の中で出現頻度が高い文字の正体は、はやり使用頻度の高い平文の文字である可能性が非常に高いことが予想できます。暗号文が長ければ長いほど、その傾向は顕著になりそうです。

上記の暗号文中で最も出現頻度の高い文字「V」を「e」と仮定し、さらに出現頻度の高い3文字の組み合わせ「G-S-V」をそれぞれ「G」=「t」、「S」=「h」と仮定します。「t」も「h」も英語文において使用頻度の高い文字であり、上記の暗号文中においても「G」「S」は使用頻度が高いので仮説が正しいことが期待できます。

次に出現頻度の高い3文字の組み合わせ「R-M-T」についても、復号結果は英文でtheの次に頻度が高い「i-n-g」と仮説を立てて、それぞれ「R」=「i」、「M」=「n」、「T」=「g」と仮定します。

これらの推測をもとに、暗号文の文字「G」「S」「V」「R」「M」「T」を置換します。

筆者は「OittOe」、「enLFgh」はそれぞれ「little」「enough」なのではないかと推測しました。

「O」→「l」、「L」→「o」、「F」→「u」と置換してみます。

可読性を高めるために、単語の区切りと思われる個所にスペースを挿入してみました。

単語の区切りが明確になると、暗号文に隠れた単語の文字がイメージしやすくなります。この時点でもおぼろげながら“ここの部分はこの単語ではないだろうか・・・?”と怪しげな部分が見つかるのではないでしょうか。

「UooW」「duIing」「theB」をそれぞれ「food」「during」「they」なのではないかと推測しました。「U」→「f」、「W」→「d」、「I」→「r」、「B」→「y」と置換し、単語の区切りだと新たに感じた個所にスペースを挿入してみます。

「Dith」「HuNNer」「Dinter」「Haid」をそれぞれ「with」「summer」「winter」「said」なのではないかと推測しました。仮定を元に暗号文を置換し、単語の区切りと思われる個所にスペースを挿入します。

ここまでくると暗号文の正体がわかってきました。この文章の正体は「アリとキリギリス」であるようです。

解読作業の途中で推測を誤り、作業がうまくいかないことも考えられますが、煮詰まったら手を戻して落ち着いて推測をし直せば、暗号鍵の総当たり攻撃を行うよりもはるかに効率的に解読を行うことが出来ます。暗号解読技術と解読対象の言語に習熟した人ならば、きっとはるかに効率的に解読を行うことでしょう。

5.まとめ

  • 鍵空間が大きくても暗号化アルゴリズムに脆弱性がある暗号は安全ではありません。
  • 単一換字式暗号はどの文字がどの文字に暗号化されるか決まっている弱点を抱えています。
  • 上記弱点により単一換字式暗号は頻度分析を利用した解読方法が有効です。
  • 暗号解読方法には暗号鍵の総当たり攻撃のほかにも、頻度分析と呼ばれる方法が存在します。
  • 暗号文は長ければ長いほど解読には有利です。

時代が中世に進むと、頻度分析を用いた解読法により変換リストを用いた単一換字式暗号も安全ではなくなり、「多表式」の変換リストに加えて暗号鍵の文字列を用いる「ヴィジュネル暗号」、単一換字式暗号の弱点を克服すべく、平文の同じ文字が出現個所によって異なる文字に暗号化する「換字式暗号」も開発されました。

更には換字式暗号も解読が進み、近代になると「エニグマ」に代表されるような「機械式」の換字式暗号やプログラム可能な電子計算機による「電子暗号」の時代に突入していくことになったのです。

次回は「ブロック暗号」と呼ばれる、その電子暗号について考えてみたいと思います。

    参考文献
  • 暗号技術入門 第3版 秘密の国のアリス 結城浩著 SBCreative
  • みんなのPython【第4版】柴田淳著 SBCreative

記事一覧に戻る