講演抄録/キーワード |
講演名 |
2010-03-05 16:10
楕円離散対数問題を解く確率的アルゴリズムに関する研究 足原 修・相良佳孝・櫻木伸英・○松嶋智子(職能開発大) IT2009-129 ISEC2009-137 WBS2009-108 |
抄録 |
(和) |
一般的な楕円曲線上の離散対数問題に対する確率的な解法を提案する.この方式は,多数の乱数$H_i \in \{0,1,\cdots, g-1\} \; (i=1,2,\cdots,m)$に対して$Q+[H_i]P$を計算し,それらの点を$X$座標の値でソートすることで,$X$座標が等しく $H_i \ne H_j$となる$Q+[H_i]P$と$Q+[H_j]P$のペアを探し,$2K_{secret}+H_i+H_j \equiv 0 \pmod{g}$から$K_{secret}$を求める.ただし,$Q = [K_{secret}]P$とし,$g$を点$P$の位数とする.本論文では,確率1/2以上で解を求めることができる乱数の数$m$が$\sqrt{g}$以下であることを示す.さらに,この解法を拡張して,
計算量を少し増やすことで記憶領域のサイズを小さくする方式や,複数の計算機で効率的に並列処理を行う方式を示す. |
(英) |
In this paper a probabilistic algorithm to solve the ECDLP is presented. This scheme uses the symmetry of the elliptic curve, and can be applied to a wide class of elliptic curves. In the proposed scheme a large number of random integers $H_i \in \{0,1,\cdots, g-1\} \; (i=1,2,\cdots)$ are generated to calculate the points $Q+[H_i]P \; (i=1,2,\cdots)$, where $Q = [K_{secret}]P$ and $g$ is the order of the point $P$. Then, the scheme tries to find a pair of points $Q+[H_i]P$ and $Q+[H_j]P$ whose $X$-coordinates are the same value but $H_i \ne H_j$, i.e., one in the pair is the inverse of the other. If such a pair is found, the secret $K_{secret}$ can be calculated by $2K_{secret}+H_i+H_j \equiv 0 \pmod{g}$.
We investigate the probability to find such a pair among $m$ random points on an elliptic curve. The probability of finding one or more pairs would be 1/2 when $m$ is of the order of $\sqrt{g}$. Furthermore, we discuss the techniques to reduce the size of disk storage and to parallelize the operation with multiple computers. It is also shown that the proposed algorithm can be extended to solve the usual discrete logarithm problem (DLP). |
キーワード |
(和) |
楕円曲線暗号 / 楕円離散対数問題 / ECDLP / DLP / 公開鍵暗号 / / / |
(英) |
ECDLP / elliptic curve / discrete logarithm problem / public key cryptography / / / / |
文献情報 |
信学技報, vol. 109, no. 445, ISEC2009-137, pp. 373-380, 2010年3月. |
資料番号 |
ISEC2009-137 |
発行日 |
2010-02-25 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2009-129 ISEC2009-137 WBS2009-108 |
|