This is an interactive implementation of the Massey-Omura cryptosystem. For a brief introduction, see the next slide.

It is sometimes the case in mathematics that operations are easier to perform than to undo (there is a reason you learn how to compute powers before logarithms!). One such example is calculating multiples of points on elliptic curves according to the group law - more directly, given a point $P$, it is significantly easier to compute multiples $kP$ than it is to figure out $k$ such that $kP$ is equal to a given point $Q$ (this is known as the 'elliptic curve discrete logarithm problem'). The goal of a cryptosystem is to exploit the 'one-way' nature of operations like the elliptic curve group law to allow secure communication that can be quickly encrypted and decrypted by the sender and recipient, but is incredibly resilient to third parties.

ECC (elliptic curve cryptography) is incredibly common - in fact, your browser and computer are probably using it right now. The most common use case is for TLS (transport layer security), the protocol that secures most of your important web traffic. Therefore, your ability to access your bank account online securely rests on cryptography like ECC and the math that powers it.

Let $p > 3$ be a prime and let $\mathbb{F}_p = \mathbb{Z}/\mathbb{Z}_p$ be the integers modulo $p$, i.e. the set of equivalence classes obtained by sorting each integer based on its remainder when divided by $p$. It turns out that this set of classes is incredibly well-behaved - we can add, subtract, multiply, and (for nonzero classes) divide equivalence classes of integers modulo $p$, just like we would with the real numbers. We call this set the finite (or Galois) field of order $p$.

An elliptic curve over a field $\mathbb{F}$ is a curve of the form $$y^2 = x^3 + ax + b$$ for some $a,b$ in $\mathbb{F}$ satisfying $4a^3 + 27b^2 \ne 0$.

While these curves have infinitely many solutions in the real numbers, they contain only finitely many points over the finite field $\mathbb{F}_p$. For example, over $\mathbb{F}_{29}$, the elliptic curve $$y^2 = x^3 - x + 1$$ from the previous slide has 36 points on it (see diagram). Although some of the points may not appear to sit on the curve, they are solutions over $\mathbb{F}_p$ nonetheless. Note that for every solution $(x,y)$, the reflection over the $x$-axis $(x,-y)$ is also a solution.

It turns out that by adding an extra point (which we will denote by $\mathcal{O}$, the 'point at infinity'), we can define an operation $\oplus$ on points of the elliptic curve. Over the real numbers, this operation has a nice geometric interpretation. For (most) points $P,Q$, we define their addition $P \oplus Q$ to be the opposite of the unique point on the curve collinear with $P$ and $Q$ (see diagram). This works except for a few cases, where we can shift the definition slightly while keeping the same spirit.

For any point $P$, define $P \oplus \mathcal{O} = \mathcal{O}$ and $\mathcal{O} \oplus P = \mathcal{O}$. To calculate $2P = P \oplus P$ (or in general, $nP = P \oplus \cdots \oplus P$), we instead use the tangent line at the point and take the opposite of the intersection of the tangent line with the curve. If there is no intersection, then $P$ is an inflection point and $P \oplus P = \mathcal{O}$. Finally, if $Q$ is the reflection of $P$ over the $x$-axis, we have $P \oplus Q = \mathcal{O}$. Note that in any case, $P \oplus Q = Q \oplus P$.

With this operation, we can add, subtract, and calculate multiples of any point on the elliptic curve, so we say the points of the elliptic curve along with $\mathcal{O}$ form an abelian group under the operation $\oplus$. We can do the same calculations when the curve is over $\mathbb{F}_p$, just without the nice geometric interpretation.

Now that the elliptic curve group law is clear, how do we use this for encryption? We need to develop a method to embed messages as points on the elliptic curve. There are several ways to do this - here is a very simple probabilistic method that uses ASCII encoding to split our message into blocks.

1) Decide on an acceptable range $r$ to search for matching points (1000 is probably good enough).
2) Convert the message to ASCII and break into integer blocks $m_i$ such that $m_i < \frac{p}{r}- 1$. Our simple ASCII encoding will use blocks of length 3.
3) For each block, find a point $P_i$ on the elliptic curve with $x$ coordinate between is between $(r*m_i)$ and $(r*(m_i + 1))$. This can be done by trying the $r$ distinct $x$ coordinates in this range until finding one that works. Note this may fail with probability approximately $2^{-r}$, so it is important to not pick $r$ too small.

Use the interactive form on the left to see how this method works for a given message.

We have now embedded our plaintext message as points $P_i$ on the elliptic curve. Before we can encrypt and send our message, we need both the sender and the receiver to select encryption and decryption keys using the process outlined below.

1) Compute the number of points on the elliptic curve $E$. In this case, we have $N = 408594286$.
2) To obtain an encryption key, select a random integer $c$ between $0$ and $N$ that is coprime to $N$.
3) To compute the associated decryption key $c'$, compute the inverse of $c$ modulo $N$.

We will denote the sender's encryption and decryption keys as $c$ and $c'$ respectively, and the receiver's keys as $d$ and $d'$.

Now that both parties have created their encryption and decryption keys, we can proceed to encrypt following the process below.

1) The sender uses the elliptic curve group law to compute and send the points $cP_i$, where $c$ is their encryption key and $P_i$ is an encoded point corresponding to an ASCII character.

Now that both parties have created their encryption and decryption keys, we can proceed to encrypt following the process below.

1) The sender uses the elliptic curve group law to compute and send the points $cP_i$, where $c$ is their encryption key and $P_i$ is an encoded point corresponding to an ASCII character.
2) The receiver computes and sends back the points $d(cP_i)$.

Now that both parties have created their encryption and decryption keys, we can proceed to encrypt following the process below.

1) The sender uses the elliptic curve group law to compute and send the points $cP_i$, where $c$ is their encryption key and $P_i$ is an encoded point corresponding to an ASCII character.
2) The receiver computes and sends back the points $d(cP_i)$.
3) The sender computes and sends the points $c'dcP_i = dP_i$.

Now that both parties have created their encryption and decryption keys, we can proceed to encrypt following the process below.

1) The sender uses the elliptic curve group law to compute and send the points $cP_i$, where $c$ is their encryption key and $P_i$ is an encoded point corresponding to an ASCII character.
2) The receiver computes and sends back the points $d(cP_i)$.
3) The sender computes and sends the points $c'dcP_i = dP_i$.
4) The receiver computes $d'dP_i = P_i$.

Now that both parties have created their encryption and decryption keys, we can proceed to encrypt following the process below.

1) The sender uses the elliptic curve group law to compute and send the points $cP_i$, where $c$ is their encryption key and $P_i$ is an encoded point corresponding to an ASCII character.
2) The receiver computes and sends back the points $d(cP_i)$.
3) The sender computes and sends the points $c'dcP_i = dP_i$.
4) The receiver computes $d'dP_i = P_i$.
5) The receiver decodes the points $P_i$ (in this case, converting them back into ASCII characters).