シーザー暗号とは？Pythonによる生成・解読器の実装【辞書攻撃】

シーザー暗号（Caesar cipher）は、もっともシンプルかつ原始的な暗号です。

この記事では、シーザー暗号の仕組みについて解説し、Python言語を使って生成・解読器を実装します。

その際、辞書を活用して自動的に暗号を解く機能（辞書攻撃）も導入します。

シーザー暗号とは

アルファベットを１文字ずつ、数個ずらす

アルファベットの \(A-Z\) の並びと、それを数個ずつ順番をシフトしたものを考えます。

この表の対応関係にしたがって、もとのアルファベットを変換した暗号をシーザー暗号といいます。

たとえばシフト量が５の場合、 \(A\to F, B\to G,\ldots Z\to E\) という置き換えを行います。

例

シーザー暗号のメリット・デメリット

シーザー暗号のメリットとしては、暗号生成が簡単で速いことが挙げられます。

とくに、アルファベットの順番さえ知っていれば、複雑な変換対応表を用意する必要はありません。

逆に、容易に解読されやすいことが最大のデメリットです。

解読のためにはシフト量が鍵となるのですが、アルファベットは26文字しかないため、最大でも25通りのシフトを試せば解読できてしまいます。

さらに、もとの文章中にある同じ文字は、暗号文中でも同じ文字になるという弱点もあります。

暗号生成・解読器をPythonで実装する

ASCIIコードの変換

計算機であるコンピュータで文字列を扱うために、文字にはASCIIコードとして番号が振られています。

アルファベットの小文字とASCIIコードの対応関係を以下に示します。

ASCIIコードに準じた文字と数値の相互変換には、Pythonのord()関数とchr()関数を使います。

• ord()：文字列を数値に変換
• chr()：数値を文字列に変換

これを利用することで、アルファベットのシフトを足し算で簡単に実装できます。

original = "z"
cipher = (ord(original) - 0x61 + 5) % 26 + 0x61
# cipher = "e"

このコードでは、"a"に対応する0x61を始点にシフトしています。

また、シフトした結果が"z"をこえたときに先頭（"a"）に戻ってくることを、剰余% 26で表現しています。

小文字専用の実装

以上のことをふまえて、アルファベットの小文字のみに対応した生成・解読を行うシーザー暗号のクラスCaesarLowerを実装します。

class CaesarLower:

    def __init__(self, dictionary=None):

        pass

    def _shift(self, c, shift):

        c_ord = ord(c)
        if c_ord < 0x61 or c_ord >= 0x7b:
            return c
        else:
            return chr((c_ord - 0x61 + shift) % 26 + 0x61)

    def encode(self, origin, shift):

        return "".join([self._shift(c, shift) for c in origin.lower()])

    def decode(self, cipher, shift):

        return self.encode(cipher, -shift)

暗号の生成はencode()メソッドで行います。

解読にはdecode()メソッドを使いますが、これはencode()の逆として実装できます。

origin = "hello world"
print(caeser.encode("hello world", 5)) # "mjqqt btwqi"
print(caeser.decode("mjqqt btwqi", 5)) # "hello world"

なお、文字列に大文字が含まれている場合はlower()関数により小文字に変換して暗号化され、

アルファベット以外の文字はそのまま出力されます。

自動解読機能の実装

全通りを試す

decode()メソッドを使うためには、解読のための鍵（シフト量）を知っていなければなりません。

しかし、シフトのパターンは最大25通りしかないため、すぐに全通りを試すことができます。

def decode_all(self, cipher):

    return [self.decode(cipher, i) for i in range(1, 26)]

decode_all()メソッドでは、25通りの解読結果とシフト量の組をすべて出力します。

その後、25通りの結果を見比べて、正しそうなものを選択することになります。

辞書を使って正解を抽出する

辞書を使って全通りの解読結果を検証することで、意味のある文章のみを抽出することができます。

具体的には、解読結果から単語を抽出し、１つずつ辞書に存在するか照合します。

そして、辞書に含まれる単語をもっとも多く含んでいる文章を出力します。

これを実装するために、以下の記事で配布している英単語辞書（set）を使用します。

pythonで英単語辞書を作成する方法【フリー辞書ファイル】

単語リストは機械学習や暗号解読のために必須のデータセットです。Pythonの文字列処理関数や正規表現を用いると、文章から簡単に単語を抽出することができます。この記事では、著名な英文学24作品に登場する全英単語を抽出する方法を解説します。また、完成した英単語辞書をダウンロードすることもできます。

ushitora.net

2023.10.18

そして、CaesarLowerクラスを以下のように作り変えます。

import re

