シーザー暗号


概要

シーザー暗号は古代ローマの軍事的指導者ガイウス・ユリウス・カエサル(英語読みシーザー)が使用したことから呼ばれる
最も知られた暗号方式の一つです。

参考
Wikipedia

常設CTFなどでは初歩の初歩として出されることがあります。

暗号化の方法

暗号化の方法はいたって単純で平文を決められた文字数(これが秘密鍵にあたる)だけ辞書順にシフトします。
例えば3文字ずらすのであれば

平文 暗号文
A => D
といった形になります。

暗号文 平文
D => A

復号の時は逆のことをやるので3文字前にずらします。
ROT13と言われる暗号方式は13字ずらしたものになります。

参考
ROT13 - Wikipedia

解読方法

この暗号の解読の仕方ですが26種類しかパターンがないので総当たりで簡単に平文は求まります。
ではこの時平文になったことをどのように機械的に判断すればいいでしょうか

今回は英文に焦点を当てますが考え方はほかでも利用できます。
英語は辞書を見ればわかる通りできやすい文字があります(eが最も使用されるなど)

ここから各文字の出現頻度の割合をあらかじめ求めておき
復号した平文に出てくる文字の出現頻度との差分を求め最も差分が少ないものが
正しく復号されたものとみなすといった形になります。

理論だけでは想像しづらいと思うので実際のコードをお見せします。

# -*- coding: utf-8 -*-

#i文字ずらしたときのシーザー暗号を解読する

#各アルファベットの出現頻度
general_frequency = [0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074]

# ある文章のアルファベットの出現頻度とgeneral_frequencyを乗算して出現頻度が一致したときの値
pmatch = 0.065

#ある文章のアルファベットの出現頻度をリストで返す
def freqanalysis(text):
    l = [0] * 26
    for i in xrange(len(text)):
        if 'A' <= text[i] and text[i] <= 'Z':
            c = ord(text[i]) - ord('A')
            l[c] = l[c] + 1
        elif 'a' <= text[i] and text[i] <= 'z':
            c = ord(text[i]) - ord('a')
            l[c] = l[c] + 1
        else:
            continue
    s = float(sum(l))
    l = [float(n)/s for n in l]
    return l

#アルファベットをi文字シフトしたときの文字を返す。アルファベット以外はそのまま
def shift(c, i):
    if 'A' <= c and c <= 'Z':
        return chr((ord(c) - ord('A') + i) % 26 + ord('A'))
    if 'a' <= c and c <= 'z':
        return chr((ord(c) - ord('a') + i) % 26 + ord('a'))
    return c

#出現頻度との一致具合を計算する
def freq(text, i):
    plain = [shift(n, i)  for n in text]
    fr = freqanalysis(plain)
    ret = 0
    for j in xrange(26):
        ret += general_frequency[j] * fr[j]
    return ret

#0~25文字ずらしたとき最も出現頻度が近いものを返す。
def findkeyletter(text):
    freqs = [abs(pmatch - freq(text, n)) for n in xrange(26)]
    return freqs.index(min(freqs))

with open('ciphertext') as fh:
    ciphertext = fh.read()

key = findkeyletter(ciphertext)
plain = [shift(n, key)  for n in ciphertext]
print "".join(plain)

ciphertextの中に復号したい文章を入れておき実行します。
findkeyletterで1~25文字ずらしたときの出現頻度の差分の中で最も差分の少ないずらす文字数を返し
文章をその文字数だけずらしたものを返します

この方法の難点は復号したい文章があまりに短い場合は正確に復号できないことです

この暗号方式は26種類の総当たりで破れますが
これを発展させたものにヴィジュネル暗号というものがあります。