# Introduction to ECC

### Elliptic Curve Cryptography

1. **Public-key cryptography** based on the concept of **elliptic curves** over **finite fields**.
2. **Smaller key size**, relative to RSA.
   * My **PGP** software uses a **2048-bit RSA** (Rivest–Shamir–Adleman) **key**.
     * To crack my **PGP key**, an attacker needs to expend the same amount of energy as **bringing the Mediterranean sea to boil**.
   * A typical crypto wallet uses a **256-bit ECC key**.
     * To crack my this key, an attacker needs to expend the same amount of energy as **bringing all the water on Earth to boil**.
   * ECC offers 400 times more security with a key that is 8 times smaller.
     * Schematically, with the current knowledge.
     * Difficulty increases with larger curves.
3. Widely used for **digital-signatures** and **key-exchange**.
   * Secures HTTPs connections (on modern browsers).
     * **google.com** uses the **elliptic curve secp256r1**, with key-size of **256 bits**.
     * **x.com** uses **RSA**, with key-size of **2048 bits**.
   * Bitcoin.
4. **Military-grade technology** ®
   * Cryptography was once part of the United State Munitions List (USML).

### Elliptic Curves

![Elliptic curve for the equation y² = x³ + ax + b](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-Lw4xXIAALrdDmJULxd2%2F-Lw54ClfIbT0ri_ctFk4%2F1_KKdvscN4y-NcGZ8Nnx1ZYQ.png?alt=media\&token=eb2036d0-088e-4d72-aa0d-6818ba53cb75)

An elliptic curve follows the general equation of $$y^2 = x^3 + ax + b$$ .

![Examples of various kinds of elliptic curves](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-Lw54Kw1Yybvz2RMPtBC%2F-Lw578Y93T2TjJAH4xBt%2F0_-8m7N8igyKR2oOUS.gif?alt=media\&token=bf3410e2-3a7c-48af-b3ee-e9da94d420c8)

{% hint style="info" %}
The above general equation is only for a particular family of elliptic curves called **Weierstrass curves**. There are several other forms that are also elliptic, but outside the scope of our study.
{% endhint %}

![Source: http://cr.yp.to/talks/2008.05.12/zoo.html](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-LwOGFbQuCL_FU2ZvI7W%2F-LwOGiikaUYyNaUHwC1N%2FScreenshot%202019-12-18%20at%2014.50.32.png?alt=media\&token=87adb47e-7a38-4010-9e69-502b7cccfcba)

{% hint style="info" %}
**Turtle curve** is used in Bitcoin, Ethereum, and Zcash. **Starfish curve** is used in Tendermint, Stellar, and Monero.
{% endhint %}

{% hint style="warning" %}
The figures above present elliptic curves over real numbers Field (R). This is convenient to get a visual understanding of what an elliptic curve is, mathematically speaking. For several reasons, the elliptic curves used in the case of ECC are defined over Finite Fields. The figure below is a more accurate representation of the elliptic curve actually used for ECC.
{% endhint %}

![An elliptic curve over a finite field.](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-LwPyZfgzu8VEjwQW9FA%2F-LwPynY8oWxlxQo-brKY%2Fimage06.png?alt=media\&token=ea7b6f9f-e09a-491e-977c-b75409899f23)

For an elliptic curve to be used for meaningful cryptography, they should also have the following two properties:

1. **Non-singularity**  →  should not have cusps or points of self-intersections.\
   &#x20;$$4a^3 + 27b^2 \neq 0$$&#x20;
2. **Projective**  →  a line between two points will always intersect a third point.

![Singularity in curves (ref. Wolfram MathWorld)](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-Lw54Kw1Yybvz2RMPtBC%2F-Lw56VmjCtn_82SU88vX%2FSingularPoints_1000.gif?alt=media\&token=408d475c-6ec3-432c-b296-ee18702afc02)

![Projective property in elliptic curves](https://93210801-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lw3TyXBjTYBK7fUhhiC%2F-Lw54Kw1Yybvz2RMPtBC%2F-Lw586nHr7mR5AnEsZB9%2F1_XDkvG91Bi_aaqWA29JSqVw.png?alt=media\&token=22c22553-7e1f-4a5b-a3bf-4969a98884f6)

### Why Python?

* **Supports 256-bit integer math.**
  * Python simply regards everything as an unbounded number.
* **Allows easy modular exponentiation.**
  * `pow()` is handy, and can also deal with negative exponents. No need to memorise [Fermat's Little Theorem](https://brilliant.org/wiki/fermats-little-theorem).
* **Easy to read.**
  * Cryptographic algorithms should be secure even if the attacker can read them. Security should not be by obscurity.
  * Good language to write reference implementations in. Ethereum's reference implementation is written in Python.
* **Expressive.**
  * Thanks to Python's magic methods, we can express finite field math using ordinary mathematical operators.

#### Resources

* [https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography](https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/)
* Lenstra, Arjen K., Thorsten Kleinjung, and Emmanuel Thomé. "Universal security." Number theory and cryptography. Springer, Berlin, Heidelberg, 2013. 121-124.\
  [https://eprint.iacr.org/2013/635.pdf](https://eprint.iacr.org/2013/635.pdf)
* **Complete code samples for the rest of the workshop:** [https://gist.github.com/onyb/cf795c819fdf8aa6015de2772fde24de](https://gist.github.com/onyb/cf795c819fdf8aa6015de2772fde24de)
