**Preamble**

One side of the security of the ECDSA depends on the Discrete logarithm security of the used Elliptic Curve ( call it $E$). Elliptic curves form an additive algebraic group of order $n$. If the group formed by the used curve is a generic group then the best classical attack is $\mathcal{O}(\sqrt{2^n})$ - Pollard's Rho.

**ECDSA**

**The private key** $k$ is calculated as a random integer in the interval $[1,n-1]$ and kept secret all the time. Note that the private key $k$ is an integer, not a point on the curve $E$.

The public key $P$, on the other hand, is calculated as a point $p = [k]G$ where $G$ is the base point of the curve defined in the standards and the operation $[k]G$ is called the scalar multiplication defined as;

$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$

This should not be confused with multiplication, no this is what we write to simplify the $k$-times additions.

The $[k]P$ can be calculated at least with double-and-add algorithm to fasten the calculation in $\mathcal{O}(\log k)$-time.

**The points**

Now as we can see, even the $k=0$ is not a problem in ECDSA since it is not a valid value for $k$.

**If the discrete log is easy**

If the discrete log is easy on this curve, that is finding $k$ given $[k]G$, then every value is easily derived.

If the curve is backdoored with another base point $H$, i.e. someone can solve the discrete logarithm to the base $H$ on the curve group. Then they can use this to solve the Dlog on the base $G$ very easily;

- They calculate $G = [t]H$ for $t \in [1,n-1]$ only once
- They solve $P =[k\cdot a]G$ to the base $H$ for $a \in [0,n-1]$. Once $ka$ is found the $k$ can be calculated as $k = a \cdot k \cdot a^{-1}$ since we know the $a$ and $a^{-1} \cdot a = 1 \bmod n$.

**If the discrete log is not easy**

In this case, one can calculate some of them up to their maximal power. Let assume you can use the supercomputer Summit and you have the power to calculate $2^{70}$ double-and-add for a given number $t$. They calculate and set up a hash table to fast query for the existence of the discrete log in the range $[1,2^{70}]$. The run in one year, and the required storage is $2^{70}*256*3$-bits (~147574 Petabyte). Well, storage is one of the problems and the other is hash table may not be $\mathcal{O}(1)$ anymore. Let assume that you have solved this problem, then what is the probability that you can find a given private key from the public key. The exact value depends on the curve group, assume one uses a curve group of size $2^{256}$ to be secure against the standard Dlog attacks. The hit probability is $$\frac{2^{70}}{2^{256}} = \frac{1}{2^{186}}.$$ This even has far less probability than $\dfrac{1}{100}$, so we say it-is-not-going-to-happen!

Does Instead of sequential random choices of $t$s change the result, NO!

**Special note 1**:`0x0000...0000`

is the usual encoding of the $\mathcal{O}(n)$ since $(0,0)$ is not on the curve. This is not accepted as a valid public key in SEC 1 Ver. 2.0 section 3.2.2.1.

**Special note 2**: Some elliptic curves are prime curves this means that the group they formed has prime order. In this case, every element is a generator, except the identity element. If the order is not prime, like in the Curve25519, then we have the cofactor $h = \#E(K)/n$ where $n$ is the largest prime dividing the order of the curve. If the full group is used, it is easy to notice the small order elements, simply check $[o]P = \mathcal{O}$ or not, where $o$ is the small order. For Curve25519, the $o$ values are $2,4,$ and $8$. This is not a security problem since legitimate users always choose $k \equiv 0 \pmod 8$.