Here we present some known attacks against elliptic curve cryptosystems. The scope is limited to algorithms solving the elliptic curve discrete logarithm problem (ECDLP), i. e. to determine given a point and a point , and it does not consider attacks against particular elements of digital signature algorithms based on elliptic curves.

Naive Exhaustive Search: The most simple approach to obtain is to compute successive multiples of until the result is equal to . In the worst case, this takes steps, where is the order of the point .

BabyStep GiantStep Algorithm: This algorithm is a timememory tradeoff of the method of exhaustive search. It requires storage for about points, and its running time is roughly steps in the worst case.

Pollard's Rho Algorithm: This algorithm is a randomized version of the baby step giantstep algorithm. With some modifications it can be sped up to have an expected running time of steps and it requires only a negligible amount of storage.

Parallelized Pollard's Rho Algorithm: The original Pollard's rho algorithm can be parallelized so that when it is run in parallel on processors, the expected running time is roughly

Pollard's Lambda Method: Pollard also presented a lambda method for computing discrete logarithms which is applicable when, the logarithm sought, is known to lie in a certain interval. In particular, when is known to lie in a subinterval , where , the parallelized version of Pollard's lambda method is faster than the parallelized Pollard's rho algorithm.

Multiple Logarithms: It turns out that if a single instance of the ECDLP is solved using (parallelized) Pollard's rho method, the following instances (for the same curve and the same base point ) can be solved faster, since some of the necessary work has already been done in the previous steps. In fact, solving k instances of the ECDLP takes only as much work as it does to solve one instance.
Hence, the best known attack against a single instance of the ECDLP is Pollard's rho algorithm and has an expected running time of , which is fully exponential.
However, there are certain elliptic curves with special vulnerabilities that can be exploited by the following algorithms. These algorithms may have shorter running times as those mentioned before; therefore elliptic curves with these vulnerabilities should be avoided.

PohligHellman Algorithm: This algorithm exploits the factorization of , the order of the point , and reduces the problem of recovering to the problem of recovering modulo each of the prime factors of . We can then recover by using the Chinese Remainder Theorem. As a countermeasure, one should select an elliptic curve whose order is a prime or almost a prime (i. e. a large prime times a small integer).

Supersingular Elliptic Curves: In some cases, the ECDLP in an elliptic curve defined over a finite field can be reduced to the ordinary discrete logarithm problem (DLP) in the multiplicative group of some extension field for . The DLP is the underlying computationally hard mathematical problem for the DSA and one can solve it using the number field sieve algorithm, which has a subexponential running time. To ensure that the reduction algorithm does not apply to a particular curve, one only needs to check that does not divide for all small for which the DLP in is tractable. In practice, it suffices to check this for when .

PrimeField Anomalous Curves: If the number of points on a curve E over is equal to , the ECDLP can be solved efficiently. This attack can be avoided by verifying that the number of points on an elliptic curve is not equal to the cardinality of the underlying field.

Curves Defined Over a Small Field: For elliptic curves with coefficients in , Pollard's rho algorithm for computing elliptic curve logarithms in can be further sped up by a factor of . For example, if is a Koblitz curve, then Pollard's rho algorithm for computing elliptic curve logarithms in ) can be sped up by a factor of .

Curves Defined Over , Composite: The Weil descent might be used to solve the ECDLP for elliptic curves defined over where is composite. There exists some evidence that when has a small divisor , e.g. , the ECDLP can be solved faster than with Pollard's rho algorithm. Thus, elliptic curves over composite fields should not be used.
Let us take a look how secure elliptic curve cryptography is in practice. Certicom challenge is one source that gives a notion about the security of ECC. The challenge is to compute the ECC private keys from a given list of ECC public keys and associated system parameters. The challenge consists of two levels:

Level I: 109bit and 131bit challenge; considered to be feasible

Level II: 163bit, 191bit, 239bit and 359bit challenge; expected to be computationally Infeasible
Concrete recommendations based on the expected cost of the Certicom challenge have been presented. They predict which elliptic curve key sizes can be considered as secure until which year using a model that incorporates technological and cryptanalytical advances. Table presents their recommendations for future years.
Table  Minimum key size for elliptic curve cryptosystems providing a sufficient level of security
Year

Elliptic Curve Key Size

Infeasible Number of Mips Years

Corresponding Number of Years on 450MHz Pentium II PC

2002

139

2,06*10^{10}

4,59*10^{7}

2003

140

3,51*10^{10}

7,80*10^{7}

2004

143

5,98*10^{10}

1,33*10^{8}

2005

147

1,02*10^{11}

2,26*10^{8}

2006

148

1,73*10^{11}

3,84*10^{8}

2007

152

2,94*10^{11}

6,54*10^{8}

2008

155

5,01*10^{11}

1,11*10^{9}

2009

157

8,52*10^{11}

1,89*10^{9}

2010

160

1,45*10^{12}

3,22*10^{9}

2011

163

2,47*10^{12}

5,48*10^{9}

2012

165

4,19*10^{12}

9,32*10^{9}

2013

168

7,14*10^{12}

1,59*10^{10}

2014

172

1,21*10^{13}

2,70*10^{10}

2015

173

2,07*10^{13}

4,59*10^{10}

2016

177

3,51*10^{13}

7,81*10^{10}

2017

180

5,98*10^{13}

1,33*10^{11}

2018

181

1,02*10^{14}

2,26*10^{11}

2019

185

1,73*10^{14}

3,85*10^{11}

2020

188

2,94*10^{14}

6,54*10^{11}

2021

190

5,01*10^{14}

1,11*10^{12}

2022

193

8,52*10^{14}

1,89*10^{12}

Share with your friends: 