未解決問題が生み落とした楕円曲線暗号〜暗号の仕組み”その８”

　｢スパイコード〜CICADA3301｣(2021年)というタイトルだけはまともなC級コメディーを見た。勿論､すぐに見るのを止めたが・・
　因みに､CICADAとはネット上に投稿された未解読の暗号パズルの事で､”高度な知的能力を持つ人を募集する”との目的で､ネット上で拡散され､都市伝説的な話題となったらしい。
　但し､主人公が暗号通貨ウォレットをハッキングし､一瞬で解読するという序盤の場面だが､彼は単に初歩的な総当たり解読法を試み､”123456”と打っただけで突破してしまう。流石､これには笑えたが､暗号通貨の標準アルゴリズムであるECC(楕円曲線暗号)がこんな簡単な筈もないが､子供騙しのコメディにしても程がある。
　だが､暗号解読のアルゴリズムが発見されれば､映画の様な事態にならないとは限らない。

　さてと､前回｢その7｣では､大まかな視点から”ポストRSA”とされる楕円曲線暗号(ECC)の未来予想図を述べました。
　そこで今日は､ミレニアム未解決問題とされる｢BSD予想｣の視点から､楕円曲線暗号の仕組みを掘り下げていきます。

100万ドルの未解決問題と暗号解読

　以下､｢数学の国のミステリー｣(M･D･ソートイ著)の第10章”100万ドルの問題”では､楕円曲線暗号(ECC)解読の困難さが､非常に判り易く説明されてるので､大まかに引用します。
　まず､例で上げた楕円曲線:y²=x³−2上のある点のx座標を3とすれば､y=±5となり､xとy座標共に整数(又は分数)で表され､(3,5)と(3,−5)は共に有理点(又は分数点)と呼ばれる。
　一方で､曲線y²=x³−2上のある点のx座標を2とすれば､y=±√6となり､√6=2.449487427831⋯は整数や分数では表されない”無理数”となる。
　そこで､楕円曲線上の点が(x=3の時の様に)x,y共に整数か分数の様な有理数となる点(有理点又は分数点)を見つける事は非常に珍しい､いや難しい。言い換えれば､普通に楕円曲線上の点を辿れば､そのx,y座標の殆どが無理数なのだ。
　つまり､前回で述べた”Qが有理点(分数か整数)となる事の困難さ”とは､そういう事である。

　因みに､無理数自体は古代ギリシャ人が既に発見してたが､彼らは我ら現代人みたいにバカじゃなかった。驚く事に､楕円曲線上に有理点(又は分数点)が1つ見つかった時､その点を利用して(同じ様な)新たな有理点を見つける方法を既に発見していたのだ。
　彼らは､最初に見つけた楕円曲線上の有理点､例えば､y²=x³−2上の点(3,5)でその曲線に接する接戦を引き､そのまま線を伸ばすと曲線上の別の点で交わり､交点のx,y座標が共に有理数(分数)になる有理点(分数点)を得た。
　事実､この新たな点は分数点(129/100,383/1000)となる(上図1)。更に､この交点から接戦を引き､再度新たな交点を求めると､(2340922881/45427600,93966726337279/306182024000)という分数点が得られる。　

　だが､この様な幾何学的な操作なしには､x=2340922881/45427600という分数を入れた時にyが分数になるという事は､まずもって分かる筈もない。
　因みに楕円曲線では､以上の手順を繰り返せば､曲線上の分数点(x,y)を幾らでも得る事が出来る。つまり､一般的な楕円曲線:y²=x³+ax+bでは､その曲線上にある分数点(x₁,y₁)が1つ見つかれば､x₂={(3x₁²+a)²−8x₁y₁²}/4y₁²､y₂={x₁⁶+5ax₁⁴+20bx₁³−5ax₁²−4abx₁−a³−8b²}/8y₁³とおく事で､新たな分数点(x₂,y₂)を得る事が出来るのだ。
　但し､先述の楕円曲線y²=x³−2では､このやり方だと無数の分数点が見つかるが､中には限られた数の点しか見つからない曲線もある。
　例えば､y²=x³−43x+166で定義される楕円曲線の場合､この曲線上には(x,y)=(0,0)(3,8)(3,-8)(-5,16)(-5,-16)(11,32)(11,-32)と､有理点が僅かに7個しか存在しないし､更にそれら全てが整数点となる。

　そこで､100万ドルの懸賞金が掛かった問題とは､”バーチ･スウィンナートン=ダイアー(BSD)予想”と呼ばれる未解決問題であるが､”楕円曲線上に無数の有理点(分数点)があるかどうか”を判別する手段の有無を問う。
　つまり､この未解決問題を解く困難さこそが楕円曲線暗号の堅固性を保証する。
　事実､この新たな暗号アルゴリズムでは､まず巧みな数字を使い､クレジットカード番号やメッセージを楕円曲線上のある点に変換し､上で説明したやり方で､その点を数学的(又は幾何学的に)に別の点に移して暗号化する。
　勿論､この手順の逆を辿って暗号を解くには､ある種の超高度な数学､つまり､未解決のBSD問題を解く必要があるが､勿論､今のところ解読は不可能である。

