楕円曲線の仕組み
離散対数問題
離散対数問題は暗号学の安全性の根拠になる数学的問題です、
$ a^p ≡ x (mod q)で、aとxが明らかな時でも、pは求めることが出来ません。これを「有限体上の離散対数問題」と言います。
この性質を使い、秘密の情報をpに格納することで暗号化されます。
有限体上の楕円曲線
こっからは、数式よりもイメージを膨らませながら理解しましょう
おさらいですが、フェルマーの小定理を理解したならば下の図の意味わかりますね?
これを1次元上のお話しだと捉えてください。
https://scrapbox.io/files/6197ed55f6769b00217f1c9d.png
これを2次元にすることを考えてみます。長方形((x,y)平面)をイメージしてください。
その長方形の上を歩き回ることを考えます。するとフェルマーの小定理より、右端に到達すると左端から出てきて、上端に到達すると下端から出てきます。
1次元の場合と同じように両端を張り付けてみるとどうでしょう?ドーナツのような形になります
https://scrapbox.io/files/6197ed61b1c941001f298f5f.png
実はこのドーナツ上にある点(x,y)の集合こそ、みなさんがよく目にするこちらの曲線なのです
https://scrapbox.io/files/61a4ab8a47dbe70022cace00.png
↓Bitcoinとかに使われる楕円曲線
https://scrapbox.io/files/6197ed6a01ccc1001d36558d.png
これらは全て、ドーナツの世界にあります。パラメータの数値が違うので形も異なりますが基本はドーナツです
イメージを残したまま、今度は数式で同じことを説明します。
$ y^2=x^3+ax+b
で決まる点 (x,y) の集合を楕円曲線といいます。(x, y) を複素数にすると、できあがる形は、やはりドーナツになります。
https://scrapbox.io/files/6197ed77758c32001d004162.png
「さっきからやたらドーナツ出すけど、だからなに??」
→このドーナツの上で点を動かすと良いことがあります!!
楕円曲線上で人が歩き回ることを考えましょう。一歩のベクトルがPだとします。
原点Oから2歩進むと2Pの位置にいます。どんどん進んで端に到達すると逆から出てきますね
10歩でも100歩でも10100歩でも進めます。そして歩いて到達した位置10Pや100P、10100Pは容易に求められることが知られています。
https://scrapbox.io/files/6197ed82758c32001d004177.png
さて、この人はうっかり何歩進んでいたか忘れてしまいました。
ところが「原点から自分がいる場所に何歩で到達できるのか」
を求めることはとても難しいということが知られています。なので思い出す術は有りませんorz
正確に書くと
「点PとQが与えられたときに、Q=nPとなるnを求めよ」
という問題になります。
この問題を「楕円曲線上の離散対数問題」(ECDLP)といいます。
この辺りのロジックは普通の離散対数問題と同じですね!それが平面上に拡張されただけです。
「点Pをa倍してQを作るときに、Q = aPからaは求まらない(楕円曲線上の離散対数問題)から、aを秘密鍵にできる」ということ
楕円曲線はy² = x³ + なんちゃら なわけで、点Q(x,y)をプロットすると巨大になってしまう問題があります。なので(x,y)を有限体Fq上にトレースするのは理にかなっているとも言えます。
驚いたことに、楕円曲線上の点を全部有限体の標数qで割っても、元の有理数でやってた楕円曲線上の操作と一致します。
つまり、有理数上の計算は有限体上の楕円曲線でも有効です。
有限体上の楕円曲線だとqで割られて全ての数がバラバラに移され、点もあっちこっち散らばってしまうので、全然直線とか曲線とかないです。楕円曲線暗号は、楕円ではない楕円曲線が素数で割られてバラバラに散ったものの上で動いています。いずれにせよ、素数qで全てを割れば、楕円曲線で生まれた綺麗な加法の性質は全て保存されるということです
https://scrapbox.io/files/61a4b22430f2bb001daa01f7.png