Intro-EC-in-Cryptography__3__Elliptic_Curves_in_Cryptography

%hide %latex \section*{3. Elliptic Curves in Cryptography} An elliptic curve over the real numbers can be interpreted as a curve in 2-dimensional space. It is defined by an equation in terms of $x$ and $y,$ and every solution $(\bar{x},\bar{y})$ of this equation is a point on the curve, which can then be graphed in the Cartesian plane. Elliptic curves are not to be confused with ellipses; they are only distantly related. Historically the term ``elliptic curve'' originates from the elliptic integral, which describes the arc length of an ellipse. Such integrals are parameterized by elliptic curves. 

%hide a = [-2,-1,0,1] b = [-1,0.001,1] s='<table bgcolor=lightgrey cellpadding=2>' s += '<tr><td></td><td align="center">$b = -1$</td><td align="center">$b = 0$</td><td align="center">$b = 1$</td></tr>' for i in range(4): s += '<tr><td>$a = %s$</td>'%a[i] for j in range(3): plot(EllipticCurve([a[i],b[j]]),xmax=1.5).save('bild%s.png'%(3*i+j),figsize=2,axes=False) s += '<td align="center"><img src="cell://bild%s.png"></td>'%(3*i+j) s += '</tr>' s += '</table>' html(s) html('Figure 3.1 Elliptic curves defined by $y^2=x^3+ax+b.$') 

b = -1
b = 0
b = 1
a = -2
a = -1
a = 0
a = 1

Figure 3.1 Elliptic curves defined by y^2=x^3+ax+b.

b = -1
b = 0
b = 1
a = -2
a = -1
a = 0
a = 1

Figure 3.1 Elliptic curves defined by y^2=x^3+ax+b.

%hide %latex \noindent Every elliptic curve can be turned into a group by defining a binary operation on the set of its points. To be useful for cryptography we need to define elliptic curves over {\it finite} fields instead of the real numbers because they then become {\it finite} groups. Such elliptic curve groups have a {\bf very hard discrete logarithm problem}, making them ideal for use in cryptographic protocols based on the DLP. This chapter introduces elliptic curves as they are used in cryptography. Some more mathematical prerequisites are necessary. If you are familiar with finite fields you may skip the first section. 

%hide %latex \newcommand{\Fp}{\mathbb{F}_p} \newcommand{\Fq}{\mathbb{F}_q} \subsection*{3.1 Finite Fields} {\it Fields} are abstractions of familiar number systems (such as the rational numbers $\mathbb{Q}$ or the real numbers $\mathbb{R}$) and their essential properties: \medskip \noindent {\bf Definition.} A {\bf field} is a set $K$ together with two operations, usually called {\it addition} and {\it multiplication} and denoted `$+$' and `$\cdot$', respectively, satisfying the following properties. \begin{itemize} \item $(K,+)$ is a commutative group with (additive) identity 0. \item $(K \backslash \{0\},\cdot)$ is a commutative group with (multiplicative) identity 1. \item {\it Distributivity.} For all $a,b,c \in K:~~a \cdot(b+c) = a \cdot b + a \cdot c.$ \end{itemize} Informally, a field is just a set of numbers where arithmetic using addition, subtraction, multiplication and division can be done as usual. Important examples are the rational numbers $\mathbb{Q},$ the real numbers $\mathbb{R},$ and the complex numbers $\mathbb{C}.$ The integers $\mathbb{Z}$ are not a field because, as explained in Chapter 2, $(\mathbb{Z} \backslash \{0\},\cdot)$ is not a group. All the fields mentioned above have an {\it infinite} number of elements, but there are also fields with only a {\it finite} number of elements. Such structures are called {\bf finite fields.} The simplest and most important finite field was introduced in Section 2.3: $\Fp$ for a prime number $p.$ Such fields are called {\bf prime fields.} We have seen that $(\Fp,+)$ is an additive group and $(\Fp^{\times},\cdot)$ is a multiplicative group. Obviously, the distributive law also holds. Essentially, $\mathbb{Z}$ (which is not a field) is turned into a finite field by doing arithmetic modulo a prime \nolinebreak $p.$ The fields $\Fp$ are not the only finite fields. In fact infinitely many kinds of finite fields can be defined. However, it can be shown (see e.g. [Finite Fields]) that they all have one property in common: The number of elements of a finite field (this is called the {\bf cardinality} of the field) is always a power of a prime, i.e. $p^r$ for a prime $p$ and a natural number $r \geq 1.$ Hence there is no finite field with $6$ elements, but there are finite fields with $8 = 2^3$ elements. It is also a basic mathematical fact that all finite fields of the same cardinality are {\it isomorphic,} meaning that they are essentially the same. For this reason, any field of cardinality $q = p^r$ is often written $\Fq$ and in this case, $p$ is referred to as the {\bf characteristic} of the field (infinite fields have characteristic 0). However, note that a finite field $\Fq$ of cardinality $q = p^r$ with $r > 1$ {\it cannot} be represented by the numbers $\{0,1,\ldots,q-1\}$ equipped with arithmetic modulo $q.$ In this case the structure of the field is much more complicated. Similar to the Diffie-Hellman key exchange, many cryptographic protocols use the finite field $\mathbb{F}_p$ (for a prime $p$) because computers have a hard time representing infinite structures, and also because arithmetic mod $p$ can be implemented efficiently. This is also true for elliptic curves used in cryptography: They are defined over a finite field as the underlying structure. When defined over a {\it finite} field, an elliptic curve (which is a set of points) becomes a {\it finite} group itself, again suitable to be used in protocols like the Diffie-Hellman key exchange. So the idea here is to replace the group $(\Fp^{\times},\cdot)$ by a finite elliptic-curve-group $E,$ which is in turn defined over the finite field $\Fp.$ 

