Elliptic Curve Cryptography

Let $y^2 = x^3 + ax + b$ be the equation of the elliptic curve E. Any line L that intersects the curve will intersect the curve in at most 3 points. Below are examples of how these look like.

A mathematical structure can defined on E. We can “add” two points on E to get a third point. First, let’s define the negative of a point. A point $Q$ is the negative of a point $P$ if the point $Q$ is the mirror image of the point $P$ with respect to the x-axis that is,

$Q = - P$

From the relation above, we can define $O$ to be

$P + (-P) = O$

The point $O$ is the “point at infinity”.

Let L be a line that intersects E at points $P$ , $Q$ and $R$ . We define the sum

$P + Q + R = O$

From this definition, we see that the the sum of any of the two points is the negative of the third point, that is, $P + Q = -R$ .

So how do we actually add 2 points given their coordinates? It turns out that if we are given the x and y coordinates of 2 points, we can easily compute the third point. To see this, let $y = mx +c$ be the equation of the line that intersects the elliptic curve $y^2 = x^3 + ax + b$ at points $P$ , $Q$ and $R$ . Solving for the x-coordinates of the intersection, we get

$\begin{array}{rl} \displaystyle x_1 &= \displaystyle \frac{m^2}{3} + \frac{2^{1/3}}{3} A - \frac{B}{3}\\ \displaystyle x_2 &= \displaystyle \frac{m^2}{3} - \frac{(1+i\sqrt{3})}{3 2^{2/3}}A + (1-i\sqrt{3})\frac{B}{6}\\ \displaystyle x_3 &= \displaystyle \frac{m^2}{3} - \frac{(1-i\sqrt{3})}{3 2^{2/3}}A + (1+i\sqrt{3})\frac{B}{6} \end{array}$

where
$A = \frac{\left(3 a-6 c m-m^4\right)}{ \sqrt[3]{\sqrt{\left(9 a m^2+27 b-27 c^2-18 c m^3-2 m^6\right)^2+4 \left(3 a-6 c m-m^4\right)^3}+9 a m^2+27 b-27 c^2-18 c m^3-2 m^6}}$

$B = \frac{\sqrt[3]{\sqrt{\left(9am^2+27b-27c^2-18cm^3-2m^6\right)^2+4\left(3a-6 cm-m^4\right)^3}+9am^2+27b-27c^2-18cm^3-2m^6}}{ \sqrt[3]{2}}$

From this we see that

$x_1 + x_2 + x_3 = m^2$

Therefore, if we have $x_1$ and $x_2$ , we can get $x_3$ from the formula:

$x_3 = m^2 -x_1 -x_2$

Once we get $x_3$ , we can get $y_3$ from the formula of the slope:

$\begin{array}{rl} \displaystyle \frac{y_3-y_1}{x_3-x_1} &= m\\ y_3-y_1 &= m(x_3 - x_1)\\ y_3 &= m(x_3 - x_1) + y_1 \end{array}$

The variable $m$ is the slope of the line. If the line is tangent to the curve E at point $P$ , the slope $m$ is calculated using the derivative of E at the $P$ :

$\begin{array}{rl} d(y^2) &= d(x^3 + ax + b) \\ 2y dy &= (3x^2 + a) dx\\ \displaystyle \frac{dy}{dx} &= m = \displaystyle \frac{3x^2 +a}{2y} \end{array}$

Addition Formula

Now that we have seen how to add two points, let’s summarize the formula here:

Given points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ , the third point $R=(x_3, -y_3)$ can be computed from

$x_3 = m^2 -x_1 -x_2$

$y_3 = m(x_3 - x_1) + y_1$

where

$m = \begin{cases} \displaystyle \frac{y_1 - y_2}{x_1 - x_2} & P \ne Q\\ \displaystyle \frac{3x^2 +a}{2y} & P = Q \end{cases}$

Important! Take note that $R=(x_3,-y_3)$ . The value of $y_3$ should be the negative of the computed value.

Example 1

Let the elliptic curve be $y^2 = x^3 -3 + 3$ , then points $P=(-2,1)$ and $Q=(0, 1.732051)$ lie on the curve. The third point can be computed as follows:

$\begin{array}{rl} m &= \displaystyle \frac{y_1 - y_2}{x_1 - x_2}\\ &= \displaystyle \frac{1-1.732051}{-2 - 0}\\ &= 0.3660255 \end{array}$

$\begin{array}{rl} x_3 &= m^2 - x_1 - x_2\\ &= (0.3660255)^2 - (-2) - 0\\ &= 2.133975 \end{array}$

$\begin{array}{rl} y_3 &= m(x_3 - x_1) + y_1\\ &= 0.3660255 ( 2.133975 - (-2)) + 1\\ &= 2.51314 \end{array}$

Therefore $R=(x_3,-y_3) = (2.133975, -2.51314)$ .

Example 2

If $P=Q=(-2,1)$ , we have:

