第２２話 RSA暗号をひねり出す
それは、昨日の朝のこと。
新しい絵馬をたずさえ、塵劫神社へ行くべく部屋を出ようとしたところで、大翔はちょっとした違和感を覚えた。
「・・・・・・。なぁんか、忘れてる気ぃするけど・・・。なんやったっけ？」
戸口で１０秒ほど考えたもののどうしても思い出せず、その日はけっきょくそのまま終わっていた。
だが今朝、制服に着替えようとして、制服のハンガーにズボンの代わりにぶら下げていたはずのケサランパサランがいなくなっているのを見て、彼はようやく忘れ物を思い出した。
昨日神社へ行ったときに、ケサランパサランを連れていくのを忘れていたのだ。ハンガーからいなくなっていたせいで気がつかなかったのである。
今朝はけっきょく、部屋をざっと探してみても見つからなかったので、家の外に逃げ出したぐらいに思ってすませていたのだが、まさかカバンの中にひそんでいたとは。
「僕の知る限り、こういう生物は地球上に存在せえへんはずなんやけど、なんでそれが君のカバンから出て来るんや？」
高木が腕を組んで、まっすぐに大翔を見る。
「奇遇やな。俺にもわからん。」
「わからんってことはないやろ。君さっき、こいつのこと“お前”って呼んでたやん。明らかに面識がある人の言い方やで？」
「む・・・。」
さすがに推理小説が好きなだけはある。人の発言を聞き逃さない。
当のケサランパサランはと言えば、フラダンスに飽きたのか、今度はキレキレのブレイクダンスを踊っている。あの神社で生活していて、そんなものをどうやって覚えたのか。
「これは未発見の・・・、新種の何かと違うんか？ 専門家に見せた方が・・・。」
「いや、それはやめといた方がええ。関わったヤツ全員、$${2^{2024}}$$匹に増殖したこいつに押しつぶされるわ。」
「ちょっと何言ってるかわからへん。」
日もとっぷり暮れ、国語準備室の中がだいぶ薄暗くなって来た。
高木はやおら立ち上がり、電気をつけてからまた席についた。
「ふふふ・・・。僕は今まで数々のミステリー小説を読んできたけど、まさか現実世界の、それもこんな至近距離にこんなミステリーが隠れていたとはね・・・。」
「ミステリーっちゅうか、どっちかと言うとファンタジーっぽいけどな。」
「ファンタジーは“幻想”や。現実に存在してる時点で、こいつはファンタジーではない。」
高木がケサランパサランをアゴで示す。ケサランパサランのブレイクダンスはいよいよクライマックスを迎え、安定したヘッドスピンを披露している。もっとも、体形的には頭を下にした方が安定していそうだが。
「そうかぁ・・・。神様なんてのがホンマにおるんやなぁ。で、そのおかげで千坂が数日で数学が得意になったわけやな。」
「いや、あの。頼むから他のヤツには言わんといてくれ。メンドウごとにしかならんような気がする。」
別に、くだんの神様に口止めされているわけではないが、すこしでも意に沿わないことがあると数学で攻撃されるあたり、どうもあれらを世間の目に晒してはいけないような気がする。新種の生物発見となれば、第１発見者として有名になれるかもしれないが、その段階で円周率しか口にできない廃人になっていたのでは元も子もない。
「言わへんて。言うても信じてもらえへんやろ。証拠としてこいつを見せようとしても、かんじんのところで雲隠れしてまうんちゃうかな。」
それはどうだろうか？ たしかにこいつらは神出鬼没ではあるが、そのわりに大翔のカバンに隠れていたりと、律儀に彼に付きまとっている。雲隠れできるぐらいなら、大翔が神社に連れて行くまでもなく、勝手に帰って欲しい。
「ふうう・・・。で、なんの話やったかいな？」
とりあえずケサランパサランは逃げる様子がないし、高木も塵劫神社関連の話を口外しないと約束してくれたので、大翔は安心した。だが、一気に別ごとに注意を持って行かれたおかげで、直前にしていた暗号の話をすっかり忘れてしまっていた。
「オイラーの定理の話やって。『任意の平文を送るにはどうしたらええか』いう疑問。」
「ああ、そやったそやった。えっと？」
大翔はホワイトボードに書かれた高木のメモを見た。
RSA暗号の基礎
公開鍵$${N}$$は$${2}$$つの整数の積
平文$${x}$$は$${0}$$以上$${N}$$未満の整数
$${x^{f+1}}$$を$${N}$$でわったあまりは$${x}$$
（整数$${f}$$は、最後の式が成り立つように選べるらしい）
オイラーの定理
$${n}$$は正の整数
$${a}$$は、$${n}$$との共通の約数を$${1}$$以外に持たない整数（つまり$${n}$$と互いに素）
$${a^{\varphi(n)}}$$を$${n}$$でわったあまりは$${1}$$
ここで$${\varphi(n)}$$は、$${0}$$以上$${n}$$以下の整数のうち、
$${n}$$と互いに素なものの個数（オイラー関数）
「・・・すまん・・・。一気に頭がクールダウンしてもうて・・・。ぜんぜん頭に入ってこん・・・。」
「・・・くだんの神様のご利益もここまでか。」
高木はあきれたように言って、ホワイトボードのメモをいったんぜんぶ消した。代わりに、簡単な図を描く。
「どっちとも、同じ数字を何回かかけ算して、別の数字でわったときのあまりについて主張してる。」
「$${\varphi(n)}$$の計算の仕方は、なんか公式があるんやったな？」
「ある。そやからそれはいったん置いとこう。この２つ、一見すると似てるけど、実は大きな違いがある。」
「$${a}$$と平文$${x}$$のとりうる値がちゃうわな。」
「それもそやけど、もっと大きな、しかも根本的な違いがあるやろ？」
「？」
「計算して出てくるあまりがそもそも違うやろ？」
「ああ、そうか。オイラーの方はあまりが$${1}$$になるんやな。」
「対してRSA暗号の基礎の方は、あまりは平文$${x}$$に戻る。ここで仮にさ。オイラーの方で$${a}$$をかける回数を$${1}$$増やしたらどうなる？」
「おおん？」
「それってつまり、$${a}$$を$${(\varphi(n)+1)}$$乗する、いうことか？」
「Yes.」
「ん〜。」
大翔はアゴに手を当て、クールダウンしていた頭を再起動させた。すると、ここ数日で身につけたあまり計算を扱う式がまた頭に浮かんできた。それをホワイトボードに書き出していく。
$$
\begin{equation*}
\begin{split}
a^{\varphi(n)+1}&=a^{\varphi(n)}\cdot a \\
&=\left(\text{○}\times n+1\right)\cdot a
\end{split}
\end{equation*}
$$
「２行目は、まさにオイラーの定理を使たわけやね。」
高木が補足を入れる。
「おう。」
$$
\begin{equation*}
\begin{split}
a^{\varphi(n)+1}&=a^{\varphi(n)}\cdot a \\
&=\left(\text{○}\times n+1\right)\cdot a \\
&=\text{○}\times a\times n+a
\end{split}
\end{equation*}
$$
「これ、ひょっとするってぇと、あれか？ あまり$${a}$$になるんか？」
「もし$${a}$$が$${0}$$以上$${n}$$未満やとしたら、そうなるね。」
第$${1}$$項は$${n}$$の倍数なのであまりには関係ない。となると、$${a}$$が$${n}$$未満なら間違いなく$${a}$$そのものがあまりだ。
「はあ、なるほど。これなら結果まで含めてオイラーとRSAがそろうわな。」
出だしの数字に戻るという意味では、RSA暗号の基礎により近い。
「それだけやないで？ かけ算の回数を$${1}$$増やしたおかげで、回数の方もちょっと形が似て来たやろ？」
オイラーの定理（書き換え版）：$${\underline{\varphi(n)}+1}$$
RSA暗号の基礎：$${\underline{f}+1}$$
「僕がシャッフルの回数に$${f}$$を提案した理由もわかったんちゃう？」
「ん〜、まあ発音は似てるっちゃ似てるか。どっちも“ファ”音やしな。」
「そうそう。」
「ひょっとしてあれか？ φってfの原型やったりするんか？」
「いいや。」
「違うんかい。」
「たしかfの原型は、“ディガンマ”っていう古いギリシャ文字や。今はもう使われてへん。似てるんは発音だけや。」
「さいですか。」
「まあ、それはわかったけど・・・。けっきょく最初の問題が解決してへんと思うが。」
大翔が最初に指摘したのは、「$${a}$$を平文だと思うと、ものによっては暗号化できない」ということだった。オイラーの定理では、$${a}$$はあくまでも$${\textbf{n}}$$と互いに素な整数だからだ。
「そこで、や。前提条件をすこし追加してみよう。」
そう言って、高木はホワイトボードのオイラーの定理をさらに書き換えた。
「ほう。ほうほうほう！ 一気にRSAっぽくなったやん！」
RSA暗号の公開鍵$${N}$$が$${2}$$つの巨大な素数の積だということは、どこのサイトを見ても明言されていることだ。
だが、そのココロは「素数の積を計算するのは簡単だが、逆にそれを素因数分解するのは難しい」というところにあった。この話はそれとは別らしい。
「ここがこの暗号の面白いところでもある。たしかに千坂の言うように、素因数分解の難しさがRSA暗号の安全性を保証してるわけやけど、公開鍵$${N}$$を$${2}$$つの素数の積に選ぶのには、もう１つ、暗号としての汎用性の確保って目的もあるわけやね。」
「ほぉ〜ん。ちゅうことは、あれか？ $${f}$$はけっきょく$${\varphi(N)}$$そのもの、いうことか？」
オイラーの定理（書き換え版）：$${\underline{\varphi(N)}+1}$$
RSA暗号の基礎：$${\underline{f}+1}$$
単純に２つを比較すると、そう思える。だが、高木は首を横に振った。
「微妙に違う。一般には、$${\varphi(N)}$$を適当に整数倍した数やね。」
$${k}$$を正の整数として、
$${f=k\varphi(N)}$$
「永遠にわからへんやんけ、$${f}$$。」
大翔があきれた顔をした。
そもそも$${f}$$がわからないから、それを知るためにオイラーの定理の話をしていたのに、またしても未知数が出て来るのか。
「そう言うなって。さっき、復号化の手順説明したやん？ 覚えてるか？」
「復号化？ あれやろ？ 暗号文自体を何乗かして$${N}$$でわるんやろ？」
「何乗するん？」
「えええっと。もう$${1}$$つの公開鍵$${e}$$が暗号化のときのかけ算の回数やから・・・。」
ホワイトボードに残っているいくつかの数式をたどって、記憶を呼び起こす。
「ああ、思い出した。こうやん。」
$$
d=\frac{f+1}{e}
$$
「うん。それって、絶対整数になる？」
「・・・・・・。ああ、なるほど？」
「ずっと説明してなかったけど、$${\varphi(N)}$$って今の場合、
$${\varphi(N)=(p-1)(q-1)}$$
（ただし、$${N=pq}$$）
で計算できるんよ。これで『$${\varphi(N)+1}$$が絶対$${e}$$の倍数になってるか？』て言ったら、それはわからんやん。」
「わからんなぁ・・・。」
「そこを保証するために、$${k}$$っていう未知数をかけるんよ。$${\varphi(N)+1}$$がダメでも、$${2\varphi(N)+1}$$とか$${3\varphi(N)+1}$$なら$${e}$$でわれるかもしれへんやん。」
「まぁ、そう・・・。そうなんか？」
「ちなみに、$${k}$$が入っててもさっきのオイラーの定理は成り立つよ。」
「ほぉぉ〜ん。」
「これでまぁ、一応RSA暗号を解読する最低限の準備は整ったな。」
To Be Continued…