%hide %latex \newcommand{\F}{\mathbb{F}} \newcommand{\Fp}{\mathbb{F}_p} \subsection*{3.2 Definition of Elliptic Curves} Let $K$ be a field of characteristic $p \neq 2,3.$ For example, $K$ can be $\mathbb{R}, \mathbb{Q}$ or $\Fp$ for any prime $p \neq 2,3.$ \medskip \noindent {\bf Definition.} An {\bf elliptic curve} $E$ over $K$ is defined by an equation $y^2 = ax^3 + bx + c$, where $a$ and $b$ are in $K$ and $4a^3 + 27b^2 \neq 0$. We often write $E/K$ to emphasize that $E$ is defined {\it over} the field $K.$ \medskip \noindent More precisely, $E$ consists of all points $(x,y) \in K \times K$ which solve the equation $y^2 = ax^3 + bx + c$, and the {\it point at infinity,} denoted by $\mathcal{O}$. This is often written as $$E(K) = \{ (x,y) \in K \times K\ |\ y^2 = ax^3 + bx + c \} \cup \{ \mathcal{O} \}.$$ The equation $y^2 = ax^3 + bx + c$ is called a {\it simplified Weierstrass equation}. The necessity of the point at infinity will become clear in Section 3.3, when point addition is defined. %\medskip \noindent %More generally, one can consider $E(L)$ for an extension field $L$ of $K.$ $E(L)$ is then called the set of {\it $L$-rational} points on $E.$ The following graph shows elliptic curves over $\mathbb{R}$. Note that the point at infinity is not visible in the graph. 

%hide html('<h3>Elliptic Curves over the Real Numbers</h3>') @interact def _(a = slider([-10..3],default=-4), b = (4,(-10..10))): if 4*a^3 + 27*b^2 == 0: html('The choice of $a$ = %s and $b$ = %s does not define an elliptic curve because this makes $27a^3 + 4b^2 = 0.$'%(a,b)) else: E = EllipticCurve([a,b]) s = '$E(\mathbb{R}) = \{ (x,y) \in \mathbb{R} \\times \mathbb{R}\ |\ %s \} \cup \{ \mathcal{O} \}$'%(latex(E)) html('<font size=5>'+s+'</font>') show(plot(E,xmax=3),axes_labels=['x','y']) html('Figure 3.2 Play around with different values for a and b and note how the curve changes. You can choose a between -10 and <br>3, and b between -10 and 10, because this is the range where you can see something happening. Also note that this program <br>only lets you choose integers for a and b, although real numbers are actually allowed for a curve over the real numbers. This <br>is because real numbers for a and b would make the output ugly.') 

%hide %latex \newcommand{\F}{\mathbb{F}} \newcommand{\Fp}{\mathbb{F}_p} \noindent Several questions immediately come to mind. Why is this equation so specific? Why are no other terms, such as $xy, x^2$ or $y,$ in there? Where does the condition $4a^3 + 27b^2 \neq 0$ come from? Really understanding the origin and the meaning of this equation requires a deep knowledge of algebraic geometry. We will only scratch the surface, as this is not essential for the further understanding of elliptic curves. Nevertheless, it gives the interested reader an idea of what the answers to the above questions look like. For more details, see [Silverman1986]. $**$We start out with an {\it affine $n$-space} over a field $K.$ This is simply the set of all $n$-tuples $\{(x_1,\ldots,x_n)~|~x_i \in \bar{K}\},$ where $\bar{K}$ denotes the {\it algebraic closure} of $K.$ In a sense, that's just the generalization of the well-known space $\mathbb{R}^3$ to an arbitrary field $K$ and dimension $n.$ The affine space can then be turned into a {\it projective space} by including some extra points, the so-called ``points at infinity''. A {\it projective variety} is a subset of a projective space with certain properties, and an {\it algebraic curve} is a projective variety of dimension 1. Finally, an {\it elliptic curve} is an algebraic curve of genus 1.$**$ Don't worry if you don't understand all of these big mathematical terms, they will play no part in the rest of this document. What's important though is the following fact: It can be shown that any elliptic curve as defined above is given by an equation of the form $$ y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6 \text{~~with~~} a_1,a_2,a_3,a_4,a_6 \in K \text{~~and~~} \Delta \neq 0. $$ This is called a {\it Weierstrass equation.} The numbering of the coefficients $a_1,\ldots,a_4,a_6$ has historical reasons and is still commonly done this way. $\Delta$ stands for the so-called {\it discriminant,} which can be calculated from the coefficients. The condition $\Delta \neq 0$ ensures that the elliptic curve is ``smooth'', i.e. there are no points at which the curve has two or more distinct tangent lines. For example, see the graph of the curve with the parameters $a=0$ and $b=0$ at the beginning of this chapter. This is technically not an elliptic curve because its equation $y^2=x^3$ has discriminant 0. It can be seen easily that the curve is not smooth. If the characteristic of $K$ is not 2 or 3, the Weierstrass equation can be simplified to $y^2 = x^3 + ax + b$ by applying a {\it change of variables.} So in any field of characteristic $\neq 2$ or 3, every elliptic curve is given by such an equation. This is why we have defined an elliptic curve by this equation in the beginning -- our definition doesn't impose any restrictions on the curve as long as the characteristic of $K$ is not 2 or 3. The discriminant simplifies to $\Delta = -16(4a^3+27b^2)$ and the condition $\Delta \neq 0$ boils down to $4a^3+27b^2 \neq 0.$ In the process of simplification, divisions by multiples of 2 and 3 are necessary. Divisions by multiples of the characteristic of a field always cause problems. Hence fields with characteristic 2 and 3 must be treated separately. If the characteristic of $K$ is 2, then there are two cases to consider. For $a_1 \neq 0$ the Weierstrass equation can be simplified to $y^2 + xy = x^3 + ax^2 + b$ with $a, b \in K$ and $\Delta = b.$ Such a curve is said to be {\it non-supersingular.} If $a_1 = 0,$ then the resulting equation is of the form $y^2+cy = x^3 + ax + b$ with $a,b,c \in K$ and $\Delta = c^4.$ Such a curve is called {\it supersingular.} Similar results can be obtained for fields of characteristic 3, but we omit them because we are not interested in this case. In practice, elliptic curves over the so-called {\bf binary fields} $\F_{2^m}$ (for large natural numbers $m$) and the prime fields $\Fp$ (for large primes $p$) are used for cryptographic purposes. Although $\F_{2^m}$ has characteristic 2 and the representation of elements of $\F_{2^m}$ is mathematically complicated, the arithmetic of elliptic curves over such fields can be implemented very efficiently on computers. That's because computers use the binary representation internally, which facilitates modulo 2 arithmetic. Nevertheless, we concentrate on elliptic curves over $\Fp.$ From now on let $K = \Fp$ for a large prime $p.$ Because the field is finite, the number of solutions $(x,y) \in \Fp \times \Fp$ of the equation $y^2 = x^3 + ax + b$ is also finite. Hence there are only finitely many points on any elliptic curve defined over a finite field. For example, if $E$ is an elliptic curve over $\mathbb{F}_7$ with defining equation $$ y^2 = x^3 + 2x + 4, $$ then the points on $E$ are $$ E(\mathbb{F}_7) = \{ \mathcal{O},(0,2),(0,5),(1,0),(2,3),(2,4),(3,3),(3,4),(6,1),(6,6) \}. $$ The modulo arithmetic produces the effect that the points of such a curve ``jump'' through space and do not result in a continuous curve (like curves over the real numbers). Rather, the graph of an elliptic curve over a finite field looks almost like a random set of points -- with one exception: The graph of any elliptic curve is symmetric about a horizontal line, since for any solution $(x,y)$ of the simplified Weierstrass equation, $(x,-y)$ is also a solution. Look at some finite elliptic curves below. Notice that again, the point at infinity is not part of the picture. 

