t-hom’s diary

主にVBAネタを扱っているブログ…とも言えなくなってきたこの頃。

VBA アラン・チューリングの映画に触発され、シーザー暗号解読プログラムを作ってみた。

昨日借りてきた映画「イミテーションゲーム」のDVDを鑑賞した。

これは天才数学者アラン・チューリングの物語。
第二次世界大戦ナチスが使用したエニグマ暗号を解読した話である。

映画のストーリーとは関係ないが、チューリングは論文の中でこんな仮想マシンを考案した。

Wikipediaより
f:id:t-hom:20151115101731p:plain

・無限に長いテープ
・その中に格納された情報を読み書きするヘッド
・機械の内部状態を記憶するメモリ
で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。

・ヘッド位置のテープに情報を書き込む
・機械の内部状態を変える
・ヘッドを右か左に一つ移動する

上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。

このマシンは決められた手順にしたがって計算できるあらゆる問題を処理することができる万能マシンであるが、もちろん、無限に長いテープを現実に用意できる訳はないので、あくまで理論上のマシンである。

そして、チューリングマシンと同等の計算ができるプログラミング言語を「チューリング完全」という。
C言語Java、そしてもちろん、VBAチューリング完全である。

チューリングは現代のコンピューター科学の礎を築いた方々のひとりなので、プログラミングをする人なら彼に敬意を示し、この映画を見ておくのも悪くないんじゃないかと思う。実際、すごく面白かった。


さて、この映画に触発され、私もVBAで暗号解読プログラムを作ってみた。
といってもエニグマ暗号はハードルが高いので、簡単にできるシーザー暗号で。

シーザー暗号は以下の過去記事で紹介したが、アルファベットをずらしていくだけの簡単な暗号である。
thom.hateblo.jp

一見意味不明であるが根気よくやれば手でも解ける。
以下はとある英文をシーザー暗号で暗号化したもの。

Jujw Vjcqrbxw Cdarwp fjb j Karcrbq yrxwnnarwp lxvydcna blrnwcrbc, vjcqnvjcrlrjw, uxprlrjw, lahycjwjuhbc jwm cqnxancrlju krxuxprbc. Qn fjb qrpquh rwoudnwcrju rw cqn mnenuxyvnwc xo lxvydcna blrnwln, yaxermrwp j oxavjurbjcrxw xo cqn lxwlnycb xo jupxarcqv jwm lxvydcjcrxw frcq cqn Cdarwp vjlqrwn, fqrlq ljw kn lxwbrmnanm j vxmnu xo j pnwnaju ydayxbn lxvydcna. Cdarwp rb frmnuh lxwbrmnanm cx kn cqn ojcqna xo cqnxancrlju lxvydcna blrnwln jwm jacrorlrju rwcnuurpnwln.

プログラムで解くのも割と簡単で、全体を1文字ずつずらしながらよく使用される特定の単語(is, a, the, as, wasなど)が現れるのをチェックすれば良い。

まず、前回紹介したシーザー暗号の暗号化の方のプログラムを少し変えて関数にする。

Function シーザー暗号(平文, オフセット) As String
    暗号文 = ""
    For i = 1 To Len(平文)
        文字コード = Asc(Mid(平文, i, 1))
        
        Select Case 文字コード
            Case 65 To 90
                文字コード = 文字コード + オフセット
                余り = 文字コード - 91
                If 余り >= 0 Then 文字コード = 65 + 余り
                
            Case 97 To 122
                文字コード = 文字コード + オフセット
                余り = 文字コード - 123
                If 余り >= 0 Then 文字コード = 97 + 余り
        Case Else
            'Do Nothing
        End Select
        
        暗号文 = 暗号文 & Chr(文字コード)
    Next
    シーザー暗号 = 暗号文
End Function

そして、このようなフォームを作成する。
(実際に暗号文を張り付けているところ)
f:id:t-hom:20151115105223p:plain

プロシージャはこのようになっている。

Private Sub 解読ボタン_Click()
    Dim Words() As String
    Words = Split(InputBox("予測される単語をスペース区切りで入力してください。"), " ")
    For i = 0 To 25
        For Each x In Words
            For Each y In Split(シーザー暗号(TextBox1.Text, i))
                If x = y Then GoTo FOUND
            Next
        Next
    Next
    MsgBox "解読できません"
    Exit Sub
FOUND:
    TextBox1.Text = シーザー暗号(TextBox1.Text, i)
    MsgBox "解読しました"
End Sub

Private Sub キャンセルボタン_Click()
    Unload Me
End Sub

Private Sub 暗号化ボタン_Click()
    TextBox1.Text = シーザー暗号(TextBox1.Text, InputBox("オフセットを入力してください。"))
End Sub


解読部分は、
まず一番外側のループでアルファベットの数だけ回し、
中間のループで入力された単語の数だけ回し、
最後に内側のループで暗号文をズラして現れた単語の数だけ回している。

入力された単語と現れた単語が一つでも一致したらGoToでFOUNDに飛ばし解読結果を表示させる。

以下の部分が分かりにくいかもしれないので解説すると、

    Dim Words() As String
    Words = Split(InputBox("予測される単語をスペース区切りで入力してください。"), " ")

例えばInputBoxで"a the is was as"と入力するとこのようになり、

    Dim Words() As String
    Words = Split("a the is was as", " ")

Split関数でスペースで切ったものを動的配列Wordに代入している。
しかし大体の英文は「is」だけで解読できてしまったのでこの処理は要らなかったかもしれない。

注意点として、このプログラムは原文と調べる単語の組み合わせによっては間違った答えを返す場合がある。
たとえば、beという単語は回転していくとorという単語が現れるので、先に見つかった方がヒットしてしまう。

isはそうした単語が無いので大丈夫。
試しに次のループを回してみると、

Sub test()
    For i = 0 To 25
        Debug.Print シーザー暗号("is", i); " ";
    Next
End Sub

このように表示される。
is jt ku lv mw nx oy pz qa rb sc td ue vf wg xh yi zj ak bl cm dn eo fp gq hr

英単語として有効なのはisだけだ。


なお、今回例につかった暗号文の元の英文はWikipediaから引用した、アラン・チューリングについての解説である。

Alan Mathison Turing was a British pioneering computer scientist, mathematician, logician, cryptanalyst and theoretical biologist. He was highly influential in the development of computer science, providing a formalisation of the concepts of algorithm and computation with the Turing machine, which can be considered a model of a general purpose computer. Turing is widely considered to be the father of theoretical computer science and artificial intelligence.

映画イミテーションゲームに出てきたマシンによるエニグマ解読は、こんな簡単なものではないだろうけど、原理的には総当たりで現れた文字が単語として成り立つかを調べていく方式なので、大枠の考え方はこの解読プログラムと変わらない。

暗号解読の原理を理解してから映画を見るとさらに面白く鑑賞できるかもしれない。

当ブログは、amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、 Amazonアソシエイト・プログラムの参加者です。