Section 4.4 Discrete logs and the ECDLP
What will be the hard problem at the center of elliptic curve cryptographic methods? We'll take the discrete log problem in \(F_p\ad\) and modify it to take account of the additive structure of \(E(\F_p)\text{.}\) We begin with a computational algorithm.
Recall that
The double-and-add algorithm is the exact analogue of the square-and-multiply fast powering algorithm presented in Algorithm 2.4.1.
Algorithm 4.4.1. Double-and-add.
\(E(\F_p)\)\(\F_p\text{.}\)\(P \in E(\F_p)\)\(nP\text{.}\)- Compute the binary expansion of \(n\text{:}\)\begin{equation*} n = n_0 + n_1 \cdot 2 + \ldots + n_r \cdot 2^r \end{equation*}where the coefficents \(n_i \in \{0, 1\}\) and we assume that \(n_r = 1\text{.}\)
- Compute the multiples \(2^i P\) for \(0\leq i \leq r\) by repeated doubling:\begin{align*} A_0 \amp = P\\ A_1 \amp = 2 A_0\\ A_2 \amp = 2 A_1 = 2^2 A_0\\ \amp \vdots\\ A_r \amp = 2 A_{r-1} = 2^{r} A_0. \end{align*}
- Compute \(nP\) with\begin{equation*} nP = n_0 A_0 + n_1 A_1 + \ldots + n_r A_r \end{equation*}where the coeffients \(n_i\) determine if a particular term is present in the expansion of \(m\text{.}\)
This algorithm provides the basis for using elliptic curves in cryptographic applications. On the one hand, the forward computation of \(nP\) given knowledge of \(n, P\) is easy. On the other hand, we have another discrete log problem.
Definition 4.4.2.
The elliptic curve discrete log problem is to find, given points \(P, Q \in E(\F_p)\text{,}\) a number \(n\) so thatThere are some notable issues with treating the ECDLP like its namesake in \(\R\text{.}\) For one, in \(E(\F_p)\) there are points \(P, Q\) for which there is no integer \(n\) so that \(nP = Q\text{.}\) Also, if there is one such \(n\text{,}\) than many exist. Why should this be the case? The structure of \(F_p\) guarantees it.
Here we start to brush up against an important area of algebra concerning what are known as cyclic subgroups, to be considered in detail in a later section if you haven't seen them before. First, note that for any point \(P \in E(\F_p)\text{,}\) the equation \(sP = \mathcal O\) has a solution. Make a list
At some point, an element in the list must repeat, since \(E(\F_p)\) is a finite set. Suppose that the repeat happens for integers \(j,k\) so that \(jP = kP\text{.}\) Then it must be the case that \((k-j)P = \mathcal O\text{,}\) and so \(s = k-j\) is a solution to \(s P = \mathcal O\text{.}\)The smallest such \(s\) is called the order of \(P\) in \(E(\F_p)\text{.}\)
Now suppose that for some \(n_0\text{,}\) we have \(n_0 P = \mathcal Q\) (that is, that \(n_0\) is a discrete log of \(Q\) with respect to \(P\)). For any integer \(k\text{,}\) we have
and so \(n_0 + ks\) is also a discrete log of \(Q\) with respect to \(P\) for all \(k \in \Z\text{.}\) That is, in the elliptic curve setting, logarithms live in \(\Z_s\text{.}\) With this observation, we can justify the name “logarithm” by showing the (odd looking) property
where the proof is left as an exercise. (The usual logarithm satisfies \(\log(xy) = \log x + \log y\text{:}\) the difference in this case is that we're working in an additive group.)
We should make some points about why elliptic curves are a tempting universe in which to do cryptography. First, unlike in \(\F_p\ad\text{,}\) inverses are trivial: if \(P = (x,y)\) then \(-P = (x, -y)\text{,}\) which makes computations much faster in Elgamal type settings. Second, and more importantly, unlike systems build on the integers and factoring problems, the fastest known algorithms that solve the ECDLP are exponential (on the order of \(O(\sqrt{N})\)), which allows the keyspace to be much smaller than methods amenable to attack by index calculus techniques (to be discussed after we talk about RSA).