%hide html('<h3>Elliptic Curves over Finite Fields</h3>') @interact def _(p = (47,(q for q in range(100) if is_prime(q))),a = (4,(0..100)),b = (38,(0..100))): K = GF(p) # p != 2,3?!!! # diskriminante != 0 !!! if Mod(4*a^3 + 27*b^2,p) == 0: html('The choice of $a$ = %s and $b$ = %s does not define an elliptic curve because this makes $27a^3 + 4b^2 = 0$ in $\mathbb{F}_{%s}.$'%(a,b,p)) else: E = EllipticCurve(GF(p),[a,b]) s = '$E(\mathbb{F}_{%s}) = \{ (x,y) \in \mathbb{F}_{%s} \\times \mathbb{F}_{%s}\ |\ %s \} \cup \{ \mathcal{O} \}$\n'%(p,p,p,latex(E)) s += 'Number of points (cardinality): $\# E(\mathbb{F}_{%s}) = %s$\n'%(p,E.cardinality()) html('<font size=5>'+s+'</font>') show(plot(E),axes_labels=['x','y']) html('Figure 3.3 You may choose different finite fields by selecting the parameter p, as well as different elliptic curves by changing <br>a and b. Observe how the number of points grows with the field size, and how fundamentally different these curves look from <br>curves over the real numbers defined by the same equations.') 

%hide %latex \subsection*{3.3 Point Addition on Elliptic Curves} A group is a set of points together with a group operation that fulfills certain properties. Our aim is to turn the set of points on an elliptic curve into a group. Therefore we need to define a group operation. This operation is usually called {\it addition} of points and defined in terms of underlying field operations. Before studying these explicit formulas, it is best to consider the geometric explanation of the addition law. There are several cases to treat. First, let's consider a curve $E$ over a field $K,$ and suppose we want to add two points $P$ and $Q$ on $E.$ If $P \neq Q$ and neither of the points is the point at infinity, their sum $P+Q = R$ is determined as follows: \begin{enumerate} \item Draw a line $l$ through $P$ and $Q$ \item Determine the third intersection $\bar{R}$ of the line $l$ with the curve $E$ \item Reflect $\bar{R}$ about the $x$-axis to obtain $R$ \end{enumerate} The process is visualized below. 

%hide html('<h3>Point Addition</h3>') ########### P != Q ############ E = EllipticCurve([-5,4]) P = E([0,2]) Q = E([1,0]) R = P + Q # E, P, Q p = [plot(E)] p[0] += plot(Q,rgbcolor=(1,0,0.2),pointsize=50) p[0] += plot(P,rgbcolor=(1,0,0.2),pointsize=50) p[0] += text('$E$',(-2.5,2), rgbcolor=(0,0,1), fontsize=12) p[0] += text('$Q$',(1.15,0.5), rgbcolor=(1,0,0.2), fontsize=12) p[0] += text('$P$',(0.2,2.4), rgbcolor=(1,0,0.2), fontsize=12) # l p += [line([(-2,6), (4,-6)], rgbcolor = (0,0.5,0),thickness=0.7)] p[1] += text('$l$',(-1.6,6), rgbcolor=(0,0.5,0), fontsize=12) # \bar{R} p += [plot(-R,rgbcolor=(1,0.4,0),pointsize=50)] p[2] += text('$\\bar{R}$',(3.2,-3.8), rgbcolor=(1,0.4,0), fontsize=12) # R p += [line([(3,-6),(3,6)],rgbcolor=(0,0.5,0),thickness=0.7,linestyle='--')] p[3] += plot(R,rgbcolor=(1,0.4,0),pointsize=50) p[3] += text('$R$',(3.2,3.8), rgbcolor=(1,0.4,0), fontsize=12) t = ['$E: %s,\ \ \ P = (0,2),\ \ \ Q = (1,0)$'%(latex(E)), '1. Draw a line $l$ through $P$ and $Q\ \ \Rightarrow\ \ l: y = -2x + 2$', '2. Determine the third intersection $\\bar{R}$ of the line $l$ with the curve $E\ \ \Rightarrow\ \ \\bar{R} = (%s,%s)$'%(R[0],-R[1]), '3. Reflect $\\bar{R}$ about the $x$-axis to obtain $R\ \ \\Rightarrow \ \ R = (%s,%s)$'%(R[0],R[1])] @interact def _(step=selector([0,1,2,3],nrows=1)): html('<font size=5>'+t[step]+'</font>') pl=p[0] for i in range(step+1): pl += p[i] show(pl,axes_labels=['x','y']) html('Figure 3.4 This graphic visualizes the addition of two points P and Q on a specific elliptic curve. Click on the numbers to see <br>the process step by step.') 

%hide %latex \noindent Next, let's consider the case where $P = Q$ and $\neq \mathcal{O}.$ In the picture above, imagine $Q$ moving along the curve in the direction of $P.$ As $Q$ gets closer and closer to $P,$ the line through the two points moves closer to the tangent line to $E$ at $P.$ The sum $P+P$ is called the {\it double} of $P$ and denoted $2P.$ Doubling a point works just like adding two distinct points, only that $l$ is taken to be the tangent line to $E$ at $P.$ \begin{enumerate} \item Draw a tangent line $l$ to $E$ at $P$ \item Determine the other intersection $\bar{R}$ of the line $l$ with the curve $E$ \item Reflect $\bar{R}$ about the $x$-axis to obtain $R$ \end{enumerate} Have a look at this visualization. 

