はじめに
こんにちは。うにぎりです。
これは卓ゲ箪笥 Advent Calendar 2024
の7日目の記事ですが、内容はボードゲームやTRPGに関係ありません。
去年
のような、好きなことを喋る記事です。
今年は暗号について好き放題喋ります。
日程枠が1つだけ空いているので適当な記事で埋めようというモチベーション故に、推敲はほぼしないし口語で書きますしファクトチェックはしません。
なんか同じ研究室の人が酒飲みながら適当言っとるわくらいの気持ちで読んでいただけると嬉しいです。
前提
暗号とは
まずは言葉の定義から始めましょう。定義は重要。
暗号とは文章をいい感じに読みにくくする手法の事です。
不特定多数に読まれたくない文章等がある時、大きく分けて2種類の対策方法があります。
ステガノグラフィーとクリプトグラフィーです。
ステガノグラフィーは、文章の存在を隠す手法です。
みかん果汁で紙に文字を書いた後に乾かすと、一見何も書いてない紙に見えるのに火で炙ると文字が浮かび上がる的なやつです。
クリプトグラフィーは、文章をそのままでは読めないようにする手法です。
読めないようにした文章自体が存在することは不特定多数に知られてしまいますが、読むためにはその文章を読める形に戻す方法を知っている必要があります。
元の文章を平文、読めないようにした文章を暗号文、読めないように加工する処理を暗号化、元の文章に戻す処理を復号と呼びます。
また、復号方法を知らない第三者が暗号文を平文に戻そうとすることを解読、そのような事をする第三者を攻撃者とこの記事では呼ぶことにします。
日本語で暗号と呼ばれているやつはクリプトグラフィーです。
余談ですが、暗号文から平文に戻せないようなものは暗号ではありません。
つまり、ハッシュ値は暗号文ではないということです。ハッシュとは何かは後で書きます。
暗号の種類
暗号も大きく分けて2種類あります。
コードとサイファーです。
コードは、ある文章等を別の言い方で表現したものです。
我奇襲に成功せりをトラトラトラと言い換えたり、飲食業でお手洗いに行くのを4番と言い換えたりするやつです。
サイファーは、平文の内容に関わらず一定の手法で読みにくくしたものです。
コードはあらかじめ取り決めた情報以外は表現できませんが、サイファーなら色々な情報を表現できます。
ちょっと例が難しいのですが、「あ」を1、「い」を2、「う」を3という風に順番に数字を割り当てるというルールを作っておくと、「あいうえお」や「こんにちは」などの色々な文章を数字で表現できるみたいな感じです。
この記事では基本的にサイファーを扱います。
いくつかの暗号の紹介
シーザー暗号
必要な言葉の定義が終わったので、そろそろ実際の暗号手法について喋ります。
シンプルなものから始めます。
手法がシンプルで古くから存在し、とても有名なのはシーザー暗号です。
カエサル暗号やシフト暗号とも呼ばれたり、英語だとROTと呼ばれたりします。
やり方はシンプルで、各文字をN文字分ずらします。
仮に1文字分後ろにずらすケースで説明すると、aを1つ後ろにずらしてbに、bを同様にずらしてcに、cを同様に…という処理をします。
平文が abcde の場合は暗号文は bcdef になり、 Hello, I'm Unigiri. Glad to have you here. は Ifmmp, J'n Vojhjsj. Hmbe up ibwf zpv ifsf. になります。長文になるとだいぶ暗号文っぽく見えますね。
この手法の弱点としては、頻度分析と全探索に弱い点です。
シーザー暗号では、ある文字は常に特定の文字に変換されます。1文字後ろにずらすケースでは a は常に b になります。
つまり、例として平文中に a が20回登場する場合、暗号文中に b が必ず20回登場します。
各言語にはたくさん使われがちな文字というものがあるので、この文字がたくさん登場しているということはおそらく元々はこの文字で…みたいな感じで推測しながら解読できます。
また、シーザー暗号で暗号化されているということが分かっていれば、全パターン調べれば必ず解読できます。
英語の場合はアルファベットが26文字なので、1つ後ろにずらすやつを試し、次は2つずらし、次は3つ…というのを26パターン全部試せば、26個の復号結果の中に必ず平文があります。1
そして一般的に平文は意味が通る文章になっているので、どれが平文かは見ればすぐに分かります。
総合すると、暗号手法としては使いやすいけど解読されやすい部類になります。
ヴィジュネル暗号
シーザー暗号の弱いところは、ずらす文字数が常に一定であるということです。
じゃあ1文字目は後ろに1文字ずらして、2文字目は5文字ずらして、3文字目は9文字ずらして…みたいにずらす数をバラバラにすれば解読されにくいのでは！？というのがヴィジュネル暗号の基本的なアイディアです。
ただし完全にランダムにずらすと復号できなくなるので、ずらし方をあらかじめ決めます。
例えば1文字目は5文字分、2文字目は10文字分、3文字目は15文字分ずらすと決めて、4文字目以降は5, 10, 15, 5, 10, 15, … とずらす文字数をループさせるという感じにします。
最初の3文字目まで決めたルールを鍵と呼びます。
この方式の強みと弱みはここでは詳しく説明しませんが、解読しようとする第三者は鍵の長さを知らないということが重要な点になります。
詳しくはヴィジュネル暗号またはヴィジュネル方陣で調べてください。
ちなみに、ヴィジュネル暗号の解読方法を考案したのはチャールズ・バベッジです。すごい。
エニグマ
シーザー暗号とヴィジュネル暗号は、紙とペンがあれば暗号化や復号が簡単にできます。
しかし時が経つにつれ人間は機械を使うようになり、計算機というものも登場します。
これらを使うことにより、紙とペンでは時間がかかりすぎるような複雑な暗号化手順を扱えるようになります。
その代表例がエニグマです。
エニグマというのは暗号の名前ではなく、暗号化と復号をする機械の名前です。
機械の中には歯車や抜き差しできるプラグなどが入っており、これらを動かすことにより複雑な暗号化を行います。
基本的なアイディアとしてはシーザー暗号とそこまで変わらず、ある文字を別の文字に変換するだけなんですが、変換ルールがとても複雑なので解読の難しさはシーザー暗号やヴィジュネル暗号の比ではありません。
エニグマは第二次世界大戦中のナチス・ドイツで使われました。
ドイツ軍内での通信時に使っていたので、連合国側だったイギリスにより解読方法が発見されました。
エニグマ関係のエピソードは興味深いものが多いんですが、記事のテーマから外れるので割愛します。
興味のある方は、解読しようとするイギリス側を描いた映画「イミテーション・ゲーム エニグマと天才数学者の秘密」を見てください。
史実とは異なる箇所も多いんですが、概ねの雰囲気は掴めるのとベネディクト・カンバーバッチの演技を楽しめるのでおすすめです。
計算機で自然言語を表現する方法
ここでちょっと話が横道に逸れます。
というのも、コンピュータがどうやって英語や日本語などの文章を扱うのかという話をしたいからです。
まず、コンピュータは本質的には0と1しかない世界で生きていますが、我々が2や3と呼んでいるような2以上の数も扱えます。
0と1だけで2以上を表現することを2進数と言います。
2進数の説明をすると基本情報技術者試験対策記事になってしまうので割愛します。コンピュータは2以上も分かるんだな、くらいに考えていただければ十分です。
そしてコンピュータで英語や日本語を表現するために、各言語の各文字に数字を割り当てます。
つまり、記事の最初の方で例として出した
「あ」を1、「い」を2、「う」を3という風に順番に数字を割り当てるというルールを作っておくと、「あいうえお」や「こんにちは」などの色々な文章を数字で表現できるみたいな感じです。
ということをやります。
どの文字にどの数字を割り当てるかのルールは種類がたくさんあり、それらを総称して文字コードと呼んでいます。
コンピュータを使っていると時々文字化けが起こるのは、文章をやりとりする端末同士で違う文字コードを使ってしまっているからです。
ちなみに、数ではないものに数を割り当てるという考え方のベースとしてゲーデル数というものがあるんですが、話が大脱線するのでここでは割愛します。
このようにして人間の言葉をコンピュータが扱えるように数字にすると、大きな利点が1つあります。
それは、数学の世界に落とし込むことができるという点です。
数学の世界に落とし込むと何が嬉しいかというと、なんかいい感じに複雑なことができるようになります。何だこの説明は…
私は数学徒ではないのでふんわりした説明しかできないんですが、計算という手順を踏むことでエニグマの比ではないほど複雑な処理を施せるようになります。
共通鍵暗号と公開鍵暗号
話を暗号に戻すんですが、コンピュータ普及以降の近代的な暗号は説明がとんでもなくめんどくさいのでざっくり省略します。
ここでは共通鍵暗号と公開鍵暗号という2つの分類があるよという話だけします。
共通鍵暗号
ヴィジュネル暗号の項目で、文字を変換する際に定めたルールを鍵と呼ぶという話をしました。
暗号化する人と復号する人で同じ鍵を使うやり方を共通鍵暗号と呼びます。
ヴィジュネル暗号とエニグマは共通鍵暗号です。
事前に何らかの方法で、暗号化する人と復号する人同士で鍵を教え合う必要があります。
また、この鍵は秘密にしておく必要があります。鍵がバレると誰でも復号できるようになってしまうからです。
公開鍵暗号
共通鍵暗号に対し、暗号化する人と復号する人で異なる鍵を使うやり方を公開鍵暗号と呼びます。
そんな事可能なのか！？と一瞬思うんですが、数学パワーを使ったりすると可能になります。
代表的な例では素因数分解の困難性を利用するんですが、当然説明が難しくなるのでここでは割愛します。
公開鍵暗号の利点は、暗号化に使う方の鍵は不特定多数にバレても問題がないということです。
暗号化するための鍵をA、復号するための鍵をBとします。
まず、暗号文が欲しい人が鍵AとBを作り、鍵Aだけを誰でも見れる所に公開して「私に暗号文を送る時はこの鍵を使ってね！」とお願いします。
それを見た他の人が鍵Aを使って文章等を暗号化し、暗号文を送ります。
受け取った人は秘密にしている鍵Bを使って暗号文を復号します。これで暗号通信は完了です。
攻撃者は鍵Aと暗号文を知ることはできますが、復号するための鍵Bを知らないので解読できません。
共通鍵暗号に必要な、事前に何らかの方法で秘密裏に鍵を教え合うという手順を省けるのが嬉しいポイントです。
ちなみに公開鍵暗号のアイディアを利用して電子署名というものもできるんですが、暗号の話からはちょっと逸れるのでここでは割愛します。
暗号ではないけど暗号のように見えるもの
暗号については喋りたいことをだいたい喋れたので、ここでは一見暗号っぽくみえるけど実は暗号ではないものの話をします。
ハッシュ
暗号文から平文へ戻せないようなものは暗号と呼べないという話の例として、ハッシュの話をします。
あるデータからある程度短い値を生成するハッシュ関数というものがあり、ハッシュ関数により生成した短い値をハッシュ値と呼びます。
例えば こんにちは と書かれたテキストファイルをMD5というハッシュ関数に与えると f5271ace09a56600e1cef7663d932807 というハッシュ値を得られます。
また、元データが完全に同じ場合にしか同じハッシュ値を得られないという特性があります。2
ハッシュ値 f5271ace09a56600e1cef7663d932807 を得られるのは、元データが こんにちは と書かれている時のみということです。
見た目的にも、違う文章は必ず違うハッシュ値になるという特性を考えても、ハッシュ値はちょっと暗号っぽく思えます。
普段ハッシュ関数を扱うことはあんまり無いかと思いますが、人間の身体に似たようなものがあります。指紋です。
指紋は一人ひとり異なり、同じ形の指紋を複数の人間が持つことはありません。3
そのため、ある人がどういう形の指紋を持っているかという情報をあらかじめ知っていれば、机に付いた指紋を調べるだけでその人が触ったということが分かります。
しかしそのような情報を知らない場合は、その指紋は持ち主を推測できない暗号のようなものになります。ちょっと説得力に欠けますがそういうことにさせてください。
ハッシュ値の話に戻ります。
ハッシュ値は暗号文のように見えますが、暗号文ではありません。
なぜならハッシュ関数は元データからハッシュ値を生成することはできますが、ハッシュ値から元のデータを復元することはできないという特性を持つからです。4
暗号と呼ぶには暗号文から平文へ復号できることが条件であり、ハッシュ関数やハッシュ値はこの条件を満たさないということになります。
暗号ではありませんが、このハッシュというやつは結構便利なのでコンピュータの世界でよく使われています。
未解読言語
一般的に、人間が話す言語は暗号ではありません。
ですが、その言葉が表す意味を理解できる人がいなくなってしまえば暗号のようなものになります。
その一例が線文字Bです。
線文字Bは紀元前にギリシア本土とクレタ島で使われていた文字ですが、長い間未解読言語となっていました。
最終的には1952年にアマチュア研究者のマイケル・ヴェントリスによって解読されましたが、その解読プロセスは暗号解読に通じるものがあります。
私は線文字Bが本当に大好きなんですが、この記事は古代言語ではなく暗号がテーマなので詳細は割愛します。
興味のある方はぜひ線文字Ｂを解読した男―マイケル・ヴェントリスの生涯
を読んでみてください。新品はもう書店に無い可能性が高いんですが、大きめの図書館とかに置いてあるかもしれません。
おわりに
いっぱい喋れて満足しました！
暗号はとても楽しい分野です。理論としても面白いですし、実用的でもあります。
今回は理論的なところはほとんどすっ飛ばして書きたいことだけを書きましたが、面白さが少しでも伝わったら嬉しいです。
最後に参考文献のご紹介です。
もし暗号についてもうちょっと詳しく知りたいなという方がいらっしゃいましたら、この2冊がおすすめです。
『暗号解読』 サイモン・シン 著
かなり平易な言葉で書かれており、とても読みやすいです。
サイモン・シンは難解に見えるテーマを分かりやすく扱うのが本当に上手い。
概ね私の記事のちゃんとした版みたいな内容です。
ちなみにアニメ涼宮ハルヒの憂鬱で長門がこの本を読んでます。
この長門が読んでるよネタ、定番なんですがそろそろ通じなくなっていそうだな……
『暗号技術入門 第3版 秘密の国のアリス』 結城浩 著
ある程度前提知識がある人向けに書かれた技術書ですが、シーザー暗号などの歴史的な暗号も扱っておりとても丁寧に書かれた本です。
コンピュータが扱う暗号技術について知りたければ、この本以上に分かりやすいものはないと考えています。