　従って､未解決難題”BSD予想”を解く事ができれば､アナタは100万ドルを手に出来るだろうし､その時には楕円曲線暗号は破綻し､史上最高で”最狂の頭脳を持つ”ハッカーと､数学者からも称賛される事だろう。
　もしかしたら､ネット社会は破綻し､ハッカーもハックという言葉も消滅するかもだが､ハッカーが天才数学者に挑み､その領域に辿り着いたという伝説だけは残るのだろう。

ECC暗号とBSD予想

　正確に言えば､BSD予想とは”楕円曲線の方程式の解が有限個か？無限個か？を判別する”方法についての予想である。
　少し言い換えると､"楕円曲線上の有理点を通る直線との交点を求める方程式に有理数解(有理点)が有限個又は無限個存在するかを判別する"予想となる。
　以下､｢楕円曲線の有理点｣を参考に纏めます。
　一方で､楕円曲線では(2次曲線の様な単純なパラメータ表示を持たない事で)有理点の個数が大きく 変動する事が知られている。
　例えば､楕円曲線上の有理点を通る直線が楕円曲線と合計3点で交わったとして､残りの2点が有理点だとは限らない。
　そこで､楕円曲線上の2つの点P,Qに対し､その2点を通る直線は楕円曲線と3点目のR′で交わる(上図2)。仮にP,Qが有理点であれば､そこを通る直線の傾きも有理数となり､点R′も有理点になる事が判る。また､点R′とx軸で対称な点Rも有理点となり､新たに作られたRをR=P+Qと(とりあえず)表記する。

　例えば､(上述した様に)有理点Pでの接線を”P+P”として定義し､P+Pで新たに作られた点を2Pと書くと､この操作により､3P=2P+P,4P=3P+P,⋯と順番に有理点が求まる。
　また､2点P,Qを結ぶ直線の傾きが∞になる時は､P+Q=∞と定義すれば､同様に､点Pでの接線の傾きが∞となる時も2P=∞と定義出来る。但し､先述の楕円曲線y²=x³−2上の有理点Pに接線の操作を施すとすぐに∞となるが､先で述べた様に､2P,3P,⋯は全て異なる有理点となる事が判っている。つまり､楕円曲線上の有理点は無数に存在する。
　以上の考察から､楕円曲線の有理点は有限個だったり無限個だったりと複雑な振る舞いをする事が判る。
　更に､｢Mordellの定理｣では､”楕円曲線上のどの点も､P1,⋯,Pnという有限個の有理点の和として求まる”事が知られている。仮に､曲線上に有理点が無限個あっても､有限個の有理点から始め､無限個の有理点が求まるのだ。

　一方で､楕円曲線上にある”全て”の有理点を見つける具体的なアルゴリズムは見つかってはいない。これもまた未解決の難題と言える。
　そこで､”楕円曲線上の有理点の個数の大きさをL関数で記述出来るのでは”と主張するのが､BSD予想だ。勿論､これもごく一部の曲線でしか証明されていないが､ミレニアムの未解決問題であリ続けている。
　更に言えば､有理点が無限個又は有限個存在するか？は､楕円曲線の階数(ランク=rank)に依存する。ここでいう楕円曲線の”階数”とは､曲線上の有理点の集合を群と見る時の､その指標となる。

　元々BSD予想とは､楕円曲線に関する整数論の予想で､楕円曲線Eの有理点の集合E(Q)は有理数体をQとすると､群の構造を持つ事が知られてるが､それを具体的に調べる方法は未だ見つかってはいない。
　そこで､1つの研究対象に楕円曲線のL関数があるが､BSD予想とは堅く言えば､この"L関数:L(s)のs=1での位数が､その楕円曲線の階数(ランク)に一致する事を主張"する。
　一方で､楕円曲線の階数とは(上述の様に)無限個の有理点どうしの”多さ”を比べる指標と考える事が出来る。
　例えば､楕円曲線の階数が0ならその曲線は有限個の有理点を持つし､階数が0よりも大きければ無限個の有理点を持つ事が判っている。
　つまり(柔らかく言えば)､”楕円曲線の有理点の<多さ>の指標となる階数の値をL関数のふるまいを調べる事で決定できる”とBSD予想は主張してるのだ。
　最後は少し抽象的になりましたが､以上､”数理女子”さんのコラムからでした。

補足〜楕円曲線とL関数の振る舞い

