エンジニアが暗号理論を学んでみた。〜共通鍵暗号と公開鍵暗号〜
こんにちは、神山です!
先日GWでしたが、皆さんはいかがでしたか。
自分は2日目から風邪を引いて、GWの最後まで寝ておりました。
東京の風邪と夜通しのモノポリーほど長引くものはないですね。
さて、前回は暗号理論の基礎的な内容を書いたので、今回は2種類の暗号方式(共通鍵暗号と公開鍵暗号)について説明しようと思います。
前回の記事はこちら
では、まず共通鍵暗号について解説していきます。
共通鍵暗号
共通鍵暗号とは暗号化と復号に同じ鍵を使用する暗号方式です。秘密鍵暗号とも言います。
身近な例
合言葉や共通認識等は共通鍵暗号です。
よくお酒を飲みに行くときに「一杯ひっかけます?」と言ったりしますよね。これは「お酒を飲みに居酒屋に寄って行きます?」ということを暗号化しております。
「お酒を飲みに居酒屋に寄って行きます?」を「一杯ひっかけます?」と暗号化していることを受け手が知っていれば、きちんと復号して飲みに行くことを理解出来ます。
あまりに身近な例なので、今度は有名な共通鍵暗号を紹介します。
シーザー暗号
これは英文を伝える時に、全てのアルファベットを指定数分ずらして英文を送ることです。
シフトさせる文字数を3文字としたとき。 a -> d k -> n のように、3文字シフトさせて暗号化する。 「THE ALFEE」 をシーザー暗号(文字数3)で暗号化すると、 「WKH DOIHH」 となる。
鍵は文字数(今回だと「3」)です。
受け手がこの鍵を知っていれば、送られてきた英文を3文字前に戻すことで「THE ALFEE」を得ることが出来ます。
しかし、共通鍵暗号には重大な欠点があります。
鍵共有問題
これは肝心の鍵を共有する安全な方法がないということです。
共有鍵暗号はお互いに鍵を知っているという前提のもと成り立ちます。その為、まず鍵を安全に伝える手段がないと使う事ができません。
口頭で伝えるという原始的な手段はあります。しかしこれはあくまで伝えたい人が近くに居る状態で、誰にも聞かれない状態でなければなりません。
そもそもこの状態であれば、暗号化する必要もないでしょう。
通信手段を使うには、安全に伝えられる方法を探さなければなりません。安全に伝える手段こそ暗号なのですが、皮肉なことに暗号を使うために暗号が必要になってしまいました。
これでは鶏が先か、卵が先か問題になってしまいます。
さてこの問題を解決してくれるのが、公開鍵暗号です。
公開鍵暗号
公開鍵暗号とは、暗号化する鍵と復号する鍵が違う暗号方式です。暗号化する鍵(公開鍵)は公開し、復号する鍵(秘密鍵)は秘密に管理します。
RSA暗号が公開鍵暗号の代表的な例です。
身近な例だと難しいので、少し特殊ですが分かり易い例を用意しました。
南京錠
ある南京錠があります。この南京錠を開ける鍵はAさんが持っている一本の鍵のみです。もちろん複製や他の手段では開けられません。
またこの南京錠自体はどこでも手に入るものだとします。
Aさんに秘密のメッセージを送りたいときは、メッセージを適当な箱に入れてこの南京錠でロックします。
すると当然ながらこの箱を開けられるのは鍵を持っているAさんしかいません。つまりAさんに安全にメッセージを伝えることが出来ます。
これが公開鍵暗号の仕組みです。南京錠自体はいくら公開しても問題ありません。
では実際に使われている公開鍵暗号が、具体的にどのような仕組みになっているか説明します。
※ ここからは数学の話が出てきます。ただ出来るだけ分かり易く言葉で説明するので、数学に抵抗意識がある人もどうか読んで頂ければと思いますm( )m
一方向性関数
一方向性関数とは、一方の計算は簡単なのにもう一方の計算は極度に難しい関数のことです。
たとえば、1454867
を素因数分解してみてください。
PCを使わずに、出来た人はすごいです。答えは911 × 1597
です。
さて、では911 × 1597
を計算してみてください。こちらはPC使わなくても簡単ですね。もちろん1454867
です。
みなさんも体感したように、素数を掛け合わせるのは簡単ですが、それを素因数分解するのはとても難しいことです。
これは人間だけでなくPCも同じです。桁数は大きくなりますが、数百桁の素数を掛け合わせた数をPCに素因数分解をさせると、解くのに何万年という膨大な時間が掛かります。
時間が無限にあればいつかは解けますが、現実的に考えると難しいと言えます。
一方向性関数を使った南京錠
先程、南京錠の例を用いたので、今回はそれに類似させた例を作りました。
Aさんのアドレスが書かれている50桁のダイヤルが付いた南京錠があります。また謎の数百桁の数が書かれてあります。これを開けるにはこの数を素因数分解して、一番大きい素数の最初の50桁をダイヤルにセットしなくてはいけません。
(桁数の50は適当です。。)
Aさんにメッセージを送りたいときは、同じように適当な箱にメッセージを入れてこの南京錠で閉じます。
もうお分かりかと思いますが、この南京錠を開けられるのは素因数分解の答えを知っているAさんのみです。
つまり相手の公開鍵さえ知っていれば、自分の情報をその人に安全に伝える事ができます。
RSA暗号
公開鍵暗号を使用した暗号の代表例です。 現在の安全な通信技術にはRSA暗号が使用されております。 仕組みは素因数分解を用いているのですが、理解するには数学の高度な知識が必要になるので、また別の機会にでも説明しようと思います。
まとめ
共通鍵暗号と公開鍵暗号について説明しました。理解をして頂くことに重点を置いたので直感的な内容になってしまったかも知れません。
間違いなどがありましたらご指摘をお願い致します。