公開鍵暗号の仕組み

 インターネットにPCを繋げて何かをする際に、当たり前のように使っている暗号化システム「公開鍵暗号」について復習したときのメモ。10年くらい前に購入した『暗号解読』(サイモン・シン,新潮社)の下巻を参考にした。20年前くらいにアメリカで出版された古い本だし、けっこうボリュームもあるが、暗号の入門書としては素晴らしいと思う。

公開鍵以前の伝統的な暗号

仕組み

 コンピュータで処理をする(=すべての文字を「0」と「1」の二進数に置き代えて考える)場合の暗号技術では、以下のステップで暗号化と復号をしていた。

  1. 平文(暗号化していない文)を二進数に変換する
  2. 1で出来た平文(二進数バージョン)をある関数Aで処理して、暗号化する
  3. 送信する
  4. 受信する
  5. 受信した暗号文を関数Aで処理して、平文(二進数バージョン)に戻す
  6. 平文(二進数バージョン)を、人が読める形でモニタ上に表示する

このとき、すべての人で 関数Aが共通していては暗号の意味がないので、組織単位/個人単位で違った関数Aを持つ必要がある。そのためには、関数Aの素となる「鍵」が各単位で異なっていればよい。しかしここで、「鍵配送」問題が生じる。

鍵配送問題

 暗号の世界で思考実験をするときは、アリスとボブ(通信者)、イブ(盗聴者)の3人が登場することが多い。鍵配送問題をこの三人で考えてみる。

  • 送信者:アリス
  • 受信者:ボブ
  • 盗聴者:イブ

とすると、アリスがボブに暗号化した通信文を送るためには、通信文を送るたびに、ボブに対して「鍵」が何かを伝えなくてはならない。電話回線を使う手もあるが、イブに盗聴されるかもしれない。そうなると、人が運ぶしかない。

 1970年代以前の「公開鍵」暗号が存在しない時代は、暗号は政府や軍や金融機関だけのものであり、新しい鍵を定期的に配達することを職業とする人々がいた。暗号を一般市民が使わなかった理由の1つは、世界各地に「鍵」を配達するだけの人件費である。

脱・鍵配送問題

 鍵配送問題を解決するために、さまざま思考実験が行われた。

思考実験1(鍵を2つかける)

※ 『暗号解読』下巻のp121くらいの内容を編集したもの

 アリスとボブが、郵便局員のモラルが非常に低い国に住んでいると仮定する。
アリスがボブにごくプライベートな手紙をボブに送るとき、手紙を鉄の箱に入れ、南京錠を掛ける。アリスは鍵を手元に残して、施錠した箱をポストに入れる。箱を受け取ったボブは、そこにさらに自分の南京錠を掛けて、箱をアリスに送り返す。アリスに届いた箱には、アリスの鍵とボブの鍵が二重に掛かっていることになる。ここでアリスが自分の分の南京錠を外せば、残りはボブの南京錠だけである。そうしておいて、その箱をボブに返送する。ボブが受け取った箱にはボブの南京錠しか付いていないわけだから、ボブは箱を開けることができる。

欠点

1.アリスが暗号化する
2.ボブが暗号化する
3.アリスが復号する
4.ボブが復号する
という順序で動くシステムなので 「鍵は掛けた順序と逆順で外さなくてはならない」(靴を脱ぐ前に靴下を脱ぐことができないように、暗号は掛けた順序と逆順に解除しなくてはならない。)という当時の暗号の基本原則が守られていない。

-->欠点はあるものの、「鍵配送」は解決可能な問題であることがわかった。

公開鍵の発明

 思考実験1がつまづいた原因は、暗号/復号に用いる関数Aの種類にあった。思考実験1で使われたような、送信者と受信者が同じだけの知識を持ち暗号と復号で同一の鍵を使うシステムを、送信者と受信者の関係が対称的と意味で「対称鍵の暗号システム」と呼ぶ。そして、こうした暗号技術に用いられる関数の種類は「双方向関数」だった。
※双方向関数とは
関数操作を施すのも、それを解除するのも簡単な関数
例:「2倍する」操作

公開鍵暗号の原理

 暗号と復号で異なる鍵を使うような「非対称の鍵システム」を作りたい。具体的には、一方向関数を暗号化に取り入れることを考える。南京錠に例えて言えば「ガチャンとはめ込むだけで誰でも鍵を掛けられるが、錠は鍵を持っている人間にしか外せない」ような暗号システムを作りたい。

そのためには、アリスは自分専用の鍵を2種類用意することになる。コンピュータによる暗号化では、鍵は1つの数になる。
復号用の鍵:周囲に秘密にしておくので「秘密鍵」とよぶ。
暗号化用の鍵:周りに公開しておくので「公開鍵」とよぶ。

ボブがアリスにメッセージを送りたいとき、ボブは電話帳のようなものでアリスの公開鍵を探し、その鍵でメッセージを暗号化して送信すればよい。アリスは受け取ったメッセージを自分の秘密鍵で復号して読むことができる。

盗聴者イブにできること
1.ボブに偽の公開鍵を伝えてアリスに成りすます。これを防止するために公開鍵の認証機関が存在する
2.アリスのコンピュータに侵入するなどして、秘密鍵を奪う。これを防止するためにウイルス対策ソフトは適切に使う必要がある。

科学者が目指したもの

 まとめると、非対称暗号を構築するためには、次の2点がポイントであり、科学者たちはこれらの条件を満たす一方向関数を探した。


1)アリスは公開鍵を作らなければならない。彼女はそれを公開して、ボブ(誰でもよい)が彼女宛のメッセージを暗号化できるようにする。公開鍵は一方向関数なので、誰かがその関数を逆転させ、アリスのメッセージを解読することは事実上不可能である。
2)しかしアリスは自分宛てのメッセージを複号する必要がある。そこで彼女は、公開鍵の効果を逆転させられるような特殊な情報、すなわち個人鍵をもたなければならない。それによりアリスは(アリスだけが)自分宛のメッセージを読む力を持つ。

『暗号解読』(下)

一方向関数として素因数分解

 結論として、素因数分解が選ばれた。

  • 秘密鍵:2つの素数p,q
  • 公開鍵:pとqの積である数N

Nが十分に大きければ、pとqを探し出すための計算量が膨大になり、事実上、だれも秘密鍵(p, q)を見つけることができない

※爆発的な計算速度を持つ量子コンピュータが暗号解読に使われるようになると、秘密鍵と公開鍵から成る暗号化システムが破られるようになる(かもしれない)

素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する[注 1]。
素因数分解には次のような性質がある。
任意の正の整数に対して、素因数分解はただ 1 通りに決定する(素因数分解の一意性)。
素因数分解の結果から、正の約数やその個数、総和などを求めることができる。

Wikipedia