上のような式は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.
式や表を作成するのが面倒大変なので図で解説する.

f:id:ushiromiya3:20190222170016p:plain
以上が単純なDHEである. 楕円曲線に注力したいので詳しい解説は省く.
公開鍵$(g, p)$と$(PubA, PubB)$がわかっても, 離散対数問題の仮定より$(a, b)$が求められないため, 盗み聞きしているYkmには共有鍵を特定できない.

続いてECDHE. 導出過程はDHEとほとんど同じで, べき計算がスカラー倍演算になっただけである(実際はスカラーから位置座標にもなっているが).

f:id:ushiromiya3:20190222172143p:plain 公開鍵$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$を使っている.

参考文献

KMOV Encryption
New Public-Key Schemes Based on Elliptic Curves over the Ring Zn
RFC7748
RFC5480

To Be Continued..

第4話

2019-02-18

楕円曲線入門 (2)

Cryptography

前回の楕円曲線入門では曲線上における演算について解説した.
今回は点のスカラー倍と群構造について解説する.

スカラー倍

前回は足し算と2倍について解説したが, 任意の定数倍はどうすればいいだろうか.
たとえば, Pの100倍である100Pを得るには2PにPを98回足せばよいが¹, 2¹⁰⁰倍するとなると2¹⁰⁰-2回の足し算を行うことになる². これは現実的でないためどうにかしたい.

+ P と * 2 だけで効率的に定数倍を求める(計算量を落とす)ことができればよいだろう.

100Pの場合は

\begin{eqnarray*} 100P & = & 4 * 25P \newline & = & 2^{2} (P + 24P) \newline & = & 2^{2} (P + 8*3P) \newline & = & 2^{2} (P + 2^{3}(P + 2P)) \newline \end{eqnarray*}

2倍, 足し算, 2倍を3回, 足し算, 2倍を2回の計8回の処理で100倍が得られる.

楕円曲線が持つ群構造

曲線状の点は整数点のみを考える.

p = 11 の例

11を法とすると, 同値類の代表元から得られる集合とその位数は{0, 1, .., 10}で11個である.
曲線にはx座標とy座標があるため, (x, y)の組み合わせは

(0, 0), (0, 1), .., (0, 10)   
(1, 0), (1, 1), .., (1, 10)
.  
.  
(10, 0), (10, 1), .., (10, 10)

以上の121個となる. この中から目的の楕円曲線の式を満たす(x, y)の組み合わせを取り出すと楕円曲線の最大の位数が得られる. (厳密には起点から無限遠点までにいくつの点が存在するかをその楕円曲線の位数とするので "最大の"という表現を使っている. base pointをどこにするかで位数が変わるので, セキュリティのためにもbase pointを適当に選んではいけない)

ある点Pをbase pontとして,

P -> 2P  
2P -> 3P   
3P -> ...

と繰り返していくといつか無限遠点Oにたどり着き, 最終的にPに戻ってくる. つまり巡回"群"の体を成している.
これは
$ aP = O; $ となる$a \, (a < p )$が存在し $ O + P = P $ であることから言える.

To be continued

第3話

1: 64Pまで2倍を繰り返してから足し算に移行するなど, 他にもいくつか方法はある
2: 2倍を100回繰り返せばいいのだが, 100bits相当の定数倍というニュアンスで

2019-01-24

楕円曲線入門 (1)

Cryptography

楕円曲線

暗号分野においてかなりの強度を持つとされている楕円曲線について紹介する.

楕円曲線は $$ \frac{x^{2}}{a^{2}} + \frac{y^{2}}{b^{2}} = 1 $$ の式で知られている楕円とは違い, グラフのイメージはどちらかというと3次曲線 $$ y = ax^{3} + bx^{2} + cx + d $$ の y >= 0 の領域をx軸を対象に折り返したものに近い.

f:id:ushiromiya3:20190123231722p:plain

実際の曲線の式は
$$ y^{2} = x^{3} + Ax + B $$ である.

楕円曲線上で演算が可能で, ポイント同士の足し算と, あるポイントの2倍が定義されている. また楕円曲線は群構造を持っているため(トーラスとなっている), 暗号分野でも利用されている. 特に明示していないが, 演算は全て素体上で行われることに注意.

ここでは足し算と2倍演算の解説を行う.

Point Addition

曲線上の2つの点P, Qを結ぶ直線と曲線の交点をx軸を対象に折り返した点をP+Qとする.

