Tech Racho エンジニアの「？」を「！」に。
  1. TOP
  2. Ruby / Rails以外の開発一般
  3. 楕円曲線暗号アルゴリズムを理解する
  • Ruby / Rails以外の開発一般

楕円曲線暗号アルゴリズムを理解する

お久しぶりです。yoshiです。みなさん、夏を満喫していますか？　私は溶けそうです。日本の夏はとってもあつい。

覚えている方がいるかどうかは分かりませんが、以前私はRSA公開鍵暗号アルゴリズムを理解するという記事を書きました。今回はその続編（？）です。

楕円曲線について

楕円曲線、という言葉を事前知識無しで見ると、

楕円

多分こんな画像が脳裏に浮かぶと思います。違います。

楕円曲線の楕円は楕円積分から現れた言葉で、楕円積分は文字通り楕円の弧長などを求める方法なので全くの無関係とは言えませんが、少なくとも楕円曲線と楕円は別の図形です。楕円のことは忘れましょう。

実際の楕円曲線は、例を示すと以下のような曲線です。

y^2 = x^3 + x + 1 y^2 = x^3 - x
楕円曲線1 楕円曲線2

一般化すると y^2 = x^3 + ax + b (ただし a \ne 0 または b \ne 0) という式で表されるこのような曲線をワイエルシュトラス型楕円曲線と呼びます。ワイエルシュトラス型、と付いているのは他のパターンもあるからで、

Y^2 = X^3 + 3X^2 + X
楕円曲線3

こんな形の楕円曲線もあります。こちらはモンゴメリ型楕円曲線と言い、一般式 BY^2 = X^3 + AX^2 + X (ただし B(A^2 - 4) \ne 0 ) の形で表すことができます。

いずれにしても、楕円曲線はx軸に対称の滑らかな曲線です。

楕円曲線上の点の加法群

楕円曲線上の任意の点の集合に、無限遠点 O という特殊な点を加えることで、楕円曲線上の加法演算を定義することができます。

ここで言う加法演算は、実数の加法とは異ります。実数の加法と同じく + という記号が現れますが、似たような性質を持っているために同じ記号が使われているだけ、といった感じに捉えてください。

楕円曲線上の点の加法は、以下のように定義されます。

任意の点 P に関して、 P + O = O + P = P

O 以外の2点 P(x_p, y_p), Q(x_q, y_q) に関して、 x_p = x_q かつ y_p = -y_q のとき、 P + Q = O

それ以外の場合、
P \ne Q のとき、P と Q を結ぶ直線を L、
P = Q のとき、楕円曲線の P 上の接線を L とする。
L と楕円曲線の P, Q と異なる交点を R とし、 R の y 座標を反転した点を R' とすると、 P + Q = R'

と、言葉だけで説明するといまいち良く分からないですね。というか無限遠点って何だ。

とりあえず無限遠点のことは置いといて、無限遠点じゃない点に関しての加法演算を視覚化してみます。

P と Q を通る直線と楕円曲線の新たな交点の y 座標を反転した点 R' が一意に定まることが分かるでしょうか。
一方で、上図の R と R' のように、x軸に対称な2点に加法演算を適用した場合、直線と楕円曲線は新たな交点を作らないので、楕円曲線上の一意な点を作れません。このような場合に解なしとしてしまうと加算群が作れなくなってしまうので、無限遠点が導入されます。

無限遠点について

無限遠点という概念を飲み込むのに引っかかりを覚えてしまう人は少なくないかと思います。実際私も「なんだそりゃ」と思わないでもありません。
ユークリッド空間の中だけで考えると、無限遠点を理解するのは難しいです。そのような点は（ユークリッド空間には）存在しないと言わざるを得ません。

なので、分かりやすそうな例を考えてみます。

奥行きのある絵や図を描く時の手法として、一点透視図法というものがあります。建物などを画面上のある特定の点（消失点）から伸びる直線に合わせて描くことで、遠近による歪みがある像をそれなりに正確に描くことができる手法です。

