初心者が暗号の基礎と歴史を勉強して見た

秋のブログ週間2023 の4本目です。

こんにちは。金融グループ所属、新卒2年目の斎藤大樹です。

社会人になってから勉強する時間をなかなか取れていないなと思い、暗号の基礎と、暗号の進化の歴史を勉強してみました。
暗号をテーマに選んだ理由は、先日プロジェクト内の定期勉強会で先輩社員の方が暗号・認証についてお話してくれたのが興味深かったからです。

書籍の紹介

今回の勉強のお供は「Pythonでいかにして暗号を破るか」というソシム社出版の本です。
内容はどちらかというと古典暗号よりですが、暗号の基礎と歴史を学ぶにはもってこいです。
暗号だけでなく、Pythonの解説も豊富で、ソースコードも章が進むごとにレベルアップしていく構成になっているので、Pythonの初学者の方にもおすすめの一冊です。

暗号とは何か

本書によれば、暗号を構成する要素は「アルゴリズム」と「暗号鍵」の2つです。

暗号文は受信者が平文（暗号化される前の元の文章）を読み解けなければ意味がないので、出鱈目に作っていいわけではなく、どんな暗号文も一定のルール・決まり事をもとに作られています。このルールが暗号におけるアルゴリズムです。子供の頃に独自の暗号のルールを考え、暗号文を友達と交換して遊んだことのある方もいるのではないでしょうか。

一方、暗号鍵はその文字通り暗号文を解いて平文に戻すための鍵になります。鍵の形は数字だったり、文字列だったりと様々です。

ハッカーから身を守る上で重要なのは、ハッカーに「鍵」を知られないことです。ハッカーは暗号化のアルゴリズムは熟知しており、暗号を解く暗号鍵だけ知らないと考えなければなりません。鍵がいかにバレにくいかが、暗号の強固さの指標になります。

暗号の進化の歴史を辿る

それでは、本書で紹介されている暗号をいくつかピックアップしながら、暗号の進化の歴史を辿っていきたいと思います。また、本書のタイトルは「Pythonでいかにして暗号を破るか」ですから、暗号のハッキング方法も簡単に紹介していきます（※法に触れるようなものではございません）

シーザー暗号

アルファベットをシフトすることで、メッセージの各文字を別の新しいを文字に置き換える暗号です。シーザー暗号においては、アルファベットをいくつ右にシフトするかの数字が暗号鍵になります。表1に鍵10でにアルファベットが変換した例を示します。シフトした結果がZを超えてしまった場合はAに戻ります（ラップアラウンド）。例えば、鍵10のときに「FUTURE ARCHITECT」という文字列を暗号化すると、「PEDEBO KBMRSDOMD」になります。

表1：シーザー暗号の鍵10で暗号化した例

[object Object] undefined

シーザー暗号のハッキングは簡単です。英語の文章の場合はアルファベットが26個なので、考えられる鍵の総数は25個です。短い文章であれば、25通り試せばいいだけですので、手作業でも簡単に解読できそうです（このように考えられる鍵をすべて試すような解読の手法は総当たりと言います）。もし日本語の場合はアルファベット（ひらがな、カタカナ、漢字）の個数が多いので手作業での総当たりは難しそうですが、コンピュータがあれば短時間で解読可能です。

シーザー暗号の名前の由来は、「ブルータス、お前もか」の格言でおなじみのジュリアス・シーザーです。シーザーは2000年前の軍人ですから、こんな大昔から暗号という概念があったというのは驚きです。

乗法暗号とアフィン暗号

シーザー暗号では鍵の値だけアルファベットを加減算して文字を変換しましたが、乗法暗号ではアルファベットのインデックスに鍵の数をかけ合わせます。例えば、鍵5で文字Cを暗号化させたい場合、Cのインデックス2に鍵5をかけて、暗号化された文字のインデックス2×5=10を得ます。インデックス10に対応する文字はKです。