%hide html('<h3>Point Doubling</h3>') E = EllipticCurve([-36,0]) P = E([-3,9]) R = 2*P # E, P p = [plot(E)] p[0] += plot(P,rgbcolor=(1,0,0.2),pointsize=50) p[0] += text('$E$',(-5.5,-8), rgbcolor=(0,0,1), fontsize=12) p[0] += text('$P$',(-3,11), rgbcolor=(1,0,0.2), fontsize=12) # l p += [line([(-6,21/2), (8,7/2)], rgbcolor = (0,0.5,0),thickness=0.7)] p[1] += text('$l$',(-5,12), rgbcolor=(0,0.5,0), fontsize=12) # \bar{R} p += [plot(-(2*P),rgbcolor=(1,0.4,0),pointsize=50)] p[2] += text('$\\bar{R}$',(5.8,6), rgbcolor=(1,0.4,0), fontsize=12) # R p += [line([(25/4,-15),(25/4,15)],rgbcolor=(0,0.5,0),thickness=0.7,linestyle='--')] p[3] += plot(R,rgbcolor=(1,0.4,0),pointsize=50) p[3] += text('$R$',(5.8,-6), rgbcolor=(1,0.4,0), fontsize=12) t = ['$E: %s,\ \ \ P = (-3,9)$'%(latex(E)), '1. Draw the tangent line $l$ to $E$ at $P\ \ \Rightarrow\ \ l: y = -\\frac{1}{2}x + \\frac{15}{2}$', '2. Determine the other intersection $\\bar{R}$ of the line $l$ with the curve $E\ \ \Rightarrow\ \ \\bar{R} =(\\frac{25}{4},\\frac{35}{8})$', '3. Reflect $\\bar{R}$ about the $x$-axis to obtain $R\ \ \\Rightarrow \ \ R = (\\frac{25}{4},-\\frac{35}{8})$'] @interact def _(step=selector([0,1,2,3],nrows=1)): html('<font size=5>'+t[step]+'</font>') pl=p[0] for i in range(step+1): pl += p[i] show(pl,axes_labels=['x','y']) html('Figure 3.5 This graphic visualizes the doubling of a point P on a specific elliptic curve. Click on the numbers to see the <br>process step by step.') 

%hide %latex \newcommand{\OO}{\mathcal{O}} \noindent Now, what if we wanted to double the point $P = (0,0)$ on the curve above? The tangent line in this point is vertical and therefore seems to have no other intersection with the curve. Here the point at infinity comes into play. It lies on the curve, and it is the other intersection. You can imagine it lying straight up, infinitely far away. Every vertical line intersects the point at infinity. This way it is ensured that {\it every} line has exactly {\it three} intersections with the curve (tangent intersections count double, just like you can have zeros of multiplicity 2 in a graph). Reflecting $\OO$ about the $x$-axis again results in $\OO.$ You can imagine a vertical line ``wrapping around'' the back of the graph, its ends meeting at infinity. Hence the top point at infinity and the bottom point at infinity coincide, in mathematics we say they are {\it identified} with each other. This is the crucial property of the {\it projective} space (as compared to the {\it affine} space). Thus, $2P = 2(0,0) = \OO$ on the curve above. Doubling the points (6,0) and (-6,0) (i.e. any point where the tangent line is vertical) also results in $\OO.$ The picture below is a nice illustration. 

%hide %html <table class="image"> <caption align="bottom">Figure 3.6 Point at infinity<br>Used with friendly permission<br>by Detlef Huehnlein / BSI</caption> <tr><td><img src="http://www.cryptool.org/images/ec.png"></td></tr> </table> 

%hide %latex \newcommand{\OO}{\mathcal{O}} \noindent Similarly, when adding two {\it distinct} points $P$ and $Q$ on a curve results in $\OO$ when the line through them is vertical. This is the case if and only if $P = (x,y)$ and $Q = (x,-y).$ We then write $Q = -P.$ We are now ready to treat the remaining cases. So far, we have not allowed the points being doubled or added to be the point at infinity. Suppose we want to add a point $P \neq \OO$ to the point $\OO.$ The line through these points is the vertical line through $P,$ the other intersection with the curve is $-P,$ and the reflection upon the $x$-axis is $P$ again. So $P + \OO = P$ for any $P.$ When $P = \OO,$ we get $P + \OO = \OO + \OO = \OO$ and the equation still holds. Here's a summary of the procedure of adding two points $P$ and $Q$ on the curve $E$ that considers all special cases: \begin{enumerate} \item If $P = \OO$ then $P + Q = \OO + Q = Q,$ if $Q = \OO$ then $P + Q = P + \OO = P.$ \item Otherwise, if $Q = -P$ then $P + Q = P + (-P) = \OO.$ \item Otherwise, if $P \neq Q$ then do the point addition procedure from above. \item Otherwise, if $P = Q$ then do the point doubling procedure from above. \end{enumerate} It is easy to derive the algebraic formulas for point addition from the geometric definition. All one has to do is work out the line between the two points while distinguishing between the two cases $P = Q$ and $P \neq Q,$ then calculate its other intersection with the curve and reflect the resulting point about the $x$-axis. These are all tasks a school student can do in $\mathbb{R}.$ Here, all operations take place in the underlying field $K,$ but other than that, they work exactly the same. The last step is the easiest. Reflection upon the $x$-axis simply turns a point $(x,y)$ into the point $(x,-y).$ Note that this point is always on the curve, as explained earlier. The formulas given below only work for fields of characteristic $\neq 2,3,$ in particular, for $\mathbb{F}_p$ with $p > 3.$ The other cases are similar. Let $K$ be a field of characteristic $\neq 2,3$ and let $E/K: y^2 = x^3 + ax + b$ be an elliptic curve. Suppose we want to add the points $P = (x_P,y_P)$ and $Q = (x_Q,y_Q)$ on $E$ to obtain the result $P + Q = R = (x_R,y_R).$ Here's the procedure, again considering all special cases: \begin{enumerate} \item If $P = \OO$ then $R = Q,$ if $Q = \OO$ then $R = P.$ \item Otherwise, if $x_P = x_Q$ and $y_P = -y_Q$ then $R = \OO.$ \item Otherwise, if $P \neq Q$ then $$ x_R = \lambda^2 - x_P - x_Q~~~~\text{and}~~~~y_R = \lambda (x_P - x_R) - y_P $$ where $ \lambda = \left( \frac{y_Q-y_P}{x_Q-x_P} \right) $ is the slope of the line through $P$ and $Q$. \item Otherwise, if $P = Q$ then $$ x_R = \lambda^2 - 2x_P~~~~\text{and}~~~~y_R = \lambda (x_P - x_R) - y_P $$ where $ \lambda = \left( \frac{3x_P^2 + a}{2y_P} \right) $ this is the slope of the tangent line at P ($a$ is the coefficient from the curve equation). \end{enumerate} 

