素数は数字のアイデンティティー②公開鍵暗号の仕組みと素因数分解

前回書いたように、

素数を、

「１と自分自身以外では割り切れない、1より大きい自然数」

と定義すると、

すべての数は、
素因数分解によって、

それぞれの数につき、
一通りの素数の組み合わせで表現することができます。

ユークリッドの数論に基づく、素因数分解の一意性

このことは、正式には、

ユークリッドの数論に基づく、
初等整数論における基本定理とされていて、

「全ての自然数は、素数の積として、ただ一通りの組み合わせで表すことができる」

という、

算術の基本定理、ないし、
素因数分解の一意性

と呼ばれていますが、

この素因数分解の一意性を利用して、

メールなどの通信情報を
他人に盗み見られないように
暗号化しながら、

本来の受信者には
すぐに解読できるようにして、

通信ネット―ワーク上で、
安全かつ速やかに情報をやり取りすることを可能にする

公開鍵暗号という仕組みが考え出されています。

暗号解読における鍵のジレンマ

通信情報を秘匿化するためには、

送信者が行う
暗号化と、

その暗号文を解読するために
受信者が行う
復号化（暗号化した文書を元の平常の文書に戻すこと）

が必要になりますが、

この暗号文の解読、すなわち、
復号を行うには、

暗号を解くのに使う
解読鍵が必要となります。

そして、

公開鍵暗号という
画期的な仕組みが考え出される前の時代、

この解読鍵自体も、

送信者から受信者へ
通信によって
直接そのままの形で送り届けられていました。

しかし、

そうすると、そもそも、
スパイや望まれない第三者による
通信の傍受を警戒して
暗号化通信を行っていたのに、

暗号を解くための鍵も
通信でそのまま送ってしまっては、

その解読鍵ごと傍受されてしまって、
スパイや第三者に
暗号を解かれ放題になってしまう、

ということが問題となっていました。

つまり、

他人には情報を傍受されたくないので、
暗号化して情報を送るが、

受信者は、
暗号化された情報を受け取っただけでは
複合化の仕方が分からないので、
解読できない、

しかし、
受信者が解読できるように
解読鍵を通信で送ってしまうと、

その解読鍵ごと他人に傍受されてしまうので、
暗号化が意味をなさない、

という
解読鍵のジレンマが生じてしまっていたわけです。

公開鍵暗号の仕組みと、素因数分解の非対称性

こうした状況を打開するために、

素因数分解の一意性という
素数の性質を利用した

公開鍵暗号の仕組みが考え出されたわけですが、

その具体的な仕組みとは以下のようなものです。

まず、
暗号を解読する鍵を直接通信で送ってしまうと、
先ほどの鍵のジレンマの問題が生じてしまうので、

暗号の解読鍵は、
通信では一切送受しないこととし、

解読鍵は、

暗号文の
受信者の方が作って、
そのままずっと誰にも渡さずに持っておきます。

そして、受信者が、この
解読鍵をつくるときに、
二つの素数を使うのです。

ここでは、例えば、
素数4229と素数7487を

解読鍵として使うとしましょう。

そして、その
解読鍵である
二つの素数を掛け合わせた合成数を

暗号文をつくるための鍵として

暗号文を送信してもらいたい相手に
通信で送っておきます。

この場合は、
素数4229と素数7487の積である、

4229×7487＝31662523

が暗号文をつくるための鍵
となります。

この暗号文をつくるための鍵は、
通信によって広く世間に公開され、
傍受可能となるので、

公開鍵ということになります。

そして、
暗号文の送信者は、この
31662523という公開鍵で

情報を暗号化して
受信者へと送信するのです。

暗号文を受け取った
受信者は、

もともと自分で考えた、
素数4229と素数7487という
解読鍵を知っているので、

31662523という
公開鍵で暗号化された暗号文を、

すぐに、
4229（または7487）という
正しい解読鍵で割って、

暗号文を解読していくことができます。

それに対して、
31662523という公開鍵だけしか
傍受できていない

スパイや望まれない第三者は、

自分で、
31662523という大きな数字を
素因数分解して、

解読鍵を
計算で見つけ出さなくてはなりません。

素因数分解を計算で出すためには、
このシリーズの前回で書いたように、

ひたすら、
小さい素数から順番に、
割り切れるかどうかを試していくしかないので、

解読鍵を持たない第三者は、
31662523を2で割って、3で割って、5で割って、7で割って、11で割って、13で割って、17で割って、19で割って、23で割って、29で割って、31で割って・・・

という
膨大な計算作業を
総当たり方式でやっていくしかないことになります。

今回は、分かりやすい例として、
4229と7487という、

たった４桁の素数を解読鍵に使いましたが、

実際の
公開鍵暗号のシステムでは、

これよりも
莫大に大きい、
100桁以上の素数を解読鍵に使うので、

たとえ、相手が
スーパーコンピューターでも、
そう簡単には解けない、

十分に複雑な暗号化が可能となります。

公開鍵暗号のシステムでは、

素数から数を合成するときの
明解さと、

合成された数から
素因数分解で元の素数を見つけ出すときの
難解さ

という、

素因数分解の非対称性

を利用して、

情報の
正当な受信者には、

暗号文を瞬時に解読してもらえるようにすると
同時に、

情報を盗み見ようとする
スパイや望まれない第三者が
無理やり暗号を解読しようとする時には、

天文学的に莫大な計算量を強いて、
実質的に解読不可能にする、

ということを実現しているのです。

以上のように、

公開鍵暗号のシステムでは、

素数の性質を利用した
正当な受信者の選別、

言わば、
identification（身分証明、同一であることの証明）
が行われていることになるので、

前回の素数を人間の属性に当てはめて考える数字遊びに続いて、

ここでも、
素数は、

数字のアイデンティティー（identity、同一性、独自性、個性）

として機能しているように思います。