Elliptic curves 101

This is very brief overview. There are better, and more complete introductions out there

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Elliptic Curves

y2=x3+ax+bmodpy^2 = x^3 + ax + b \mod p

  • Described by this function
  • But x, y are integers
  • And x, y are between 0 and some prime number p


© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

The key properties

  • Addition (and multiplication by a scalar) is 'easy'
  • Division (undoing the multiplication) is 'hard'
© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)



  • Geometrically, P+Q+R=0P + Q + R = 0 if P, Q, R all lie on the same "line" (mod p).
  • Thus addition looks like: P+Q=RP + Q = -R.
  • -R is R reflected around the line y=p/2y = p / 2

P+PP + P has no geometric construction, but is analogous to tangent on the continuous curve
(and the math works out the same - mod p)

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Scalar Multiplication

Define scalar multiplication as

nP=P+P+...+Pn timesnP = \underbrace{P + P + ... + P} _{n\text{ times}}

This can be calculated in O(logn)O(\log n) time, using the double and add

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Multiplication properties

These elliptic curves have the associative property:

nP+mP=(n+m)PnP + mP = (n+m)P

but they are also cyclic, meaning for some value n, the results of the multiplication start repeating:

kP=(kmodn)PkP = (k \mod n)P

  • P is called the base point or generator of the curve.
  • n is the order of the cyclic subgroup of the curve generated by P.
  • In ECC, P is chosen so that n is large
© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Discrete logarithm problem

If we know P and Q, and Q=kPmodpQ = kP \mod p, can we easily find k?

i.e. k=Q/Pk = Q/P

  • No known 'easy' algorithm (i.e. runs in polynomial time)
  • need to do divide by trial and error (choose k, check, repeat)
  • for large k, this takes too long to be feasible

This is the basis of all ECC cryptography

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Rules of cryptography (mod 3)

  1. Never roll your own crypto
  2. Never roll your own crypto
  3. Don't. Roll. Your. Own. Crypto.

you will shoot yourself in the foot


  • null
© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Elliptic Curve Cryptography (ECC)

  • Private key a random integer d[1,n1]d \in [1, n-1] with n the order of the sub-group.
  • Public key P=kGP = kG, where G is base point, or generator of the group
© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Encryption with Elliptic Curve Diffie-Hellman (ECDH)

DH is a method for two parties to securely exchange keys.

Alice Bob
Create key pair Pa=ka.GP_a = k_a.G Create key pair Pb=kb.GP_b = k_b.G
Sends Bob PaP_a Sends Alice PbP_b
Calc Ps=ka.Hb=ka.kb.GP_s = k_a.H_b = k_a.k_b.G Calc Ps=kb.Ha=ka.kb.GP_s = k_b.H_a = k_a.k_b.G

PsP_s is a shared secret than an eavesdropper has no practical hope of figuring out.

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Signing and verifying messages

Alice wants to sign a message, m, that Bob (or anyone else) can verify with her public key, PaP_a.

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

EdDSA algorithm


  1. Alice has her public and private keys Pa=kaGP_a = k_aG
  2. Calculate a temporary key from random nonce j: R=rGR = rG
  3. Calc e=Hash(Rm)e = \text{Hash}(R || m)
  4. Calc s=r+ekas = r + ek_a

Send m, R and s to Bob

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

EdDSA Verification

Bob has s, R, m, and PaP_a.

He doesn't know kak_a or r.

s.G=(r+eka)G=rG+ekaG=R+ePas.G = (r + ek_a)G = rG + ek_aG = R + eP_a

So Bob calculates s.G and e, and compares it to R+ePaR+ eP_a.
If they match, he knows that Alice signed the message.

© Tari Labs, 2018-2021. (License : CC BY-NC-SA 4.0)

Note: Disclaimer. This is a rough guide for engineers wanting to get their hands wet with the nuts and bolts of the cryptographic math behind blockchain security. Therefore I may be loosy goosy with some terminology and most of the concepts oversimplified, so excuse that. However, if there are any _egregious_ errors in this presentation, please [open an issue](https://github.com/tari-labs/tari-university/issues) on github.

Note: You can forget about all this technical detail. It's just included here for completeness.

note: Now that the abstract algebra stuff is largely out of the way, we can do some cryptography!

note: This should make sense now based on all the preliminary discussion. _k_ is kept secret, _kG_ is relatively easy to calculate, giving you a public key, but finding _k_ from _kG_ involves solving the discrete logarithm problem.

note: - When creating their keys, Alice and Bob use the same curve parameters: same curve, _G_ etc. - When they exchange public keys, it can be over an insecure channel

note: This is a simplified algorithm. There are a few details ommitted, like always using modular arithmetic at limits on the choice of nonce.