　事実､楕円曲線の有理点の数とL関数の振る舞いは密接に関係する。つまり､L関数を解析的道具として使う事で､楕円曲線の階数(ランク)をL関数の零点での導関数を用いて探る事を可能にする。
　因みに､楕円曲線E:y²=x³+ax+bにおけるL関数とは､各素数pを法とした曲線E上の点の個数Nₚからオイラー積(ζ(s)=∏ₚ(1/(1−p⁻ˢ))を構成する事で定義される関数である。
　この時､楕円曲線の判別式Δ=−16(4a³+27b²)を割り切る素数pが存在しないなら､L関数はL(s,E)=∏ₚ(1/(1−aₚp⁻ˢ+p¹⁻²ˢ))で表される。
　但し､aₚ=p−Nₚとなり､整数の組(x,y)=(0≦x

　更に､L関数がL(1,E)=0 をみたし､そのテイラー展開がL(s,E)=aₖ(E)(s−1)ᵏ+aₖ₊₁(E)(s−1)ᵏ⁺¹+⋯と書ける時､このkの値をL関数のs=1における零点の位数と呼ぶ。
　つまり､BSD予想とは”楕円曲線Eの階数がEのL関数L(s,E)のs=1における零点の位数に等しい事を主張”する。
　故に､L(1,E)≠0の時は､L(1,E)のs=1における零点での位数は0となり､BSD予想が正しければ､曲線Eの階数も0となる。従って､楕円曲線は有限個の有理点を持つ事が示せる(上図補足)。

　以上より､この”L関数がs=1で零点を持つ時､その導関数の値が楕円曲線E上の有理点の個数(階数)に関する情報を持つ”というのが､この予想のキモとなるのだ。但し､曲線上の有理点の個数情報とは､楕円曲線の階数であり､有理点の”多さ”の指標となる。
　事実､L関数のs=1での導関数の値を記述した｢Gross-Zagierの公式｣により､L関数の零点での位数が1の時に限っては､BSD予想が正しい事が導ける。
　つまり､L(1,E)=0であればL(s,E)のs=1における零点での位数が1となり､(BSD予想が正しくなり)楕円曲線の階数も1となる。従って､楕円曲線上には無限に有理点が存在する(上図補足)。

　実際､楕円曲線E:y²=x³−2のL関数での振る舞いを曲線データを用いて計算すると､L(1,E)=0となり､L関数の零点はs=1で0を持つ。更に､s=1でのL(s,E)の位数は1となり､BSD予想の部分的解決の結果から､楕円曲線の階級も1(≠0)となるので､この曲線上には無限に有理点が存在する事が示される。
　一方で､y²=x³−43x+166は8個の整数点を持つ事は既に述べたが､事実､L(1,E)≠0と計算でき､(上述した)テイラー展開の零点での位数の定義により､楕円曲線の階数は0となり､有限個の有理点を持つ事が示せる。
　以上より､楕円曲線の階数(ランク)=0の時は､L(1,E)≠0となり､楕円曲線上には有限個の有理点が存在するし､階数≠0の時は､L(1,E)=0となり､無限個の有理点が存在する。
　つまり､BSD予想が主張するのはこの事である。が勿論､これはごく一部の楕円曲線の例での話であり､全ての楕円曲線における解明はほぼ不可能と言える。

　因みに､この様な楕円関数におけるL関数はハッセとヴェイユにより発見され､H･ハッセは複素数の範囲にも解析接続により拡張できると予想したが､楕円曲線の無限に聳える風景を見つけ出すまでには至らなかった。
　｢素数の音楽｣の著者M･D･ソートイの言葉を借りれば､”虚平面上での点1での風景の高さが0なら楕円曲線上の有理点は無限個あるが､高さが0でないなら有理点は有限個である”となる。但し､点1とはL関数でのs=1の事で､風景の高さとはL(1,E)の事であろう。

最後に

　以上をまとめると､BSD予想とは､楕円曲線の階数で示される有理点の分布(有限個か？無限個か？)に関する深遠な予想であり､そうした幾何学上の問題を､L関数の位数(振る舞い)という微積分の問題に結びつけようとする大胆な試みでもある。
　勿論､この予想の証明は未だ困難を極め続けているが､これこそがRSAに代わるECC暗号の安全性を保証してくれる。

　我ら大衆が(騙されてるのも気づかずに)安心してビットコインに群がり､(どんな貧乏でも)おサイフケータイやECサイトに目がないのも､以上で長々と説明した数学上の難問や未解決問題を扱った暗号システムのお陰なのである。
　だが､殆どの大衆は楕円曲線の意味は勿論､その言葉すら知らないだろう。もっと言えば､”BSD予想”や”離散対数問題”なんて夢の夢の筈だ。
　それでも我らは､こうした超難解な暗号の堅固性により､大切な個人情報は守られ､ネット上で安心して買い物や投資やコミニュケーションが出来る。

　楕円曲線暗号(ECC)がこの世に初めて登場した時､”楕円曲線なんて数学者以外に誰が理解出来ようか？”とネット事業者らは反対したらしい。だが”ECCのお陰で楕円曲線を理解しようとする業者が現れれば､とても喜ばしい事じゃないか”と､説得したそうだ。
　つまり､暗号の安全性は数学の難しさに支えられている。更に､数学が難しい程､暗号鍵はより短くでき､処理速度は向上し､使い勝手は良くなる。
　という事で､長々と楕円曲線暗号のお話でした。

数字の国のミステリー (新潮文庫) マーカス デュ・ソートイ 新潮社