シーザー暗号を理解しよう

シーザー暗号を理解していきます。

シーザー暗号は、情報系の勉強したことのある学生なら知っているようなかなり有名な暗号です。理論も簡単です。張り切っていきましょう！

1.シーザー暗号って何ですか

シーザー暗号は、文字をずらすだけの単純な暗号です。かの有名なGaius Iulius Caesar(ガイウス・ユリウス・カエサル)が使ったとされる暗号です。
※wikipediaのリンク(ガイウス・ユリウス・カエサル)を置いておきます

シーザー暗号は、彼の名前をもじって名付けられました。情報系の授業でも取り上げられがちで、多くの学生が耳にしたことがあると思います。

2.シーザー暗号の暗号化

では、シーザー暗号の暗号化を理解していきましょう。

冒頭で軽く触れた通り、シーザー暗号はただ文字をずらすだけです。

まずは、アルファベットの列を思い浮かべましょう。

では、この列を右に3文字ずらします。

ずらすとこんな感じになります。

つまりは、aはxに、bはy、cはz、dはa…といった感じになります。実際にhelloは、khoorになります。

いい感じに暗号っぽくなりました！

分からなかったら、アルファベットの列を紙に書いて試してみましょう

3.シーザー暗号の復号

次に、シーザー暗号の復号です。

暗号化の反対は復号化ではなく、復号なのです。

シーザー暗号の復号は、左に3文字ずらすだけです。
では、先ほど暗号化した際のアルファベットの列を思い出しましょう。

この列を、暗号化のときと同じように右に3文字にずらします。

ずらすとこんな感じになります。

つまりは、dがa、eがb、fがc、…といった感じになります。実際に、khoorを復号するとhelloになりました。

4.シーザー暗号の暗号化と復号をまとめると

以上をまとめると、シーザー暗号は、

暗号化：左に3文字ずらす
復号：右に3文字ずらす

よく見ると、暗号化と復号のやり方はかなり似ていますね！

実は、3文字にこだわる必要はありません。何文字ずらしてもよいです。この何文字ずらすかは、暗号理論では鍵といいます。つまり、この鍵を得られれば、暗号化も復号もできるわけです。

もっと踏み込むと、暗号化と復号を同じ鍵で行うことを共通鍵暗号方式や、対称鍵暗号方式といいます。

5.シーザー暗号の鍵

ここで、シーザー暗号の鍵について考えましょう。先ほど、何文字ずらしても良いと言いました。では、1つの平文(暗号化する前の文章のこと)から、暗号文は何種類作ることが可能でしょうか？

答えは、26種類になります。

では、helloを例として確認してみましょう。

k = 0   : hello
k = 1   : ifmmp
k = 2   : jgnnq
k = 3   : khoor
k = 4   : lipps
k = 5   : mjqqt
k = 6   : nkrru
k = 7   : olssv
k = 8   : pmttw
k = 9   : qnuux
k = 10 : rovvy
k = 11 : spwwz
k = 12 : tqxxa
k = 13 : uryyb
k = 14 : vszzc
k = 15 : wtaad
k = 16 : xubbe
k = 17 : yvccf
k = 18 : zwddg
k = 19 : axeeh
k = 20 : byffi
k = 21 : czggj
k = 22 : dahhk
k = 23 : ebiil
k = 24 : fcjjm
k = 25 : gdkkn
k = 26 : hello
k = 27 : ifmmp
k = 28 : jgnnq
k = 29 : khoor
k = 30 : lipps
k = 31 : mjqqt
k = 32 : nkrru
k = 33 : olssv
k = 34 : pmttw
k = 35 : qnuux

上にk = 0 ~ 35まで載せてみました。よく観察してみましょう。

よく見てみると、k=0のときとk=26のときは、どちらもhelloです。同じようにk = 1のときと、k = 27のときの暗号文が一致しています。

つまり、暗号文は26でループしてそうです。

これは、暗号化する際にアルファベットの列をずらしていることに理由があります。アルファベットの列を26文字ずらすと元に戻ります。なので、いくらkを大きくしても26通りしか暗号文は生成されないのです。

6.シーザー暗号を解読する

シーザー暗号をあらかた見てきたので、最後に解読してみましょう。

総当たり攻撃

先ほど暗号文は26通りでした、つまり鍵も26通りしかないわけです。この鍵の種類をまとめた集合を鍵空間といいます。シーザー暗号の鍵空間のおおきさは26になります。

鍵空間の鍵を総当たりして解読しようとすることを、ブルート・フォース・アタック(総当たり攻撃)といいます。

シーザー暗号は鍵空間が26しかないのでこの総当たり攻撃が有効です。では、次の暗号を解読してみましょう！

暗号文： qffbu