ここで、消失点から伸びる直線は、平面的に見ればもちろん平行ではありませんが、絵の中の世界では平行のはずの線です。ユークリッド空間では平行線はどこまで行っても交わりませんが、一点透視図法の空間では平行線は消失点で交わるのです。したがって、この消失点は、ユークリッド空間上の点に置き換えることができない点ということになります。

ここで、ユークリッド空間の概念を拡張して、無限遠点を導入します。すなわち、

  • 平行線は交わらない

ではなく、

  • 平行線は有限な点では交わらないが、無限遠点で交わる

ということにしてしまえば、一点透視図法からの変換も容易です。このような空間はもはやユークリッド空間とは言い難いですが。
逆に、一点透視図法の消失点は、絵の中の世界における無限遠点であると言えます。

無限遠点の概念は、他にも例えば3DCGの世界などで見ることができます。３Dオブジェクトをライティングする際に、平行光源という物を使い、例えば太陽光のような光を再現することがあります。現実における太陽はもちろん地球から約1auの距離にあって無限遠にある訳ではないので、厳密には太陽からの光は平行ではありませんが、平行としてしまってもおおむね問題なく描画できます（リアリティを求める場合はそれでも足りないかもしれませんが）。現実にはそのような光源は存在しませんが、もし存在すると仮定するなら、それは無限遠に位置する光源ということになります。

さて、無限遠点がなんとなく飲み込めて来たでしょうか。まだ飲み込めてなかったらすみません、もっといい説明の方法がありそうなら教えて下さい。ここから先は無限遠点の概念が分かってきたという体で話します。

楕円曲線上の加法群における無限遠点は、「 y 軸に平行な直線と楕円曲線が交わる点のうち、有限な座標を持たないもの」と考えることができます。もちろん実際は交わりませんが、一点透視図法のように、グラフを傾ければ無限に伸ばした先で直線と楕円曲線が交わる消失点があるはずです。厳密とは言い難いですが、これが O の正体です。

さらにこのまま考えを進めて、 O と楕円曲線上の任意の点 P を結ぶことを考えてみます。
O はもちろん仮想的な点であり、具体的な座標は分かりませんが、これを「消失点と任意の点を結ぶ」と同じように考えてみることができます。消失点から出た直線は一点透視図法の世界では互いに平行な直線です。同様に、無限遠点を通る直線も互いに平行とみなすと、 y 軸に平行な直線が無限遠点を通るわけですから、「無限遠点を通る任意の直線は y 軸と平行」と考えられます。

y 軸に平行で点 P を通る直線は、ユークリッド空間に戻ってくると、一意な一本の直線になり、その x 座標は点 P の x 座標ということになります。

先程のこの図で言うと、 R と R' を結ぶ直線は無限遠点と R を結ぶ直線であると言う事もできるわけです。

さて、ここで R + O について考えてみると、 R と O を通る直線と楕円曲線が作るもう一つの交点は R' となります。そして R' の y 座標を反転した点は R 自身になるわけですから、 R + O = R が成り立つ訳です。

と言うのが、無限遠点 O が楕円曲線上の加法群において「任意の点 P に関して、 P + O = O + P = P」という演算が成り立つ（言い換えれば、 O は楕円曲線上の加法群における単位元である）ロジックかなと思います。だいぶ厳密性を欠いている気はしますが。

無限遠点 O について、ガッテンしていただけましたでしょうか。

加法の一般式

この節は数式がものすごく多くなってしまいどうしたものかと思わないでもないですが、この記事の目的の半分は自分がアルゴリズムを理解することなのでその道筋として書いておきます。同じようなことは色んな場所に書いてあって、Wikipediaの楕円曲線暗号の記事などを見てもいいと思います。ただ、筆者は見ただけではどうしてその計算になるのか分からなかったので細かく計算をやり直しています。

O 以外の点 P(x_p, y_p), Q(x_q, y_q)(x_p \ne x_q) に関して、 P + Q = R'(x_r, -y_r) とすると、その座標を求めるには、P, Q を通る直線の式 y = {{y_p - y_q} \over {x_p - x_q}}(x - x_p) + y_p と楕円曲線の式 y^2 = x^3 + ax + b からなる連立方程式のを解くことになります。