$$ P := (x_{1}, y_{1}), \, Q := (x_{2}, y_{2}) $$

f:id:ushiromiya3:20190123231346p:plain

まずはP, Qを通る直線の式を考える.

1次関数の傾きは変化の割合で求めることができるので, yの差分をxの差分で割ればよく

$$ \lambda := \frac{y_{2} - y_{1}}{x_{2} - x_{1}} $$

傾きがわかれば, 通る点はわかっているので直線の式が得られる.

\begin{eqnarray} y - y_{1} & = & \lambda(x - x_{1}) \newline y & = & \lambda(x - x_{1}) + y_{1} \newline y & = & \lambda x - \lambda x_{1} + y_{1} \newline y & = & \lambda x + \beta; \, \beta = y_{1} - \lambda x_{1} \newline \end{eqnarray}

直線と曲線の交点は上式と曲線の式を等式で結び, $$ y^{2} = (\lambda x + \beta)^{2} = x^{3} + Ax + B $$

$$ x^{3} -\lambda^{2}x^{2} - 2 \lambda x \beta - \beta^{2} + Ax + B = 0 $$

の解を求めることでxが特定できる.
この方程式の解(交点)は点Pのx1, 点Qのx2, そして3つ目の交点x3である.
この事実は以下の式で表すことができ $$ (x - x_{1})(x - x_{2})(x - x_{3}) = 0 $$

これを展開すると \begin{eqnarray} x^{3} - x^{2} x_{1} - x^{2} x_{2} - x^{2} x_{3} + x_{1}x_{2}x + x_{1}x_{3}x + x_{2}x_{3}x - x_{1}x_{2}x_{3} & = & 0 \newline x^{3} - x^{2}(x_{1} + x_{2} + x_{3}) + x_{1}x_{2}x + x_{1}x_{3}x + x_{2}x_{3}x - x_{1}x_{2}x_{3} & = & 0 \end{eqnarray}

この式と先の方程式のx²の係数から

\begin{eqnarray} \lambda^{2} & = & x_{1} + x_{2} + x_{3} \newline x_{3} & = & \lambda^{2} - x_{1} - x_{2} \newline \end{eqnarray}

x1, x2はそれぞれ点P, Qのx(既知)で, x3が求めようとしている3つ目の交点である. x3がわかったので, 直線の式に代入し

$$ y = \lambda(x_{3} - x_{1}) + y_{1} $$

ただし, y3はx軸に対称なので

\begin{eqnarray} y_{3} = -y & = & -\lambda(x_{3} - x_{1}) - y_{1} \newline & = & \lambda(x_{1} - x_{3}) - y_{1} \end{eqnarray}

$$ x_{3} := \lambda^{2} - x_{1} - x_{2}, \,\, y_{3} := \lambda(x_{1} - x_{3}) - y_{1} $$

$$ \lambda := \frac{y_{2} - y_{1}}{x_{2} - x_{1}} $$ これでP + Qを求めることができた.

Point Doubling

曲線上のある点における接線と曲線の交点をx軸を対称に折り返した点を2倍値(2P)とする.
点Pに同じ点Pを足したものとしても定義できる. 2つの点が異なるならばPoint Adding, 同じならばPoint Doublingである.

$$ P := (x_{1}, y_{1}), \, Q := (x_{1}, y_{1}) $$

f:id:ushiromiya3:20190123231518p:plain

基本的には足し算と同じだが, λの導出が異なる.
足し算では2点間を結ぶ直線を考えたが, ここでは接線を傾きとするので微分を行う.

$$ y^{2} = x^{3} + Ax + B $$

上式をxで微分すると

\begin{eqnarray} (2y)dy & = & (3x^{2} + A) dx \newline \frac{dy}{dx} & = & \frac{3x^{2} + A}{2y} = \lambda \end{eqnarray}

あとは同様に

$$ x_{3} := \lambda^{2} - 2x_{1}, \,\, y_{3} := \lambda(x_{1} - x_{3}) - y_{1} $$

$$ \lambda := \frac{3x^{2} + A}{2y} $$

これで P + Q = 2Pを求めることができた.

Curve25519

X25519として知られているCurve25519は, 同じ楕円曲線でも今回紹介したものと式が異なり, Montgomery Curveと言われる. 足し算や2倍演算も異なるので注意.

Montgomery Curveの一般式は以下のようになる.

$$ By^{2} = x^{3} + Ax^{2} + x $$

To be continued..

~~安全性や攻撃について~~

第二話