aRiSA

第17話 RSA暗号*

　RSAの暗号化に用いられる指数 65537 は、インターネットのセキュリティ事業に勤める人にとって、計算の都合がよい 16 進法で 10001 と表される 5 桁の数でしかないが、代数学を専門としている慈道にとってはそれなりに思い入れがあるようであった。ついつい慈道は暗号理論とは関係のない作図問題を引っ張り出して、自分で話の腰を折ってしまっていたのだ。

「いやあ、またやってしまった。RSAに戻ろう」

　慈道はアリサとは目線を合わせずに話を始める。

「今何をやっていたかを振り返る。巨大な素数 p、q を用意し、 N ＝ p q とした。そして L ＝ (p − 1)(q − 1) とおいた。そして L と互いに素な整数 e を用意する。これは一般に素数 65537 とする。俺の想像だと、もし L が 65537 で割り切れてしまったら、 p と q を選び直していると思う。あとで説明するが、 e ＝ 65537 が親しまれているのは、そこそこの大きさであるという点と、繰り返し2乗法という計算法を踏まえると、かなり計算が楽になるからだと思う。さて、 e と L は互いに素であるから

　　　e d ＋ L M ＝ 1

となる整数 d、M がとれる。この段階でもし 0 ≦ d ＜ L でなかった場合、 d を L で割ったときの商と余りをそれぞれ q、r とするとき

　　　d ＝ L q ＋ r　(0 ≦ r ＜ L)

と書けるので、これを e d ＋ L M ＝ 1 に代入すると

　　　e(L q ＋ r) ＋ L M ＝ 1 　⇔　 e r ＋ L(M ＋ e q) ＝ 1

となるので、改めて r を d、 M ＋ eq を M と書き換えれば

　　　e d ＋ L M ＝ 1　(0 ＜ d ≦ L)

とできる。 e ＞ 0、L ＞ 0 より必然的に M ＜ 0 となることは軽く注意しておく。さて、合同式の定義より

　　　e d ≡ 1 mod L

となる。ここでまでよろしいかな」

　少し式が煩雑ではあるが、大学2年生のアリサもこのレベルの数式処理はなんとかいけるようだ。

「さあ、いよいよ平文 m を暗号化する。 m を e 乗して、それを N で割ったときの余りを暗号文 c とする。この定義より

　　　c ≡ m^e mod N

が成り立つ」

「e って 65537 ですよね。 m を e 乗するって物凄く大変な計算じゃないですか？　しかもめちゃくちゃ大きい数になってしまう気がしますが」

「一見 65537 回もの計算が必要に思えるが、実はちゃんとした抜け道があって、それを使えば 17 回の計算でできるから心配なさんな」

「え？　そんな簡単にいくんですか？」

「うん。昔偉い人が思いついたんだ。さっきちらっと言った繰り返し2乗法ってやつ。最初に考えた人は天才だと思う。まあまあ、それはあとで具体例のときに説明するから、とりあえず一般論で話を進める。俺がちょっと面白いなと思ったのは、柴山の言う通り、 m^e は莫迦でかい数だ。 N も 600 桁と十分大きいが、 m が仮に 100 桁の整数だとすると、

　　　10^99 ≦ m ＜ 10^100

だから両辺を e 乗して

　　　10^(99e) ≦ m^e ＜ 10^(100e)

となるから、 m^e は 100e ＝ 100 × 65537 桁の数になる。しかし、実際暗号文として使うのは、 N で割ったときの余りで、高々 600 桁の部分だけだ。こんなにばっさり切って本当に復号ができるか心配になるだろう。これがうまくできていて、 c ≡ m^e の両辺を d 乗すれば m が出てくる。つまり

　　　c^d ≡ m mod N

が成り立つ。何故かを説明しよう。まず、滅多にないことだが、 m が p または q の倍数の場合、 N ＝ p q に注意すれば、 m ≡ 0 mod N なので、

　　　c ≡ m^e ≡ 0 mod N

だから c^d ≡ m は成り立つ。次に m が p の倍数でも q の倍数でもないとき、フェルマーの小定理より

　　　m^(p − 1) ≡ 1 mod p

　　　m^(q − 1) ≡ 1 mod q