\phi = {{y_p - y_q} \over {x_p - x_q}} とおくと、直線の式は
y = \phi(x - x_p) + y_p = \phi x - \phi x_p + y_p
-\phi x_p + y_p = -{(y_p - y_q)x_p \over {x_p - x_q}} + {(x_p - x_q)y_p \over {x_p - x_q}} = {{x_p y_q - x_q y_p} \over {x_p - x_q}}　より、 \psi = {{x_p y_q - x_q y_p} \over {x_p - x_q}} とおくと、 y = \phi x + \psi となります。

(\phi x + \psi)^2 = x^3 + ax + b を整理して、 x^3 - \phi^2x^2 - 2\phi \psi x + ax - \psi ^2 + b = 0

この3次式の根は (x_p, x_q, x_r) なので、根と係数の関係より、 x_p + x_q + x_r = \phi^2
したがって、
x_r = \phi^2 - x_p - x_q
-y_r = -\phi x_r - \psi
が導けます。

2倍算

P = Q のとき、すなわち P + P を計算する時は、上記の方法と同じように \phi を求めることはできず、 P における楕円曲線の接線を使います、つまり、 y^2 = x^3 + ax + b の両辺を x で微分して、

2y\frac{dy}{dx} = 3x^2 + a
y' = \frac{dy}{dx} = {3x^2 + a \over 2y}

これに x_p, y_p を代入したものが傾きとなるため、

\phi = {3{x_p}^2 + a \over 2y_p}
\psi = y_p - \phi x_p = - {3{x_p}^3 + ax_p - 2{y_p}^2 \over 2y_p}

となります、ここまで来れば後は P, Q が異なる点である時と同じように求めることができます。

整数倍

これらの式から、整数倍を導くことができます。これはそれほど難しい話ではありません。楕円曲線上の任意の点について、 P + P = 2P, P + 2P = 3P, P + 3P = 4P, ... と繰り返せば整数倍です。

コンピューターで計算する際は愚直に繰り返すのではなく高速化を行うらしいのですが、そこは本題には関係ないので割愛します（実際の所、筆者がまだ理解してません）

楕円曲線「暗号」の話

この文書の主題は暗号です。ここまで楕円曲線上の加法群の話をして来ましたが、数学的な厳密性はさておき、これは暗号の話をする前置きです。

今までは実数座標系の楕円曲線について考えてきましたが、コンピューターでは実数は扱えないので、今後は有限体 \mathbb{F}_p 上の楕円曲線という物を扱います。

さて、今度は有限体 \mathbb{F}_p という概念が登場した訳ですので、少しばかりこれにも触れる必要があります。とは言え、ここらへんの話を始めると長くなる上に本筋から外れすぎるのでゆるふわな説明で留めたいところです。体より広範な概念である群についてもあまり説明せずに登場させてしまったことだし。

有限体は、四則演算が成立する有限個の元からなる集合です。プログラマーにとってわかりやすいのは整数型でしょうか。整数型の値はそのビット数で表すことのできる範囲しかとれないため、有限集合であり、四則演算が成り立つので有限体と言えます。

つまり、コンピューターで扱うのは有限体が限界であり、そのため、有限体 \mathbb{F}_p 上の楕円曲線という物に落とし込まないといけないのです。ここで、 \mathbb{F} は有限体を表す慣例的な記号であり、 p は任意の素数です。

上述のようにワイエルシュトラス型楕円曲線の式は y^2 = x^3 + ax + b で表されますが、これに相当する有限体 \mathbb{F}_p 上の楕円曲線はこうです。

y^2 \equiv x^3 + ax + b \pmod p

実際に暗号化に使う p はとても大きな数を使いますが、例によって簡単にするために p = 5 で考えてみます。
楕円曲線は上で使った例から y^2 = x^3 + x + 1 の曲線を持ってきてみましょう。つまり、

y^2 \equiv x^3 + x + 1 \pmod 5

