前回の楕円曲線入門 (2)では曲線上の点のスカラー倍について, 群構造を持つことを示した.
第一話と合わせて, 楕円曲線における計算が可能になった.
本稿では, 前提となる数学知識などを踏まえながら, どのようにして楕円曲線が暗号として利用されるかを解説する.
離散対数問題 (Discrete Logarithm Problem)
楕円曲線上の離散対数問題を考える前に, まず例として一般的な離散対数問題を挙げる.
$$ y = g^{x} \, mod \, p $$
上のような式はElGamalやRSAなどで見たことがあるだろう.
既知である\((y, g, p)\)から未知の\(x\)を求めるのが困難であるものを離散対数問題という. \((x, g, p)\)から\(y\)を求めるのに比べ計算量がはるかに大きい.
楕円曲線の場合は, ある点Pに対してべき計算\(P^{e}\)ではなくスカラー倍\(eP\)を考える. 文献によっては点のスカラー倍表記を\([e]P\)とするものもあり, 本稿ではこちらに従う.
さて, 楕円曲線での離散対数問題を考える.
$$ Q = [e]P $$
既知の\((e, P)\)から\(Q\)は, 前回のスカラー倍計算を考えれば容易に求めることができる. それに対して, \((Q, P)\)から\(e\)を求めることが困難であることが(楕円曲線上の)離散対数問題である.
以上の知識を利用し, 楕円曲線を暗号に用いる.
DHEがよく知られていると思う.
なぜ楕円曲線暗号の利用を勧めるのか
一般的な離散対数問題を解くことよりも楕円曲線上の離散対数問題を解くことが困難だとされているからである.
256bitsの楕円曲線暗号は, RSAでは3072bitsの強度に相当すると言われている(2048としている文献も確認している). なぜ楕円曲線上の離散対数問題を解くことが困難なのか, 知っている人がいたら教えてほしい.
楕円曲線を利用すればRSA等の暗号アルゴリズムよりも小さなビット数で同程度の強度を持つため, いわゆる軽量化ができる.
(EC)DHE
ここでは(楕円曲線)ディフィー・ヘルマン鍵交換の解説をする.
まず登場人物. 通信を行いたいAliceとBob, そして通信を盗み聞きしているYkm.
式や表を作成するのが面倒大変なので図で解説する.
以上が単純なDHEである. 楕円曲線に注力したいので詳しい解説は省く.
公開鍵\((g, p)\)と\((PubA, PubB)\)がわかっても, 離散対数問題の仮定より\((a, b)\)が求められないため, 盗み聞きしているYkmには共有鍵を特定できない.
続いてECDHE. 導出過程はDHEとほとんど同じで, べき計算がスカラー倍演算になっただけである(実際はスカラーから位置座標にもなっているが).
公開鍵\(P\)にたいして, AliceとBobはそれぞれの秘密鍵\(a\)と\(b\)を用意する.
Aliceは\([a]P\)を計算しBobへ,
Bobは\([b]P\)を計算しAliceへ
最後にAliceは\([ab]P\)を, Bobは\([ba]P\)を計算する. \([ab]P = [ba]P\)であることから鍵が共有できたことが示せた.
DHE同様に, \((PubA, PubB)\)から\((a, b)\)を求めるのが困難であるという仮定により, Ykmは共有鍵を特定できない.
もしかするとこの時点で「いや楕円曲線って結局は座標\((x, y)\)だし, 鍵としての利用はどうすりゃええんや??」と思っている人もいるかもしれない.
ここでの解説は省略し, 知りたい人はRFC7748やRFC5480を読むことをおすすめする.
KMOV Encryption
楕円曲線を利用した暗号アルゴリズムで, KとOはそれぞれKoyama氏とOkamoto氏を表しており, 提案者の名前の頭文字を取っている.
RSAに似ている暗号方式である. 1992年に論文が提出されているが, 攻撃法や新しい提案論文が最近提出されている(これとか)
暗号化/復号の解説をする前にPreliminariesを置く.
Preliminaries
- 楕円曲線の表記
再掲だが, 楕円曲線は以下の式で表される(厳密な表記はWikipediaなど参照).
$$ y^{2} = x^{3} + Ax + B $$
AとB, そしてModulusのpを楕円曲線のパラメータとし, これを
$$ E_{p}(A, B) $$
と書き表す.
たとえば, \(E_{p}(3, 1)\) は \( y^{2} = x^{3} + 3x + 1\)
AとBの選び方は,
$$ 4A^{3} + 27B^{2} \neq 0 $$
となるようにするのが通例である. これの理由については省略する.
- 楕円曲線の位数
前回, 楕円曲線は群構造を持つという話をした. ということは``位数''が存在する.
位数が何を表すかというと, たとえば点\(P\)の位数が\(n\)のとき, \([n]P = O\)となる.
もちろん\(E_{p}(A, B)\)の点の選び方によって位数は変わるのだが, 今は最大の位数を考え, これを\(\#E_{p}(A, B)\)と書く. 位数というより曲線上の点の数というとわかりやすいかもしれない.
ある点\(P\)の位数が12だとして, \([12]P\)はもちろん無限遠点(単位元)の\(O\)になるが, 12の約数(\([3]P\)や\([4]P)\)でも単位元に到達することがある.
この場合でも, ラグランジュの定理より, 部分群の位数は元の群の位数を割り切るため点\(P\)に対して\(\#E_{p}(A, B)\)倍すると必ず単位元になる.
$$ [\#E_{p}(A, B)]P = O $$
特殊な場合の位数
KMOVでは, \(p \equiv 2 \, mod \, 3\)である素数pを使って\(E_{p}(0, B)\)の曲線を利用する.
$$ y^{2} = x^{3} + B $$
この時の位数\(\#E_{p}(0, B)\)は必ず\(p+1\)になる.
\(Proof\) \(p \equiv 2 \, mod \, 3\)を満たす素数pを法とした\(F_{p}\)では, \(x \mapsto x^{3}\, mod \, p\)の写像は順序が変わっただけで, 集合としては変化しない(+Bが無視できる).
p = 11 1 2 3 4 5 6 7 8 9 10 ↓ 1 8 5 9 4 7 2 6 3 10
そして, この中で平方剰余である数字の数はBによらず\(\frac{p-1}{2}\)個になる.
平方剰余とは \(x^{2} \equiv a \, mod \, p;\, x,a \in F_{p}\)となる\(x\)が存在する\(a\)を指す.
考える式は\(x^{3} + B\)であり(平方剰余の個数にBは影響しないので無視できる), 上の例で\(B=0\)とすると\(\{1, 3, 4, 5, 9\}\)が平方剰余となる. 実際に\(\frac{11-1}{2} = 5\)個である.
xに対してyは正負があるので, \((x, \pm\sqrt{x^{3}+B})\)
これより \( \frac{p-1}{2} * 2 = (p - 1)\)個.
そして単位元\(O\)と\((\sqrt[3]{-B} ,0)\)で2個.
\begin{eqnarray} \#E_{p}(0, B) & = & \frac{p - 1}{2} * 2 + 2 \newline & = & p + 1 \end{eqnarray}
\(\#E_{p}(0, B) = p+1\)が示せた.
また, \(n=p*q\) のとき, \( \#E_{n}(A, B) = \#E_{p}(A,B)*\#E_{q}(A,B )\) となる. この事実はKMOVの復号で登場する.
ここで重要なのは, 曲線上の点は位数倍で無限遠点(単位元)になるということだ.
Key Generation
基本的にRSAと同様.
大きな素数\(p, q\) ただし \(p \equiv q \equiv 2 \, mod \, 3\)
\(n = p*q\)
適当な数字\(e\)(65537とか)
\(d = e^{-1} \, mod \, (p+1)(q+1) \)
\((e, n)\)を公開鍵, \((d, n)\)を秘密鍵とする.
Encryption
平文(の座標)を\(M\), 暗号文(の座標)を\(C\), 公開鍵を\((e, n)\), 秘密鍵を\(d\)とする.
\begin{eqnarray} M & := & (x_{M}, y_{M}) \newline b_{M} & := & y_{M}^{2} - x_{M}^{3} \, mod \, n \newline E_{M} & := & E_{n}(0, b_{M}) \end{eqnarray}
$$ C = (x_{C}, y_{C}) := e*M \, \, Over \, E_{M} $$
Decryption
\begin{eqnarray} b_{C} & := & y_{C}^{2} - x_{C}^{3} \, mod \, n \newline E_{C} & := & E_{n}(0, b_{C}) \end{eqnarray}
$$ M_{dec} := d*C \, \, Over \, E_{C} $$
以上で復号処理は終わりである.
\begin{eqnarray} M_{dec} & = & d*C \, \, Over \, E_{C} \newline & = & ed * M \newline & = & (k(p+1)(q+1) + 1) * M \newline & = & kO_{M} + M \newline & = & O_{M} + M \newline & = & M \end{eqnarray}
\(ed \equiv 1 \, mod \, (p+1)(q+1)\) と \((O + P) = P\)を使っている.