%hide html('<h3>Point Addition for Elliptic Curves over the Rational Numbers</h3>') @interact def _(a = (-4,(-10..3)), b = (4,(-10..10)), xP = input_box(default=2,width=12), xQ = input_box(default=1,width=12), negyP = checkbox(label='negative yP',default=False),negyQ = checkbox(label='negative yQ',default=False)): if 4*a^3 + 27*b^2 == 0: html('The choice of $a$ = %d and $b$ = %d does not define an elliptic curve because this makes $27a^3 + 4b^2 = 0.$'%(a,b)) return E = EllipticCurve(QQ,[a,b]) if not E.is_x_coord(xP): html('<font size=5>The choice of xP = $%s$ does not define a rational point on $E: %s.$</font>'%(latex(xP),latex(E))) plot(EllipticCurve([a,b]),xmax=3).show() return if not E.is_x_coord(xQ): html('<font size=5>The choice of xQ = $%s$ does not define a rational point on $E: %s.$</font>'%(latex(xQ),latex(E))) plot(EllipticCurve([a,b]),xmax=3).show() return P = E.lift_x(xP) if negyP: P = -P yP = P[1] pP = plot(P,pointsize=50,rgbcolor="red") Q = E.lift_x(xQ) if negyQ: Q = -Q yQ = Q[1] pQ = plot(Q,pointsize=50,rgbcolor=[1,0.4,0]) R = P+Q xR = R[0] yR = R[1] m = max(2.5,xP,xQ,R[0]) pE = plot(E,xmax=m+0.5) pl = line([(xP,yP),(xQ,yQ),(xR,-yR)], rgbcolor = (1,0.8,0),thickness=1) pll = line([(xR,-yR),(xR,yR)],rgbcolor=(1,0.8,0),thickness=1,linestyle='--') s = '<font color="blue">$E(\mathbb{Q}) = \{ (x,y) \in \mathbb{Q} \\times \mathbb{Q}\ |\ %s \} \cup \{ \mathcal{O} \}$</font>'%(latex(E)) s += '\n<font color="red">$P = (%s,%s)$</font> <font color="#FF6600">$Q = (%s,%s)$</font> '%(P[0],P[1],Q[0],Q[1]) if R == E([0,1,0]): s += '$P + Q = \mathcal{O}$' graph = pE+pP+pQ+line([P,Q],rgbcolor=(1,0.8,0),thickness=1,linestyle='--') else: s += '$R = P + Q$' pR = plot(R,pointsize=50,rgbcolor=(0,0.5,0)) pRm = plot(-R,pointsize=50,rgbcolor="green") if P == Q: lam = (3*xP^2+a)/(2*yP) s += '\n$\lambda = \\frac{3 x_P^2+a}{2 y_P} = \\frac{3 (%s)^2+(%s)}{2 (%s)} = %s$'%(latex(xP),latex(a),latex(yP),latex(lam)) else: lam = (yQ-yP)/(xQ-xP) s += '\n$\lambda = \\frac{y_Q - y_P}{x_Q - x_P} = \\frac{%s - (%s)}{%s - (%s)} = %s$'\ %(latex(yQ),latex(yP),latex(xQ),latex(xP),latex(lam)) xR = lam^2 - xP - xQ s += '\n$x_R = \lambda^2 - x_P - x_Q = ( %s ) ^2 - (%s) - (%s) = %s$'%(latex(lam),latex(xP),latex(xQ),latex(xR)) yR = lam*(xP-xR) - yP s += '\n$y_R = \lambda (x_P - x_R) - y_P = %s (%s - (%s)) - (%s) = %s$'%(latex(lam),latex(xP),latex(xR),latex(yP),latex(yR)) s += '\n$\Rightarrow$ <font color="#008000">$R = (%s,%s)$</font>'%(latex(xR),latex(yR)) graph = pl+pll+pE+pP+pQ+pR+pRm R = E([xR,yR]) if R != P+Q: html('Fehler, falsches Ergebnis!!!') html('<font size=5>'+s+'</font>') show(graph,axes_labels=['x','y']) html('Figure 3.7 Try adding some points. You may choose the curve parameters a and b, and the x-coordinates xP and xQ of the <br>points P and Q that you wish to add (type them in the format 2.5 or 5/2). The program then determines the appropriate <br>y-coordinate (such that (x,y) solves the curve equation). By default, it always takes the positive value for y. You can tell the <br>program to use the negative value by checking the appropriate negative yP or negative yQ box. Although we are working <br>with curves over the rational numbers, not every rational number is a valid x-coordinate (this is only the case if the <br>corresponding y-coordinate is also rational). The program will inform you in such a case and you will have to choose a <br>different value.') 