というものについて考えます。

有限体 \mathbb{F}_5 の元は 0, 1, 2, 3, 4 の5つです。

x = 0 の時、 y^2 \equiv 0^3 + 0 + 1 \equiv 1 \pmod 5 で、これを満たすのは y = 1, 4 です。
x = 1 の時、 y^2 \equiv 1^3 + 1 + 1 \equiv 3 \pmod 5 で、これを満たす y はありません。
x = 2 の時、 y^2 \equiv 2^3 + 2 + 1 \equiv 1 \pmod 5 で、これを満たすのは y = 1, 4 です。
x = 3 の時、 y^2 \equiv 3^3 + 3 + 1 \equiv 1 \pmod 5 で、これを満たすのは y = 1, 4 です。
x = 4 の時、 y^2 \equiv 4^3 + 4 + 1 \equiv 4 \pmod 5 で、これを満たすのは y = 2, 3 です。

という訳で、 \mathbb{F}_5 上の楕円曲線 y^2 \equiv x^3 + x + 1 \pmod 5 はこうなります。

うーむ、もはや楕円でもなければ曲線でもない。

さて、このような点に関して、先程の２倍算や整数倍を実行するとどうなるか。
例えば P=(0, 1) とすると、

\phi = {1 \over 2}
\psi = 1

より、

2P = ({1 \over 4}, -{9 \over 8})

となります。ただ、これだと有限体 \mathbb{F}_5 上の点ではないので、変換を挟む必要があります。
すなわち、 {1 \over 4 } を \pmod 5 で 4 倍したときに 1 になる数とみなすと、これは 4 が対応します。
同様に、 -{9 \over 8} は、 8 倍して -9 (=1 \pmod 5) となる数とみなすと、これは 2 であることが分かります。したがって、

2P \equiv (4, 2) \pmod 5

これを図示すると、このようになります。

このように、有限体 \mathbb{F}_p 上の楕円曲線でも加法や整数倍が成り立ち、 O 以外の点同士の加算は必ず他の楕円曲線上の点もしくは O になります。

点の個数は有限なので、 P, 2P, 3P, ... と順に求めるといずれ O に至り、またP に戻ってくる巡回群となります。

ここで、 点 P を起点とし位数 n の巡回群内の任意の点 Q について、 Q = kP (k = 1, 2, ..., n-1) となるような整数 k が一意に定まることが分かります。

このような整数 k を求めるのは離散対数問題なので、解読は容易ではありません。つまり、 k = 1, 2, ..., n -1 を総当りで求めるくらいの方法しかないので、 k が十分に大きければ現実的な時間で解くことができない問題となります。つまり、 P, Q を公開鍵とすると、 k が秘密鍵ということになります。

k が十分に大きくなるためには n が十分大きくなければならないので、実際の楕円曲線暗号ではそうなるように楕円曲線の種類や巡回群の起点 P が選ばれています。少なくとも、例示したような形の楕円曲線では一瞬で破られてしまいます。

終わりに

当初の予定では、この後前回と同じようにごく簡単な例で暗号化と復号までやってみようと思っていたのですが、思った以上に理論と計算で手間取ってしまい時間がなくなったので、一旦ここで終了としたいと思います。私自身の知識も、「曲線をどうやって暗号に使ってるんだろうなー」みたいな所からそれなりに先に進めたので良しとしたい所です。

それではまた。

おたより発掘


タグ
この記事を書いた人

yoshi

平成元年生まれのC++er。Qiitaで誰が得するのか分からないような重箱の隅をつつく黒魔術を書いていたが、2016年8月からBPSに入社。

yoshiの書いた記事一覧へ

本記事の内容へのお問い合せはTwitterで@techrachoへMentionまたはDMにてご連絡頂くか、運営会社であるBPS株式会社のお問い合せフォームよりお問い合せ下さい。

CONTACT

TechRachoでは、パートナーシップをご検討いただける方からの
ご連絡をお待ちしております。ぜひお気軽にご意見・ご相談ください。
CONTACT FORM