$\begin{array}{rl} m &= \displaystyle \frac{3x^2 +a}{2y}\\ &= \displaystyle \frac{3(-2)^2 -3}{2(1)}\\ &= 4.5 \end{array}$

$\begin{array}{rl} x_3 &= m^2 - x_1 - x_2\\ &= (4.5)^2 - (-2) - (-2)\\ &= 24.25 \end{array}$

$\begin{array}{rl} y_3 &= m(x_3 - x_1) + y_1 \\ &= 4.5 ( 24.25 - (-2)) + 1\\ &= 119.125 \end{array}$

Therefore, $R=(x_3,-y_3) = (24.5, -119.125)$

Group Structure

The set of points of E together with the point at infinity, $E\cup \{O\}$ , forms a group under the addition operation defined above.

It is associative: $(P+Q) + R = P + (Q+R)$
Every element has an inverse: $P + (-P) = O$
It contains the identity element. From the inverse we have $P - P = 0$ . Therefore, $P + O = P$ , which makes $O$ the identity element.
It is closed: For every $P, Q$ , $P + Q \in E\cup \{O\}$

Modulo Arithmetic

The addition formula also works for modular arithmetic. Let $p$ be a prime number, then given two points $P$ and $Q$ , the third point can be computed as

$x_3 = m^2 -x_1 -x_2 \mod p$

$y_3 = m(x_3 - x_1) + y_1 \mod p$

where

$m = \begin{cases} \displaystyle \frac{y_1 - y_2}{x_1 - x_2} \mod p & P \ne Q\\ \displaystyle \frac{3x^2 +a}{2y} \mod p & P = Q \end{cases}$

Example

Suppose $p=71$ , $P =(0,28)$ and $Q = (-2, 1)$ , then we compute the third point $R$ as follows:

$\begin{array}{rl} m &= \displaystyle \frac{y_1 - y_2}{x_1 - x_2} \mod 71\\ &= \displaystyle \frac{28-1}{0 - (-2)} \mod 71\\ &= 27(36) \mod 71, \text{ where 36 is the inverse of 2 modulo 71}\\ &= 49 \end{array}$

$\begin{array}{rl} x_3 &= m^2 - x_1 - x_2 \mod 71\\ &= 49^2 - 0 - (-2) \mod 71\\ &= 60 \end{array}$

$\begin{array}{rl} y_3 &= m(x_3 - x_1) + y_1 \mod 71\\ &= 49(60 - 0) + 28\\ &= 57 \end{array}$

Therefore, $P+Q = R = (x_3,-y_3) = (60, -57) \mod 71 = (60, 14)$

N-fold Point Addition

Let $B$ be a point in E. If $n$ is an integer greater than 1, the point $nB$ is defined as

$nB = \underbrace{B + B + \ldots + B}_{\text{n times}}$

Example

Let $y^2 = x^3 - 3x + 3 \mod 71$ . Let $B=(0,28)$ , then using the formula for $x_3$ and $y_3$ :

$\begin{array}{rl} 3B &= (0,28) + (0,28) + (0,28) \mod 71\\ &= (37,63) \mod 71 \end{array}$

Elliptic Curve Cryptography

Alice and Bob want to exchange information using Elliptic Curve Cryptography. They agree on an elliptic curve equation and a base point $B$ . Alice and Bob both choose a random number between 1 and 71. Let $e_a$ and $e_b$ be the secret numbers chosen by Alice and Bob (respectively) and publishes the public keys $e_aB$ and $e_bB$ . Alice wants to send the message encoded in a point $P$ . She multiplies Bob’s public key and her private key and adds it to the message $P$ to get $P+ e_ae_bB$ and sends the pair $\{e_aB, P + e_ae_bB\}$ .

Bob receives the message multiplies his private key to Alice’s public key to get $e_be_aB$ . He then subtracts this to the message $P+ e_ae_bB$ to get the original message $P$ .

Assume Bob and Alice agree on the equation $y^2 = x^3 - 3x + 3$ , the base point $B=(0,28)$ and the modulus p=71. Suppose Alice’s private key is 4 and Bob’s private key is 5. Alice will publish her public key as $e_aB = 4B = (42,57)$ . Likewise, Bob will publish his public key as $e_bB = 5B=(30,2)$ .

Alice wants to send Bob a message encoded in the point $P=c(2,17)$ of E. First, Alice will multiply Bob’s public key with her private key to get $e_ae_bB = 4\cdot (30,2) = (18,32)$ . She will then add this to $P$ to get encrypted message $P + e_ae_bB = (2,17) + (18,32) = (10,11)$ . She will send $(10,11)$ to Bob.

Bob then receives the message $(10,11)$ . The first thing he will do is to multiply Alice’s public key $e_aB = (42,57)$ with his private key to get $e_be_aB = 5\cdot(42,57) = (18,32)$ . Next, he will subtract this from the encrypted message to get $(10,11) + (18,-32) = (2,17)$ , which is the unencrypted message of Alice!