%hide html('<h3>Point Addition for Elliptic Curves over Finite Fields</h3>') @interact def _(p = (23,(q for q in range(5,100) if is_prime(q))), aa = slider([0..100],default=9,label='a'), bb = slider([0..100],default=17,label='b'), xxP = input_box(default=4,width=12,label='xP'), xxQ = input_box(default=5,width=12,label='xQ'), negyP = checkbox(label='negative yP',default=False), negyQ = checkbox(label='negative yQ',default=False)): K = GF(p) a = K(aa) b = K(bb) xP = K(xxP) xQ = K(xxQ) if 4*a^3 + 27*b^2 == 0: html('The choice of $a$ = %d and $b$ = %d does not define an elliptic curve because this makes $27a^3 + 4b^2 = 0.$'%(a,b)) return E = EllipticCurve(K,[a,b]) if not E.is_x_coord(xP): html('<font size=5>The choice of xP = $%s$ does not define a point on $E: %s.$</font>'%(latex(xP),latex(E))) plot(EllipticCurve([a,b]),xmax=3).show() return if not E.is_x_coord(xQ): html('<font size=5>The choice of xQ = $%s$ does not define a point on $E: %s.$</font>'%(latex(xQ),latex(E))) plot(EllipticCurve([a,b]),xmax=3).show() return P = E.lift_x(xP) if negyP: P = -P yP = P[1] pP = plot(P,pointsize=50,rgbcolor="red") Q = E.lift_x(xQ) if negyQ: Q = -Q yQ = Q[1] pQ = plot(Q,pointsize=50,rgbcolor=[1,0.4,0]) R = P+Q xR = R[0] yR = R[1] m = max(2.5,xP,xQ,R[0]) pE = plot(E,xmax=m+1) s = '<font color="blue">$E(\mathbb{Q}) = \{ (x,y) \in \mathbb{Q} \\times \mathbb{Q}\ |\ %s \} \cup \{ \mathcal{O} \}$</font>'%(latex(E)) s += '\n<font color="red">$P = (%s,%s)$</font> <font color="#FF6600">$Q = (%s,%s)$</font> '%(P[0],P[1],Q[0],Q[1]) if R == E([0,1,0]): s += '$P + Q = \mathcal{O}$' graph = pE+pP+pQ#+line([P,Q],rgbcolor=(1,0.8,0),thickness=1,linestyle='--') else: s += '$R = P + Q$' pR = plot(R,pointsize=50,rgbcolor=(0,0.5,0)) pRm = plot(-R,pointsize=50,rgbcolor="green") if P == Q: lam = (K(3)*xP^2+a)/(K(2)*yP) s += '\n$\lambda = \\frac{3 x_P^2+a}{2 y_P} = \\frac{3 (%s)^2+(%s)}{2 (%s)} = %s$'%(latex(xP),latex(a),latex(yP),latex(lam)) else: lam = (yQ-yP)/(xQ-xP) s += '\n$\lambda = \\frac{y_Q - y_P}{x_Q - x_P} = \\frac{%s - (%s)}{%s - (%s)} = %s$'\ %(latex(yQ),latex(yP),latex(xQ),latex(xP),latex(lam)) xR = lam^2 - xP - xQ s += '\n$x_R = \lambda^2 - x_P - x_Q = ( %s ) ^2 - (%s) - (%s) = %s$'%(latex(lam),latex(xP),latex(xQ),latex(xR)) yR = lam*(xP-xR) - yP s += '\n$y_R = \lambda (x_P - x_R) - y_P = %s (%s - (%s)) - (%s) = %s$'%(latex(lam),latex(xP),latex(xR),latex(yP),latex(yR)) s += '\n$\Rightarrow$ <font color="#7CFC00">$-R = (%s,%s)$</font>, <font color="#008000">$R = (%s,%s)$</font>'%(latex(xR),latex(-yR),latex(xR),latex(yR)) graph = pE+pP+pQ+pR+pRm R = E([xR,yR]) if R != P+Q: html('Fehler, falsches Ergebnis!!!') html('<font size=5>'+s+'</font>') show(graph,axes_labels=['x','y']) html('Figure 3.8 Now try adding some points on curves over finite fields. You may choose the size p of the finite field, the curve <br>parameters a and b, and the x-coordinates xP and xQ of the points P and Q that you wish to add. Again, not all values for <br>xP result in a valid y-coordinate. You may try choosing a point from the graph of the curve and entering the value of its <br>x-coordinate. The program then determines the appropriate y-coordinates (such that (x,y) solves the curve equation). Observe <br>that this discrete case cannot be visualized as nicely as the continuous case (i.e. curves over the real numbers). Because we <br>are working with modulo arithmetic where numbers "wrap around" from p-1 to 0, points seem to "jump around" in space, <br>with the result that straight lines cannot be graphed as such.') 

%hide %latex \newcommand{\OO}{\mathcal{O}} \subsection*{3.4 Elliptic Curve Group Structure} The addition law turns every elliptic curve into a commutative group. More precisely, for any elliptic curve $E$ defined over a field $K$ the set $E(K)$ of points on this curve together with the point addition operation is an additive group $(E(K),+)$ with identity $\OO.$ Three of the four group axioms can be easily verified: \begin{itemize} \item {\it Identity element.} $P + \OO = \OO + P = P$ for all $P \in E(K).$ Thus $\OO$ is the identity element. \item {\it Inverse element.} $P + (-P) = \OO$ for all $P \in E(K).$ Thus any point $P$ has the inverse $-P.$ \item {\it Commutativity.} $P + Q = Q + P$ for all $P,Q \in E(K)$ because a line through $P$ and $Q$ is obviously the same as a line through $Q$ and $P.$ \end{itemize} Verification of the associative law is not quite as quick. It can be done either by several pages of lengthy but straight forward calculations (taking three general points $P,Q,R$ on $E,$ working out $(P+Q)+R$ and $P+(Q+R)$ separately and then checking that the results are the same) or in a few lines using some specific mathematical machinery. 

%hide %latex \subsection*{3.5 Scalar Multiplication of Elliptic Curve Points} Because of the group structure, elliptic curves may be used in any cryptographic protocol that can be generalized to arbitrary groups, as we have done with the Diffie-Hellman protocol in Chapter 2. In such protocols, it is often necessary to calculate multiples of points. This section considers methods for computing $mP$ (i.e. $P + P + P + \ldots + P~~m$-times) where $m$ is an integer and $P$ is a point on an elliptic curve $E.$ This operation is called {\it scalar multiplication} and is {\it not} a group operation because it operates on one group element and one whole number (and not on two group elements). It dominates the execution time of elliptic curve cryptographic schemes. The most naive way of calculating $mP$ is by starting with $2P$ and then adding $P$ to the result $(m-2)$ times. It takes one doubling and $m-2$ additions, i.e. $m-1$ group operations in total, to determine $mP.$ This method works, but there are much more efficient approaches. For example, if we wanted to calculate $16P,$ we could start with $2P,$ double that, and double the result two more times, i.e. we would calculate $2(2(2(2P))).$ This only takes $4$ doublings (instead of the $15$ additions that the previous naive method would take). For $20P$ we could do $4P + 16P = 2(2P) + 2(2(2(2P))),$ which uses $6$ doublings and $1$ addition, i.e. $7$ group operations in total. If we're smart, we only calculate the value of $4P$ once and remember it. Then we can go from there when we calculate $16P$ and save another $2$ multiplications. This method is called {\it double-and-add} and is analogous to the perhaps better known {\it square-and-multiply} algorithm applied in many different settings, including RSA. It works with the {\it binary} representation of $m,$ so let $m = (m_{t-1},m_{t-2},\ldots,m_0)$ be the binary representation of $m,$ meaning that $$m = \sum_{i=0}^{t-1} m_i 2^i.$$ In our example, $$m = 20 = 16+4 = 2^4+2^2 = (1,0,1,0,0).$$ The double-and-add algorithm starts with small powers of $2$ and then adds the appropriate higher power-$2$ multiples of $P.$ It remembers the multiples of $2$ that it has already calculated. That way, they don't have to be recomputed in every step. \medskip \noindent {\bf Double-and-Add Algorithm.} \\ {\sc Input:} $m = (m_{t-1},\ldots,m_0),~P \in E(K)$ \begin{enumerate} \item $Q \leftarrow \mathcal{O}$ \item For $i$ from $0$ to $t-1$ do \begin{enumerate} \item If $m_i = 1$ then $Q \leftarrow Q + P$ \item $P \leftarrow 2P$ \end{enumerate} \end{enumerate} {\sc Output:} $mP = Q$ 

