Elliptic_Curve_Cryptography

• The equation $\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$ defines an ellipse.

• An elliptic curve (over a field k) is a smooth projective curve of genus 1 (defined over k) with a distinguished (k-rational) point.

• Every elliptic curve with real coefficients can be put in the standard form

  • $y^2 = x^3 + Ax + B$

• Requirement of smoothness

  • $4A^3 + 27 B^2 \ne 0$

• Let $E$ be an elliptic curve over $Q$.
• If $P$ and $Q$ are two rational points on $E$, then the line $\overline{PQ}$ intersects $E$ in a third rational point $R$.

• The group $E(Q)$ is a finitely generated abelian group.

• Problem: Given a point $P \in E(\mathbb{F}_q)$ and $Q = nP$, determine $n$.
• The best known algorithm for solving the discrete log problem in $E(\mathbb{F}_q)$ takes time $\Omega(\sqrt{q})$, which is fully exponential in $log(q)$.
• This allows cryptographic systems based on the elliptic curve discrete log problem to use key sizes that are much smaller than other systems.
• However, there is no proof that the elliptic curve discrete log problem is hard.

• In the discrete log setting, we selected a generator $g$ and computed $g_0$, $g_1$, $\ldots$ mod $p$.
• This group generated by the generator had an order that divided the order of the parent group by Lagrange’s Theorem.
• In Elliptic Curves we can select a point P which is like a generator and

compute $0P$, $P$, $2P$, $\ldots$ mod $p$, called a Base Point.

• Let $p$ be a prime that does not divide the discriminant $\Delta(E) = −16(4A^3 + 27B^2)$.
• If we reduce A and B modulo p, we obtain an elliptic curve $E_p := E \bmod p$

• Let $E/\mathbb{F}_p$ be an elliptic curve with a point $P \in E(\mathbb{F}_p)$.