RSA暗号に代わる楕円曲線暗号の近未来予想図〜暗号の仕組み”その７”

　前回｢その6｣では､エニグマ暗号の限界とチューリングによるエニグマ解読の歴史を紹介しました。そのチューリングですが､自身が発明した万能計算機によって､代数学における”計算の不完全性”を実証しましたが､”数学の不完全性”となると､そこには明確な矛盾と限界があった事は歪めませんでした。
　その後､チューリングは自身の万能計算機で数学史上の未解決問題とされる｢リーマン予想｣の矛盾を解き明かそうとしたが､簡単に跳ね返されてしまう。
　一方で､暗号の世界でも数学の難題は存在感を増し､現在のRSA暗号は素因数分解の困難さを安全性の根拠としています。が､かつては難攻不落と思われてたエニグマがそうであった様に､RSA暗号も絶対ではない事が明らかになりつつある。

　そこで”ポストRSA”とされる暗号鍵の短い楕円曲線暗号(ECC)が登場し､最近では航空無線やモバイル機器など様々な場面で広く活用され､RSA暗号に代わりつつある勢いです。
　その楕円曲線暗号もRSAアルゴリズムを支える素因数分解と同じく､｢BSD予想｣という未解決問題や離散対数問題の困難さに支えられている。
　そこで今日は､楕円曲線暗号の未来予想図について書きたいと思います。

楕円曲線暗号の仕組み

　楕円曲線暗号(ECC=Elliptic Curve Cryptography)とは､楕円曲線に基づく”公開鍵暗号”の一種で､RSA暗号と共に､鍵交換･デジタル署名･暗号化などの操作を､暗号鍵を公開する事で安全な方法で行う事が出来る。実際､早くから航空無線暗号など飛行機の飛行経路を安全に保つ為に使われていた。
　暗号理論に楕円曲線(EC=elliptic curve)を利用するアイデアは､1985年にニール･コブリッツとビクター･ミラーにより独立に提案され､ECCは2004~05年頃から小型無線などで広く使用される様になる。
　最近では､ビットコインをはじめ､暗号通貨に楕円曲線暗号が採用され､ECCの存在知った人も多いだろうが､BluetoothやWi-Fiやおサイフケータイで有名な近距離通信(NFC)の様な無線通信でも頻繁に使用される様になった。
　そこでまずは､誰もが理解し易い様に､｢楕円曲線暗号とは何か？｣を参考に大まかに紹介する。

　楕円曲線暗号(以下､ECC)の主な特徴として､RSA(素数暗号)よりも短い暗号鍵と狭い帯域幅で高い安全性を確保でき､計算能力が低いスマホやモバイル端末等でも実装できる事にある。
　ECCは楕円曲線と呼ばれる超越関数の難解な数学の分野に基づくが､楕円曲線とは一般に y²=x³+ax+bという形の方程式で定義される。グラフにすれば､x軸に対称な曲線になるが､例えば､a=0,b=−2として､y²=x³−2の曲線上の点のx座標を3とすれば､y=±5となる事からすぐに判る。
　一方で､ECCのセキュリティの堅固性はRSAの素因数分解の困難さと同様に､楕円曲線離散対数問題(EC-DLP)として知られる問題を解決する事の困難さに基づく。
　(少し抽象的になるが)例えば､楕円曲線上の点Pとスカラーk(非負整数)が与えられた時､Q=kPを満たす曲線上の点Qを決定する事の困難さにある(上図)。
　つまり､Q/Pが有理点(x,y座標が共に分数か整数となる点)となる事の困難さと言える。但し､このkが楕円曲線上の離散対数となる事にも留意する。
　故に､ECC暗号は非常に大きな数を因数分解するよりも､遥かに困難とされるのだ。　

　そこで､難解とされる”EC-DLP”に関して(ウイキを参考に)補足すると､巡回群Gの任意の要素(楕円曲線上の点)Qに対し､Q=kGを満たすkが{0,1,…,n−1}の中に常に1つだけ存在する。この様なkをQの離散対数(DL=discrete logarithm)と呼び､群Gから無作為に選らんだQの離散対数を求める問題を”楕円曲線上の離散対数問題”(EC-DLP)と呼ぶ。
　ここで､kからQへは1対1対応であり､kからQを計算するのは比較的容易だが､Qからkを計算する事は実質的に不可能だ。従って､kとQの対応は”一方向性関数”となり､この性質を利用し､スカラーkを秘密鍵､Qを公開鍵としたのがECC暗号となります。

　例えば､最もポピュラーな離散対数問題では､”p素数,g∈Gとy=gˣ(mod p)からxを求めよ”との問題があるが､yを求めるのは容易でも､逆にxを求めるのは困難な事が理解できますね。　
　因みに､aをGの生成元として､Gの任意の元gは整数kを用いてg=aᵏと書く時に､一般的には､k=logₐGを群Gにおけるaを底とする離散対数と呼ぶが､この離散対数kを計算する有効なアルゴリズムは知られてはいない。また､aのべき乗を順に計算し､求めるgが得られるまで延々と計算する方法もあるが､群Gの要素の桁数(bit数)に応じた指数的な実行時間を要する為､巨大なGに対しては実用的でない。
　

RSA暗号の限界

　一方で､RSAも非常に堅牢だが､問題が無い訳ではない。勿論､非常に大きな数を素因数分解するのは困難だが､以前よりかは難しくなくなっている。事実､数学者は何世紀にも渡り､素因数分解を容易にする方法を模索してきた。現実に､大きな数を因数分解するに有効なアルゴリズム(NFS)も存在する。これは110桁を超える大きな数を因数分解する最も高速な方法とされる。
　他方､昨今の計算能力は驚異的な速度で拡大し､”ハードの性能は2年毎に倍増する”という｢ムーアの法則｣は70年代から的中し､更には超過する勢いだ。お陰で計算能力の価格は年と共に低下し続ける。

