Abstract: This paper begins by describing basic properties of finite field and elliptic curve cryptography over prime field and binary field. Then we discuss the discrete logarithm problem for elliptic curves and its properties. We study the general common attacks on elliptic curve discrete logarithm problem such as the Baby Step, Giant Step method, Pollard’s rho method and Pohlig-Hellman method, and describe in detail experiments of these attacks over prime field and binary field. The paper finishes by describing expected running time of the attacks and suggesting strong elliptic curves that are not susceptible to these attacks.c
Abstract: Elliptic curve discrete logarithm problem(ECDLP) is
one of problems on which the security of pairing-based cryptography
is based. This paper considers Pollard’s rho method to evaluate
the security of ECDLP on Barreto-Naehrig(BN) curve that is an
efficient pairing-friendly curve. Some techniques are proposed to
make the rho method efficient. Especially, the group structure on
BN curve, distinguished point method, and Montgomery trick are
well-known techniques. This paper applies these techniques and
shows its optimization. According to the experimental results for
which a large-scale parallel system with MySQL is applied, 94-bit
ECDLP was solved about 28 hours by parallelizing 71 computers.