はじめに
楕円曲線のFault Attackについて. Fault Attackと言っても色々あるが, 今回は特にBase PointのValidationが行われない場合の攻撃について.
- Base Pointのvalidationがない(好きな点を与えられる)
- 与えた点について計算結果を返してくれる(たとえば秘密鍵\(d\)を使った\([d]P\))
上の条件を満たす時に成功する.
簡単に説明すると, DLPを解くのが難しい(位数が素数である)曲線を都合の良い(位数が小さな素数に素因数分解できる)曲線に置き換えてDLPを解く.
事前準備
定義体は\(K := GF(p)\)とする(256 [bits] 程度). \(a, b \in K\)
\( E := \{ (x, y) \in K \mid y^{2} = x^{3} + ax + b \} \cup \{ \mathcal{O} \} \) \(|E|\)は素数.
\(P, Q \in E\), \(Q = [d]P\), \(d\)は秘密鍵とする.
今, オラクルとして好きな点\(P\)を投げると\(d\)倍して\([d]P\)を返してくれるとする. このままではPohlig-Hellman Algorithmも使えないのでDLPを効率的に解けない.
攻撃の解説
\(P^{\prime}\)を曲線\(E\)に乗っていない点とする. \(P^{\prime} \notin E \)
この\(P^{\prime}\)を与えて\(Q^{\prime} = [d]P^{\prime}\)を得る.
\(P^{\prime}, Q^{\prime}\)が乗るような曲線 \( E^{\prime} := \{ (x, y) \in K \mid y^{2} = x^{3} + a^{\prime}x + b^{\prime} \} \cup \{ \mathcal{O} \} \) を考えたい.
楕円曲線のパラメータ\(b\)は点の足し算や倍算に影響しないので, \(a^{\prime} = a\)とすれば\(E^{\prime}\)上の\(d\)倍は\(E\)上の\(d\)倍に対応する.
\(b^{\prime}\)は\(P^{\prime}\)が曲線\(E^{\prime}\)に乗るように取ればよいので, \(b^{\prime} := y_{P}^{2} - x_{P}^{3} - ax_{P}\)
\(|E^{\prime}|\)が小さい素数に素因数分解できるように\(P^{\prime}\)を取れば\(Q^{\prime} = [d]P^{\prime} \)のDLPを簡単に解くことができ, これは\(Q = [d]P \)に対応しているので\(E\)上のDLPが解けたことになる.
\(E^{\prime}\)の例として, \(4a^{3}+27{b^{\prime}}^{2} = 0\)となるように\(b^{\prime}\)を取ると\((F_{p}, *) \)のDLPに落とせる. この方法を採用するかどうかは, \(|E^{\prime}|\)と\(p-1\)の素因数分解の結果で決めればいいだろう.
おわりに
まだ他にも楕円曲線に対するFalut Attackはあるのでまとめていきたい.
参考
- Abdulaziz Alkhoraidly, Agustín Domínguez-Oviedo, M. Anwar Hasan, ”Fault Attacks on Elliptic Curve Cryptosystems”, Fault Analysis in Cryptography (2012) pp.137-155