が成り立つ。ここで L ＝ (p − 1)(q − 1) だったのを思い出そう。上の2つの合同式をそれぞれ (q − 1) 乗、 (p − 1) 乗して

　　　m^L ≡ 1 mod p

　　　m^L ≡ 1 mod q

となる。合同の言い換えによると

　　　m^L ＝ 1 ＋ (pの倍数)

　　　m^L ＝ 1 ＋ (qの倍数)

だから、 1 を移項して

　　　m^L − 1 ＝ (pの倍数)

　　　m^L − 1 ＝ (qの倍数)

となる。 p、q は異なる素数なので

　　　m^L − 1

　　　＝ (pの倍数かつqの倍数)

　　　＝ (p qの倍数)

　　　＝ (Nの倍数)

より

　　　m^L ≡ 1 mod N

となる。すると

　　　e d ＋ L M ＝ 1

だったので、 mod N で考えると

　　　c^d

　　　＝ m^(e d)

　　　＝ m^(1 − L M)

　　　＝ m^1 × m^(− L M)

　　　＝ m × (m^L)^(− M)

　　　≡ m × 1^(− M)

　　　＝ m

となり、めでたく平文 m が姿を表すということだ」

「へえ、なるほどー」

　3年生の柴山はかなり飲み込みが早かった。アリサも負けじと板書の写しを急いで理解に努めようとしていた。

<thm>

■RSA暗号： p、 q を巨大な素数とする。 N ＝ p q、 L ＝ (p − 1)(q − 1) とするとき、 L と互いに素な正の整数 e をランダムにとり、

　　　e d ≡ 1 mod L

となる正の整数 d をとる。このとき、任意の整数 m に対して、 m^e を N で割ったときの余りを c とするとき、

　　　c^d ≡ m mod N

が成り立つ。

</thm>

「では、実際に具体例を見てみようか。文字コードはオリジナルでいこう。十の位で行を表し、一の位で段を表すことにする。ただし、ア行カ行サ行……は順に0、1、2……で表し、ア段イ段ウ段を順にそれぞれ1、2、3……で表ことにする。例えば、アケミだったら

　　　011462

となる」

「なんで行は 0 から始まるのに段は 1 で始まるんですか？」

「本当は 1 から始めたかったんだけど、そしたらワ行の領域が確保できなかったんだ」

　柴山は指を折りながら「アカサタナ……」と数え始めた。

「そっか、全部で十行あるから、十の位は 0 から始めないと足りないんですね」

「そういうこと。では

　　　m ＝ 11462

と置いて m を暗号化してみよう。ぱっと思いつく我々にとって大きな素数として

　　　p ＝ 1777、q ＝ 1993

をとろう」

「ぱっとって、私たちには思いつきませんよ」

「確か、 1993 は『ジュラシック・パーク』の公開年ですよね。 1777 はなんですか？」

　アリサが覚えていた。

「さっき生年月日問題でさりげなく 1777 を使っていたが、実はガウスの誕生年でやはり素数だ」

「またガウスですね」

「さて、RSAのアリゴリズムにのっとり、

　　　N ＝ p q ＝ 1777・1993

　　　L ＝ (p − 1)(q − 1) ＝ 1776・1992

とする。柴山、計算」

「はいはーい。

　　　N ＝ 3541561

　　　L ＝ 3537792

になりました」

　柴山はそろばんをやっていて暗算が得意である。

「よし。 e としては 65537 を使いたいが、さすがに大きすぎるので、 F_2 ＝ 17 を使おう。すなわち

　　　e ＝ 17

とする。次に

　　　e d ＋ L M ＝ 1 　⇔　 17d ＋ 3537792M ＝ 1

となる整数 d、M を求めよう。これは多分高校でやってる不定方程式ってやつだ。大学ではディオファントス方程式とかいう。本来だったら拡張ユークリッド互除法を使うんだが、手計算でもできないかやってみよう」

「え、これって、勘で1組の解を探すやつですよね。コンピューターなしでいけますか？」

「あまり文明の利器に頼ってもいかんぞ。試しに L を e で割ってくれ」

「……文明の利器には頼らないけど、私には頼るんですね」

　柴山のその言葉に、アリサは噴き出してしまった。

「違う違う。別に柴山に頼ってるわけじゃなくて、試してるんだよ」

