Attacking the ECDLP

Overview

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). http://www.cryptrec.go.jp/exreport/ 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\left(\mathbb{F}_{p}\right)$ be an elliptic curve over a finite field. Furthermore, we suppose that $P$ has order $n$ and $Q \in\langle P\rangle .$ We want to solve the ECDLP $k 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 $\sqrt{n}$ operations and $\sqrt{n}$ storage and hence its deterministic running time is $\mathcal{O}(\sqrt{n})$. The major disadvantage of this method is that it requires a lot of storage. Let $m=\lceil\sqrt{n}\rceil$. According to the division algorithm:Division_Algorithm, we can write $k$ as $k=j m+i$ with uniquely determined integers $j$ and $i \in\{0,1, \ldots, m-1\}$. Since

  $$Q=k P=(j m+i) P=j m P+i P$$

  it follows that

  $$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 $i P$), and then calculate the possible values of $Q-j m P$ (the giant steps) until we get a match. Once we find a corresponding point, we know $i$, and $j$, and hence $k=j m+i$.

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

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

Example:

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

We put $m=\lceil\sqrt{41}\rceil=7$. First, we compute $m P=7 P=(756,670)$. Then, we compute and store the list of baby steps $i P$ for $i=0,1, \ldots, 6$ (see Table 1). In the next step, we compute the giant steps, i.e., the points $Q-j m P$, as shown in Table 2 (for this, we first compute jmP, then reverse the sign of the $y$-component in order to get the inverse $-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=5$ and $j=3$, which means that $5 P=Q-21 P$. Hence, it follows that $Q=26 P$.

Table 1

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

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

Table 2

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

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