%hide m = 500 ########################################################################################### html('<h3>Double-and-Add Algorithm</h3>') if m == 0: html('<font size=6 color="green">0 P₀ = O</font>') else: t = floor(log(m,2)) + 1 @interact def _(step=slider([-1..floor(log(m,2))])): t = floor(log(m,2)) + 1 # binary rep of m n = m b = range(t) for i in range(t): b[t-1-i] = n % 2 n = floor(n/2) if step == -1: ms = 'm = %s, binary representation: m = ('%m for i in range(t): ms += '%s'%b[i] if i != t-1: ms += ',' ms += ')' html('<font size=6>'+ms+'</font>') html('<font size=6>t = %s\n</font>'%t) html('<font size=6, color="blue">Initialization\n\n</font>') html('<font size=6>Q = $\mathcal{O}\n\n</font>') html('<font size=6>\nP = P₀</font>') else: Q = '' Q2 = ' = ' Q3 = '' for i in range(step+1): if b[t-i-1] == 1: if Q != '': Q += ' + ' Q2 += ' + ' Q3 += ' + ' if i != step: Q = Q + '2^%s P₀'%i Q2 = Q2 + '%s P₀'%2^i else: Q = Q + '<font color="red">2<font color="blue">^%s</font> P₀</font>'%i Q2 = Q2 + '<font color="red">%s P₀</font>'%2^i Q3 = Q3 + '%s P₀'%2^i if Q == '': Q = '$\mathcal{O}$' Q2 = '' Q3 = '$\mathcal{O}$' ms = 'm = %s, binary representation: m = ('%m for i in range(t): if i == t-step-1: ms += '<font color="red">%s</font>'%b[i] else: ms += '%s'%b[i] if i != t-1: ms += ',' ms += ')' html('<font size=6>'+ms+'</font>') html('<font size=6>t = %s\n</font>'%t) html('<font size=6, color="blue">Step: i = %s</font>'%step) html('<font size=6>m<font color="blue">_%s</font> = <font color="red">%s</font>\n</font>'%(step,b[t-step-1])) html('<font size=6>Q = %s\n%s</font>'%(Q,Q2)) html('<font size=6>\nP = 2<font color="blue">^%s</font> P₀\n = %s P₀</font>'%(step+1,2^(step+1))) if step == t-1: html('\n\n<font size=6 color="green">%s P₀ = %s</font>'%(m,Q3)) html('Figure 3.9 Click through the steps of the algorithm. For clarity, the original point (that it wants to calculate a multiple of) is <br>denoted P₀ and the remembered value of multiples of P₀ is denoted P. If you want to change the value of m, click on the gray <br>%hide above. A window of code will appear. In the second line, change the number 500 to your desired value of m. Do not <br>change any of the other code. Then hit the keys Shift + Enter. (Unfortunately there is no better way of doing this in the <br>current version of Sage!)') 