　慈道は自己矛盾に動揺したが、すぐに開き直る。

「どうせ面倒臭いからですよね？」

「いいから早くやれ」

「はいはい……商 208105、余り 7 です」

「ご苦労。

　　　L ＝ 208105e ＋ 7

だから、 e d ＋ L M ＝ 1 に代入すると

　　　e d ＋ (208105e ＋ 7) M ＝ 1

　　　e(d ＋ 208105M) ＋ 7 M ＝ 1

　　　17(d ＋ 208105M) ＋ 7 M ＝ 1

となるな。おお！」

「え？」

　慈道は一人で感心しているのに対して、柴山とアリサは掴みきれていない。

「なんだ分からないか？　ここまできたら

　　　17x ＋ 7y ＝ 1

の解を探すのと同じだろう」

「ああ、なるほどね！」

　遅れて柴山も気付く。

「x ＝ − 2、y ＝ 5 ですか？」

「いや…… x ＝ 5、y ＝ − 12 がいいな。いいかな？　鈴木さん。これで

　　　17・5 ＋ 7・(− 12) ＝ 1

となったよね」

「はい」

「今俺たちが知りたいのは

　　　17(d ＋ 208105M) ＋ 7 M ＝ 1

を満たす d と M だ。ってことは

　　　d ＋ 208105M ＝ 5

　　　M ＝ − 12

とすればオッケーだろう」

「あ！　本当だ。なるほど」

「係数が大きくなるとついつい互除法に走りたがるが、一回の割り算で突破口が開けることもある。はい。柴山、 d の値」

「もう求めてます。

　　　d ＝ 2497265

です」

「よーし。これで準備は揃ったな。試しにさ、スマホで

　　　m^e ＝ 11462^17

を計算してみてよ」

「一応やってみますけど、大きすぎて全部表示されないと思いますね。ああ、やっぱり」

　柴山は慈道に横向きでスマートフォンの画面を見せる。そこには

　　　1.017248059505712e62

とあった。

「ふむ。 e62 ってのは 10 の 62 乗ってことかな」

「おそらく」

「よしここらで少し頭を使おう。例えばある数 a を 16 乗したいときは、実際に a を 16 回掛け合わせるよりも、 2 乗計算を 4 回やった方がはるかに速い」

　慈道は黒板に

　　　a

　　　↦ a^2

　　　↦ (a^2)^2 ＝ a^4

　　　↦ (a^4)^2 ＝ a^8

　　　↦ (a^8)^2 ＝ a^16

と書いた。

「おお！　最後に a をかければ a^17 が求まりますね！」

　アリサは口には出さないが、頷いて理解を示していた。

「そう。 m^17 を計算するには、 m を 4 回 2 乗してから m をかければよい。もっというと、 m^17 を N で割ったときの余りが知りたいのだから、 m^17 を計算仕切ってからではなく、段階毎に N で割ったときの余りを求めていけば、常に N 未満の数に抑えられる。お前のスマホで、余りの計算ってできるの？」

「はい。一応」

　iOSの計算機アプリで余りの計算はできないが、Spotlight検索で、例えば a mod b と打ち込むと、 a を b で割ったときの余りが表示される。

「それじゃあ、 m^2 ＝ 11462^2 を N ＝ 3541561 で割ったときの余りを頼む」

「339687 です」

「つまり mod N で考えると、

　　　m^2 ≡ 339687

ということだな。両辺を 2 乗すれば

　　　m^4 ≡ 339687^2

となる。この右辺を N で割った余りを頼む」

「ええっと、 3200589 ですね」

　この調子で、慈道と柴山はスマートフォンの電卓を駆使して

　　　m^4 ≡ 3200589

　　　m^8 ≡ 3081837

　　　m^8 ≡ 3081837

　　　m^16 ≡ 3503501

を得た。

「最後に両辺を m 倍して

　　　m^17 ≡ 3503501 × 11462

となる。はい、右辺の余り！」

「2909844 だと思います」

「そうか、すなわち

　　　m^17 ≡ 2909844

で、この右辺が暗号 c となる」

「いやあ、これは電卓使ってもしんどいですね。完全にコンピューターの仕事って感じです」

「実際は 17 乗じゃなくて 65537 乗だからな」

