- Addition (and multiplication by a scalar) is 'easy'
- Division (undoing the multiplication) is 'hard'

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

$P + P$ has no geometric construction, but is analogous to tangent on the continuous curve

(and the math works out the same - mod *p*)

Define scalar multiplication as

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

algorithm.

These elliptic curves have the associative property:

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

*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

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

i.e. $k = 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

- Never roll your own crypto
- Never roll your own crypto
- Don't. Roll. Your. Own. Crypto.

because

you will shoot yourself in the foot

`null`

*Private key*a random integer $d \in [1, n-1]$ with*n*the order of the sub-group.*Public key*$P = kG$, where*G*is base point, or generator of the group

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

Alice | Bob |
---|---|

Create key pair $P_a = k_a.G$ | Create key pair $P_b = k_b.G$ |

Sends Bob $P_a$ | Sends Alice $P_b$ |

Calc $P_s = k_a.H_b = k_a.k_b.G$ | Calc $P_s = k_b.H_a = k_a.k_b.G$ |

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

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

- Alice has her public and private keys $P_a = k_aG$
- Calculate a temporary key from random nonce
*j*: $R = rG$ - Calc $e = \text{Hash}(R || m)$
- Calc $s = r + ek_a$

Send *m*, *R* and *s* to Bob

Bob has *s*, *R*, *m*, and $P_a$.

He doesn't know $k_a$ or *r*.

So Bob calculates *s.G* and e, and compares it to $R+ eP_a$.

If they match, he knows that Alice signed the message.

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.