%hide %latex \noindent The exact complexity of this algorithm depends on the number of ones in the binary representation of $m.$ Obviously, if there are many ones, then many additions need to be done. If there are only few ones, then only few additions have to be done. The average number of ones in the binary representation of $m$ is $\frac{t}{2}.$ So the algorithm takes about $\frac{t}{2}$ additions on average. It also takes $t$ point doublings. That makes a total of approximately $\frac{t}{2} + t = \frac{3}{2}t$ group operations on average, and $2t$ operations at maximum. This is a good example for a polynomial-time algorithm. The input is $m,$ the length of the input is $t = \log_2 m.$ The {\it expected} (that means average) complexity is $\frac{3}{2}t,$ which is a polynomial in $t,$ i.e. a polynomial in the {\it length} of the input. In comparison, the naive algorithm is exponential in the length of $m.$ It takes approximately $m$ operations (the `$-1$' can be neglected) where $m = 2^t$ (because $t = \log_2 m$). So the complexity in terms of the {\it length} of the input is $2^t,$ which is exponential! Since the efficiency of elliptic curve cryptographic schemes critically depends on the efficiency of scalar multiplication, much effort is made to further speed up this process. One option is to use a better representation of $m$ in the double-and-add algorithm. One such representation is called {\it non-adjacent form} (NAF), which provides an 11\% speedup for large values of $m.$ Instead of zeros and ones, the NAF of a number contains the values $0,1$ and $-1.$ It may be one bit longer than the binary representation, but it consists of only $\frac{1}{3}$ non-zero entries on average, which significantly reduces the number of additions that have to be done. If $l$ is the length of the NAF of $m,$ then the expected complexity is only $\frac{1}{3}l + l = \frac{4}{3}l.$ 

%hide x = var('x') ########################################################################### t1 = text('binary',(7.5,15),rgbcolor="blue") t2 = text('naive',(6,30),rgbcolor="red") t3 = text('NAF',(7.5,7),rgbcolor=[0,1,0]) min=0 maxi=10 # m p1 = plot(2^x,(min,maxi-5),rgbcolor=[1,0,0]) # 3/2 t p2 = plot(3/2*x,(min,maxi),rgbcolor=[0,0,1]) # 4/3 l p3 = plot(4/3*x,(min,maxi),rgbcolor="green") (p1+p2+p3+t1+t2+t3).save('j1.png',axes_labels=['length of $m$ in bits','operations'],figsize=5) # logarithmic ############################################################ t1 = text('binary',(18000,23),rgbcolor="blue") #t2 = text('sub-exponential',(20,10000),rgbcolor="red") t3 = text('NAF',(75000,21),rgbcolor=[0,1,0]) min=0 maxi=100000 # m #p1 = plot(x,(min,maxi-990),rgbcolor=[1,0,0]) # 3/2 t p2 = plot(3/2*log(x,2),(min+1,maxi),rgbcolor=[0,0,1]) # 4/3 l p3 = plot(4/3*(log(x,2)+1),(min+0.5,maxi),rgbcolor="green") (p2+p3+t1+t3).save('j2.png',axes_labels=['$m$','operations'],figsize=5) ############################################################################ html('<table bgcolor=lightgrey cellpadding=2>') html('<tr><td align="center"><img src="cell://j1.png"></td>') html('<td align="center"><img src="cell://j2.png"></td></tr>') html('</table>') html('Figure 3.10 Comparison of the three methods of scalar multiplication. Notice that the graph on the right is a logarithmic view, <br>meaning that the x-axis shows m and not t (the length of m).') 

Figure 3.10 Comparison of the three methods of scalar multiplication. Notice that the graph on the right is a logarithmic view, 
meaning that the x-axis shows m and not t (the length of m).

Figure 3.10 Comparison of the three methods of scalar multiplication. Notice that the graph on the right is a logarithmic view, 
meaning that the x-axis shows m and not t (the length of m).

%hide %latex \newcommand{\Fq}{\mathbb{F}_q} \subsection*{3.6 Elliptic Curve Group Order} Let $E$ be an elliptic curve over a finite field $\Fq$ (for $q$ a prime power). Since the underlying field is finite, there are only finitely many points on the curve. \medskip \noindent {\bf Definition.} The number or points in $E(\Fq)$ is called the {\bf order} of $E$ over $\Fq.$ It is denoted $\# E(\Fq)$ or $| E(\Fq) |.$ \medskip \noindent When a specific elliptic curve is used for cryptographic purposes, knowing its group order is crucial. It is easy to find lower and upper bounds, but calculating it precisely is not trivial. Since $\mathcal{O}$ is always on the curve and the Weierstrass equation has at most two solutions for each $x \in \Fq,$ we know that $\# E(\Fq) \in \{ 1,\ldots,2q+1 \}.$ Hasse's theorem provides tighter bounds: $$ q + 1 - 2 \sqrt{q} \leq \# E(\Fq) \leq q + 1 + 2 \sqrt{q}. $$ There are also a few theoretical results about the existence of elliptic curves with a certain order, but that's about as good as theory gets. Finding point counting algorithms is currently a major area of elliptic curve research. The obvious naive algorithm -- finding, for each $x \in \Fq,$ the number of solutions $y \in \Fq$ to the Weierstrass equation of $E$ -- is clearly infeasible for field sizes of cryptographic interest. The currently best algorithm known for counting the points on arbitrary elliptic curves over prime fields $\mathbb{F}_p$ is the so-called {\it Schoof-Elkies-Atkin (SEA) algorithm.} It takes a few minutes for values of $p$ of practical interest. The currently fastest method for counting the points on elliptic curves over binary fields $\mathbb{F}_{2^m}$ is {\it Harley's algorithm.} It can do its job in one tenth of a second for values of around $160$ for $m.$ For a comprehensive overview of point counting algorithms, see [Vercauteren2003]. 

%hide %latex \newcommand{\Fq}{\mathbb{F}_q} \subsection*{3.7 The Elliptic Curve Discrete Logarithm Problem} Our goal is to use elliptic curves for discrete logarithm based cryptographic algorithms. Thus the major prerequisite is that the discrete logarithm problem is hard in these groups. Let's recall the problem itself. The formulation is similar to the definition in Chapter 2, but it looks a bit different when written down for an additive group. It is also more general here. \medskip \noindent {\bf Elliptic Curve Discrete Logarithm Problem (ECDLP).} Given an elliptic curve $E$ defined over a finite field $\Fq,$ a point $P \in E(\Fq)$ of order $n,$ and a point $Q \in \langle P \rangle,$ find the integer $l \in \{ 0,\ldots,n-1 \}$ such that $Q = lP.$ The integer $l$ is called the {\it discrete logarithm of $Q$ to base $P$,} denoted $l = \log_P Q.$ \medskip \noindent $P$ is called the {\bf base point.} In Chapter 2 we required $P$ to be a generator of the group, but generators of elliptic curves are hard to find (in fact, the curves used in cryptography usually aren't even cyclic). Thus we are satisfied using a point of large order instead. $\langle P \rangle = \{ rP~|~r \in \mathbb{N}_0 \}$ is called the {\it span} of $P$ and contains all multiples of $P.$ Requiring $Q \in \langle P \rangle$ ensures that the discrete logarithm problem has a solution. In practice this is the relevant case anyway because $Q$ is always calculated as a multiple of $P,$ say $Q = lP,$ and the task is to ``undo'' this calculation and find $l.$ The best currently known general-purpose attack on the ECDLP is a combination of the Pohlig-Hellman algorithm and Pollard's rho algorithm, but that still has a fully-exponential running time in the length of the largest prime divisor of $n.$ In fact all general-purpose attacks on the DLP (mentioned in Section 2.2) can also be applied to the ECDLP. But they have the same complexity (i.e. exponential!) here and can thus be circumvented by carefully selecting appropriate elliptic curve parameters. These will be discussed in Chapter \nolinebreak 5. The crucial result is that index calculus does not work for elliptic curves. The index calculus algorithm used to solve the DLP in $\mathbb{F}_p^{\times}$ makes crucial use of the so-called {\it factor base}, a set of ``relatively small'' prime numbers (compared to the size of $p$). More precisely, it finds numbers of a certain form that factor completely into the small primes contained in the factor base and then uses these to solve the DLP. Index calculus must fail for elliptic curve groups since there is no concept like prime numbers and unique factorization into prime factors for elliptic curves, leaving it unclear how an appropriate factor base might be chosen. Approaches like ``lifting'' curves and points to the rational numbers, number fields or function fields are doomed to fail because there is no efficient procedure of doing this, and even if there was, there would not be enough space to write down the coordinates of the resulting points. Of course there could be other ways of applying the index calculus methodology for solving the ECDLP. Thus far, no one has found an approach that yields a general sub-exponential-time (or better) algorithm for the ECDLP. If the elliptic curve parameters are carefully chosen to defeat all known attacks, then the ECDLP is believed to be infeasible given the state of today's computer technology. However, there is no mathematical proof that the ECDLP is intractable! Indeed, such a proof would be extremely surprising, as it would settle one of the fundamental (if not to say {\it the} major) outstanding open questions in computer science. Furthermore, there is no theoretical evidence that the ECDLP is intractable. Nonetheless, much practical evidence for the infeasibility of the ECDLP has been gathered over the years and most researchers are willing to trust the hardness of the ECDLP. As long as no contradicting results are obtained, the use of elliptic curves in cryptography is very attractive.