class CaesarLower:

    def __init__(self, dictionary=None):

        self.dictionary = dictionary

    def _shift(self, c, shift):

        c_ord = ord(c)
        if c_ord < 0x61 or c_ord >= 0x7b:
            return c
        else:
            return chr((c_ord - 0x61 + shift) % 26 + 0x61)

    def encode(self, origin, shift):

        return "".join([self._shift(c, shift) for c in origin.lower()])

    def decode(self, cipher, shift):

        return self.encode(cipher, -shift)

    def decode_all(self, cipher):

        return [self.decode(cipher, i) for i in range(1, 26)]

    def predict(self, cipher):

        if self.dictionary is None:
            raise ValueError("Dictionary is not set.")
        answers = []
        max_score = 0
        for i, d in enumerate(self.decode_all(cipher)):
            tokens = re.split("\W+", d.lower())
            score = sum([word in self.dictionary for word in tokens]) / len(tokens)
            if score == max_score:
                answers.append((d, i+1))
            elif score > max_score:
                answers = [(d, i+1)]
                max_score = score
        return (answers, max_score)

（※文章を区切って単語を取り出す方法についても、英単語辞書の配布記事でくわしく解説しています。）

CaesarLowerクラスを作る際に辞書（list, set, dict）を与えておくと、predict()メソッドを使って解答を予測できます。

なお、辞書から単語を検索するスピードは、listに比べてset, dictの方が圧倒的に速くなります。

以下に、鍵（シフト量）がわからない場合での自動解読の例を示します。

caeser.predict("bpm ycqks wvgf owjtqv rcuxa wdmz bpm tihg leizn")
# ([('the quick onyx goblin jumps over the lazy dwarf', 8)], 1.0)

（出典：Now I Know My ABC’s）

大文字・数字への対応

シーザー暗号を拡張する

一般的な文章には、アルファベットの大文字や数字も含まれるため、これらの文字もシーザー暗号の中に組み込むことを考えます。

この場合のシフトの仕方には、全体をまとめてシフトする方法

と、それぞれの文字種の中でシフトする方法

の２通りが考えられます。

あとのコードでは前者の方法でシフトしますが、実装をわずかに変えることで後者にも対応できます。

ASCIIコードを使った実装

ASCIIコードは、ほぼすべての文字と対応しているため、

（理論上は）ord()とchr()の関数を使うことで全文字種によるシーザー暗号をつくることができます。

def _shift(c, shift):
    return chr((ord(c) + shift) % 0x110000)

def encode(original, shift):
    return "".join([_shift(c, shift) for c in original])

（Pythonが扱えるASCIIコードは0x110000未満）

しかし、ASCIIコードには記号や改行コードも含まれるため、出力される暗号は取り扱いにくいものになります。

ASCIIコードを使わない実装

そのため、シーザー暗号を大文字や数字に対応させる場合は、以下のようにASCIIコードを使用しない実装をすると良いでしょう。

なお、数字（0x30～0x39）、アルファベット大文字（0x41～0x5a）、小文字（0x61～0x7a）のASCIIコードは連続ではなく、

その間に":", "?"等が含まれるので、ord()とchr()の使用は勧められません。

import re
import numpy as np

class Caesar:

    def __init__(self, obj=["number", "upper", "lower"], dictionary=None):

        chrs = []
        if "number" in obj:
            chrs.append([chr(i) for i in np.arange(0x30, 0x3a)])
        if "upper" in obj:
            chrs.append([chr(i) for i in np.arange(0x41, 0x5b)])
        if "lower" in obj:
            chrs.append([chr(i) for i in np.arange(0x61, 0x7b)])

        self.chrs = np.hstack(chrs)
        self.n_chrs = len(self.chrs)
        if self.n_chrs == 0:
            raise ValueError("Appropriate string type is not set.")
        self.dictionary = dictionary

    def _shift(self, c, shift):

        ind = np.where(self.chrs == c)[0]
        if len(ind) == 0:
            return " "
        else:
            return self.chrs[(ind[0] + shift) % self.n_chrs]

    def encode(self, origin, shift):

        return "".join([self._shift(c, shift) for c in origin])

    def decode(self, cipher, shift):

        return self.encode(cipher, -shift)

    def decode_all(self, cipher):

        return [self.decode(cipher, i) for i in range(1, self.n_chrs)]

    def predict(self, cipher):

        if self.dictionary is None:
            raise ValueError("Dictionary is not set.")
        answers = []
        max_score = 0
        for i, d in enumerate(self.decode_all(cipher)):
            tokens = re.split("\W+", d.lower())
            score = sum([word in self.dictionary for word in tokens]) / len(tokens)
            if score == max_score:
                answers.append((d, i+1))
            elif score > max_score:
                answers = [(d, i+1)]
                max_score = score
        return (answers, max_score)

Caesarクラスでは、作成時に数字（number）, 大文字（upper）, 小文字（lower）の中から好きなものを選んで対応させられるように実装しています。