　従って､非常に大きな数を素因数分解するに必要な計算資源は容易に入手可能であり､(サイバー犯罪者を含む)一般向けに手頃な価格になった為､RSAキーのサイズは拡大する必要がある。故に､RSAでは暗号化と復号化の処理が重くなり､特にスマホ等のモバイル端末上では大きなメッセージの暗号化を実現できない。
　その代わり､昨今のRSAはデジタル署名に広く使用されるから､実際のデータはより短時間のセッションキーを持つ対称暗号化アルゴリズムを使用して暗号化される。
　それとは逆に､楕円曲線暗号は鍵が短い為､安全なセキュリティを提供でき､計算速度と帯域幅の点でより効率的とされる。
　つまり､モバイル端末でも使えるECCの様な安全で高速な暗号システムは､時代のトレンドを掴んでいた事になる。

　ECCとRSAも公開鍵アルゴリズムを使用するが､その仕組みは最も基本的で堅牢なアルゴリズムである”トラップドア関数”にある。このトラップドアをある方向に通り抜ける事は簡単だが､ドアはその方向にしか開かない為､逆方法に通り抜ける事は非常に困難となる。
　これは､ドアの開いたオートロック式では一度閉まれば解読鍵を持ってないと､まずは出られないのと同じ仕組みですね。
　従って､暗号アルゴリズムが効果的かつ安全である為には､メッセージの暗号化が容易である必要があるが､非暗号化鍵(公開鍵)なしで復号化する事はほぼ不可能だ。
　この公開鍵の暗号化には､公開鍵と秘密鍵の 2つが必要で､公開鍵はメッセージを暗号化し､数学的アルゴリズムを適用し､非常に大きくランダムに出現する番号に変換する。メッセージは秘密鍵でのみ復号化でき､一方で､ECCとRSAの背後にある数学は非常に複雑で､コンピュータを使用してのみ解決が可能となる。
　事実､楕円曲線の離散対数問題や素因数分解の高いハードルは､次世代コンピュータでのみクリアできるレヴェルにある。

　
楕円曲線暗号の長所と弱点

　ECCがRSAに優る点として､鍵サイズの小ささが挙げられる。つまり､鍵生成･暗号化･復号化の操作が高速で行なえ､計算リソースも少なく､帯域幅も小さい。これはスマホなどを扱うエンドユーザーの待ち時間が少なく､ストレスが掛らない事を意味する。
　事実､RSAの鍵長は一般的には2048bitだが､ECCでは128bit以上とかなり短い。勿論､RSAが素因数分解の困難さに依るものなら､ECCは楕円曲線上の離散対数問題の困難さと安全性に依るという大きな違いもある。

　その安全性で言えば､ECCはRSAの上を行くとも言われる。確かに､顧客のカード情報は楕円曲線上にバラ撒かれ､跡形も姿を消すのだから､当然とも言えますね。
　一方､量子コンピュータは(理論上では)RSAを破る可能性があると考えられてる。実際にそうなるかは大きな議論の的だが､ECC はその数学的複雑さにより､RSAに比べ､量子コンピュータの攻撃に対し､より耐性があるとされる。
　では､実際にどれ程の耐性があるのか？
　オランダの数学者ArjenLenstraは共同執筆した研究論文の中で､暗号解読と水の沸騰を比較した。
　論文によると､小さじ1杯の水を沸騰させるよりも228bitのRSA鍵を解読するに掛かるエネルギーが少ないとされる一方で､228bitのECC鍵を解読するエネルギーは､地球上の全ての水を沸騰させる可能性がある。従って､RSAと同レベルのセキュリティでは､2380ビットもの鍵サイズが必要になるという。
　つまり､ECCを突破する事は現在の理論では不可能となる。

　一方で(ウイキでは)､”EC-DLP”を解くアルゴリズムがまだ見つかってない為､RSA暗号と比べ､同レベルの安全性をより短い鍵で実現でき､処理速度も速い事をメリットとして､”ポストRSA”として注目されているとある。
　但し､これまた未解決問題とされるP=NP予想(計算複雑性理論)が成立した場合､EC-DLPを(指数的ではなく)”多項式時間内”で解くアルゴリズムが存在する事になり､ECCが破綻する事が指摘されてはいる。更に､鍵長256bitのECCは､128bitの(古典的な)共通鍵暗号AESと同程度のセキュリティ強度に過ぎないとの指摘もある。

　事実､ECCを標準暗号システムとして認定する全米国立技術研究所(NIST)は､セキュリティ強度が112bitのECC暗号は2030年までは社会的な用途で使用を許容されるが､31年以降は128bit以上のみが許容可能だと勧告する。
　更に､離散対数問題(DLP)を効率的に解く事が出来るショア･アルゴリズムでは､量子コンピュータによるECCの解読にも利用できるとされる。実際に､2004年には109bitのECCが､09年には112bitのECCがPS3により解読されている。だが､228bitのECCを解読する様な量子コンピュータの構築は10年以上先になると見られている。　

　以上､大まかに楕円曲線暗号システムとRSAアルゴリズムの違いと特徴を述べましたが､正直､RSA暗号に代わるECC暗号が現実に登場し､多くの分野で使われている事に､驚きと困惑を感じてます。
　次回は､新世代の暗号アルゴリズムである楕円曲線について､少し掘り下げて説明したいと思います。