第１９話 数字をシャッフルする
「なるほど。その“リフルシャッフル暗号”とやら、公開鍵暗号だけやなくて、RSA暗号のたとえにもなってるなぁ。」
高木が感心したように言った。
「うん？ そうなん？」
大翔がけげんな顔をする。
「“リフルシャッフル暗号”のキモは、カードの束を一定回数シャッフルすると元のならびに戻るっていうことやん？」
「おう。」
「RSA暗号も、けっこうそれに似てるんよ。平文にある操作を一定回数くわえると、もとの平文に戻るねん。」
「平文はあくまでも数字なんやな？」
「そうでないといろいろ不便やからな。普通の文章を送りたかったら、それこそ上杉暗号なりなんなり使って数字に直す。話はそこからやね。」
「ふうむ・・・。」
大翔はアゴに手を当て、すこし考えた。
「つまり、こういう対応関係があるっちゅうことは、RSA暗号で暗号化するときは、“ある操作”とやらを中途半端にやるわけか？」
“リフルシャッフル暗号”では、暗号化は適当な回数（たとえば$${8}$$回）のシャッフルだった。そして復号化は残り回数（$${23-8=15}$$回）分のシャッフルである。それで元のいろは歌を再現できるという話だった。
同じ発想で行くなら、RSA暗号も“ある操作”を適当な回数だけして暗号化し、残り回数だけ“操作”すれば復号化できるはずである。
「まあざっくり言うと、そんな感じかな。」
「ほうほう。で、その“ある操作”とやら・・・、もうメンドいからこれも“シャッフル”て言うてまうけど、具体的に何をどうすんねん？ まさか、平文の数字を$${1}$$ケタずつカードに書いてリフルシャッフルするとか？」
「まさか！ そんな暗号、コンピュータを使ったら秒で解かれるって。」
「・・・やんなぁ。」
たしか、叔父の豪もそんなことを言っていた。
高木はカバンから水筒を取り出し、コップにお茶を注いで一口飲んだ。
「RSA暗号の場合の“シャッフル”は、
平文の数字をかけ算して
公開鍵$${\textbf{N}}$$でわったあまりを求める
やな。」
「ちょっと何言ってるかわからへん。」
「せめて、もうちょい悩めよ。たとえば、君の叔父さんが出してきたクイズの場合やとなぁ。」
高木が大翔のスマホを指差した。
公開鍵：$${N=2077, e=283}$$
暗号文：$${1189, 465, 1500, 190, 907}$$
「この暗号文は、いったん放っとこう。うーん、そやなぁ。たとえば千坂。君の誕生日っていつ？」
「おん？ １２月５日やけど？」
「ふむ。じゃあその個人情報を他の人にバレんように、粕谷さんに送ることになったとしよう。」
「陽菜に？ 今さら？ あいつ俺の誕生日くらい知っとるぞ。」
「そりゃ仲がよろしいようでなにより。そのたとえが不満なら、ブラジルのナニガシさんに送るでもええよ。とにかく、君の誕生日“$${1205}$$”を平文として、公開鍵$${N=2077, e=283}$$を使って暗号化してみよう。」
「ふむ。」
「そしたらまずシャッフル１回目。平文“$${1205}$$”に、同じく平文“$${\textbf{1205}}$$”をかけ算する。」
「うん？ $${1205\times1205}$$ってこと？」
「そう。」
「うーん？？」
大翔は腕を組んで天井を見上げた。
うまく説明できないが、何か違和感がある。これで本当にシャッフルになっているのか？ しかし、どれだけ考えても違和感の出どころは見えてこない。
彼はあきらめて電卓アプリを起動し、$${1205^2}$$を計算した。
「あー、$${1452025}$$。なかなかにデカいな。」
「ふむ。じゃあ次に、その値を公開鍵$${N=2077}$$でわったあまりを求めてみ？」
「ええ、メンド！ 俺、電卓であまりを計算する方法知らんぞ？」
「んー。ほな代わりに、グーグルル・クローン開いて。」
「ほう。」
「ほんで検索バーに、“$${1452025\ \text{mod}\ 2077}$$”って打って検索かけて。」
「！！」
そのとおりにすると、驚いたことに、検索結果のトップに電卓のようなイラストが現れ、$${202}$$という数字が表示された。
「マジでか！！ グーグルル検索にこんな機能があったんか！」
「うん。わりと便利やで。暗号の設計してるときは。」
「とたん、ありがたみがわからんなった。」
メリットが独特すぎる。よく考えたら、日常生活であまりを計算するシーンが思い当たらない。
「君もなかなか強情だね。・・・まぁええわ。今の一連の流れが、RSA暗号のシャッフル１回分や。」
「・・・えっと？ 平文かけ算して、$${\textbf{N}}$$でわったあまりを求める・・・か？」
「そ。じゃあ問題。『２回目のシャッフルをせよ』。さあ、どうする？」
「んと？ 平文を・・・何にかけたらええんや？」
まさか、平文にかけるわけではないだろう。それではまったく同じ計算のくり返しである。
“リフルシャッフル暗号”ではどうしていたんだったか？ たしか、$${1}$$回シャッフルしたカードの束をさらにシャッフルしていたから・・・。
「ああそうか、$${1}$$回目のシャッフルの結果にかけたらええのか。つまり$${202\times1205}$$やって・・・。」
今度は、かけ算もグーグルルでやってみる。結果は$${243410}$$だった。
「ほんで、それをまた$${N=2077}$$でわったあまりを、と。」
結果は$${401}$$である。
「正解！ たぶん。」
「たぶん？！」
「いや、僕かてそんな計算、暗算ではようせんよ。結果の数字は知らんけど、手順の方はとりあえず合ってる。」
大翔はパイプ椅子の背もたれに身をあずけ、腕を組んだ。パイプ椅子がギシッと音を立てる。
「ほーん。けっこう難しいっちゅうか、ややこしいことするんやなぁ。まあ、リフルシャッフルも難しいは難しいが。」
「まあな。あとはぜんぶ同じ要領。
前回のシャッフル結果に平文をかけて
公開鍵$${\textbf{N}}$$でわったあまりを求める
これのくり返し。」
「ふむ。で、暗号化するときはこれを何回やんねん？」
「もう１つ公開鍵があるやろ？ “$${e}$$”ってヤツ。それから$${1}$$引いた数だけ。」（*1）
大翔はいったんグーグルルを閉じ、またRINEを開いて叔父からの問題を確認した。
「$${e}$$って・・・。$${283}$$？！ 冗談きついわ。こんな計算、$${282}$$回もやれるかいっ。」（*1）
あまりを直接求める方法がわかったのはよいが、それでも毎回検索バーに数字をチマチマ打ち込むのは鬱陶しすぎる。
「いやいや、落ち着けって。何も、今ここで君の誕生日を暗号化する必要ないやろ？ あくまでも暗号化の手順を確認するのが目的やからさ。」
「お、おう。そやな。」
「まあじゃあ、暗号化の方法はわかったとして、次は復号化の方法か。あと何回シャッフルしたらええか、いう話やけど。」
RSA暗号での“シャッフル”の内容はわかった。あとはそれを暗号文に対してさらに何度かやるだけだ・・・。
「ん？！」
そこまで考えて、大翔はようやくさきほど感じた違和感の正体に気がついた。
「高木。このシャッフル、ホンマにこれでええんか？」
「？ ウソはついてないけど？」
「いや、仮にこれがRSA暗号のシャッフルやとしてさ。暗号受け取った側はそのシャッフルでけへんやろ。平文がわかってなあかんねんから。」
高木の言うRSA暗号のシャッフルは、その計算に平文のかけ算を含んでいる。ということは暗号文を受け取った人は、復号化するために、そのゴールである平文を知っていないといけないのだ。それがわかっているなら、そもそも復号化の作業など必要ない。
「ふっ。気づいたか。それでこそ、我が相棒・・・。」
高木はメガネを中指でクイっと直した。
「いや、いらんいらん、そういうの。」
「だが残念ながら、シャッフルの内容に誤りはないのだよ・・・。」
高木はメガネを中指でクイっと直した。
「おい・・・。」
「受信者は平文を知ることなく、復号化することができるのさ・・・。」
高木はメガネを中指でクイっと直した。
「うぜぇな。」
「そしてそれこそが、『受信者が何回シャッフルをすれば復号化できるのか』ということと密接に関係しているのだ！！」
「机に足を載せんな！！」
「・・・・・・。"To Be Continued…"」
「うっさいわ！！」
お茶を一口飲んでから、高木が普通の口調で言った。
「いやじっさい、そのあたりはRSA暗号の巧妙なところやと、個人的には思っててな。そこを説明しようと思うと、まず次の数式をわかってもらう必要がある。」
彼はゆっくり立ち上がると、壁際にあるホワイトボードの前に立ち、何かを書き始めた。
（平文を$${n}$$回シャッフルした結果）＝（$${\text{平文}^{n+1}}$$を$${N}$$でわったあまり）
「わかる？ これ。」
「おおん？ ちょっと待てよ。その右辺の“$${\text{平文}^{n+1}}$$”っちゅうのは、平文を$${(n+1)}$$乗した数か？」
「そうそう。」
「$${n}$$は？」
「なんでもええ。$${1}$$でも$${2}$$でも$${e}$$でも、それ以上でも。」
「んんんー。」
さきほどの説明だとRSA暗号でのシャッフルは、毎回$${N}$$でわってあまりを求める。それを$${n}$$回くり返すというのが左辺の内容だ。
これに対し右辺は、平文のかけ算をさきにぜんぶやりきってしまえ、というものである。あまりを求める計算は、そのあとに$${1}$$回こっきりやるだけでよい。それで本当に同じ結果になるのか？
だが、大翔はつい先日、あまりの計算を手なずけたばかりだった。彼の脳が、ふたたび活性化し始めた。
おもむろに立ち上がり、ホワイトボードの前に立つ。
「“平文”って書くのメンドくさいから、“$${x}$$”っておくで。」
まさか、「〇〇を$${x}$$とおく」などというフレーズが、自分の口から能動的に出てくる日が来るとは・・・。
「まず出だしからや。$${1}$$回目のシャッフルの場合、お前のお題は
（平文を$${1}$$回シャッフルした結果）＝（$${\text{平文}^{2}}$$を$${N}$$でわったあまり）
やけど、これはもう見たまんまやろ。不思議でもなんでもない。」
「というより、シャッフルの定義そのものと言っても過言ではないな。」
高木が同意する。
「仮に左辺 ––– $${1}$$回シャッフルした結果 ––– を$${r_1}$$とするなら、こんなふうに書けるはずやろ。
$$
\begin{equation}
x^2=a_1N+r_1
\end{equation}
$$
先週、陽菜がケサランパサランの群れでやっていたことの数式版だ。$${x^2}$$匹のケサランパサランを$${N}$$匹ずつまとめていくと$${a_1}$$個のセットになり、$${r_1}$$匹あまるという感じである。
「うん、書けるな。」
さすが、学年トップ。たいして説明しなくても、数式の意味を即座に理解したようだ。
「というか、なんで$${r}$$を使ったの？」
「そらお前、"result" の頭文字やろ。シャッフルの結果なわけやし。」
「なんや！ 『けっこう通な文字使うなぁ』と思ったら。」
「は？ 通？」
「数学の世界やと、あまりのことをよく$${r}$$って書くんよ。もっとも、"result" やなくて "remainder（＝あまり）" の略やけど。」
「さいですか。」
「ちなみに、"a" は "answer" の略？」
高木がいたずらっぽく笑う。
「それならそれでええわい。なんなら、“答え”の$${k}$$にしたろうか？ 次、$${2}$$回目のシャッフル行くぞ。目指すゴールは
（平文を$${2}$$回シャッフルした結果）＝（$${\text{平文}^{3}}$$を$${N}$$でわったあまり）
や。さっきと同じように左辺を$${r_2}$$とする。$${2}$$回目のシャッフルは、$${1}$$回目のシャッフルの結果$${r_1}$$に平文かけて$${N}$$でわるんやから、
$$
\begin{equation}
r_1x=a_2N+r_2
\end{equation}
$$
なわけや。」
「$${a_2}$$は、$${r_1x}$$を$${N}$$でわった答えなわけやね？」
「そうそう。次に$${x^3}$$が知りたいから、さっきの式(1)の両辺に$${x}$$かけてやる。
$${x^3=a_1xN+r_1x}$$
そしたら第$${2}$$項が$${r_1x}$$やん。こいつに式(2)を代入したったら・・・。
$$
\begin{equation*}
\begin{split}
x^3&=a_1xN+a_2N+r_2 \\
&=(a_1x+a_2)N+r_2
\end{split}
\end{equation*}
$$
第$${1}$$項は$${N}$$の倍数やから、あまりには関係なし。つまり、第$${2}$$項が$${x^3}$$を$${N}$$でわったあまりやけど、これって$${2}$$回目のシャッフルの結果やん？ これでもう終わりやろ。」
もちろん、真面目にやるならもっと大きい$${n}$$についてもやるべきだが、やることはぜんぶ一緒だろう。またしても数学的帰納法のお出ましだ。
「OK、OK！ なんや千坂、数学苦手みたいに思ってたけど、やるやん！！」
「『男子、３日会わざれば刮目して見よ』ってな。」
大翔は親指を立てて見せた。
事実、数学の面白さに目覚めたのは２日前である。某ゲームでたまたま知った古い言葉を、自分がそのまま体現していた。
「その犠牲で、宿題２つとも忘れるんはいただけんけどな。」
「ふん。聞こえんな。」
「まあともかく、これで第一関門は終わったわ。これで、シャッフルの残り回数の話ができる。」
To Be Continued…
*1: 一部誤記がありましたので、修正いたしました。またそれに合わせて、解説図も修正いたしました。大変申し訳ありません（2024/10/17）。
誤：「その数だけ」 → 正：「それから$${1}$$引いた数だけ」