「RSA(公開鍵暗号)の素数と鍵の非対称性(閉める鍵と開ける鍵が別)」

RSA(公開鍵暗号)　素数

世の中に、たとえば、
「ヒラカタ」
という地名があるとして、ただそれそれだけで、
「枚方」だか「平潟」は判別できない。が、そこに
「アンゴウ」という「キー」を与えれば、たちどころに、
TSUTAYAのレジのバーcodeということが判る。いっぽう、
「ヒラカタ」が「キラカタ」となれば、吉良方の斬られ役のうち、
落命したのは16人である。が、その30年前の
浄瑠璃坂の仇討ちでは敵方の死者が
16人だったのである。かつて、
米映画の復讐モノで一世を風靡した
チャールズ・ブロンスンふうに言えばこうなる。
「うーん、ランダム!」
それはともあれ、
吉良方で斬られて落命したのは、上野介役を加えて
17人ということになる。ちなみに、
17は素数である。百人一首で17番は
在原業平朝臣である。百人秀歌で17番は
河原左大臣(源融)である。ともに、
女性にモテモテの色男である。が、
彼らのようなスケコマシがいるいっぽうで、私のような、
いかなる女性からも好かれない醜男がいる。そういう
モノにとっては女性への想いは一方的である。が、
たとえば愛情のかけらもない、原始的な色欲の世界だったら、
この私でも通用する場所があるのが
世の中のおもしろいところである。昨今は、
「セフレ」と言うらしい。世間体を気にする見栄っぱりな私は、
「セフレタリ」などと秘所かに呼んでる類である。たとえば、
亭主持ちの婦人と情交を営むときなどは、
周囲に知られないような通信が必要になる。そこで、
たとえば「あいうえお……」をみもじずつずらして、
「あすひとよんまるまるにいつものらふほにて」を
「うたほぬるうめわめわのおなよふれまむのに」と
換字することで感じさせてしまおうと短慮する。
やはりスケコマシのモテモテ男だったカエサルの名を冠した、いわゆる
「シーザー暗号」というものである。が、
ご亭主がそこそこの知能の持ち主ならこんな
「みもじ」という鍵はいとも容易く破って
解読してしまうことだろう。そうなったらすみやかに
変エザルをえなくなる。ともあれ、
ここで大事なのはこの「みもじずらす」という「鍵」を、
平文を暗号化するときにも使い、また、
暗号文を復号化(または解読)して平文に戻すときにも使う、
「対称性」を有してるということである。すると、
その「鍵」を正規にしろ不正にしろ持ってるモノはみな、
平文を得ることもできるし、逆に、暗号文を発信できる、
ということである。が、それでは
暗号の意味がない。

ところが、
1970年代に、米国で研究してた3人の数学者、
リヴェスト、シャミール、エイデルマンによって開発された暗号は、
いわば掛ける鍵と開ける鍵が別、という画期的なものだった。
その3人のサーネイムの頭文字をとって
「RSA暗号」と呼ばれる。これは、
ごくごく簡単に言えば、
「ある程度大きい素数に
別のある程度大きい素数を掛けあわせた数(三百数十桁)」
というものを素因数分解することが実は容易ならないこと、
という性質を利用したものである。
日本のスパコンで計算しても数億年かかる、
というレヴェルなのである。そんな大きい数でなくてもたとえば、
19582176857というたった11桁の数を
紙と鉛筆だけで素因数分解するのは、
とんでもない労力が要るはずである。もっとも、
レンホウ女史のようなのに邪魔されないで開発が進めば、
三百数十桁でも破られる日が近いかもしれないが。ともあれ、
19582176857は二つの素数32582657と601を掛けたものである。
それはひとまずおいといて、
「RSA暗号」は、(数値化して2桁ずつに分けた)平文を、
選んだ二つの素数を掛け合わせた数と互いに素な、
その二つの素数からそれぞれ1を引いた数を
掛け合わせた数未満の整数乗したものを、
選んだ二つの素数を掛け合わせた数で割った余り、
が「暗号文」になる。つまり、
「選んだ二つの素数を掛け合わせた数」と、
「その二つの素数を掛け合わせた数以下の整数」が、
「公開鍵」となるのである。ここで初歩的なことだが、
「掛け合わせる前の二つの素数そのもの」をバラしては
元も子もなくなる。知れていいのはあくまでも、
「掛け合わせた数」である。ともあれ、
その「暗号文」を元に戻すには、
二つの素数からそれぞれ1を引いた数を
掛け合わせた数を整数倍したものに1を加えた数を
整数乗した数で割った数乗した数を
二つの素数を掛け合わせた数で割った余り、である。つまり、
[mod]=モジュールという関数を使う。これは、
剰余計算であるが、アナログの時計を想起すれば解りやすい。
24時間制で19時は、12という数字で割って余る7を使って
午後7時というのと同じである。

これでは何のことなのかさっぱり解らないと思うので、
以下はもっと簡単にするために、たとえば、
二つの素数に「2」と「5」を使うことにする。
2×5=【10】
である。暗号を作るときの冪乗数は、
(2-1)×(5-1)=4
未満でそれと互いに素な整数だから、
【3】のみである。ここで、平文を
「あいしてる」として、それを数値におきかえたものが
「01 02 03 04 05」であると仮にする。まず、
「01」を暗号化してみる。
1^3=1→これを10で割った余り→1
次に「02」。
2^3=8→これを10で割った余り→8
同様に、
3^3=27→これを10で割った余り→7
4^3=64→これを10で割った余り→4
5^3=125→これを10で割った余り→5
したがって、暗号文は、
「01 08 07 04 05」
となる。"解く鍵"は、
4n+1を3で割った整数である。n=2のときが最小で
「2」となるのでこの「3」で試してみる。
1^3=1→これを10で割った余り→1
8^3=512→これを10で割った余り→2
7^3=343→これを10で割った余り→3
4^3=64→これを10で割った余り→4
5^3=125→これを10で割った余り→5
ここではたまたま鍵を掛けるときの数と
開けるときの数がおなじく「3」となるが、これは
例にした数が小さいからである。さて、
これでもまだ何がなんだか解らないと思うので、
表にしてみる。

　　1乗 2乗 3乗 4乗 5乗 6乗 7乗 8乗 9乗 10乗 11乗 ...
01　01　01　01　01　01　01　01　01　01　01　 01　 ...
02　02　04　08　06　02　04　08　06　02　04　 08　 ...
03　03　09　07　01　03　09　07　01　03　09　 07　 ...
04　04　06　04　06　04　06　04　06　04　06　 04　 ...
05　05　05　05　05　05　05　05　05　05　05　 05　 ...
06　06　06　06　06　06　06　06　06　06　06　 06　 ...
07　07　09　03　01　07　09　03　01　07　09　 03　 ...
08　08　04　02　06　08　04　02　06　08　04　 02　 ...
09　09　01　09　01　09　01　09　01　09　01　 09 　...
10　00　00　00　00　00　00　00　00　00　00　 00　 ...
11　01　01　01　01　01　01　01　01　01　01　 01　 ...

この表の最左縦列の数字は平文の数字である。この
最左縦列の数字と9乗したときの縦列の数字が
同じになる。つまり、
平文を3乗して暗号化し、それをさらに3乗して、
つごう9乗すると元に戻る、のである。以上は先日、
あんこう鍋を囲んだ席で、隣のグループの
ロレックスをしてる人に教えてもらった話である。当然、
鮟鱇と餡子の味の違いが判らない拙脳なる私には
ちんぷんかんぷんな話である。