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.

   • My Ledger Nano X uses a 256-bit ECC key.

     • To crack my Ledger Nano X 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.

     • twitter.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

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

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.

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.

  • New in Python 3.8

• 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.

• I ❤Python.

  • You can get a lot of people excited about traditionally opaque technology, just by thinking in Python.

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​