治安の悪い地域で荷物を確実に届ける方法

■世界中のPCでも解けない「鍵暗号」とは

暗号は大事なモノや情報を相手に届けるため、さまざまな場所で使われている。その暗号には大別して2種類あって、その1つが公開鍵暗号で、もう1つが「共通鍵暗号（秘密鍵暗号）」と呼ばれるものだ。

後者の共通鍵暗号は最も古典的な暗号で、「シーザー（カエサル）暗号」ともいわれる。たとえば、「イノシシ」という単語を暗号化するとき、「あいうえお順で3文字ずらす」ことをルール（鍵）にし、「オフソソ」と相手に伝える。

これでは意味不明だが、3文字ずらすという共通の鍵を使って、元の「イノシシ」に戻すことができる。共通鍵暗号はこのようにシンプルな仕組みで使い勝手がよい半面、見破られやすいというデメリットがある。3文字、5文字……とずらしながら試していくうちに、そう時間を要せずにバレてしまう可能性が高いのだ。

この共通鍵暗号の課題を克服したのが、もう1つの公開鍵暗号なのだ。これは2つの鍵を使ったものなのだが、その説明に入る前に、次のクイズで頭をほぐそう。

「AがBに大切な荷物を送りたいと考えている。しかし、2人の住む地域は非常に治安が悪く、配送業者でさえ中身を盗むことがある。そこで確実に荷物を届けたいAは、どう送ればいいか」

答えは以下。「Aが箱に錠をかけてBに送る。配達員は鍵がなく箱を開けられず、Bに箱が無事届く。Bも鍵を持っておらず開けられないが、Bは別の錠を新たにかけてAに箱を送り返す。Aは自分がかけた錠を外し、再びBに送る。そしてBは自分がかけた錠を外して中身を取り出す」（図参照）。こうすると手間はかかるが、確実に中身を受け取れる。

■推測の演算には、数十年、数百年かかる

本題の公開鍵暗号だが、素数の積と素因数分解をベースに開発された。「13×17＝221」で見てみよう。13と17は素数で、この積「221」は筆算で簡単に計算できる。一方、221を素因数分解するには、「2で割って、3で割って……」と順に探しても、「13×17」にたどり着くまでに時間を要する。この素因数分解の演算の面倒さを利用したのが公開鍵暗号なのだ。

その公開鍵暗号は基本的に公開鍵（閉める鍵）と秘密鍵（開ける鍵）のペアで成り立つ。上記の例でいうと公開鍵は「17をかける操作」、秘密鍵は「221を素因数分解する操作」だ。公開鍵はその名のとおり、誰でも利用できるように公開されている。

※写真はイメージです（写真＝iStock.com／peshkov）

たとえば、Cが「17をかける」という公開鍵を世界中にオープンにして、大事な情報を送ってもらうとする。Cの元には公開鍵「17をかける」で閉められた情報「221」が集まってくる。そしてCは自分だけが知っている「221を素因数分解する操作」の秘密鍵で開けるわけなのである。

公開鍵暗号をもとに秘密鍵を探り出すことは可能だが、実際の公開鍵暗号は膨大なケタの素数を利用しているため、地球上のすべてのコンピューターを駆使しても推測の演算には、数十年、数百年かかるといわれている。そして先の荷物問題は、2つの鍵を使って安全に届けるという点で公開鍵暗号に近いのだ。

----------

横山明日希
数学のお兄さん
2012年、早稲田大学大学院修士課程単位取得（理学修士）。数学応用数理専攻。大学在学中から、数学の楽しさを世の中に広く伝えるために「数学のお兄さん」として活動を開始、精力的に講演やイベントを行う。

----------

（数学のお兄さん 横山 明日希 構成＝田之上 信　写真＝iStock.com）