👩‍🏫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

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

Examples of various kinds of elliptic curves

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.

Source: http://cr.yp.to/talks/2008.05.12/zoo.html

Turtle curve is used in Bitcoin, Ethereum, and Zcash. Starfish curve is used in Tendermint, Stellar, and Monero.

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.

An elliptic curve over a finite field.

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. $4a^3 + 27b^2 \neq 0$
2. Projective → a line between two points will always intersect a third point.

Singularity in curves (ref. Wolfram MathWorld)

Projective property in elliptic curves

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.

• 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

• 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

• Complete code samples for the rest of the workshop: https://gist.github.com/onyb/cf795c819fdf8aa6015de2772fde24de