> For the complete documentation index, see [llms.txt](https://thias-organization.gitbook.io/p256-documentation/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://thias-organization.gitbook.io/p256-documentation/brief-introduction-to-elliptic-curve-cryptography-ecc.md). # Brief Introduction to Elliptic Curve Cryptography (ECC) *Before diving into the implementation of* [*RISC Zero's k256 Accelerator*](/p256-documentation/risc-zero-k256-accelerator.md)*, we will need to understand some basic Mathematics about elliptic curves like k256 and p256. However, feel free to skip this part if you already know the basics!* An elliptic curve is defined by an equation of the form $$ y = x^3 + ax + b $$ where $$a$$and $$b$$ are constants that satisfy certain conditions to ensure the curve's security properties. ECC relies on the difficulty of the [Elliptic Curve Discrete Logarithm Problem (ECDLP)](https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Rationale), where given $$P$$ and $$Q$$ on the curve, it is computationally infeasible to determine the integer $$k$$ such that $$Q = kP$$. This hard problem underpins the security of various ECC-based protocols, including encryption, digital signature, and key exchange. ## Elliptic Curve Over Finite Fields ECC uses elliptic curves over the finite field $$\mathbb{F}\_p$$, where $$p$$ is prime. This means that the field is a square matrix of size $$p \times p$$ and the points on the curve are limited to **integer coordinates** within the field only. * Operations like point addition or multiplication will result in a point within the field * Elliptic curve over the finite field $$\mathbb{F}\_p$$ takes the following form $$ y^2 \equiv x^3 + ax + b \mod p $$ ## Calculations ### Point Addition Adding a point $$Q$$ to another point $$P$$ on the curve will result in another point on the curve. Geometrically, this is equivalent to: * Drawing a straight line that passes through points $$Q$$ and $$P$$ * Find the intersection point (that is not $$Q$$ and $$P$$) of this line with the curve * Reflect this point over the $$x$$-axis to get the result $$R$$ $$ Q + P = R $$

Point addition in ECC (source)

Mathematically, calculating point addition $$P + Q = R$$ on an elliptic curve is done using the following algorithm: $$ \begin{align\*} \lambda &= \frac{y\_Q - y\_P}{x\_Q - x\_P}\\ x\_R &= \lambda^2 - x\_P - x\_Q\\ y\_R &= \lambda ( x\_P - x\_R) - y\_P \end{align\*} $$ ### Point Doubling For a given point $$Q$$, point doubling finds a point such that $$Q + Q = 2\*Q$$. Geometrically, this involves: * calculating the slope of the tangent to the curve at $$Q$$ * finding the intersection with the curve * reflect this point over the $$x$$-axis Mathematically, this is calculated as [above](#point-addition) except we use a different $$\lambda$$ value $$ \lambda = \frac{3x\_P^2 + a}{2y\_P} $$ ### Multiplying Point by Integer A point $$G$$ over an elliptic curve over finite field can be [multiplied](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) by an integer $$k$$ and the result is another point $$P$$ on the curve: $$ P = k \* Q $$ There exists more efficient algorithms to calculate point multiplication and they can be found [here](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication). ## Order of an Elliptic Curve Аn elliptic curve over a finite field can form a finite [cyclic algebraic group](https://en.wikipedia.org/wiki/Cyclic_group), which consists of all the points on the curve. The **order of the curve** $$n$$ is the **total number of all points** on the curve. This total number of points includes also the special point called "[*point at infinity*](https://en.wikipedia.org/wiki/Point_at_infinity)", which is obtained when a point is multiplied by 0. *Note the* [*difference*](https://crypto.stackexchange.com/questions/44582/elliptic-curve-cryptography-when-to-use-p-and-when-to-use-n) *between* $$n$$ *(order)* *and* $$p$$ *(prime modulus)!* * We use $$p$$ when dealing with **field** arithmetic or$$(x, y)$$-coordinates * We use $$n$$ when dealing with **scalar** arithmetic or private key operations ## Generator Point Every elliptic curve in crypto-systems has a special generator point $$G$$ which is the base point that can generate any other point in its subgroup but **multiplying** $$G$$ **by some integer** in the range $$\[0 \dots r]$$ where $$r$$ is the order of the subgroup. ## Private Key and Public Key In ECC, we have the elliptic curve over the finite field $$\mathbb{F}\_p$$ and a generator point $$G$$. If we choose an integer $$k$$ as the **private key** and multiply $$G$$ with it, we will get the **public key** $$P=k \* G$$