Attacking the ECDLP

Learn the different types of attacks on ECDLP in this lesson.

We'll cover the following


There are two different categories of attacks on the ECDLP, namely generic attacks that work in general, regardless of the properties of an elliptic curve, and attacks that work for elliptic curves with special properties. We outline these attacks in order to determine how to select curves with good cryptographic properties. This is discussed in detail by Darrel Hankerson et al. (2016)Darrel Hankerson, Alfred J. Menezes, and Scott Vanstone. Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York, 2006. Springer., Don Johnson et al. (2001)Don Johnson, Alfred Menezes, and Scott Vanstone. The elliptic curve digital signature algorithm (ECDSA). International Journal of Information Security, 1(1):36-63, Aug 2001., Neal Koblitz et al. (2000)Neal Koblitz, Alfred Menezes, and Scott Vanstone. The state of elliptic curve cryptography. Des. Codes Cryptography, 19(2-3):173-93, March 2000., Alfred Menezes (2001)Alfred Menezes. Evaluation of security level of cryptography: The elliptic curve discrete logarithm problem (ecdlp). cryptrec-ex-1028-2001.pdf, 2001. Accessed: 2018-11-17., Tun Myat Aung et al. (2017)Tun Myat Aung and Ni Ni Hla. A study of general attacks on elliptic curve discrete logarithm problem over the prime field and binary field. SSRN Electronic Journal 11(11): 1153-60 2017., Lawrence C. Washington (2008)Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography, Second Edition. Discrete Mathematics and Its Applications. New York, 2008. CRC Press., and Annette Werner (2013)Annette Werner. Elliptische Kurven in der Kryptographie. Springer-Lehrbuch. Berlin Heidelberg, 2013. Springer..

In the following description, let E(Fp)E\left(\mathbb{F}_{p}\right) be an elliptic curve over a finite field. Furthermore, we suppose that PP has order nn and QP.Q \in\langle P\rangle . We want to solve the ECDLP kP=Qk P=Q.

  • Baby-Step Giant-Step (BSGS) attack: This generic attack was proposed by ShanksDaniel Shanks. Class number, a theory of factorization and genera. Proceedings of Symposium of Pure Mathematics, volume 20, pages 415-40, 1996. and combines computational power and storage in order to attack the ECDLP. The method requires approximately n\sqrt{n} operations and n\sqrt{n} storage and hence its deterministic running time is O(n)\mathcal{O}(\sqrt{n}). The major disadvantage of this method is that it requires a lot of storage. Let m=nm=\lceil\sqrt{n}\rceil. According to the division algorithm:Division_Algorithm, we can write kk as k=jm+ik=j m+i with uniquely determined integers jj and i{0,1,,m1}i \in\{0,1, \ldots, m-1\}. Since

    Q=kP=(jm+i)P=jmP+iPQ=k P=(j m+i) P=j m P+i P

    it follows that

    iP=QjmP.i P=Q-j m P.

Now, the idea is as follows: we compute and store the whole list of the right side of the equation (i.e., of the baby steps iPi P), and then calculate the possible values of QjmPQ-j m P (the giant steps) until we get a match. Once we find a corresponding point, we know ii, and jj, and hence k=jm+ik=j m+i.

  1. Fix an integer m=nm=\lceil\sqrt{n}\rceil and compute mPm P.
  2. Construct and store a list of iPi P for 0i<m0 \leq i<m.
  3. Compute the points QjmPQ-j m P for j=0,1,,m1j=0,1, \ldots, m-1 until one point matches an entry from the list.
  4. If iP=QjmPi P=Q-j m P, we obtain Q=kPQ=k P with ki+jm  mod nk \equiv i+j m \space \space mod \space n.

An efficient way to compute the solution is to calculate each point iPi P by adding PP to (i1)P(i-1) P (a baby step) and to add mP-m P to Q(j1)mPQ-(j-1) m P (a giant step).


We want to solve the ECDLP kP=Qk P=Q in E(Fp)E\left(\mathbb{F}_{p}\right), where p=991p=991 a prime, E:y2=x3+446x+471,P=(531,165),ord(P)=41E: y^{2}=x^{3}+446 x+471, P=(531,165), ord(P)=41, and Q=(611,751)Q=(611,751).

We put m=41=7m=\lceil\sqrt{41}\rceil=7. First, we compute mP=7P=(756,670)m P=7 P=(756,670). Then, we compute and store the list of baby steps iPi P for i=0,1,,6i=0,1, \ldots, 6 (see Table 1). In the next step, we compute the giant steps, i.e., the points QjmPQ-j m P, as shown in Table 2 (for this, we first compute jmP, then reverse the sign of the yy-component in order to get the inverse jmP-j m P, which we then add to Q), and compare the results with the entries in Table 1. We can see that there is a match for i=5i=5 and j=3j=3, which means that 5P=Q21P5 P=Q-21 P. Hence, it follows that Q=26PQ=26 P.

Table 1

List of baby steps iPiP for i=0,1,,6.i = 0, 1, \cdots, 6.

ii iPiP
0 O\mathcal{O}
1 (531,165)(531,165)
2 (963,446)(963,446)
3 (879,462)(879,462)
4 (366,309)(366,309)
5 (367,809)(367,809)
6 (560,674)(560,674)

Table 2

List of giant steps (at the far-right row of the table)

jj jmj m jmPj m P jmP-j m P Q+(jmP)=QjmPQ+(-j m P)=Q-j m P
0 0 O\mathcal{O} O\mathcal{O} (611,751)(611,751)
1 7 (756,670)(756,670) (756,670)(756,-670) (275,713)(275,713)
2 14 (374,774)(374,774) (374,774)(374,-774) (923,666)(923,666)
3 21 (635,314)(635,314) (635,314)(635,-314) (367,809)(367,809)

Get hands-on with 1200+ tech skills courses.