Back

ECC Notes 1 - Divisors

Attempting to learn Elliptic Curve Cryptography.

Introduction

After my absolute failure attempt to solve zipfel in \langlehxp CTF 2021\rangle(https://ctftime.org/event/1447), I have decided for the $n^{\text{th}}$ time to seriously learn Elliptic Curve Cryptography. This time, hopefully I will finally understand pairings, supersingular curves and isogeny crypto. After all, I want to be a cool guy too!

\langleblockquote class=“twitter-tweet”\rangle\langlep lang=“en” dir=“ltr”\rangleIsogeny crypto is what cool guys do these days: walking around graphs of supersingular elliptic curves.\langlebr\rangle\langlebr\rangleI've written yet another brief introduction to it, using the many great resources available.\langlebr\rangle\langlebr\rangleWe talk about SIDH and CSIDH, but for now we will only use the second.\langle/p\rangle— Riccardo Zanotto (@Drago1729) \langlea href=“https://twitter.com/Drago1729/status/1473004035129159685?ref_src=twsrc%5Etfw"\rangleDecember 20, 2021\langle/a\rangle\langle/blockquote\rangle \langlescript async src=“https://platform.twitter.com/widgets.js" charset=“utf-8”\rangle\langle/script\rangle

Disclaimer

This blog post is NOT a tutorial starting from scratch. The main purpose of the blog will be to organize the material into a format I can easily review and learn, based on MY previous knowledge on the topic. I cannot even guarantee the material to be 100% correct, though I constantly cross-reference my understanding with multiple resources. Despite this, I still hope the blog provides a starting point, especially if you know nothing apart from P.tate_pairing(Q, P.order(), 1). If you have any questions, feel free to reach out to me on grhkm#4429!

Elliptic Curves

Let $K = \mathbb{F}_q = \mathbb{F}_{p^k}$ be a finite field and $E(K)$ be the elliptic curve

$$E: \{(x, y)\in K^2 |\ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6\} \cup \{\infty\}$$

with $a_i\in K$, also known as the long Weierstra$\beta$ equation. As it turns out, when $p\geq 5$ the curve can be transformed into a short Weierstra$\beta$ form, where all coefficients vanish except $a_4$ and $a_6$. That is, we shall work with curves

$$E: y^2 = x^3 + a_4x + a_6.$$

In Sage, the class is straightforward to understand and use:

sage: q = 17
sage: a_4 = 1
sage: a_6 = -3 # = 14 mod 17
sage: E = EllipticCurve(GF(q), \langlea_4, a_6\rangle)
sage: E
Elliptic Curve defined by y^2 = x^3 + x + 14 over Finite Field of size 17

Divisors

Back when we were in high school, we learned that for the field $\mathbb{C}$, we are able to factor every non-constant polynomial into a product of linear factors. $$P = \sum a_ix^i = a_0\prod (x - \alpha_i)^{\beta_i}.$$ Moreover, we were taught that polynomials are uniquely determined by its roots up to a constant factor. For example, the polynomial $f(x) = x^4 - 9x^3 + 29x^2 - 39x + 18 = (x - 1)(x - 2)(x - 3)^2$ can be stored as its roots $v = \{1, 2, 3, 3\}$. If we assign each number $x$ a special symbol $\langlex\rangle$, we can then write $f(x) {\ \color{cyan} =\ } \langle1\rangle + \langle2\rangle + 2\langle3\rangle$. More generally, we can write every polynomial $$P = \sum a_ix^i {\ \color{cyan} =\ } \sum \alpha_i\langler_i\rangle.$$

Furthermore, there is a natural extension of this notation for rational functions $\frac{P(x)}{Q(x)}$ - we simply subtract the special symbols of $Q(x)$ from $P(x)$. For example, $\frac{x^2 - x + 6}{x^3 + 4x^2 - 4x - 16} {\ \color{cyan} =\ } \frac{(x + 3)(x - 2)}{(x + 4)(x + 2)(x - 2)} = \langle-3\rangle + \langle2\rangle - \langle-4\rangle - \langle-2\rangle - \langle2\rangle = \langle-3\rangle - \langle-4\rangle - \langle-2\rangle$.

Of course, it is not clear what the symbols mean or what we can do with them, as shown by the cyan equal sign. However, the idea is clear: roots uniquely identify polynomials, and vice versa.


Here comes the interesting part: this is also possible for rational functions on elliptic curves! First, let’s define what those square bracket symbols are:

\rangle A divisor $D$ on an elliptic curve $E$ is a (finite) formal sum of points on $E$, written as $$D = \sum a_i\langleP_i\rangle.$$

Here, the term formal sum means that the points are merely symbols with no actual meaning - most importantly, they do not add like elliptic curve points.

For example, suppose we use the Elliptic Curve $E(\mathbb{F}_{17}) : y^2 = x^3 + x - 3$. It is easy to verify that $P = (1, 4), (5, 5), (10, 15)$ and $\infty$ are all on the curve. Some examples of divisors on $E$ are

  • $\langle1, 4\rangle + 2\langle5, 5\rangle - 3\langle10, 15\rangle$
  • $\langle1, 4\rangle + \langle\infty\rangle$
  • $-\langle5, 5\rangle + 5\langle1, 4\rangle - \langle10, 15\rangle$.

Notice that we actually have $(1, 4) + (5, 5) = (10, 15)$ on the curve. However, that does not imply $\langle1, 4\rangle + \langle5, 5\rangle = \langle10, 15\rangle$. Remember, they are merely symbols, not points on the curve.

Now similar to what we did to complex polynomials, let’s see the usage of divisors:

Denote the set of polynomials of $E : y^2 = x^3 + a_4x + a_6$ by $$K[E] := K[x, y] / (y^2 - x^3 - a_4x - a_6).$$ Let $P = (a, b)$ be a point on $E$ not of order $2$ and $g(x, y)\in K[E]$ be a function.

If $\exists h\in K[E], k\in\mathbb{Z}^{\times}$ such that $g(x, y) = (x - a)^k h(x, y)$ and $h(a, b)\neq 0, \infty$, we write $\text{ord}_P(g) = k$ and say

  • $g$ has a zero at $P$ of multiplicity $k$ if $k > 0$, and
  • $g$ has a pole at $P$ of multiplicity $-k$ if $k < 0$.

Finally, we write $g {\ \color{cyan} =\ } \sum_{P\in E} \text{ord}_P(g)[P]$.

The notation is quite a bit to digest. Intuitively speaking, $K[E]$ is the set of all polynomial functions in terms of $x$ and $y$, where we replace all $y^2$ with $x^3 - a_4x - a_6$. This has a natural consequence that all elements $g(x, y)\in K[E]$ can be written as $A(x) + B(x)y$, where $A, B$ are single-variable polynomials in $x$.

TODO: examples of divisor notations, some results about $\langle\prod (x - a_j)^{c_j}\rangle$ and constructing function with given divisor.

Built with Hugo
Theme Stack designed by Jimmy