「確かに……それだけやればセキュアな感じしますね」

「ちなみに 17 は

　　　2^4 ＋ 1

だから、 2 乗 4 回と m 倍 1 回で計算ができた。同様に考えれば

　　　65537 ＝ 2^16 ＋ 1

だから、こっちの場合は 2 乗 16 回と m 倍 1 回で計算できるから、コンピューターにとってはそんなに手間は変わらない」

「そっかー。 65537 回をたった 17 回で……本当によく考えられてますね」

「先人の知恵は恐ろしい。さあ、今度はアケミの文字コード 11462 を暗号化した c ＝ 2909844 を復号しなければならない。復号には c^d だ」

「あれ？　確か d って、 2497265 ですよ」

　柴山は血の気が引いていた。

「さすがにここまできたら文明の利器を借りよう。柴山さ、Mathematicaを作ってる会社のホームページで、色々計算してくれるやつあったろ」

「ああ、WolframAlphaですね。待っててくださいね」

　柴山は手提げからタブレットを取り出して、https://www.wolframalpha.com にアクセスした。

「そこでこの式を計算させてくれ」

　慈道は黒板に

　　　c^d ＝ 2909844^2497265 をN ＝ 3541561で割ったときの余り

と書いて、窓の方を向いて薄暗くなり始めている外の景色を見ていた。

「少々お待ちを……えっと確か、余りを計算するには、mod と書けば十分だったような」

　柴山は黒板を確認しながらWolramAlphaの入力フォームに

　　　2909844^2497265 mod 3541561

と入力していた。

「多分これでいけるかと……えい！」

　柴山はフォームを送信した。

「どうだ？」

　口数が少なくならざるをえないアリサは当然のこと、慈道も妙な緊張感を放出し始めていた。

「見事に 11462 が戻ってきましたよ！」

　柴山は声高に言って、笑顔でタブレットの画面を慈道に向けた。慈道は教卓を乗り越えて、アリサも身を乗り出して確認する。

（https://www.wolframalpha.com/input/?i=2909844%5E2497265+mod+3541561）

「ああ、よかった。これで復号できてなかったら、柴山の電卓計算ミスのせいだから別にいいんだけど……」

　慈道は一息つき、最前列の机の上に座った。

「すごーい」

　アリサも唇を丸くして小さく手叩きをする。その控え目なリアクションがかえって慈道にはいじらしく思えたらしい。

「もともと3文字の日本語でこの規模ですから、もっと長い文章を扱うとなると大変そうですね」

「あ、一応断っておくと、RSA暗号を始めとする公開鍵暗号は暗号化・復号に時間がかかるので、巨大なデータを暗号化するには不向きだそうだ。もし巨大なファイルを暗号化したいのなら、共通鍵暗号で高速に暗号化して、その共通鍵をRSA暗号で暗号化して送るらしい。これなら別に打ち合わせはしなくてもいい」

「鍵を暗号化するのにも使えるんですね。本当に色々考えられてるなあ。純粋数学もいいですけど、こういう数学もちょっと面白いなって思えるようになりました」

「ほう、そりゃあ良かった。俺が知っているRSA暗号の知識はこんなもんだ。お疲れさん」

「お疲れ様ですー」

　柴山はいつもの軽いのりで言った

「ありがとうございました」

　アリサはそう言って相変わらずの上品な仕草でゆっくりお辞儀をした。

「ねえ、小腹が空いたというか、甘いもの食べたくならない？」

　柴山がぺろっと舌を一瞬だけ出してアリサに言った。

「それ、私も思っていたんですー」

　アリサは両の手を合わせて、懐かしむように言う。

「先輩、食堂に行きますよ！」

「あ？　俺は別に甘いものはいらんぞ」

　よく頭の回転には糖分が必要とされるが、慈道は甘いものが苦手だった。

「別にいいですよ。ラーメンでもなんでも食べてればー」

「ああ、そう」

　あまり気が進まない態度をとっているが、いずれも顔立ちが整っている二人の女子大生と食堂に行くということに、慈道は俗な期待を感じていたが、それと同時に気恥ずかしさも感じていた。

　変に取り繕わず、自然体でいつもの俺を演じるんだ。

　慈道はそう自分に言い聞かせ、食堂の方へ気持ちと体を向けた。