## 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

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 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 algorithmShanks Daniel Shanks. Class number, a theory of factorization and genera. Proceedings of Symposium of Pure Mathematics, volume 20, pages 415-40, 1996. , we can write $k$ as $k=j m+i$ with uniquely determined integers $j$ and $i \in\{0,1, \ldots, m-1\}$. Since: Division_Algorithm $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$.

- Fix an integer $m=\lceil\sqrt{n}\rceil$ and compute $m P$.
- Construct and store a list of $i P$ for $0 \leq i<m$.
- Compute the points $Q-j m P$ for $j=0,1, \ldots, m-1$ until one point matches an entry from the list.
- 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)$ |

Get hands-on with 1200+ tech skills courses.