表2に、鍵5を使ってアルファベットA～Zを暗号化させた例を示します。シーザー暗号と同様に、暗号化後の文字がZを超える（インデックスが25を超える）場合はAに戻ります。このラップアラウンド処理の計算は「（インデックス×鍵） mod（アルファベットの個数）」で計算できます。例えば、鍵5のときに「FUTURE ARCHITECT」という文字列を暗号化すると、「ZWRWHU AHKJORUKR」になります。

乗法暗号を単独で使用すると、インデックス0の文字は暗号化後も同じ文字になってしまいます。そのため、乗法暗号で暗号化したのちに、シーザー暗号でさらに暗号化してやることで、より強力になります。このステップで作られた暗号はアフィン暗号と呼ばれます。

表2：乗法暗号の鍵5で暗号化した例

[object Object] undefined

26文字のアルファベットに対するシーザー暗号の鍵の個数は25個しかありませんでしたが、アフィン暗号では2つの鍵を組み合わせるため、鍵の総数は数百通りとなります。このように、アフィン暗号はシーザー暗号よりは遥かに安全になったものの、総当たりによるハッキングはまだまだ容易に出来てしまいます。

単一換字式暗号

シーザー暗号やアフィン暗号のように鍵の総数が少ない暗号は総当たりが容易です。その問題を解決するのが単一換字式暗号です。
単一換字式暗号では変換後の文字を、送信者が「AはYに、BはJに変えよう」という具合に、重複のないように任意に決定します（重複があると、復号の時に困ってしまいます）。「え、そんなのでアルゴリズムって呼べるの？」という気もしますが、26文字のアルファベットを暗号化する場合の鍵の総数は通りと膨大で、通常のコンピュータでは解読に数年かかります。

暗号化のポイントは、「鍵をハッカーにバレてはいけない」ことですから、鍵の数が多いということはシンプルながら非常に強力な暗号になります。単一換字式暗号は総当たり攻撃には強い一方で、頻度解析や単語パターン解析には弱く、ハッキングされやすいといった欠点もあります。

ヴィジュネル暗号

総当たり攻撃、頻度解析、単語パターン検索に強い、夢のような暗号が1553年に発表されました。これがヴィジュネル暗号（多表換字暗号）です。古典暗号の中では最も強力な部類で、19世紀まで解読されることがなかったようです。

ヴィジュネル暗号の鍵は単一英単語のような文字列で、この文字列が複数の1文字の鍵（サブ鍵と呼ぶ）に分割され、平文を暗号化します。各サブ鍵は整数（インデックス）に変換され、シーザー暗号の鍵として扱います。例えば、文字Cはシーザー暗号の鍵2に対応します（表1を参照）。

例えば、「FUTURE ARCHITECT」という文字列を鍵「DOG」で暗号化すると「IIZXFK DFIKWZHRZ」になります。
暗号化の仕組みを表3に示します。1文字目の「F（インデックス5）」は「D（インデックス3）」により右に3シフトするので「I（インデックス8）」に変換されます。次の文字U、Tも同様にO、Gを使って変換していきます。鍵「DOG」は3文字なので、4文字目はまたDに戻る…という要領です。シーザー暗号と同様、Zを超えた場合はAに戻ります。

表2：ヴィジュネル暗号の鍵DOGで暗号化を行う例

[object Object] undefined

ヴィジュネル暗号の鍵は長ければ長いほど安全です。
「DOG」のように3文字の鍵で暗号化する場合の鍵の総数は通りしかありませんが、もし20文字の鍵を使う場合の鍵の総数は約通りにもなり、総当たりでの解読は現実的ではなくなります。鍵の長さが1つ増えるたびに、鍵の候補数が26倍に増えるのが、ヴィジュネル暗号の強みです。

