# 0.3 Elliptic Curve Cryptography

To create a decentralized ledger, we need a way for users to authenticate their transactions without relying on a central authority. This is where **Elliptic Curve Cryptography (ECC)** comes in.

Elliptic Curve Cryptography is a form of asymmetric cryptography that provides the same security as traditional methods like RSA but with much smaller key sizes. This efficiency makes it well-suited for use in blockchain and cryptocurrencies.

ECC is based on mathematical structures called **elliptic curves**, which follow an equation of the form:

$$
y^2 = x^3+a\cdot x+b\ \ (\text{mod}\ p)
$$

When we consider this equation in the domain of [finite fields](https://www.youtube.com/watch?v=uxZAZ4T05wQ\&list=PLE8WtfrsTAinMMyQkK_CzXhXU_LHRNXy_\&index=1) of the form Z/pZ where p is a prime number, the set of solutions forms a group, where addition is defined as the operation of adding points on the curve according to specific rules.

{% embed url="<https://files.gitbook.com/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FvhcF8MdVyA1W0ElVe7v6%2Fuploads%2FXInKuvzMeOLbaGwmPQ8y%2FThirdOrder.mp4?alt=media&token=b5745810-c752-4989-8971-f5f5e68ff89e>" %}

In ECC, addition of two points P and Q on the elliptic curve is defined geometrically:

* If P≠Q, draw a line through P and Q. This line will intersect the curve at a third point R. The reflection of R over the x-axis gives the sum P+Q.
* If P=Q, draw the tangent line at P. This line intersects the curve at a new point, which is reflected to get 2P.
* If the line is vertical, the result is the identity element (point at infinity).

<figure><img src="https://2329510431-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FvhcF8MdVyA1W0ElVe7v6%2Fuploads%2FizuVrOb5I6YDxdoMPX74%2Fimage.png?alt=media&#x26;token=6c62cb81-500b-47b9-99c3-4fcf525b87d7" alt=""><figcaption></figcaption></figure>

A key operation in ECC is **scalar multiplication**, where a point P is added to itself repeatedly:

$$
k\cdot P = P + P+...+P \ \ \text{  (}k\text{ times)}
$$

These curves sometimes have unique properties that make cryptographic operations secure. One of the fundamental concepts behind ECC is the **Elliptic Curve Discrete Logarithm Problem (ECDLP).**

The idea is the following. Let's say we chose the elliptic curve parameters so the group of points on the curve has a cyclic sub-group of order q, a high prime, with generator G.

If someone takes a random scalar  in \[0, q-1] uniformly, and computes:

$$
A=a\cdot G
$$

Then the ECDLP is said to be "hard" if it is difficult to find $$a$$ given any $$A$$ in a short amount of time. Basically the only solution would have to be to check every possible $$a$$. Although it remains "easy" to compute $$A$$ from . In fact, parameters of ECC curves are also chosen to make computing a multiplication operation as fast as possible.

This is exactly how an asymmetric key pair is generated:

* Generate a random scalar $$a\in \[1, q-1]$$
* Compute $$A=a\cdot G$$

$$a$$ is the private key, and $$A$$ the public key. On the chain, you are identified as A. You can broadcast your public key so other users can encrypt messages using $$A$$ that only you can decrypt. Let's see how this work in practice:

#### Encryption

$$B$$ wants to send a message to $$A$$. The message is encoded as a single field element:  $$m \in \[0, p-1]$$.

1. $$B$$ generate a random $$r\in \[1, q-1]$$. It should be new and never be used again.
2. $$B$$ computes from $$r$$ a  "nonce" group element: $$N= r\cdot G$$.
3. $$B$$ then generates a view key group element: $$E= r\cdot A$$.
4. $$B$$ hashes the view key to get a field element: $$h= \text{hash}(E) \in \[0, p-1]$$.
5. $$B$$ calculates the cipher text: $$c= m+h$$.

&#x20;$$(c, N)$$ is the encrypted message that can be shared with $$A$$ through an insecure channel.

#### Decryption

$$A$$ receives $$(c, N)$$, and recovers the original message $$m$$ following those steps;

1. $$A$$ computes $$a\cdot N$$, which is the view key group element $$E$$ because:\
   $$a\cdot N = a\cdot(r\cdot G) = (ar)\cdot G = (ra)\cdot G = r\cdot(a\cdot G) = r\cdot A=E$$.
2. $$A$$ hashes the view key to get back the field element: $$h= \text{hash}(E)$$.
3. $$A$$ computes the plain text message: $$m= c-h$$.

Let's see in next chapter how your private key k allows you to authenticate the transaction you want to broadcast to the network to spend your coins.