k = 0   : qffbu
k = 1   : peeat
k = 2   : oddzs
k = 3   : nccyr
k = 4   : mbbxq
k = 5   : laawp
k = 6   : kzzvo
k = 7   : jyyun
k = 8   : ixxtm
k = 9   : hwwsl
k = 10 : gvvrk
k = 11 : fuuqj
k = 12 : ettpi
k = 13 : dssoh
k = 14 : crrng
k = 15 : bqqmf
k = 16 : apple
k = 17 : zookd
k = 18 : ynnjc
k = 19 : xmmib
k = 20 : wllha
k = 21 : vkkgz
k = 22 : ujjfy
k = 23 : tiiex
k = 24 : shhdw
k = 25 : rggcv

上に全通りの暗号文を示します。すると、k = 16にappleがあります。どうやら暗号文はappleをk = 16で暗号化したものみたいです。

鍵空間は小さいほど総当たり攻撃に弱く、簡単に解読されてしまいます。

現在使われている暗号の鍵空間は、シーザー暗号とは比にならない大きさです。

頻度分析

総当たり攻撃以外にもシーザー暗号を解く手法は存在します。
まずは、英語の文章を考えましょう。

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

「Caesar cipher」（30 November 2020, at 19:17 (UTC)）『 Wikipedia』。https://en.wikipedia.org/wiki/Caesar_cipher

英語版Wikipediaのシーザー暗号の冒頭を観察してみます。アルファベットだけを見てみると、eやaはよく出てきそうです。反対にxやzはなかなか含まれていなさそうです。シーザー暗号はただ文字をずらすだけなので、この分布は暗号文でも変わらなさそうです。

文字の出現頻度を分析することを頻度分析といいます。頻度分析はシーザー暗号のように、文字が決められた文字に変換される場合に有効です。

解読方法としては簡単です。まずは暗号文に対して頻度分析を行います。次に、英語の頻度分析の結果と比較します。英語の頻度分析の結果はWikipedia等にあります。最後に、頻度とのずれを求めます。それが鍵となります。

例を見てみましょう！

lq fubswrjudskb, d fdhvdu flskhu, dovr nqrzq dv fdhvdu'v flskhu, wkh vkliw flskhu, fdhvdu'v frgh ru fdhvdu vkliw, lv rqh ri wkh vlpsohvw dqg prvw zlghob nqrzq hqfubswlrq whfkqltxhv. lw lv d wbsh ri vxevwlwxwlrq flskhu lq zklfk hdfk ohwwhu lq wkh sodlqwhaw lv uhsodfhg eb d ohwwhu vrph ilahg qxpehu ri srvlwlrqv grzq wkh doskdehw. iru hadpsoh, zlwk d ohiw vkliw ri 3, g zrxog eh uhsodfhg eb d, h zrxog ehfrph e, dqg vr rq. wkh phwkrg lv qdphg diwhu mxolxv fdhvdu, zkr xvhg lw lq klv sulydwh fruuhvsrqghqfh.

まずは、暗号文に対して頻度分析を行います。すると、上位3つは以下の様になります。

1. h  : 51 文字
2. l   : 32 文字
3. w : 32 文字

英語に対して頻度分析を行った結果は、

1. e
2. t
3. a

となります。eとhの差は3、t と wの差は3文字となり、どうやら鍵は３の様です。実際に鍵3で復号すると、先ほどの英語版Wikipediaのシーザー暗号の冒頭の英文が得られます。

頻度分析は、今回のように暗号化された文章に対して有効です。しかし、文字の先頭に無意味な文字列を追加したり、ピリオドや空白だけは、ある文字に置き換えるなどをした場合は、頻度が乱れるので確実に解読できるわけではありません。

例1　無意味な文字列

eeeeeeeeeeeeeeeeeeeeelq fubswrjudskb, d fdhvdu flskhu, dovr nqrzq dv fdhvdu'v flskhu, wkh vkliw flskhu, fdhvdu'v frgh ru fdhvdu vkliw, lv rqh ri wkh vlpsohvw dqg prvw zlghob nqrzq hqfubswlrq whfkqltxhv. lw lv d wbsh ri vxevwlwxwlrq flskhu lq zklfk hdfk ohwwhu lq wkh sodlqwhaw lv uhsodfhg

例2　ピリオド、カンマをすべてxに置き換える

lq fubswrjudskbx d fdhvdu flskhux dovr nqrzq dv fdhvdu'v flskhux wkh vkliw flskhu, fdhvdu'v frgh ru fdhvdu vkliwx lv rqh ri wkh vlpsohvw dqg prvw zlghob nqrzq hqfubswlrq whfkqltxhvx lw lv d wbsh ri vxevwlwxwlrq flskhu lq zklfk hdfk ohwwhu lq wkh sodlqwhaw lv uhsodfhg eb d ohwwhu vrph ilahg

7.ROT 〇

シーザー暗号はROT k で表されることがあります。例えば、鍵が3の場合はROT3などです。有名なものとしてROT3、ROT13などがあります。

8.まとめ

今回は、シーザー暗号を題材にしてきました。シーザー暗号はとても単純な暗号ですが、暗号に入門する際に大切な概念が入っている暗号でもあります。これを機に暗号理論に興味を持ってくれたらいいと思います。お疲れさまでした。