ヴィジュネル暗号の弱点は、鍵に周期性があることです。例えば、「THE CAT IS OUT OF THE BAG」を鍵「SPILLTHEBEANS」で暗号化すると「LWMNLMPWPYTBXLWMMLZ」になります。太字で記したように、暗号文で文字列LWMが2回反復しているのが分かります。これは、平文の単語THEが同じ鍵SPIで暗号化されたからです。例文は簡単な例ですが、ヴィジュネル暗号ではこのように同じ文字の反復が現れるので、この反復の間隔を調べることで鍵長を推定出来ます。鍵長の推定が出来たら、頻度分析にかけていき、鍵の候補をさらに絞り込んでいきます。鍵の候補が絞り込めれば、後は総当たりにかけてやることで、この強力な暗号も解読されてしまいます。

ワンタイムパッド暗号

ヴィジュネル暗号の弱点を補い、解読不可能となった暗号がワンタイムパッド暗号です。ワンタイムパッド暗号は次の3つの条件を満たします。

ヴィジュネル暗号において、鍵は暗号化するメッセージと同じ長さを持つ。
鍵は真にランダムである
鍵はメッセージの暗号化に一度だけ使用し、再び使用しない

鍵長がメッセージ長と等しい場合、平文の各文字にサブ鍵が一意に使われ、各文字は同等の確率で任意の文字に置き換えられるため、周期性が失われ頻度分析にも強くなります。

例えば、「FUTURE ARCHITECT」の文字列を鍵「KLABIITPFQWZLGN」で暗号化すると、「PFTVZMTGHXESPIG」になります。「FUTURE ARCHITECT」は15文字なので、鍵の総数はです。実は、ハッカーがこれを総当たり出来る強力なコンピュータを持っていても、ワンタイムパッド暗号は解読できません。それは、どの暗号文でも、すべての平文が等しく候補となりうるためです。

どういうことかというと、例えば上で得られた暗号文「PFTVZMTGHXESPIG」を鍵「KLABIITPFQWZLGN」で復号すれば「FUTURE ARCHITECT」になりますが、別の鍵「MXYRIULBZVEZHUT」で復号すると、全く別の単語「DIVERSIFICATION（多様化）」になります。

多くの暗号が解読されやすい理由は、分かりやすい英語に復号する鍵が通常1つしかないからですが、ワンタイムパッド暗号では全く異なる2つ以上の平文から同じ暗号文が得られてしまうため、ハッカーがいかに強力なコンピュータを持っていようが元のメッセージがどれであるか判定することはできません。

公開鍵と秘密鍵

暗号の歴史を追ってきて、絶対にハッキング不可能な暗号が出来ることが分かりました。しかしこれで終わりではありません。送信者が暗号文を相手に送るとき、受信者が暗号文を解読できるように鍵を一緒に渡さなければなりません。暗号がどれだけ強力であっても、鍵ごとハッキングされたらどうでしょうか。メッセージは簡単にハッカーに知れ渡ってしまいます。

この問題を解決するのが公開鍵暗号方式です。今まで記述した暗号では、暗号化と復号に同じ鍵を使っていましたが、公開鍵暗号方式では暗号化と復号に異なる鍵を使います。そして、暗号鍵で暗号化されたメッセージは、それと対となる復号鍵だけで復号できます。暗号鍵ではメッセージを解読できず、世界中で共有できるので公開鍵と呼ばれています。一方で、復号鍵は誰にもバレてはいけないので秘密鍵と呼ばれます。

例えば、AがBにメッセージを送りたいとき、AはBから公開鍵を受け取り、その公開鍵を使ってメッセージを暗号化します。公開鍵はメッセージを復号できないので、他の人にバレても問題ありません。
BはAから暗号化されたメッセージを受け取ると、自分の秘密鍵でそれを復号します。Bだけが、Bの公開鍵で暗号化されたメッセージを復号できる秘密鍵を持っているのです（秘密鍵は他の人にバレてはいけません）。

BがAに返信したい場合、今度はBがAの公開鍵を使ってメッセージを暗号化します。AはBから受け取った暗号文を、Aの秘密鍵を使って復号します。

このように、公開鍵暗号方式では、メッセージをハッカーに傍受される心配をせずにメッセージを交換できます。